开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
bi_matching.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：1k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

bi_matching.c：源码内容
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  5. main()
  6. {
  8. GRAPH<int,int> G;
  9. list<node> A,B;
  10. edge e;
  12. test_bigraph(G,A,B);
  14. edge_array<int>  weight1(G);
  17. forall_edges(e,G) G[e] = weight1[e] =  rand_int(0,1000);
  20. if (Yes("show graph? ")) G.print();
  22. float T = used_time();
  24. cout << "MAX_CARD_BIPARTITE MATCHING            ";
  25. cout.flush();
  26. list<edge> M0 = MAX_CARD_BIPARTITE_MATCHING(G,A,B);
  27. cout << string("%5.2f sec    |M| = %dn",used_time(T), M0.length());
  29. /*
  30. if (Yes("output ? "))  
  31.    { newline;
  32.      forall(e,M0) { G.print_edge(e); newline; }
  33.      newline;
  34.     }
  35. */
  37. cout << "MAX_CARD_MATCHING                      ";
  38. cout.flush();
  39. list<edge> M1 = MAX_CARD_MATCHING(G);
  40. cout << string("%5.2f sec    |M| = %dn",used_time(T), M1.length());
  42. /*
  43. if (Yes("output ? "))  
  44.    { newline;
  45.      forall(e,M1) { G.print_edge(e); newline; }
  46.      newline;
  47.     }
  48. */
  50. newline;
  52. int w = 0;
  54. cout << "MAX_WEIGHT_BIPARTITE_MATCHING <int>    ";
  55. cout.flush();
  56. list<edge> M2 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight1);
  57. forall(e,M2)  w += weight1[e];
  58. cout << string("%5.2f sec   W = %dn",used_time(T),w);
  60. double W = 0;
  62. edge_array<double> weight2(G);
  64. forall_edges(e,G) weight2[e] =  weight1[e]/1000.0; 
  66. cout << "MAX_WEIGHT_BIPARTITE_MATCHING <double> ";
  67. cout.flush();
  68. list<edge> M3 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight2);
  69. forall(e,M3)  W += weight2[e];
  70. cout << string("%5.2f sec   W = %.2fn",used_time(T),W);
  72. return 0;
  73. }