Learning objectives
Assembling new graph algorithms from builtin graph algorithms and own code 
This section demonstrates by means of a simple problem how we can write our own graph algorithms with the help of LEDA.
Selfwritten graph algorithms typically consist of the
following ingredients: The class graph
and
some data structures, such as node_array
,
that associate information to the graph, one or more builtin
algorithms for the class graph
, code for
iterating and navigating in a graph
, and
finally code that assembles an own algorithm from all this.
In a family tree, one tries to go back into the past as far as possible and to list all ancestors of today's generation, in as much as they are known. This leads to graphs like the one from Figure 5.33: For each individual, an edge is drawn to each of its children. Moreover it is of importance whether an individual is or has been father or mother, that is, sex is playing a role (in most cases, it is obvious from the first name in family trees).
The opposite question is: When does a (directed) graph represent a possible family tree? Mother Nature imposes the following conditions to such graphs:
Each individual has at most 2 parents. (It may be that one or both parents are unknown.)
No individual is its own ancestor.
The parents of an individual must be of a different sex.
A directed graph whose nodes are labeled with sexual information and that satisfies these conditions is denoted a genetic graph. Figure 5.33 shows such a genetic graph.
Translated into the language of graph theory, the previous conditions read as follows: A directed graph is genetic if and only if the following conditions are satisfied:
The indegree of each node is less or equal than 2.
The graph is acyclic.
The nodes v can be marked with a label sex(v) having value “m” or “f” such that the following holds: If there are two edges (u,v) and (v,w) in the graph, sex(u) is different from sex(v).
Not every graph that satisfies conditions 1 and 2 is genetic, that is, can be labeled such that it additionally satisfies condition 3. The graph from Figure 5.34 gives an example for that: Let us suppose that the parents 0 and 2 of node 4 receive sexes m and f, respectively. Then, on the one hand, node 1 has to receive sex f (being mother of 3), on the other hand, it has to receive sex m (being father of 5). Trying an inverse labeling of 0 and 2, we end up with a corresponding contradiction.
Now, with LEDA's help, how can we write a function
Is_Genetic_Graph()
that tests whether a graph
is genetic? The first two conditions are quickly verified:
Indegrees can be queried with the method
indeg()
and the
forall_nodes
macros, and for testing whether a
graph is acyclic, we can use the function
Is_Acyclic()
from
basic_graph_alg.h
.
But how can be check condition 3? The way we have shown that
the graph from Figure 5.34 is not
genetic gives us a hint: With the help of a (recursive) function
assign_sex()
, we try to assign a label
“m” or “f” to each node such that
condition 3 is met after all nodes have got a label. This works as
follows: If the sex of a node is not yet known, we make it female
with a call of assign_sex()
. (We could also
start with a male label, which would only lead to a different
valid labeling  if there is one , but we prefer women in our
surroundings.)
assign_sex()
labels the node v passed
to it with the sex s passed to it and then looks at all children c
of this node and at all their parents p that are different from
v. If such a parent p does not yet have a sex, we give it the sex
that is different from s in a recursive call of
assign_sex()
. If, in contrast, p already has
a sex and if this sex is equal to s, condition 3 cannot be
satisfied.
The following program implements this algorithms. To
associate a sexual information to the nodes, we use a
node_array
here.
#include <LEDA/graph.h> #include <LEDA/basic_graph_alg.h> #include <LEDA/node_array.h> #include <LEDA/graphwin.h> #include <LEDA/string.h> #include <iostream> using leda::graph; using leda::node; using leda::node_array; using leda::GraphWin; using leda::window; using leda::list; using leda::edge; using leda::string; using std::cout; enum sex { male, female, unknown }; bool assign_sex(graph& G, node v, node_array<sex>& sex_of_node, sex s); bool Is_Genetic_Graph(graph& G, node_array<sex>& sex_of_node, int& violated_constraint) { // each individual has at most two parents node v; forall_nodes(v,G) if(G.indeg(v) > 2) { violated_constraint = 1; return false; } // no individual is its own ancestor if( ! Is_Acyclic(G) ) { violated_constraint = 2; return false; } // the parents belong to opposite sexes // try to assign a sex to every node of G forall_nodes(v,G) if(sex_of_node[v] == unknown) if(!assign_sex(G, v, sex_of_node, female)) { // women preferred ;) violated_constraint = 3; return false; } // if we haven't returned yet, we have a genetic graph return true; } bool assign_sex(graph& G, node v, node_array<sex>& sex_of_node, sex my_sex) { sex_of_node[v] = my_sex; sex other_sex = (my_sex == male ? female : male); edge e; forall_out_edges(e, v) { node child = G.target(e); edge f; forall_in_edges(f, child) { node other_parent = G.source(f); if(other_parent == v) continue; // v is not the other parent if(sex_of_node[other_parent] == unknown) { if(!assign_sex(G, other_parent, sex_of_node, other_sex)) return false; } else if(sex_of_node[other_parent] == my_sex) return false; } } return true; } int main() { graph G; GraphWin gw(G, 500, 500, "Genetic Graph Test"); gw.set_node_label_type(leda::user_label); gw.set_flush(false); gw.display(window::center,window::center); while(gw.edit()) { node_array<sex> sex_of_node(G,unknown); int violated_condition; string msg; if(Is_Genetic_Graph(G, sex_of_node, violated_condition)) { node v; forall_nodes(v,G) { string label; switch(sex_of_node[v]) { case male: label = "M"; break; case female: label = "F"; break; case unknown: label = "U"; break; } gw.set_user_label(v, label); gw.redraw(); msg = "G is genetic."; } } else { msg = "G is not genetic. "; switch(violated_condition) { case 1: msg += "Some individual has more than 2 parents."; break; case 2: msg += "Some individual is its own ancestor."; break; case 3: msg += "Sexes could not be assigned suitably."; break; } } msg += " Click <done>."; gw.message(msg); gw.wait(); gw.del_message(); } }
Exercise 72.  The condition that the parents of an individual have to be of different sex can be reduced to the condition that a certain graph has to be bipartite: If u and w are parents of v, the edge {u,w} is induced. In the graph G' created in this way, u and w have to be elements of different subsets of a bipartition. Write a function that, based on this
observation, tests with the help of function

Exercise 73.  A Euler tour in an undirected, connected graph is a path that traverses each edge exactly once and ends at the start node again. Such is tour is possible if and only if each node has an even degree: In a Euler tour, each node is left as often as it is entered. Therefore the degree of each node has to be even. Conversely, a tour in such a graph can be constructed as follows: We start from an arbitrary node v_{0} and keep on running, at each node choosing an edge that we have not yet traversed. We shall come back to v_{0} sometime! (Why?) Let P_{0} be the path constructed so far. Either we have traversed all edges now, thus P_{0} already being a Euler tour, or there is another node v_{1} that has an incident edge not yet traversed. We start running from v_{1} with the same method, always using only edges that have not yet been traversed, and shall come back to v_{1}. (Why?) In doing so, we suitably insert the edges traversed into the path constructed before and obtain a path P_{1}. Either we have traversed all edges now, thus P_{1} being a Euler tour, or there is another node v_{2}, and so on. Since sometime we shall run out of edges, we shall finally end up with a path P_{k} that is a Euler tour. Work out the details and write a function that tests whether a Euler tour is possible in an (undirected) connected graph passed to it. If it is, the function is to compute such a tour and to return it. 