COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper_test.cc @ 393:4535f78639e2

Last change on this file since 393:4535f78639e2 was 393:4535f78639e2, checked in by marci, 20 years ago

misc

File size: 2.2 KB
Line 
1// -*- c++ -*-
2#include <iostream>
3#include <fstream>
4#include <vector>
5
6#include <list_graph.h>
7//#include <smart_graph.h>
8//#include <dimacs.h>
9#include <time_measure.h>
10#include <for_each_macros.h>
11#include <bfs_iterator.h>
12#include <graph_wrapper.h>
13#include <maps.h>
14#include <edmonds_karp.h>
15
16using namespace hugo;
17
18int main() {
19  typedef UndirListGraph Graph;
20  typedef Graph::Node Node;
21  typedef Graph::NodeIt NodeIt;
22  typedef Graph::Edge Edge;
23  typedef Graph::EdgeIt EdgeIt;
24  typedef Graph::OutEdgeIt OutEdgeIt;
25
26  Graph g;
27  //Node s, t;
28  //Graph::EdgeMap<int> cap(g);
29  //readDimacsMaxFlow(std::cin, g, s, t, cap);
30  std::vector<Graph::Node> s_nodes;
31  std::vector<Graph::Node> t_nodes;
32  for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
33  for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
34  g.addEdge(s_nodes[0], t_nodes[2]);
35  g.addEdge(t_nodes[1], s_nodes[2]);
36 
37  Graph::NodeMap<int> ref_map(g, -1);
38  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
39  for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
40  for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
41  typedef BipartiteGraphWrapper<Graph> BGW;
42  BGW bgw(g, bipartite_map);
43  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
44    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
45  }
46
47  BGW::NodeMap<int> dbyj(bgw);
48  BGW::EdgeMap<int> dbyxcj(bgw);
49
50  typedef stGraphWrapper<BGW> stGW;
51  stGW stgw(bgw);
52  ConstMap<stGW::Edge, int> const1map(1);
53  stGW::NodeMap<int> ize(stgw);
54  stGW::EdgeMap<int> flow(stgw);
55
56  BfsIterator< BGW, BGW::NodeMap<bool> > bfs(bgw);
57  Graph::NodeIt si;
58  Graph::Node s;
59  s=g.first(si);
60  bfs.pushAndSetReached(BGW::Node(s));
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();
75  max_flow_test.augmentOnShortestPath();
76
77  std::cout << max_flow_test.flowValue() << std::endl;
78
79  return 0;
80}
Note: See TracBrowser for help on using the repository browser.