COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/graphdemo.cc @ 2:37117ebbabe2

Last change on this file since 2:37117ebbabe2 was 2:37117ebbabe2, checked in by Alpar Juttner, 18 years ago

bfs

File size: 4.7 KB
Line 
1#include <iostream>
2#include <graph.h>
3#include <bfs.h>
4
5using namespace NEGRO;
6using namespace std;
7
8class NodeData;
9class EdgeData;
10
11typedef Graph<NodeData,EdgeData> TestGraph;
12
13class NodeData
14{
15public:
16  int id;
17  bool isVis;
18  bfs_node_data<TestGraph> bfs;
19};
20
21class EdgeData
22{
23public:
24  int id;
25};
26
27typedef Graph<NodeData,EdgeData> TestGraph;
28
29/*
30struct isVis_map {};
31bool Get(isVis_map p,TestGraph::NodeIterator i) { return i->isVis;}
32void Set(isVis_map p,TestGraph::NodeIterator i,bool b) {  i->isVis=b;}
33*/
34
35class my_bfs_maps
36{
37public:
38  //isVis_map visited;  //node->bool (RW)
39  class_element_map<TestGraph::NodeIterator,
40                    TestGraph::NodeType,
41                    bool,
42                    &NodeData::isVis> visited;
43  struct _tree_map_t {
44    typedef TestGraph::EdgeIterator value_type;
45    void Set(const TestGraph::NodeIterator &n,const value_type &t)
46    {
47      cout << t.From()->id << "->" << t.To()->id << '\n';
48    }
49  } tree;
50  do_nothing_map dist;   //node->int (W)
51  do_nothing_map priority; //node->int (W)
52  //priority_map priority; //node->int (W)
53};
54
55
56
57
58class IGraph
59{
60public:
61
62  //  struct NodeType {bfs_node_data<TestGraph> bfs;};
63  struct NodeType {bool isVis;};
64
65  vector<NodeType> nodes;
66 
67  class NodeIterator
68  {
69  public:
70    IGraph *G;
71    int n;
72    NodeIterator &operator ++() { n++; return *this;}
73    NodeType &operator *() const { return G->nodes[n];}
74    NodeType *operator ->() const { return &(G->nodes[n]);}
75    bool isValid() const {return n<=5000;}
76    int Index() {return n;} //csak a kiirashoz kell
77  };
78
79  void GetFirst(NodeIterator &i) {i.G=this;i.n=1;}
80
81  class OutEdgeIterator
82  {   
83  public:
84    IGraph *G;
85    int f,t;
86    int gcd() { int a=f;int b=t;int c;while(c=a%b) {a=b;b=c;} ; return b;}
87    OutEdgeIterator &operator ++() {while(++t<=5000&&gcd()==1);return *this;}
88    bool isValid() const {return t<=5000;}
89    NodeIterator From() const {NodeIterator i; i.G=G;i.n=f;return i;}
90    NodeIterator To() const {NodeIterator i; i.G=G;i.n=t;return i;}
91    NodeIterator Anode() const {return From();}
92    NodeIterator Bnode() const {return To();}
93  };
94
95  typedef OutEdgeIterator EdgeIterator;
96  void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
97  {i.G=this;i.f=n.n;i.t=0;++i;}
98
99  IGraph() : nodes(5000) {}
100};
101
102class IMaps_t
103{
104public:
105//     class_element_map<IGraph::NodeIterator,
106//                  IGraph::NodeType,
107//                  bool,
108//                  &IGraph::NodeType::isVis> visited;
109  struct _visited_map_t {
110    typedef bool value_type;
111    void Set(const IGraph::NodeIterator &n,const value_type &t) { n->isVis=t; }
112    value_type Get(const IGraph::NodeIterator &n) const { return n->isVis; }
113  } visited;
114  struct _tree_map_t {
115    typedef IGraph::EdgeIterator value_type;
116    void Set(const IGraph::NodeIterator &n,const value_type &t)
117    { cout << t.From().Index() << "->" << t.To().Index() << '\n'; }
118  } tree;
119  do_nothing_map dist;   //node->int (W)
120  do_nothing_map priority; //node->int (W)
121};
122
123void main()
124{
125  TestGraph G;
126  TestGraph::NodeIterator n,m,o,p,q;
127  TestGraph::OutEdgeIterator e,f,g,h;
128  int i,j,k;
129
130 
131  //for(i=1;i<=10;i++) G.AddNode().n=i; //Ez nagyon rossz!!!!!!!!
132  for(i=1;i<=10;i++) G.AddNode()->id=i; //Ez a jo!!!!!!!!
133
134  //n=G.AddNode();
135 
136   //for(i=1;i<=10;i++) cout << (G.AddNode()->n=i) << ' ';
137   //cout << '\n';
138 
139  i=0;
140  for(G.GetFirst(n);n.isValid();n++)
141    for(G.GetFirst(m);m.isValid();++m)
142      if(n!=m) G.AddEdge(n,m)->id=++i;
143   
144  cout << "Number of edges: " << i << "\n\n";
145
146  TestGraph::AllEdgeIterator a;
147  for(G.GetFirst(a);a.isValid();++a)
148    cout << a->id << ":" << a.From()->id << "->" << a.To()->id << "   ";
149
150  cout << "\n\n\n";
151 
152  for(G.GetFirst(n);n.isValid();++n)
153    {
154      cout << n->id << "->";
155      for(G.GetFirst(e,n);e.isValid();++e)
156        cout << e->id << ":" << e.To()->id << ' ';
157      cout << '\n';
158    }
159 
160  cout << "\n\n\n\nB-verzio:\n\n\n";
161 
162  G.Clean();
163
164  for(i=1;i<=10;i++) G.AddNode()->id=i;
165 
166  i=0;
167  for(n=G.First();n.isValid();n++)
168    for(m=G.First();m.isValid();++m)
169      if(n!=m) G.AddEdge(n,m)->id=++i;
170   
171  ;
172  for(n=G.First();n.isValid();++n)
173    {
174      e=G.First(n);
175      while(e.isValid())
176        if((e->id)%2) G.Delete(e++);
177        else ++e;
178    }
179 
180  // cout << "Number of edges: " << i << "\n\n";
181
182  for(a=G.First();a.isValid();++a)
183    cout << a->id << ": " << a.From()->id << "->" << a.To()->id << "   ";
184 
185  cout << "\n\n\n";
186 
187  for(n=G.First();n.isValid();++n)
188    {
189      cout << n->id << "->";
190      for(e=G.First(n);e.isValid();++e)
191        cout << e->id << ":" << e.To()->id << ' ';
192      cout << '\n';
193    }
194 
195  n=G.First();
196
197
198  //G.Clean();
199
200  cout << "\n\n\n BFS \n\n\n";
201  //my_bfs_maps Maps;
202  //  bfs_static_maps<TestGraph> Maps(&NodeData::bfs);
203 
204  /// bfs(G,n,Maps);
205
206  cout << '\n';
207
208  IGraph IG;
209  IMaps_t IMaps;
210
211  IGraph::NodeIterator in;
212  IG.GetFirst(in);
213  ++in;
214  bfs(IG,in,IMaps);
215 
216 
217}
Note: See TracBrowser for help on using the repository browser.