home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / testall.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.1 KB  |  227 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/ugraph.h>
  3. #include <LEDA/graph_alg.h>
  4.  
  5. declare2(GRAPH,string,real)
  6.  
  7. declare2(UGRAPH,string,real)
  8.  
  9. main()
  10. {
  11.  
  12. GRAPH(string,real) G;
  13.  
  14. random_graph(G,10,40);
  15.  
  16.  
  17. G.print("Graph G");
  18.  
  19. edge_array(int)  cost(G);
  20. node_array(int)  dist(G);
  21. edge_array(real) cost1(G);
  22. node_array(real) dist1(G);
  23. node_array(edge) pred(G);
  24.  
  25. node_array(int)   ord(G);
  26. node_array(int)   compnum(G);
  27. edge_array(int)   flow(G) ;
  28. edge_array(real)  flow1(G) ;
  29. node_array(bool)  reached(G,false);
  30. node_array(int)   dfs_num(G);
  31. node_array(int)   comp_num(G);
  32. node_array(int)   layer(G,-1);
  33.  
  34. node_matrix(int)  M(G);
  35. node_matrix(real) M1(G);
  36.  
  37. list(node) nl;
  38. list(edge) el;
  39. node       v,w;
  40. edge       e;
  41.  
  42.  
  43. UGRAPH(string,real) U = G;
  44.  
  45. node_array(int) compnum1(U);
  46.  
  47. init_random();
  48. forall_edges(e,G)  G[e] = cost1[e] = cost[e] = random(0,1000);
  49.  
  50.  
  51.  
  52. cout << "TOPSORT:\n";
  53. if (TOPSORT(G,ord)) 
  54.    cout << "graph is acyclic\n";
  55. else 
  56.    cout << "graph is cyclic\n";
  57. newline;
  58.  
  59. newline;
  60. cout << "DFS:\n";
  61. newline;
  62. nl = DFS(G,G.choose_node(),reached);
  63. forall(v,nl) { G.print_node(v); newline; }
  64. newline;
  65.  
  66. newline;
  67. cout << "DFS_NUM:\n";
  68. DFS_NUM(G,dfs_num,comp_num);
  69. forall_nodes(v,G) 
  70. { G.print_node(v);
  71.   cout << form("  dfsnum = %2d  compnum = %2d \n",dfs_num[v],comp_num[v]);
  72.  }
  73. newline;
  74.  
  75. newline;
  76. cout << "BFS:\n";
  77. nl = BFS(G,G.first_node(),layer);
  78. forall_nodes(v,G)
  79. { G.print_node(v);
  80.   cout << form("  layer = %2d\n",layer[v]);
  81.  }
  82. newline;
  83.  
  84.  
  85. newline;
  86. cout << "COMPONENTS:\n";
  87. COMPONENTS(U,compnum1);
  88. forall_nodes(v,U)
  89. { U.print_node(v);
  90.   cout << form("  compnum = %2d \n",compnum1[v]);
  91.  }
  92. newline;
  93.  
  94. newline;
  95. cout << "COMPONENTS1:\n";
  96. COMPONENTS1(U,compnum1);
  97. forall_nodes(v,U)
  98. { U.print_node(v);
  99.   cout << form("  compnum = %2d \n",compnum1[v]);
  100.  }
  101. newline;
  102.  
  103.  
  104. newline;
  105. cout << "MAX_FLOW(int):  ";
  106. cout.flush();
  107. node s = G.first_node();
  108. node t = G.last_node();
  109. int val = MAX_FLOW(G,s,t,cost,flow) ;
  110. cout << form("total flow = %d \n",val);
  111. newline;
  112.  
  113. cout << "MAX_FLOW(real): ";
  114. cout.flush();
  115. real val1 = MAX_FLOW(G,s,t,cost1,flow1) ;
  116. cout << form("total flow = %f \n",~val1);
  117. newline;
  118.  
  119. forall_edges(e,G) 
  120. { G.print_edge(e);
  121.   cout << form(" cap = %d  flow = %d  flow1 = %f\n", cost[e],flow[e],~flow1[e]);
  122.  }
  123. newline;
  124.  
  125.  
  126. newline;
  127. cout << "TRANSITIVE_CLOSURE:\n";
  128. graph G1 = TRANSITIVE_CLOSURE(G);
  129. G1.print("Graph G1 = transitive closure of G");
  130. newline;
  131.  
  132. newline;
  133. cout << "SPANNING_TREE: \n";
  134. el = SPANNING_TREE(G);
  135. forall(e,el) 
  136.   { G.print_edge(e);;
  137.     newline;
  138.    }
  139. newline;
  140.  
  141. cout << "MIN_SPANNING_TREE: \n";
  142. el = MIN_SPANNING_TREE(G,cost);
  143. forall(e,el) 
  144. { G.print_edge(e);;
  145.   newline;
  146.  }
  147.  
  148.  
  149. newline;
  150. cout << "STRONG_COMPONENTS:\n";
  151. STRONG_COMPONENTS(G,compnum);
  152. forall_nodes(v,G) 
  153. { G.print_node(v);
  154.   cout << form("  compnum = %d\n",compnum[v]);
  155.  }
  156. newline;
  157.  
  158.  
  159. s = G.first_node();
  160.  
  161. float T = used_time();
  162.  
  163. newline;
  164. cout << "DIJKSTRA (int)      ";
  165. cout.flush();
  166. DIJKSTRA(G,s,cost,dist,pred);
  167. cout << form("%6.2f sec  \n",used_time(T));
  168.  
  169. cout << "DIJKSTRA (real)     ";
  170. cout.flush();
  171. DIJKSTRA(G,s,cost1,dist1,pred);
  172. cout << form("%6.2f sec  \n",used_time(T));
  173.  
  174. cout << "BELLMAN_FORD (int)  ";
  175. cout.flush();
  176. BELLMAN_FORD(G,s,cost,dist,pred);
  177. cout << form("%6.2f sec  \n",used_time(T));
  178.  
  179.  
  180. cout << "BELLMAN_FORD (real) ";
  181. cout.flush();
  182. BELLMAN_FORD(G,s,cost1,dist1,pred);
  183. cout << form("%6.2f sec  \n",used_time(T));
  184.  
  185.   used_time(T);
  186.   cout << "ALL PAIRS SHORTEST PATHS (int) ";
  187.   cout.flush();
  188.   ALL_PAIRS_SHORTEST_PATHS(G,cost,M);
  189.   cout << form("%.2f sec\n",used_time(T));
  190.  
  191.   forall_nodes(v,G)
  192.   { forall_nodes(w,G) cout << form("%7d ",M(v,w));
  193.     newline;
  194.    }
  195.   newline;
  196.  
  197.  
  198.   used_time(T);
  199.   cout << "ALL PAIRS SHORTEST PATHS (real)  ";
  200.   cout.flush();
  201.   ALL_PAIRS_SHORTEST_PATHS(G,cost1,M1);
  202.   cout << form("%.2f sec\n",used_time(T));
  203.   
  204.   forall_nodes(v,G)
  205.   { forall_nodes(w,G) cout << form("%7.2f ",~M1(v,w));
  206.     newline;
  207.    }
  208.   newline;
  209.   
  210. /*
  211.    if (PLANAR(G)) 
  212.    { cout << "G is planar\n";
  213.      cout << "STRAIGHT_LINE_EMBEDDING: \n";
  214.      node_array(int)   xcoord(G);
  215.      node_array(int)   ycoord(G);
  216.      STRAIGHT_LINE_EMBEDDING(G,xcoord,ycoord);
  217.      forall_nodes(v,G) 
  218.      { G.print_node(v);
  219.        cout << form("  x = %3d   y = %3d\n",xcoord[v],ycoord[v]);
  220.       }
  221.      newline;
  222.     }
  223.   else cout << "G is not planar\n";
  224. */
  225.  
  226. }
  227.