home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / strongcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  913 b   |  68 lines
  1. #include <LEDA/graph_alg.h>
  2. #include <LEDA/graph_edit.h>
  3. #include <LEDA/array.h>
  4.  
  5.  
  6. int STRONG(graph& G, node_array<int>& compnum)
  7. { 
  8.   node v,w;
  9.   int n = G.number_of_nodes();
  10.   int count = 0;
  11.  
  12.   array<node> V(1,n);
  13.   list<node>  S;
  14.  
  15.   node_array<int>  dfs_num(G);
  16.   node_array<int>  compl_num(G);
  17.   node_array<bool> reached(G,false);
  18.  
  19.   DFS_NUM(G,dfs_num,compl_num);
  20.  
  21.   forall_nodes(v,G) V[compl_num[v]] = v;
  22.  
  23.   G.rev();
  24.  
  25.   for(int i = n; i > 0; i--)
  26.    { if ( ! reached[V[i]] ) 
  27.      { S = DFS(G,V[i],reached);
  28.        forall(w,S) compnum[w] = count;
  29.        count++;
  30.       }
  31.     }
  32.  
  33.  return count;
  34.    
  35. }
  36.  
  37.  
  38.  
  39. main()
  40. {
  41.   GRAPH<point,int>  G;
  42.  
  43.   window W;
  44.  
  45.  
  46.   for(;;)
  47.   { 
  48.     graph_edit(W,G);
  49.  
  50.     node_array<int> comp_num(G);
  51.  
  52.     STRONG(G,comp_num);
  53.  
  54.     node v;
  55.     forall_nodes(v,G)
  56.     { int i = comp_num[v];
  57.        W.draw_int_node(G[v],i,i%16);
  58.      }
  59.  
  60.    if (W.read_mouse() == 3) break;
  61.  
  62.   }
  63.  
  64.   return 0;
  65.  
  66. }
  67.  
  68.