COIN-OR::LEMON - Graph Library

Changeset 195:19f8bd411014 in lemon-0.x


Ignore:
Timestamp:
03/17/04 16:41:00 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@272
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/max_bipartite_matching_demo.cc

    r194 r195  
    5656  std::vector<Node> t_nodes;
    5757
    58   for(int i=0; i<20; ++i) {
     58  for(int i=0; i<4; ++i) {
    5959    s_nodes.push_back(G.addNode());
    6060  }
    61   for(int i=0; i<20; ++i) {
     61  for(int i=0; i<4; ++i) {
    6262    t_nodes.push_back(G.addNode());
    6363  }
    64   random_init();
    65   for(int i=0; i<50; ++i) {
    66     G.addEdge(s_nodes[random(20)], t_nodes[random(20)]);
    67   }
     64//   random_init();
     65//   for(int i=0; i<6; ++i) {
     66//     G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
     67//   }
     68 
     69  G.addEdge(s_nodes[2], t_nodes[4-4]);
     70  G.addEdge(s_nodes[2], t_nodes[7-4]);
     71  G.addEdge(s_nodes[2], t_nodes[4-4]);
     72  G.addEdge(s_nodes[3], t_nodes[6-4]);
     73  G.addEdge(s_nodes[3], t_nodes[5-4]);
     74  G.addEdge(s_nodes[3], t_nodes[5-4]);
     75
     76
    6877  Graph::NodeMap<bool> s_map(G); //false
    6978  Graph::NodeMap<bool> t_map(G); //false
    7079 
    71   for(int i=0; i<20; ++i) {
     80  for(int i=0; i<4; ++i) {
    7281    s_map.set(s_nodes[i], true);
    7382    t_map.set(t_nodes[i], true);
    7483  }
     84
     85  cout << "bfs and dfs iterator demo on the directed graph" << endl;
     86  for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) {
     87    cout << G.id(n) << ": ";
     88    cout << "out edges: ";
     89    for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e))
     90      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
     91    cout << "in edges: ";
     92    for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e))
     93      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
     94    cout << endl;
     95  }
     96
    7597
    7698  {
     
    93115    }
    94116
    95 //   std::cout << "maximum flow: "<< std::endl;
    96 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    97 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    98 //   }
    99 //   std::cout<<std::endl;
     117    std::cout << "maximum matching: "<< std::endl;
     118    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     119      if (flow.get(e))
     120        std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     121    std::cout<<std::endl;
     122    std::cout << "edges which are not in this maximum matching: "<< std::endl;
     123    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e)) 
     124      if (!flow.get(e))
     125        std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
     126    std::cout<<std::endl;
     127   
    100128    std::cout << "elapsed time: " << ts << std::endl;
    101129    std::cout << "number of augmentation phases: " << i << std::endl;
Note: See TracChangeset for help on using the changeset viewer.