5.2.7. Special auxiliary data structures for graph algorithms

Learning objectives

The class node_list
The class node_set
The class node_pq
The class b_node_pq
The class node_partition
The class edge_set

In graph algorithms, one often has to manage nodes in a linear list.Of course, a list list<node> may be used for that purpose. For this special combination, however, LEDA offers an especially efficient implementation in the form of the class node_list. Compared to list, this implementation has a restricted interface, though. Moreover, each node of a graph can be contained in only one node_list at every point in time. The test whether a certain node is contained in a node_list takes an expected time of only O(1).

According to this, there is the special type node_set for sets of nodes and the type node_partition for partitions of nodes. For priority queues of nodes, LEDA provides the types node_pq and b_node_pq. The latter type is only convenient for priority queues with bounded integral priorities.

In addition, there is the class edge_set for efficiently managing sets of edges.

By reasons of efficiency, all these classes generally should be used wherever the correspondingly parameterized container type or priority queue would otherwise be used and where the program gets on by with the functions of the restricted interface.

We want to refrain from a detailed description of the interfaces here, since they widely comply with the interfaces of the more general types anyway. We rather refer to the manual pages of node_list, node_set, node_partition, node_pq, b_node_pq and edge_set

An example: An implementation of TOPSORT()

As an example for a reasonable use of a node_list, we want to show a way to implement the function TOPSORT() for calculating a topological sorting of a graph.

We run once over all nodes of the graph, memorizing the original in-degrees and storing all nodes with in-degree 0 in a node_list called ZEROINDEG. As long as this list is not empty, we extract a node from it and give it the next number in the topological sorting. We (conceptually) remove it from the graph by decreasing the in-degrees of all neighbor nodes by 1. If the in-degree of a node is set to 0 in this process, this node is inserted into ZEROINDEG. The method terminates when ZEROINDEG becomes empty.

If, at the end, each node has received a (consecutive) number, the graph has a topological sorting. If, in contrast, ZEROINDEG has become empty without each node having received a number, the graph contains a cycle.

Filename: TOPSORT.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/graph.h>
#include <LEDA/node_array.h>
#include <LEDA/node_list.h>

using leda::graph;
using leda::node_array;
using leda::node_list;
using leda::node;

bool TOPSORT(const graph& G, node_array<int>& top_num)
{
  // store all nodes with indegree = 0 in ZEROINDEG
  node_list ZEROINDEG;  
  node_array<int> INDEG(G, 0); // and count indegrees
  node v;
  forall_nodes(v, G) 
    if((INDEG[v] = G.indeg(v)) == 0) 
      ZEROINDEG.append(v);


  // while there is a node with indegree = 0, pop it and assign next
  // topological number to it
  int counter = 0 ;
  while(!ZEROINDEG.empty()) { 
    v = ZEROINDEG.pop();
    top_num[v] = ++counter;
    // decrement indegree of all adjacent nodes w
    // append w to ZEROINDEG if indegree becomes 0
    node w;
    forall_adj_nodes(w, v)
      if(--INDEG[w] == 0) 
        ZEROINDEG.append(w);
  }

  // G has a topological sorting iff all nodes have been numbered
  return counter == G.number_of_nodes();
}

As each node v is inserted only once into ZEROINDEG and as each edge (v,w) is examined only once, this method has a running time of O(n+m).

Exercises

Exercise 62.

If TOPSORT() ends without each node having received a number, the graph contains a cycle. Every node that has not yet a number is part of a cycle then: Every node in the remaining graph has an in-degree > 0, that is, it has a predecessor; therefore, one may start from an arbitrary node and walk on to an arbitrary predecessor until one reaches a node that already has been visited. Then the path walked over in this manner forms a cycle.

Sometimes it is important to recognize such a cycle and to remove it, for example, when a program is to be statically linked against several libraries. These libraries have to be specified to the linker in the (reverse) order of a topological sorting of their mutual dependencies (and thus must not contain circular dependencies).

Extend TOPSORT() such that it additionally recognizes cycles and returns them.




Imprint-Dataprotection