1.1 --- a/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 15:09:48 2004 +0000
     1.2 +++ b/src/work/marci/max_bipartite_matching_demo.cc	Wed Mar 17 15:41:00 2004 +0000
     1.3 @@ -55,24 +55,46 @@
     1.4    std::vector<Node> s_nodes;
     1.5    std::vector<Node> t_nodes;
     1.6  
     1.7 -  for(int i=0; i<20; ++i) {
     1.8 +  for(int i=0; i<4; ++i) {
     1.9      s_nodes.push_back(G.addNode());
    1.10    }
    1.11 -  for(int i=0; i<20; ++i) {
    1.12 +  for(int i=0; i<4; ++i) {
    1.13      t_nodes.push_back(G.addNode());
    1.14    }
    1.15 -  random_init();
    1.16 -  for(int i=0; i<50; ++i) {
    1.17 -    G.addEdge(s_nodes[random(20)], t_nodes[random(20)]);
    1.18 -  }
    1.19 +//   random_init();
    1.20 +//   for(int i=0; i<6; ++i) {
    1.21 +//     G.addEdge(s_nodes[random(4)], t_nodes[random(4)]);
    1.22 +//   }
    1.23 +  
    1.24 +  G.addEdge(s_nodes[2], t_nodes[4-4]);
    1.25 +  G.addEdge(s_nodes[2], t_nodes[7-4]);
    1.26 +  G.addEdge(s_nodes[2], t_nodes[4-4]);
    1.27 +  G.addEdge(s_nodes[3], t_nodes[6-4]);
    1.28 +  G.addEdge(s_nodes[3], t_nodes[5-4]);
    1.29 +  G.addEdge(s_nodes[3], t_nodes[5-4]);
    1.30 +
    1.31 +
    1.32    Graph::NodeMap<bool> s_map(G); //false
    1.33    Graph::NodeMap<bool> t_map(G); //false
    1.34    
    1.35 -  for(int i=0; i<20; ++i) {
    1.36 +  for(int i=0; i<4; ++i) {
    1.37      s_map.set(s_nodes[i], true);
    1.38      t_map.set(t_nodes[i], true);
    1.39    }
    1.40  
    1.41 +  cout << "bfs and dfs iterator demo on the directed graph" << endl;
    1.42 +  for(NodeIt n=G.first<NodeIt>(); G.valid(n); G.next(n)) { 
    1.43 +    cout << G.id(n) << ": ";
    1.44 +    cout << "out edges: ";
    1.45 +    for(OutEdgeIt e=G.first<OutEdgeIt>(n); G.valid(e); G.next(e)) 
    1.46 +      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
    1.47 +    cout << "in edges: ";
    1.48 +    for(InEdgeIt e=G.first<InEdgeIt>(n); G.valid(e); G.next(e)) 
    1.49 +      cout << G.id(G.tail(e)) << "->" << G.id(G.head(e)) << " ";
    1.50 +    cout << endl;
    1.51 +  }
    1.52 +
    1.53 +
    1.54    {
    1.55      std::cout << "on-the-fly max bipartite matching demo on wrapped leda graph..." << std::endl;
    1.56      Graph::EdgeMap<int> flow(G); //0 flow
    1.57 @@ -92,11 +114,17 @@
    1.58        ++i; 
    1.59      }
    1.60  
    1.61 -//   std::cout << "maximum flow: "<< std::endl;
    1.62 -//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
    1.63 -//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    1.64 -//   }
    1.65 -//   std::cout<<std::endl;
    1.66 +    std::cout << "maximum matching: "<< std::endl;
    1.67 +    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
    1.68 +      if (flow.get(e))
    1.69 +	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
    1.70 +    std::cout<<std::endl;
    1.71 +    std::cout << "edges which are not in this maximum matching: "<< std::endl;
    1.72 +    for(EdgeIt e=G.first<EdgeIt>(); G.valid(e); G.next(e))  
    1.73 +      if (!flow.get(e))
    1.74 +	std::cout << G.id(G.tail(e)) << "-" << flow.get(e) << "->" << G.id(G.head(e)) << " ";
    1.75 +    std::cout<<std::endl;
    1.76 +    
    1.77      std::cout << "elapsed time: " << ts << std::endl;
    1.78      std::cout << "number of augmentation phases: " << i << std::endl; 
    1.79      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;