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.
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.
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 nonsense 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 selfloops 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.
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 builtin graph algorithms of LEDA, such as the
function 
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

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 selfedge
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 selfloops, 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 welldefined. 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 
Exercise 51.  Test what happens if you make the
Rephrase the program with
