marci@368: // -*- c++ -*-
marci@368: #include <iostream>
marci@368: #include <fstream>
marci@368: #include <vector>
marci@368: 
marci@368: #include <list_graph.h>
marci@389: //#include <smart_graph.h>
marci@368: //#include <dimacs.h>
marci@368: #include <time_measure.h>
marci@368: #include <for_each_macros.h>
marci@368: #include <bfs_iterator.h>
marci@368: #include <graph_wrapper.h>
marci@379: #include <maps.h>
marci@379: #include <edmonds_karp.h>
marci@368: 
marci@368: using namespace hugo;
marci@368: 
marci@368: int main() {
marci@368:   typedef UndirListGraph Graph; 
marci@368:   typedef Graph::Node Node;
marci@368:   typedef Graph::NodeIt NodeIt;
marci@368:   typedef Graph::Edge Edge;
marci@368:   typedef Graph::EdgeIt EdgeIt;
marci@368:   typedef Graph::OutEdgeIt OutEdgeIt;
marci@368: 
marci@368:   Graph g;
marci@368:   //Node s, t;
marci@368:   //Graph::EdgeMap<int> cap(g);
marci@368:   //readDimacsMaxFlow(std::cin, g, s, t, cap);
marci@368:   std::vector<Graph::Node> s_nodes;
marci@368:   std::vector<Graph::Node> t_nodes;
marci@368:   for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
marci@368:   for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
marci@368:   g.addEdge(s_nodes[0], t_nodes[2]);
marci@368:   g.addEdge(t_nodes[1], s_nodes[2]);
marci@368:   
marci@368:   Graph::NodeMap<int> ref_map(g, -1);
marci@368:   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
marci@368:   for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
marci@368:   for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
marci@368:   typedef BipartiteGraphWrapper<Graph> BGW;
marci@368:   BGW bgw(g, bipartite_map);
marci@368:   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
marci@368:     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
marci@368:   }
marci@368: 
marci@379:   BGW::NodeMap<int> dbyj(bgw);
marci@379:   BGW::EdgeMap<int> dbyxcj(bgw);
marci@368: 
marci@379:   typedef stGraphWrapper<BGW> stGW;
marci@379:   stGW stgw(bgw);
marci@379:   ConstMap<stGW::Edge, int> const1map(1);
marci@379:   stGW::NodeMap<int> ize(stgw);
marci@379:   stGW::EdgeMap<int> flow(stgw);
marci@379: 
marci@379:   BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
marci@379:   Graph::NodeIt si;
marci@379:   Graph::Node s; 
marci@379:   s=g.first(si);
marci@379:   bfs.pushAndSetReached(BGW::Node(s));
marci@379:   while (!bfs.finished()) ++bfs;
marci@379: 
marci@379:   BGW::EdgeMap<bool> cap(bgw);
marci@379:   BGW::EdgeMap<bool> flow1(bgw);
marci@379: 
marci@379:   typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 
marci@379:     RBGW;
marci@379:   RBGW rbgw(bgw, cap, flow1);
marci@379:   RBGW::NodeMap<int> u(rbgw);
marci@379:   
marci@379: 
marci@379:   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
marci@379:     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
marci@379:   max_flow_test.augmentOnShortestPath();
marci@393:   max_flow_test.augmentOnShortestPath();
marci@393: 
marci@393:   std::cout << max_flow_test.flowValue() << std::endl;
marci@368: 
marci@368:   return 0;
marci@368: }