DirPath fejlodes.
Kiserleti struktura a forditasi idoben kapcsolhato konzisztencia es range
ellenorzesekre.
6 #include <list_graph.h>
7 //#include <smart_graph.h>
8 #include <bfs_iterator.h>
9 #include <graph_wrapper.h>
16 template <typename Graph, typename NodeNameMap>
19 NodeNameMap& node_name_map;
21 EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
22 graph(_graph), node_name_map(_node_name_map) { }
23 string get(typename Graph::Edge e) const {
25 (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
29 int main (int, char*[])
31 //typedef SmartGraph Graph;
32 typedef ListGraph Graph;
34 typedef Graph::Node Node;
35 typedef Graph::Edge Edge;
46 Graph::NodeMap<string> node_name(G);
47 node_name.set(s, "s");
48 node_name.set(v1, "v1");
49 node_name.set(v2, "v2");
50 node_name.set(v3, "v3");
51 node_name.set(v4, "v4");
52 node_name.set(t, "t");
65 cout << " /--> -------------> "<< endl;
66 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
67 cout << " / | | / /-> \\ "<< endl;
68 cout << " / | | / | ^ \\ "<< endl;
69 cout << "s | | / | | \\-> t "<< endl;
70 cout << " \\ | | / | | /-> "<< endl;
71 cout << " \\ | --/ / | | / "<< endl;
72 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
73 cout << " \\--> -------------> "<< endl;
75 // typedef TrivGraphWrapper<const Graph> CGW;
78 // cout << "bfs and dfs demo on the directed graph" << endl;
79 // for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {
81 // cout << "out edges: ";
82 // for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
84 // cout << "in edges: ";
85 // for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)
91 typedef TrivGraphWrapper<const Graph> GW;
94 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
96 cout << "bfs and dfs iterator demo on the directed graph" << endl;
97 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
98 cout << node_name.get(n) << ": ";
99 cout << "out edges: ";
100 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
101 cout << edge_name.get(e) << " ";
102 cout << "in edges: ";
103 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
104 cout << edge_name.get(e) << " ";
108 cout << "bfs from s ..." << endl;
109 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
110 bfs.pushAndSetReached(s);
111 while (!bfs.finished()) {
114 cout << edge_name.get(bfs) << /*endl*/", " <<
115 node_name.get(gw.aNode(bfs)) <<
116 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
117 node_name.get(gw.bNode(bfs)) <<
118 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
119 ": is not newly reached.");
121 cout << "invalid" << /*endl*/", " <<
122 node_name.get(bfs.aNode()) <<
123 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
131 cout << " /--> -------------> "<< endl;
132 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
133 cout << " / | | / /-> \\ "<< endl;
134 cout << " / | | / | ^ \\ "<< endl;
135 cout << "s | | / | | \\-> t "<< endl;
136 cout << " \\ | | / | | /-> "<< endl;
137 cout << " \\ | --/ / | | / "<< endl;
138 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
139 cout << " \\--> -------------> "<< endl;
141 cout << "dfs from s ..." << endl;
142 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
143 dfs.pushAndSetReached(s);
144 while (!dfs.finished()) {
148 cout << edge_name.get(dfs) << /*endl*/", " <<
149 node_name.get(gw.aNode(dfs)) <<
150 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
151 node_name.get(gw.bNode(dfs)) <<
152 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
153 ": is not newly reached.");
155 cout << "invalid" << /*endl*/", " <<
156 node_name.get(dfs.aNode()) <<
157 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
167 typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
170 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
172 cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
173 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
174 cout << node_name.get(n) << ": ";
175 cout << "out edges: ";
176 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
177 cout << edge_name.get(e) << " ";
178 cout << "in edges: ";
179 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
180 cout << edge_name.get(e) << " ";
184 cout << "bfs from t ..." << endl;
185 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
186 bfs.pushAndSetReached(t);
187 while (!bfs.finished()) {
190 cout << edge_name.get(bfs) << /*endl*/", " <<
191 node_name.get(gw.aNode(bfs)) <<
192 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
193 node_name.get(gw.bNode(bfs)) <<
194 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
195 ": is not newly reached.");
197 cout << "invalid" << /*endl*/", " <<
198 node_name.get(bfs.aNode()) <<
199 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
207 cout << " /--> -------------> "<< endl;
208 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
209 cout << " / | | / /-> \\ "<< endl;
210 cout << " / | | / | ^ \\ "<< endl;
211 cout << "s | | / | | \\-> t "<< endl;
212 cout << " \\ | | / | | /-> "<< endl;
213 cout << " \\ | --/ / | | / "<< endl;
214 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
215 cout << " \\--> -------------> "<< endl;
217 cout << "dfs from t ..." << endl;
218 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
219 dfs.pushAndSetReached(t);
220 while (!dfs.finished()) {
224 cout << edge_name.get(dfs) << /*endl*/", " <<
225 node_name.get(gw.aNode(dfs)) <<
226 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
227 node_name.get(gw.bNode(dfs)) <<
228 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
229 ": is not newly reached.");
231 cout << "invalid" << /*endl*/", " <<
232 node_name.get(dfs.aNode()) <<
233 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
242 //typedef UndirGraphWrapper<const Graph> GW;
243 typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;
246 EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
248 cout << "bfs and dfs iterator demo on the undirected graph" << endl;
249 for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {
250 cout << node_name.get(n) << ": ";
251 cout << "out edges: ";
252 for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))
253 cout << edge_name.get(e) << " ";
254 cout << "in edges: ";
255 for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))
256 cout << edge_name.get(e) << " ";
259 // for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
260 // cout << edge_name.get(e) << " ";
264 cout << "bfs from t ..." << endl;
265 BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);
266 bfs.pushAndSetReached(t);
267 while (!bfs.finished()) {
269 if (gw.valid(GW::OutEdgeIt(bfs))) {
270 cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
271 node_name.get(gw.aNode(bfs)) <<
272 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
273 node_name.get(gw.bNode(bfs)) <<
274 (bfs.isBNodeNewlyReached() ? ": is newly reached." :
275 ": is not newly reached.");
277 cout << "invalid" << /*endl*/", " <<
278 node_name.get(bfs.aNode()) <<
279 (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
287 cout << " /--> -------------> "<< endl;
288 cout << " / /-- v1 <-\\ /---- v3-\\ "<< endl;
289 cout << " / | | / /-> \\ "<< endl;
290 cout << " / | | / | ^ \\ "<< endl;
291 cout << "s | | / | | \\-> t "<< endl;
292 cout << " \\ | | / | | /-> "<< endl;
293 cout << " \\ | --/ / | | / "<< endl;
294 cout << " \\ \\-> v2 <--/ \\-- v4 -/ "<< endl;
295 cout << " \\--> -------------> "<< endl;
297 cout << "dfs from t ..." << endl;
298 DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);
299 dfs.pushAndSetReached(t);
300 while (!dfs.finished()) {
303 if (gw.valid(GW::OutEdgeIt(dfs))) {
304 cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
305 node_name.get(gw.aNode(dfs)) <<
306 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
307 node_name.get(gw.bNode(dfs)) <<
308 (dfs.isBNodeNewlyReached() ? ": is newly reached." :
309 ": is not newly reached.");
311 cout << "invalid" << /*endl*/", " <<
312 node_name.get(dfs.aNode()) <<
313 (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<