# source:lemon-0.x/src/work/bfsdemo.cc@4:8009bb5ddd09

Last change on this file since 4:8009bb5ddd09 was 4:8009bb5ddd09, checked in by Alpar Juttner, 19 years ago

a 'bfs algorithm class' proposal added

File size: 3.1 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();}
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  } visited;
71  struct _tree_map_t {
72    typedef IGraph::EdgeIterator value_type;
73    void Put(const IGraph::NodeIterator &n,const value_type &t)
74    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
75  } tree;
76  do_nothing_map dist;   //node->int (W)
77  do_nothing_map priority; //node->int (W)
78};
79
80// New style bfs traits
81class BFS_T
82{
83public:
84
85  typedef IGraph Graph_t;
86  typedef IGraph::OutEdgeIterator SearchEdgeIterator;
87
88  struct visited_map_t {
89    typedef bool value_type;
90    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
91    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
92  };
93  struct tree_map_t {
94    typedef IGraph::EdgeIterator value_type;
95    void Put(const IGraph::NodeIterator &n,const value_type &t)
96    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
97  };
98  typedef do_nothing_map dist_map_t;   //node->int (W)
99  typedef do_nothing_map priority_map_t; //node->int (W)
100};
101
102
103int main()
104{
105  IGraph IG;
106
107//   //Function-syte calling
108//   IMaps_t IMaps;
109
110//   IGraph::NodeIterator in;
111//   IG.GetFirst(in);
112//   ++in;
113//   bfs_fn(IG,in,IMaps);
114
115  //Class-style calling:
116
117  IGraph::NodeIterator in;
118  IG.GetFirst(in);
119  ++in;
120  Bfs<BFS_T> bfs;
121  bfs.SetG(IG);
122  bfs.Init(in);
123  bfs.Run();
124}
Note: See TracBrowser for help on using the repository browser.