Algorithmic Solutions > LEDA > LEDA Guide > Graphs and Related Data Types > Example Graphs and Related Data Types

## 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;
}  ```

Graphs

Node Arrays

Stacks/Queues

Manual Entries:

Manual Page Graphs

LEDA Item Concept

Iteration