COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/bfsdemo.cc @ 3:272a5677bd6d

Last change on this file since 3:272a5677bd6d was 3:272a5677bd6d, checked in by Alpar Juttner, 17 years ago
  • Marci type iterator constructors
  • src/demo/bfsdemo.cc: demo for bfs.h
  • cosmetical changes
File size: 2.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 
29  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
30
31  class OutEdgeIterator
32  {   
33  public:
34    IGraph *G;
35    int f,t;
36    int gcd() { int a=f;int b=t;int c;while((c=a%b)) {a=b;b=c;} ; return b;}
37    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
38    bool isValid() const {return t<=5000;}
39    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
40    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
41    NodeIterator Anode() const {return From();}
42    NodeIterator Bnode() const {return To();}
43  };
44
45  typedef OutEdgeIterator EdgeIterator;
46  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
47  {i.G=this;i.f=n.n;i.t=0;++i;}
48
49  IGraph() : nodes(5001) {}
50};
51
52class IMaps_t
53{
54public:
55//     class_element_map<IGraph::NodeIterator,
56//                  IGraph::NodeType,
57//                  bool,
58//                  &IGraph::NodeType::isVis> visited;
59  struct _visited_map_t {
60    typedef bool value_type;
61    void Put(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
62    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
63  } visited;
64  struct _tree_map_t {
65    typedef IGraph::EdgeIterator value_type;
66    void Put(const IGraph::NodeIterator &n,const value_type &t)
67    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
68  } tree;
69  do_nothing_map dist;   //node->int (W)
70  do_nothing_map priority; //node->int (W)
71};
72
73
74int main()
75{
76  IGraph IG;
77  IMaps_t IMaps;
78
79  IGraph::NodeIterator in;
80  IG.GetFirst(in);
81  ++in;
82  bfs(IG,in,IMaps); 
83}
Note: See TracBrowser for help on using the repository browser.