5.4. A self-written graph algorithm

Learning objectives

Assembling new graph algorithms from built-in 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.

Self-written 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 built-in algorithms for the class graph, code for iterating and navigating in a graph, and finally code that assembles an own algorithm from all this.

An example: Recognizing genetic graphs

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:

  1. Each individual has at most 2 parents. (It may be that one or both parents are unknown.)

  2. No individual is its own ancestor.

  3. 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.

Figure 5.33. A genetic graph

A genetic graph

Parent-child relationships are represented with directed edges. Each individual has sex m or f. No individual has more than two parents or is its own ancestor. The parents of each individual are of different sex.


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:

  1. The in-degree of each node is less or equal than 2.

  2. The graph is acyclic.

  3. 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.

Figure 5.34. A non-genetic graph

A non-genetic graph

Nodes 0 and 2 must be of different sex, for example, m and f. Then node 1, being a common parent of a child of 0 and 2, must have both sexes f and m, a 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: In-degrees 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.

Filename: GeneticGraphTestNodeArray.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#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();
  }
}

Exercises

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 Is_Bipartite() whether a graph is genetic.

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 v0 and keep on running, at each node choosing an edge that we have not yet traversed. We shall come back to v0 sometime! (Why?) Let P0 be the path constructed so far. Either we have traversed all edges now, thus P0 already being a Euler tour, or there is another node v1 that has an incident edge not yet traversed. We start running from v1 with the same method, always using only edges that have not yet been traversed, and shall come back to v1. (Why?) In doing so, we suitably insert the edges traversed into the path constructed before and obtain a path P1. Either we have traversed all edges now, thus P1 being a Euler tour, or there is another node v2, and so on. Since sometime we shall run out of edges, we shall finally end up with a path Pk 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.




Imprint-Dataprotection