Topological Order

Write a LEDA program that generates a topological order for a randomly generated graph, in O(n+e) time, i.e., using the ideas presented in the text pp.381-382.

Hints

Generate the graph using random_simple_loopfree_graph. The graph generated may have a cycle, so you can put the graph generation into a loop until an acyclic graph is generated ...
```
do {
    random_simple_loopfree_graph(MyGraph,NumberOfNodes,NumberOfEdges);
    } while (!Is_Acyclic(MyGraph));
```
As LEDA does not index its graph nodes with integers, for each node you'll need a struct to record both its in-degree and (for nodes with in-degree 0) the next node with in-degree 0 ...
```
typedef struct {
    node NextNode;
    int InDegree;
    } node_degree;
```
Then use a node array of node_degree ...
```
node_array<node_degree> Predecessors(MyGraph);
```

Here's sample output:

geoff@duck:~/c++> TO 5 5
Creating random graph with 5 nodes and 5 edges ...

[0] : [0]---->[4][0]---->[3]
[1] :
[2] : [2]---->[4][2]---->[1][2]---->[0]
[3] :
[4] :

[2][0][3][4][1]

There's an executable version ~geoff/c++/TO available on duck for you to experiment with.

Answer

TO.cpp