COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfsdemo.cc @ 363:7a05119c121a

Last change on this file since 363:7a05119c121a was 8:cd54905012bc, checked in by Alpar Juttner, 21 years ago

-New test: bfsdemo2.cc added

  • Graph class has a NodeMap? and an EdgeMap? member class
  • default_bfs_T uning the above Maps is added
  • a (property)map must provide a member function SetG() to attach the map to a graph
File size: 3.2 KB
Line 
1#include <iostream>
2#include <graph.h>
3#include <bfs.h>
4
5using namespace NEGRO;
6using namespace std;
7
8class IGraph
9{
10public:
11
12  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
13  struct NodeType {bool isVis;};
14
15  vector<NodeType> nodes;
16 
17  class NodeIterator
18  {
19  public:
20    IGraph *G;
21    int n;
22    NodeIterator &operator ++() { n++; return *this;}
23    NodeType &operator *() const { return G->nodes[n];}
24    NodeType *operator ->() const { return &(G->nodes[n]);}
25    bool isValid() const {return n<=5000;}
26    int Index() {return n;} //csak a kiirashoz kell
27
28    NodeIterator() {}
29    NodeIterator(IGraph &Gr) {G=&Gr;n=1;} //Bfs class prefer this.
30  };
31 
32  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
33
34  class OutEdgeIterator
35  {   
36  public:
37    IGraph *G;
38    int f,t;
39    int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}
40    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
41    bool isValid() const {return t<=5000;}
42    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
43    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
44    NodeIterator Anode() const {return From();}
45    NodeIterator Bnode() const {return To();}
46
47    OutEdgeIterator() {}
48    OutEdgeIterator(IGraph &Gr,NodeIterator &n)  //Bfs class prefer this.
49    {G=&Gr;f=n.n;t=0;operator++();}
50  };
51
52  typedef OutEdgeIterator EdgeIterator;
53  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
54  {i.G=this;i.f=n.n;i.t=0;++i;}
55
56  IGraph() : nodes(5001) {}
57};
58
59class IMaps_t
60{
61public:
62//     class_element_map<IGraph::NodeIterator,
63//                  IGraph::NodeType,
64//                  bool,
65//                  &IGraph::NodeType::isVis> visited;
66  struct _visited_map_t {
67    typedef bool value_type;
68    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
69    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
70    void SetG(IGraph &G) {}
71  } visited;
72  struct _tree_map_t {
73    typedef IGraph::EdgeIterator value_type;
74    void Put(const IGraph::NodeIterator &n,const value_type &t)
75    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
76    void SetG(IGraph &G) {}
77  } tree;
78  do_nothing_map dist;   //node->int (W)
79  do_nothing_map priority; //node->int (W)
80};
81
82// New style bfs traits
83class BFS_T
84{
85public:
86
87  typedef IGraph Graph;
88  typedef IGraph::OutEdgeIterator SearchEdgeIterator;
89 
90  struct visited_map_t {
91    typedef bool value_type;
92    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
93    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
94    void SetG(IGraph &G) {}
95  };
96  struct tree_map_t {
97    typedef IGraph::EdgeIterator value_type;
98    void Put(const IGraph::NodeIterator &n,const value_type &t)
99    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
100    void SetG(IGraph &G) {}
101  };
102  typedef do_nothing_map dist_map_t;   //node->int (W)
103  typedef do_nothing_map priority_map_t; //node->int (W)
104};
105
106
107int main()
108{
109  IGraph IG;
110
111//   //Function-syte calling
112//   IMaps_t IMaps;
113
114//   IGraph::NodeIterator in;
115//   IG.GetFirst(in);
116//   ++in;
117//   bfs_fn(IG,in,IMaps); 
118
119  //Class-style calling:
120 
121  IGraph::NodeIterator in;
122  IG.GetFirst(in);
123  ++in;
124  Bfs<BFS_T> bfs;
125  bfs.SetG(IG);
126  bfs.Init(in);
127  bfs.Run();
128}
Note: See TracBrowser for help on using the repository browser.