src/work/marci/bipartite_graph_wrapper_test.cc
changeset 381 d72470496fbe
parent 368 0beed7a49063
child 389 770cc1f4861f
equal deleted inserted replaced
0:77c4f6208403 1:c2bf4c95d750
     8 //#include <dimacs.h>
     8 //#include <dimacs.h>
     9 #include <time_measure.h>
     9 #include <time_measure.h>
    10 #include <for_each_macros.h>
    10 #include <for_each_macros.h>
    11 #include <bfs_iterator.h>
    11 #include <bfs_iterator.h>
    12 #include <graph_wrapper.h>
    12 #include <graph_wrapper.h>
       
    13 #include <maps.h>
       
    14 #include <edmonds_karp.h>
    13 
    15 
    14 using namespace hugo;
    16 using namespace hugo;
    15 
    17 
    16 int main() {
    18 int main() {
    17   typedef UndirListGraph Graph; 
    19   typedef UndirListGraph Graph; 
    39   typedef BipartiteGraphWrapper<Graph> BGW;
    41   typedef BipartiteGraphWrapper<Graph> BGW;
    40   BGW bgw(g, bipartite_map);
    42   BGW bgw(g, bipartite_map);
    41   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
    43   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
    42     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
    44     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
    43   }
    45   }
    44 //   Graph::NodeMap<OutEdgeIt> pred(G);
       
    45 //   Timer ts;
       
    46 //   {
       
    47 //     ts.reset();
       
    48 //     Graph::NodeMap<bool> reached(G);
       
    49 //     reached.set(s, true);
       
    50 //     pred.set(s, INVALID);
       
    51 //     std::queue<Node> bfs_queue;
       
    52 //     bfs_queue.push(t);
       
    53 //     while (!bfs_queue.empty()) {
       
    54 //       Node v=bfs_queue.front();	
       
    55 //       bfs_queue.pop();
       
    56 //       OutEdgeIt e;
       
    57 //       for(G.first(e,v); G.valid(e); G.next(e)) {
       
    58 // 	Node w=G.head(e);
       
    59 // 	if (!reached[w]) {
       
    60 // 	  bfs_queue.push(w);
       
    61 // 	  reached.set(w, true);
       
    62 // 	  pred.set(w, e);
       
    63 // 	}
       
    64 //       }
       
    65 //     }
       
    66 
    46 
    67 //     std::cout << ts << std::endl;
    47   BGW::NodeMap<int> dbyj(bgw);
    68 //   }
    48   BGW::EdgeMap<int> dbyxcj(bgw);
    69 
    49 
    70 //   {
    50   typedef stGraphWrapper<BGW> stGW;
    71 //     ts.reset();      
    51   stGW stgw(bgw);
    72 //     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    52   ConstMap<stGW::Edge, int> const1map(1);
    73 //     bfs.pushAndSetReached(s);
    53   stGW::NodeMap<int> ize(stgw);
    74 //     pred.set(s, INVALID);
    54   stGW::EdgeMap<int> flow(stgw);
    75 //     while (!bfs.finished()) { 
    55 
    76 //       ++bfs; 
    56   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
    77 //       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
    57   Graph::NodeIt si;
    78 // 	pred.set(bfs.bNode(), bfs);
    58   Graph::Node s; 
    79 //     }
    59   s=g.first(si);
    80 //     std::cout << ts << std::endl;
    60   bfs.pushAndSetReached(BGW::Node(s));
    81 //   }
    61   while (!bfs.finished()) ++bfs;
       
    62 
       
    63   BGW::EdgeMap<bool> cap(bgw);
       
    64   BGW::EdgeMap<bool> flow1(bgw);
       
    65 
       
    66   typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 
       
    67     RBGW;
       
    68   RBGW rbgw(bgw, cap, flow1);
       
    69   RBGW::NodeMap<int> u(rbgw);
       
    70   
       
    71 
       
    72   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
       
    73     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
       
    74   max_flow_test.augmentOnShortestPath();
    82 
    75 
    83   return 0;
    76   return 0;
    84 }
    77 }