1 // -*- mode:C++ -*- |
|
2 |
|
3 #include <lemon/smart_graph.h> |
|
4 #include <lemon/maps.h> |
|
5 #include <vector> |
|
6 #include <iostream> |
|
7 |
|
8 using namespace lemon; |
|
9 |
|
10 struct _BFS_DEFAULT_VIS {}; |
|
11 struct _BFS_CUSTOM_VIS {}; |
|
12 |
|
13 |
|
14 class _Bfs_Traits |
|
15 { |
|
16 typedef ListGraph Graph; |
|
17 } |
|
18 |
|
19 template<class T> |
|
20 class _Bfs |
|
21 { |
|
22 public: |
|
23 typedef typename T::Graph Graph; |
|
24 typedef typename T::Reached Reached; |
|
25 typedef typename T::PredNode PredNode; |
|
26 typedef typename T::PredEdge PredEdge; |
|
27 typedef typename T::Priority Priority; |
|
28 |
|
29 typedef typename T::DefaultReachedTag DefaultReachedTag; |
|
30 |
|
31 typedef typename Graph::Node Node; |
|
32 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
33 |
|
34 const Graph &_graph; |
|
35 |
|
36 Node _source; |
|
37 |
|
38 Reached *_visited; |
|
39 PredNode _predNode; |
|
40 PredEdge _predEdge; |
|
41 Priority _priority; |
|
42 |
|
43 _Bfs(const Graph &g, |
|
44 Node s, |
|
45 Reached *v, |
|
46 PredNode &pn, |
|
47 PredEdge &pe, |
|
48 Priority &pr) :_graph(g), _source(s), |
|
49 _visited(v), |
|
50 _predNode(pn), _predEdge(pe), _priority(pr) { } |
|
51 |
|
52 |
|
53 int run(const _Bfs_CUSTOM_VIS &) |
|
54 { |
|
55 using namespace std; |
|
56 |
|
57 int N=_graph.nodeNum(); |
|
58 vector<Node> Q(N); |
|
59 int Qh=0; |
|
60 int Qt=0; |
|
61 |
|
62 for(typename Graph::NodeIt n(_graph);n!=INVALID;++n) |
|
63 _visited->set(n,false); |
|
64 |
|
65 Q[Qh++]=_source; |
|
66 _visited->set(_source,true); |
|
67 do { |
|
68 Node m; |
|
69 Node n=Q[Qt++]; |
|
70 for(OutEdgeIt e(_graph,n);e!=INVALID;++e) |
|
71 if(!(*_visited)[m=_graph.target(e)]) { |
|
72 Q[Qh++]=m; |
|
73 _visited->set(m,true); |
|
74 _predNode.set(m,n); |
|
75 _predEdge.set(m,e); |
|
76 } |
|
77 } while(Qt!=Qh); |
|
78 |
|
79 return 1; //Why return 1? |
|
80 } |
|
81 int run(const _BFS_DEFAULT_VIS &) |
|
82 { |
|
83 _visited= new Reached(_graph); |
|
84 int r = run(_BFS_CUSTOM_VIS()); |
|
85 delete _visited; |
|
86 return r; |
|
87 } |
|
88 int run() { return run(DefaultReachedTag());} |
|
89 |
|
90 template<class T> _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
91 setVisitMap(T &t) |
|
92 { |
|
93 return _Bfs<Graph,T,_BFS_CUSTOM_VIS,PredNode,PredEdge,Priority> |
|
94 (_graph,_source,&t,_predNode,_predEdge,_priority); |
|
95 } |
|
96 |
|
97 template<class T> |
|
98 _Bfs<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> |
|
99 setPredNodeMap(T &t) |
|
100 { |
|
101 return _BFS<Graph,Reached,DefaultReachedTag,T,PredEdge,Priority> |
|
102 (_graph,_source, |
|
103 _visited, |
|
104 t,_predEdge,_priority); |
|
105 } |
|
106 |
|
107 template<class T> |
|
108 _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> |
|
109 setPredEdgeMap(T &t) |
|
110 { |
|
111 return _BFS<Graph,Reached,DefaultReachedTag,PredNode,T,Priority> |
|
112 (_graph,_source, |
|
113 _visited, |
|
114 _predNode,t,_priority); |
|
115 } |
|
116 |
|
117 _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> |
|
118 setNothing() |
|
119 { |
|
120 return _Bfs<Graph,Reached,DefaultReachedTag,PredNode,PredEdge,Priority> |
|
121 (_graph,_source, |
|
122 _visited, |
|
123 _predNode,_predEdge,_priority); |
|
124 } |
|
125 }; |
|
126 |
|
127 |
|
128 template<class G> |
|
129 _Bfs<G, |
|
130 typename G::template NodeMap<bool>, |
|
131 _BFS_DEFAULT_VIS, |
|
132 NullMap<typename G::Node,typename G::Node>, |
|
133 NullMap<typename G::Node,typename G::Edge>, |
|
134 NullMap<typename G::Node,int> > |
|
135 bfs(const G &g,typename G::Node s) |
|
136 { |
|
137 // typename G::template NodeMap<bool> v(g); |
|
138 |
|
139 return _Bfs < G, |
|
140 typename G::template NodeMap<bool>, |
|
141 _BFS_DEFAULT_VIS, |
|
142 NullMap<typename G::Node,typename G::Node>, |
|
143 NullMap<typename G::Node,typename G::Edge>, |
|
144 NullMap<typename G::Node,int> > |
|
145 (g,s, |
|
146 (typename G::template NodeMap<bool>*)(NULL), |
|
147 *((NullMap<typename G::Node,typename G::Node>*)(NULL)), |
|
148 *((NullMap<typename G::Node,typename G::Edge> *)(NULL)), |
|
149 *((NullMap<typename G::Node,int> *)(NULL)) |
|
150 ); |
|
151 } |
|
152 |
|
153 |
|
154 class MyReachedMap : public SmartGraph::NodeMap<bool> |
|
155 { |
|
156 const SmartGraph &_G; |
|
157 public: |
|
158 MyReachedMap(const SmartGraph &G) : SmartGraph::NodeMap<bool>(G), _G(G) {} |
|
159 void set(SmartGraph::Node n,bool b) |
|
160 { |
|
161 SmartGraph::NodeMap<bool>::set(n,b); |
|
162 if(b) std::cout << _G.id(n) << std::endl; |
|
163 } |
|
164 }; |
|
165 |
|
166 |
|
167 int main() |
|
168 { |
|
169 SmartGraph G; |
|
170 SmartGraph::Node s=G.addNode(); |
|
171 SmartGraph::Node n1=G.addNode(); |
|
172 SmartGraph::Node n2=G.addNode(); |
|
173 SmartGraph::Node n3=G.addNode(); |
|
174 SmartGraph::Node n4=G.addNode(); |
|
175 SmartGraph::Node n5=G.addNode(); |
|
176 SmartGraph::Node n6=G.addNode(); |
|
177 SmartGraph::Node n7=G.addNode(); |
|
178 |
|
179 G.addEdge(s,n1);G.addEdge(s,n3);G.addEdge(n1,n2);G.addEdge(n1,n3); |
|
180 G.addEdge(s,n4);G.addEdge(n4,n7);G.addEdge(n7,n6);G.addEdge(n4,n5); |
|
181 G.addEdge(n7,n2);G.addEdge(n6,n3);G.addEdge(n4,s);G.addEdge(n1,s); |
|
182 |
|
183 |
|
184 |
|
185 SmartGraph::NodeMap<SmartGraph::Node> m(G); |
|
186 SmartGraph::NodeMap<SmartGraph::Edge> em(G); |
|
187 |
|
188 MyReachedMap vm(G); |
|
189 |
|
190 |
|
191 //Runs BFS on graph 'G' from node 's'. |
|
192 //(It practically does nothing, for it throws away its result.) |
|
193 bfs(G,s).run(); |
|
194 |
|
195 //Runs BFS on graph 'G' from node 's'. Puts the predessor nodes to 'm'. |
|
196 bfs(G,s).setPredNodeMap(m).run(); |
|
197 |
|
198 //Runs BFS on graph 'G' from node 's'. |
|
199 //Puts the predessor nodes to 'm' and the edges of the bfs tree to 'em'. |
|
200 bfs(G,s).setPredNodeMap(m).setPredEdgeMap(em).run(); |
|
201 |
|
202 //Runs BFS on graph 'G' from node 's'. |
|
203 //It uses a scpecial 'visited map' that prints out the reached nodes. |
|
204 bfs(G,s).setVisitMap(vm).run(); |
|
205 |
|
206 } |
|