A graph is directed unless nothing different is said. This means that for every node v two (circular) lists are kept: The list out_edges(v) holds all edges whose source is v, that is, all edges that leave v. In contrast, the list in_edges(v) holds all edges whose target is v, that is, all edges that are incident to v. The list adj_edges(v) is a synonym for out_edges(v) and is often called the adjacency list of v. Figure 5.6 shows an example.

Figure 5.6. Internal representation of a directed graph

A graph with the three nodes 0, 1, 2 and the five edges a, b, c, d and e. source(a)=0, target(a)=1 etc. a=(0,1), d=(0,1), so a and d are multiedges. e is a self-loop.

out_edges(0)=(a,c,d), in_edges(0)=(), out_edges(1)=(b), in_edges(1)=(a,d), out_edges(2)=(e), in_edges(2)=(b,c,e).

G.make_undirected() adds every list in_edges(v) to out_edges(v), and the lists out_edges(v) are renamed adj_edges(v). The flag is set to undirected. G is undirected then. The lists in_edges(v) and out_edges(v) are no longer available.

To work in LEDA with a directed graph in the classical sense, nothing more than

graph G;

has to be said. An edge e that is inserted afterwards by G.new_edge(v1,v2) always has a direction: source(e)=v1 and target(e)=v2.

	Note
	In contrast to the classical term “incident”, LEDA calls an edge e=(v1,v2) (in a directed graph) adjacent to v1 (but not to v2!). (In the classical terminology, (v1,v2) is called “incident to v2” and “incident from v1”, even though the last term is non-sense with regard to the meaning of the Latin word “incident” = “falling into”.)

The only difference from a directed graph in the classical sense is the possibility to insert multiedges. This means that from a node v, some edges lead to the same node w.

LEDA's notion of undirected graphs is the following: Every directed graph without self-loops can be interpreted as an undirected graph if only the term “adjacent” is defined differently. The edges in an undirected graph still have a direction, they still know the source node and the target node; internally, they are stored differently, though.

With the sequence of statements

graph G;
G.make_undirected();

G is defined as an undirected graph (in the sense of LEDA). This has the following effects: For every node v, only the list adj_edges(v) exists; it contains all nodes whose source or target is v. Therefore, an edge is considered adjacent both to the source edge and to the target edge. Figure 5.7 shows an example.

Figure 5.7. Internal representation of an undirected graph

A graph with the three nodes 0, 1, 2 and the four edges a, b, c and d. a=(0,1), d=(0,1), b=(1,2), c=(0,2). These edges still have a direction! source (a)=0, target(a)=1 etc. a and d are multiedges.

adj_edges(0)=(a,c,d), adj_edges(1)=(a,b,d), adj_edges(2)=(c,b).

G.make_directed() splits adj_edges(v) into in_edges(v) and out_edges(v) again, for example, into out_edges(1)={b}, in_edges(1)={a,d} etc.

What makes the difference here from the classical sense of the term “undirected”? First notice again that multiedges are allowed. From a programmer's point of view, using an undirected graph yields some important consequences:

The macros that serve to iterate over the edges and nodes that are adjacent to a node (in the sense of LEDA) work differently from with a directed graph. The reason for this is that now other (in general more) edges and nodes may be considered adjacent to a node v.

	Important
	Many built-in graph algorithms of LEDA, such as the function BFS(), expect a directed graph as input and fail if this graph is made undirected before with a call of G.make_undirected().

If one wants to work, by using one of these functions, with a graph that is undirected in the classical sense of the term, one has to insert the corresponding reverse edge for every edge, as we did it in the program for breadth first search by means of BFS(). Such a graph graph is called bidirected. The method

G.make_bidirected();

makes a graph bidirected by inserting missing reverse edges. This allows for an easy way to simulate an undirected graph (in the classical sense) by a directed graph.

	Tip
	In general one can get along with a directed graph for managing an undirected graph: The macro forall_inout_edges an the method opposite() suffice in most problems to “forget” the direction information of a directed graph and thereby to move in this graph as in an undirected graph.

The method

G.is_directed();

tests whether a graph (in the sense of LEDA) is directed or undirected. What does this function do internally? Very easy: It returns the value of a flag. So merely one flag decides whether a graph is considered directed or undirected - not the question whether a reverse edge exists for every edge, neither something else. The methods of the class graph ensure automatically that a graph stays directed and undirected, respectively. So, for example, it is impossible to insert a self-edge into an undirected graph.

Initially this flag is set to true until a call of make_undirected() sets it to false. But such a call does more: It removes all self-loops, appends every list in_edges(v) to out_edges(v), and renames the latter adj_edges(v). The original lists in_edges(v) and out_edges(v) are not available anymore - their contents are not well-defined. So, for example, the graph of Figure 5.7 arises from the graph of Figure 5.6 by a call of make_undirected().

In contrast, this flag is reset to true by the call

G.make_directed();

This method splits each list adj_edges(v) into two lists in_edges(v) and out_edges(v) - it is able to do so, because the edges have a direction also in an undirected graph.

	Warning
	The methods make_directed() and make_undirected() are not inverse to each other! If the graph of Figure 5.7 is made directed again, the graph of Figure 5.6 will not arise again: The original self-loops will be missing. This means that these methods are only partially inverse.