home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / bi_match.c next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  1.4 KB  |  79 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. nodelist A,B;
  11. edge e;
  12.  
  13. test_bigraph(G,A,B);
  14.  
  15. edge_array(int)  weight1(G);
  16. edge_array(real) weight2(G);
  17.  
  18. init_random();
  19.  
  20. forall_edges(e,G) 
  21. { int r = random(0,1000);
  22.   G[e] = r;
  23.   weight1[e] = r;
  24.   weight2[e] = r/1000.0;
  25. }
  26.  
  27.  
  28. if (Yes("show graph? ")) G.print();
  29.  
  30. float T = used_time();
  31.  
  32. cout << "MAX_CARD_BIPARTITE MATCHING          ";
  33. cout.flush();
  34. list(edge) M0 = MAX_CARD_BIPARTITE_MATCHING(G,A,B);
  35. cout << form("%5.2f sec    |M| = %d\n",used_time(T), M0.length());
  36.  
  37. /*
  38. if (Yes("output ? "))  
  39.    { newline;
  40.      forall(e,M0) { G.print_edge(e); newline; }
  41.      newline;
  42.     }
  43. */
  44.  
  45. cout << "MAX_CARD_MATCHING                    ";
  46. cout.flush();
  47. list(edge) M1 = MAX_CARD_MATCHING(G);
  48. cout << form("%5.2f sec    |M| = %d\n",used_time(T), M1.length());
  49.  
  50. /*
  51. if (Yes("output ? "))  
  52.    { newline;
  53.      forall(e,M1) { G.print_edge(e); newline; }
  54.      newline;
  55.     }
  56. */
  57.  
  58. newline;
  59.  
  60. int w = 0;
  61.  
  62. cout << "MAX_WEIGHT_BIPARTITE_MATCHING (int)  ";
  63. cout.flush();
  64. list(edge) M2 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight1);
  65. forall(e,M2)  w += weight1[e];
  66. cout << form("%5.2f sec   W = %d\n",used_time(T),w);
  67.  
  68. double W = 0;
  69.  
  70. cout << "MAX_WEIGHT_BIPARTITE_MATCHING (real) ";
  71. cout.flush();
  72. list(edge) M3 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight2);
  73. forall(e,M3)  W += weight2[e];
  74. cout << form("%5.2f sec   W = %.2f\n",used_time(T),W);
  75.  
  76.  
  77.  
  78. }
  79.