Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
topsort.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 1k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

topsort.c：Code Content
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_edit.h>
  5. bool TOPSORT(const graph& G, node_array<int>& ord)
  6. { 
  7.   node_array<int> cur_indeg(G);
  9.   list<node> zero_indeg;
  11.   int count = 0;
  13.   node v,w;
  15.   forall_nodes(v,G) 
  16.   { cur_indeg[v] = G.indeg(v);
  17.     if (G.indeg(v)==0) 
  18.        zero_indeg.append(v); 
  19.    }
  21.   while ( ! zero_indeg.empty() )
  22.   { 
  23.     count++;
  25.     v = zero_indeg.pop();
  26.   
  27.     ord[v] = count;
  29.     forall_adj_nodes(w,v) 
  30.        if (--cur_indeg[w]==0) zero_indeg.append(w);
  31.    }
  32.   
  33.   return (count==G.number_of_nodes());
  34. }
  35.      
  40. main()
  41. {
  42.   GRAPH<point,int>  G;
  44.   window W;
  46.   for(;;)
  47.   { 
  48.     graph_edit(W,G);
  50.     node_array<int> node_num(G);
  52.     if (TOPSORT(G,node_num)==false)
  53.     { W.acknowledge("Graph is cyclic, cannot sort");
  54.       continue;
  55.      }
  57.     node v;
  58.     forall_nodes(v,G)
  59.        W.draw_int_node(G[v],node_num[v],blue);
  61.    if (W.read_mouse() == 3) break;
  63.   }
  65.   return 0;
  66. }