COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/bipartite_graph_wrapper_test.cc @ 368:0beed7a49063

Last change on this file since 368:0beed7a49063 was 368:0beed7a49063, checked in by marci, 20 years ago

experimental bipartite graph wrapper

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
14using namespace hugo;
15
16int main() {
17  typedef UndirListGraph Graph;
18  typedef Graph::Node Node;
19  typedef Graph::NodeIt NodeIt;
20  typedef Graph::Edge Edge;
21  typedef Graph::EdgeIt EdgeIt;
22  typedef Graph::OutEdgeIt OutEdgeIt;
23
24  Graph g;
25  //Node s, t;
26  //Graph::EdgeMap<int> cap(g);
27  //readDimacsMaxFlow(std::cin, g, s, t, cap);
28  std::vector<Graph::Node> s_nodes;
29  std::vector<Graph::Node> t_nodes;
30  for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
31  for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
32  g.addEdge(s_nodes[0], t_nodes[2]);
33  g.addEdge(t_nodes[1], s_nodes[2]);
34 
35  Graph::NodeMap<int> ref_map(g, -1);
36  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
37  for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
38  for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
39  typedef BipartiteGraphWrapper<Graph> BGW;
40  BGW bgw(g, bipartite_map);
41  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
42    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
43  }
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
67//     std::cout << ts << std::endl;
68//   }
69
70//   {
71//     ts.reset();     
72//     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
73//     bfs.pushAndSetReached(s);
74//     pred.set(s, INVALID);
75//     while (!bfs.finished()) {
76//       ++bfs;
77//       if (G.valid(bfs) && bfs.isBNodeNewlyReached())
78//      pred.set(bfs.bNode(), bfs);
79//     }
80//     std::cout << ts << std::endl;
81//   }
82
83  return 0;
84}
Note: See TracBrowser for help on using the repository browser.