Some modifications and another testfile.
5 #include <list_graph.hh>
6 #include <bfs_iterator.hh>
10 int main (int, char*[])
12 typedef ListGraph::NodeIt NodeIt;
13 typedef ListGraph::EdgeIt EdgeIt;
14 typedef ListGraph::EachNodeIt EachNodeIt;
15 typedef ListGraph::EachEdgeIt EachEdgeIt;
16 typedef ListGraph::OutEdgeIt OutEdgeIt;
17 typedef ListGraph::InEdgeIt InEdgeIt;
18 typedef ListGraph::SymEdgeIt SymEdgeIt;
23 NodeIt v1=G.addNode();
24 NodeIt v2=G.addNode();
25 NodeIt v3=G.addNode();
26 NodeIt v4=G.addNode();
40 std::cout << "bfs and dfs demo on the directed graph" << std::endl;
41 for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
42 std::cout << i << ": ";
43 std::cout << "out edges: ";
44 for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
45 std::cout << j << " ";
46 std::cout << "in edges: ";
47 for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
48 std::cout << j << " ";
49 std::cout << std::endl;
52 //std::cout << std::endl;
53 //EachNodeIt u1=G.first<EachNodeIt>();
54 //EachEdgeIt u=G.first<EachEdgeIt>();
55 //OutEdgeIt u=G.first<OutEdgeIt>(s);
56 //InEdgeIt u=G.first<InEdgeIt>(s);
57 //SymEdgeIt u=G.first<SymEdgeIt>(s);
58 //OutEdgeIt u=G.first<OutEdgeIt>(s);
59 //EachNodeIt u=G.first<EachNodeIt>();
60 //EachEdgeIt u=G.first<EachEdgeIt>();
61 //OutEdgeIt u=G.first<OutEdgeIt>(s);
62 //InEdgeIt u=G.first<InEdgeIt>(s);
63 //SymEdgeIt u=G.first<SymEdgeIt>(s);
65 //u=G.first_ize(s, OutEdgeIt());
66 //std::cout << "ize " << u << std::endl;
70 std::cout << "iterator bfs demo..." << std::endl;
71 NodePropertyVector<ListGraph, bool> reached(G, false);
73 std::queue<ListGraph::OutEdgeIt> bfs_queue;
74 bfs_queue.push(G.firstOutEdge(G.firstNode()));
75 BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached);
76 for ( ; !bfs.finished(); ++bfs) {
77 if (OutEdgeIt(bfs).valid()) {
78 std::cout << "OutEdgeIt: " << bfs;
79 std::cout << " aNode: " << G.aNode(bfs);
80 std::cout << " bNode: " << G.bNode(bfs) << " ";
82 std::cout << "OutEdgeIt: " << "invalid";
83 std::cout << " aNode: " << G.aNode(bfs);
84 std::cout << " bNode: " << "invalid" << " ";
86 if (bfs.bNodeIsNewlyReached()) {
87 std::cout << "bNodeIsNewlyReached ";
89 std::cout << "bNodeIsNotNewlyReached ";
91 if (bfs.aNodeIsExamined()) {
92 std::cout << "aNodeIsExamined ";
94 std::cout << "aNodeIsNotExamined ";
101 std::cout << "iterator dfs demo..." << std::endl;
102 NodePropertyVector<ListGraph, bool> reached(G, false);
103 reached.set(s, true);
104 std::stack<ListGraph::OutEdgeIt> dfs_stack;
105 dfs_stack.push(G.firstOutEdge(G.firstNode()));
106 DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached);
107 for(; !dfs.finished(); ++dfs) {
108 if (OutEdgeIt(dfs).valid()) {
109 std::cout << "OutEdgeIt: " << dfs;
110 std::cout << " aNode: " << G.aNode(dfs);
111 std::cout << " bNode: " << G.bNode(dfs) << " ";
113 std::cout << "OutEdgeIt: " << "invalid";
114 std::cout << " aNode: " << G.aNode(dfs);
115 std::cout << " bNode: " << "invalid" << " ";
117 if (dfs.bNodeIsNewlyReached()) {
118 std::cout << "bNodeIsNewlyReached ";
120 std::cout << "bNodeIsNotNewlyReached ";
122 if (dfs.aNodeIsLeaved()) {
123 std::cout << "aNodeIsLeaved ";
125 std::cout << "aNodeIsNotLeaved ";
127 std::cout<<std::endl;
129 if (OutEdgeIt(dfs).valid()) {
130 std::cout << "OutEdgeIt: " << dfs;
131 std::cout << " aNode: " << G.aNode(dfs);
132 std::cout << " bNode: " << G.bNode(dfs) << " ";
134 std::cout << "OutEdgeIt: " << "invalid";
135 std::cout << " aNode: " << G.aNode(dfs);
136 std::cout << " bNode: " << "invalid" << " ";
138 if (dfs.bNodeIsNewlyReached()) {
139 std::cout << "bNodeIsNewlyReached ";
141 std::cout << "bNodeIsNotNewlyReached ";
143 if (dfs.aNodeIsLeaved()) {
144 std::cout << "aNodeIsLeaved ";
146 std::cout << "aNodeIsNotLeaved ";
148 std::cout<<std::endl;
153 std::cout << "iterator bfs demo 1 ..." << std::endl;
154 ListGraph::NodeMap<bool> reached(G, false);
155 reached.set(s, true);
156 std::queue<ListGraph::OutEdgeIt> bfs_queue;
157 bfs_queue.push(G.first<OutEdgeIt>(s));
158 BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
159 while (!bfs.finished()) {
160 if (OutEdgeIt(bfs).valid()) {
161 std::cout << "OutEdgeIt: " << bfs;
162 std::cout << " aNode: " << G.aNode(bfs);
163 std::cout << " bNode: " << G.bNode(bfs) << " ";
165 std::cout << "OutEdgeIt: " << "invalid";
166 std::cout << " aNode: " << G.aNode(bfs);
167 std::cout << " bNode: " << "invalid" << " ";
169 if (bfs.bNodeIsNewlyReached()) {
170 std::cout << "bNodeIsNewlyReached ";
172 std::cout << "bNodeIsNotNewlyReached ";
174 if (bfs.aNodeIsExamined()) {
175 std::cout << "aNodeIsExamined ";
177 std::cout << "aNodeIsNotExamined ";
179 std::cout<<std::endl;
185 std::cout << "iterator bfs demo 2 ..." << std::endl;
186 //ListGraph::NodeMap<bool> reached(G, false);
187 //reached.set(s, true);
188 //std::queue<ListGraph::OutEdgeIt> bfs_queue;
189 //bfs_queue.push(G.first<OutEdgeIt>(s));
190 BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
191 bfs.pushAndSetReached(s);
192 while (!bfs.finished()) {
193 if (OutEdgeIt(bfs).valid()) {
194 std::cout << "OutEdgeIt: " << bfs;
195 std::cout << " aNode: " << G.aNode(bfs);
196 std::cout << " bNode: " << G.bNode(bfs) << " ";
198 std::cout << "OutEdgeIt: " << "invalid";
199 std::cout << " aNode: " << G.aNode(bfs);
200 std::cout << " bNode: " << "invalid" << " ";
202 if (bfs.isBNodeNewlyReached()) {
203 std::cout << "bNodeIsNewlyReached ";
205 std::cout << "bNodeIsNotNewlyReached ";
207 if (bfs.isANodeExamined()) {
208 std::cout << "aNodeIsExamined ";
210 std::cout << "aNodeIsNotExamined ";
212 std::cout<<std::endl;
221 std::cout << "iterator dfs demo 1..." << std::endl;
222 ListGraph::NodeMap<bool> reached(G, false);
223 reached.set(s, true);
224 std::stack<ListGraph::OutEdgeIt> dfs_stack;
225 dfs_stack.push(G.first<OutEdgeIt>(s));
226 DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
229 if (OutEdgeIt(dfs).valid()) {
230 std::cout << "OutEdgeIt: " << dfs;
231 std::cout << " aNode: " << G.aNode(dfs);
232 std::cout << " bNode: " << G.bNode(dfs) << " ";
234 std::cout << "OutEdgeIt: " << "invalid";
235 std::cout << " aNode: " << G.aNode(dfs);
236 std::cout << " bNode: " << "invalid" << " ";
238 if (dfs.bNodeIsNewlyReached()) {
239 std::cout << "bNodeIsNewlyReached ";
241 std::cout << "bNodeIsNotNewlyReached ";
243 if (dfs.aNodeIsLeaved()) {
244 std::cout << "aNodeIsLeaved ";
246 std::cout << "aNodeIsNotLeaved ";
248 std::cout<<std::endl;
249 } while (!dfs.finished());
254 std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
255 ListGraph::NodeMap<bool> reached(G, false);
256 reached.set(t, true);
257 std::queue<ListGraph::InEdgeIt> bfs_queue;
258 bfs_queue.push(G.first<InEdgeIt>(t));
259 BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
260 while (!bfs.finished()) {
261 if (InEdgeIt(bfs).valid()) {
262 std::cout << "InEdgeIt: " << bfs;
263 std::cout << " aNode: " << G.aNode(bfs);
264 std::cout << " bNode: " << G.bNode(bfs) << " ";
266 std::cout << "InEdgeIt: " << "invalid";
267 std::cout << " aNode: " << G.aNode(bfs);
268 std::cout << " bNode: " << "invalid" << " ";
270 if (bfs.bNodeIsNewlyReached()) {
271 std::cout << "bNodeIsNewlyReached ";
273 std::cout << "bNodeIsNotNewlyReached ";
275 if (bfs.aNodeIsExamined()) {
276 std::cout << "aNodeIsExamined ";
278 std::cout << "aNodeIsNotExamined ";
280 std::cout<<std::endl;
287 std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
288 ListGraph::NodeMap<bool> reached(G, false);
289 reached.set(t, true);
290 std::queue<ListGraph::SymEdgeIt> bfs_queue;
291 bfs_queue.push(G.first<SymEdgeIt>(t));
292 BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
293 while (!bfs.finished()) {
294 if (SymEdgeIt(bfs).valid()) {
295 std::cout << "SymEdgeIt: " << bfs;
296 std::cout << " aNode: " << G.aNode(bfs);
297 std::cout << " bNode: " << G.bNode(bfs) << " ";
299 std::cout << "SymEdgeIt: " << "invalid";
300 std::cout << " aNode: " << G.aNode(bfs);
301 std::cout << " bNode: " << "invalid" << " ";
303 if (bfs.bNodeIsNewlyReached()) {
304 std::cout << "bNodeIsNewlyReached ";
306 std::cout << "bNodeIsNotNewlyReached ";
308 if (bfs.aNodeIsExamined()) {
309 std::cout << "aNodeIsExamined ";
311 std::cout << "aNodeIsNotExamined ";
313 std::cout<<std::endl;