*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 `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`

`node_pq`

`b_node_pq`

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`

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.

#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; forall_adj_nodes(w, v) 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).