### 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;
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.