home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graph / match_te.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  955 b   |  60 lines
  1.  
  2. #include <LEDA/graph.h>
  3. #include <LEDA/graph_alg.h>
  4.  
  5. declare2(GRAPH,int,int);
  6.  
  7. edge_array(int)* W;
  8.  
  9. int EDGE_CMP(edge& e1, edge& e2)
  10. { return (*W[e1]-*W[e2]); }
  11.  
  12. main()
  13. {
  14.  
  15. GRAPH(int,int) G;
  16. nodelist A,B;
  17. edge e;
  18.  
  19. test_bigraph(G,A,B);
  20.  
  21.  
  22. edge_array(int) weight(G);
  23.  
  24. W = &weight;
  25.  
  26. if (Yes("random edge weights from [a..b] ? "))
  27.  { int a = read_int("a = ");
  28.    int b = read_int("b = ");
  29.    init_random();
  30.    forall_edges(e,G) G[e] = random(a,b);
  31.   }
  32. else
  33.  forall_edges(e,G)
  34.    { G.print_edge(e);
  35.      G[e] = read_int("  w = ");
  36.     }
  37.  
  38. forall_edges(e,G) weight[e] = G[e];
  39.  
  40. if (Yes("show graph ? ")) G.print();
  41.  
  42. list(edge) M1 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight);
  43.  
  44. forall(e,M1) { G.print_edge(e); newline; }
  45. newline;
  46.  
  47.  
  48. G.sort_edges(EDGE_CMP);
  49.  
  50. int i = 0;
  51. forall_edges(e,G) G[e] = weight[e] = i++;
  52. if (Yes("show graph? ")) G.print();
  53.  
  54. list(edge) M2 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight);
  55.  
  56. forall(e,M2) { G.print_edge(e); newline; }
  57. newline;
  58.  
  59. }
  60.