Example: Topological Sorting

The following program demonstrates how graphs and the related data types of LEDA can be used. The program consists of a function TOPSORT() which computes a topological ordering if the graph is acyclic. In this case it returns true (,i.e., a positive integer). If the graph contains a cycle it returns false (=0).

A topological ordering ord of a graph is a numbering of the nodes with the following property: ord(u)< ord(v) if e=(u,v) is an edge of the graph.

The main()-function creates a graph G of five nodes and four edges and prints the graph. Then a node_array<int> ord is defined for G. This node_array will contain the ordering of the nodes after the call of TOPSORT() with G and ord as parameters. After calling TOPSORT(), main() iterates through all nodes v of G and prints v and the corresponding value of ord.

The function TOPSORT() is also quite simple. It initializes the node_array<int> INDEG with the indegrees of the nodes of G and appends v to the queue<node> ZEROINDEG if the indegree of v is zero. The interesting part of TOPSORT() is the while-loop. While ZEROINDEG is not empty the next node v is taken out of ZEROINDEG and ord[v] is assigned the next int value. Then the value INDEG[w] for all target nodes w of edges out of v is decreased and the while-loop goes into the next iteration. This procedure ensures that ord[s]<ord[t] for an edge e=(s,t) with source s and target t as long as there is no cycle in G.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/graph_gen.h>
#include <LEDA/core/queue.h>

using namespace leda;

bool TOPSORT (const graph& G, node_array<int>& ord) 
{
  node_array<int> INDEG(G);
  queue<node> ZEROINDEG;	
		
  node v;
  forall_nodes(v,G) {
    INDEG[v]=G.indeg(v);
    if (INDEG[v]==0) ZEROINDEG.append(v); 
  }

  int count=0;
  while (!ZEROINDEG.empty()) {
    v=ZEROINDEG.pop();
    ord[v]=++count;
			
    edge e;
    forall_out_edges(e,v) {
      node w=G.target(e);
      if (--INDEG[w]==0) ZEROINDEG.append(w);
    }
  }
	
  return (count==G.number_of_nodes());
}

 int main()
{
  graph G;
  node v[5];
  int i;for (i=0;i<5;i++) v[i]=G.new_node();
  G.new_edge(v[3],v[0]);
  G.new_edge(v[0],v[1]);
  G.new_edge(v[0],v[2]);
  G.new_edge(v[1],v[4]);

  G.print();

  node_array<int> ord(G);
  bool acyclic= TOPSORT(G,ord);

  if (acyclic) {
    node v;
    forall_nodes(v,G) {
      G.print_node(v);
      std::cout << ": " << ord[v] << "\t";
    }
	std::cout << std::endl;
  }
  else std::cout << "graph is cyclic!\n";

  return 0;
}  

See also:

Graphs

Node Arrays

Stacks/Queues

Manual Entries:

Manual Page Graphs

LEDA Item Concept

Iteration