Example Node Partitions

The following program implements Kruskals algorithm for computing a minimum spanning tree of a weighted graph.

The main() function first creates a complete graph G of five vertices. Then every edge e of G is assigned a random integer cost using an edge_array with integer information. After that, MST() is called for G and cost. The result is a list of edges containing the edges of the minimum spanning tree. This list is is finally printed.

The computation of the minimum spanning tree in MST() works as follows. We start with the empty list T of edges and consider the edges in the order of increasing cost. To sort the edges, a priority queue PQ of type p_queue<int,edge> is used. When considering edge e=(u,v), we check whether e would close a cycle using the operation P.same_block() for the two end nodes u and v of e. If e does not close a cycle it is added to T and the blocks of u and v are united.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_partition.h>
#include <LEDA/core/random_source.h>
#include <LEDA/core/p_queue.h>

using namespace leda;

list<edge> MST(const graph& G,const edge_array<int>& cost)
{ 
  list<edge> T; //the minimum spanning tree
  
  p_queue<int,edge> PQ;
  edge e;
  forall_edges(e,G) PQ.insert(cost[e],e);
   //sort edges according to cost
 
  node_partition P(G);
  while (!PQ.empty()) {
    e=PQ.inf(PQ.find_min());  //get edge with minimum cost
    PQ.del_min();

    node u=G.source(e);
    node v=G.target(e);
			
    if (!P.same_block(u,v)) {
      T.append(e);
      P.union_blocks(u,v);
    }
  }
  
  return T;
}  

int main()
{
  graph G;
  complete_graph(G,5);

  random_source S;
  edge_array<int> cost(G);
  edge e;forall_edges(e,G) S>>cost[e];

  list<edge> tree=MST(G,cost);

  forall(e,tree) {
    G.print_edge(e);
    std::cout << std::endl;
  }

  return 0;
}

See also:

Minimum Spanning Trees

Edge Arrays

Node Arrays

Linear Lists

Priority Queues

Manual Entries:

Manual Page Node Partitions

Iteration