Example Topological Ordering

The following example shows how to compute a topological ordering for a graph using the corresponding basic graph algorithm.

The program defines a graph G and initializes it as a random graph with 10 nodes and 6 edges. Then a node_array<int> ord is defined for G and the function TOPSORT() is called for G and ord. TOPSORT() returns true if G is acyclic and false otherwise. If G is acyclic, ord contains the topological ordering after the call of TOPSORT(). In this case the entries of ord for every node of G are printed.

Remark: It is also possible to use a parameterized graph instead of a graph as the first parameter of TOPSORT().

#include <LEDA/graph/graph.h>
#include <LEDA/graph/basic_graph_alg.h>

using namespace leda;

int main()
{
  graph G;   

  random_graph(G,10,6);

  node_array<int> ord(G);     //node_array for result of TOPSORT
  bool acyclic=TOPSORT(G,ord);  //call TOPSORT for G and ord

  if (acyclic) {
    node v;
    forall_nodes(v,G) {
      G.print_node(v);
      std::cout << " " << ord[v] << std::endl;
    }
  }

  else std::cout << "G contains cycles! No topological ordering possible!\n";

  return 0;
}

See also:

Topological Ordering

Graphs

Parameterized Graphs

Node Arrays

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms