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).