### 5.2.3. Directed and undirected graphs

Learning objectives

 Directed and undirected graphs in LEDA The methods `make_undirected()`, `make_directed()`, and `is_directed()` The method `make_bidirected()`

Two very frequently asked questions in the context of LEDA's graph types are how LEDA distinguishes between directed and undirected graphs and how to create a directed or an undirected graph. Recall the program for breadth first search by means of BFS() just presented: For every edge, we inserted a reverse edge, so we (implicitly) created the undirected version of a graph. Can this be done in another way? As we already mentioned, LEDA's notion of the terms “directed” and “undirected” is a little different from the classical point of view.

To understand the difference, we have to know a little bit about how the nodes and edges of a graph are stored internally. First of all, all nodes are in a list V and all edges are in a list E. Moreover, the edges are part of additional lists, as we will see soon.

#### Directed graphs in LEDA

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.

#### Undirected graphs in LEDA

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.

`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 real difference between directed and undirected graphs in LEDA

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.

#### The methods `make_directed()` and `make_undirected()`

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.

#### Exercises

 Exercise 51. Test what happens if you make the `graph` undirected in the program for breadth first search by means of BFS(). Try `make_undirected()` at different positions.Rephrase the program with `make_bidirected()` so that for all edges, you do not have to insert also the reverse edge explicitly.