home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / spanning.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  872 b   |  54 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3.  
  4. declare2(GRAPH,int,int);
  5.  
  6. main()
  7. {
  8.  
  9. GRAPH(int,int) G;
  10.  
  11. test_graph(G);
  12.  
  13. int a = read_int("a = ");
  14. int b = read_int("b = ");
  15.  
  16. edge_array(int)  cost(G,0);
  17. list(edge) el;
  18. edge x;
  19. int total;
  20.  
  21. init_random();
  22. forall_edges(x,G) cost[x] = G[x] = random(a,b);
  23.  
  24. float T = used_time();
  25.  
  26. cout << "SPANNING_TREE:     ";
  27. cout.flush();
  28. el = SPANNING_TREE(G);
  29. cout << form(" %4.2f sec    ",used_time(T));
  30.  
  31. total = 0;
  32. forall(x,el)  total += cost[x];
  33.  
  34. if (Yes("Ausgabe? ")) 
  35.  forall(x,el) { G.print_edge(x); newline; }
  36.  
  37. cout << form("total cost %d\n",total);
  38.  
  39.  
  40. cout << "MIN_SPANNING_TREE: ";
  41. cout.flush();
  42. el = MIN_SPANNING_TREE(G,cost);
  43. cout << form(" %4.2f sec    ",used_time(T));
  44.  
  45. total = 0;
  46. forall(x,el)  total += cost[x];
  47.  
  48. if (Yes("Ausgabe? ")) 
  49.  forall(x,el) { G.print_edge(x); newline; }
  50.  
  51. cout << form("total cost %d\n",total);
  52.  
  53. }
  54.