lemon-0.x: comparison src/work/iterator_bfs_dfs

equal deleted inserted replaced

--1:000000000000
+:8ab4251c10d1
+#include <iostream>
+#include <vector>
+#include <string>
+#include <list_graph.hh>
+#include <bfs_iterator.hh>
+using namespace marci;
+int main (int, char*[])
+{
+typedef ListGraph::NodeIt NodeIt;
+typedef ListGraph::EdgeIt EdgeIt;
+typedef ListGraph::EachNodeIt EachNodeIt;
+typedef ListGraph::EachEdgeIt EachEdgeIt;
+typedef ListGraph::OutEdgeIt OutEdgeIt;
+typedef ListGraph::InEdgeIt InEdgeIt;
+typedef ListGraph::SymEdgeIt SymEdgeIt;
+ListGraph G;
+NodeIt s=G.addNode();
+NodeIt v1=G.addNode();
+NodeIt v2=G.addNode();
+NodeIt v3=G.addNode();
+NodeIt v4=G.addNode();
+NodeIt t=G.addNode();
+G.addEdge(s, v1);
+G.addEdge(s, v2);
+G.addEdge(v1, v2);
+G.addEdge(v2, v1);
+G.addEdge(v1, v3);
+G.addEdge(v3, v2);
+G.addEdge(v2, v4);
+G.addEdge(v4, v3);
+G.addEdge(v3, t);
+G.addEdge(v4, t);
+std::cout << "bfs and dfs demo on the directed graph" << std::endl;
+for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
+std::cout << i << ": ";
+std::cout << "out edges: ";
+for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)
+std::cout << j << " ";
+std::cout << "in edges: ";
+for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)
+std::cout << j << " ";
+std::cout << std::endl;
+}
+//std::cout << std::endl;
+//EachNodeIt u1=G.first<EachNodeIt>();
+//EachEdgeIt u=G.first<EachEdgeIt>();
+//OutEdgeIt u=G.first<OutEdgeIt>(s);
+//InEdgeIt u=G.first<InEdgeIt>(s);
+//SymEdgeIt u=G.first<SymEdgeIt>(s);
+//OutEdgeIt u=G.first<OutEdgeIt>(s);
+//EachNodeIt u=G.first<EachNodeIt>();
+//EachEdgeIt u=G.first<EachEdgeIt>();
+//OutEdgeIt u=G.first<OutEdgeIt>(s);
+//InEdgeIt u=G.first<InEdgeIt>(s);
+//SymEdgeIt u=G.first<SymEdgeIt>(s);
+//u=G.first(s);
+//u=G.first_ize(s, OutEdgeIt());
+//std::cout << "ize " << u << std::endl;
+/*
+{
+std::cout << "iterator bfs demo..." << std::endl;
+NodePropertyVector<ListGraph, bool> reached(G, false);
+reached.set(s, true);
+std::queue<ListGraph::OutEdgeIt> bfs_queue;
+bfs_queue.push(G.firstOutEdge(G.firstNode()));
+BfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > bfs(G, bfs_queue, reached);
+for ( ; !bfs.finished(); ++bfs) {
+if (OutEdgeIt(bfs).valid()) {
+	std::cout << "OutEdgeIt: " << bfs;
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << G.bNode(bfs) << " ";
+} else {
+	std::cout << "OutEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (bfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (bfs.aNodeIsExamined()) {
+	std::cout << "aNodeIsExamined ";
+} else {
+	std::cout << "aNodeIsNotExamined ";
+}
+std::cout<<std::endl;
+}
+}
+{
+std::cout << "iterator dfs demo..." << std::endl;
+NodePropertyVector<ListGraph, bool> reached(G, false);
+reached.set(s, true);
+std::stack<ListGraph::OutEdgeIt> dfs_stack;
+dfs_stack.push(G.firstOutEdge(G.firstNode()));
+DfsIterator< ListGraph, ListGraph::OutEdgeIt, NodePropertyVector<ListGraph, bool> > dfs(G, dfs_stack, reached);
+for(; !dfs.finished(); ++dfs) {
+if (OutEdgeIt(dfs).valid()) {
+	std::cout << "OutEdgeIt: " << dfs;
+	std::cout << " aNode: " << G.aNode(dfs);
+	std::cout << " bNode: " << G.bNode(dfs) << " ";
+} else {
+	std::cout << "OutEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(dfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (dfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (dfs.aNodeIsLeaved()) {
+	std::cout << "aNodeIsLeaved ";
+} else {
+	std::cout << "aNodeIsNotLeaved ";
+}
+std::cout<<std::endl;
+}
+if (OutEdgeIt(dfs).valid()) {
+std::cout << "OutEdgeIt: " << dfs;
+std::cout << " aNode: " << G.aNode(dfs);
+std::cout << " bNode: " << G.bNode(dfs) << " ";
+} else {
+std::cout << "OutEdgeIt: " << "invalid";
+std::cout << " aNode: " << G.aNode(dfs);
+std::cout << " bNode: " << "invalid" << " ";
+}
+if (dfs.bNodeIsNewlyReached()) {
+std::cout << "bNodeIsNewlyReached ";
+} else {
+std::cout << "bNodeIsNotNewlyReached ";
+}
+if (dfs.aNodeIsLeaved()) {
+std::cout << "aNodeIsLeaved ";
+} else {
+std::cout << "aNodeIsNotLeaved ";
+}
+std::cout<<std::endl;
+}
+*/
+{
+std::cout << "iterator bfs demo 1 ..." << std::endl;
+ListGraph::NodeMap<bool> reached(G, false);
+reached.set(s, true);
+std::queue<ListGraph::OutEdgeIt> bfs_queue;
+bfs_queue.push(G.first<OutEdgeIt>(s));
+BfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
+while (!bfs.finished()) {
+if (OutEdgeIt(bfs).valid()) {
+	std::cout << "OutEdgeIt: " << bfs;
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << G.bNode(bfs) << " ";
+} else {
+	std::cout << "OutEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (bfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (bfs.aNodeIsExamined()) {
+	std::cout << "aNodeIsExamined ";
+} else {
+	std::cout << "aNodeIsNotExamined ";
+}
+std::cout<<std::endl;
+bfs.next();
+}
+}
+{
+std::cout << "iterator dfs demo 1..." << std::endl;
+ListGraph::NodeMap<bool> reached(G, false);
+reached.set(s, true);
+std::stack<ListGraph::OutEdgeIt> dfs_stack;
+dfs_stack.push(G.first<OutEdgeIt>(s));
+DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);
+do {
+dfs.next();
+if (OutEdgeIt(dfs).valid()) {
+	std::cout << "OutEdgeIt: " << dfs;
+	std::cout << " aNode: " << G.aNode(dfs);
+	std::cout << " bNode: " << G.bNode(dfs) << " ";
+} else {
+	std::cout << "OutEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(dfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (dfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (dfs.aNodeIsLeaved()) {
+	std::cout << "aNodeIsLeaved ";
+} else {
+	std::cout << "aNodeIsNotLeaved ";
+}
+std::cout<<std::endl;
+} while (!dfs.finished());
+}
+{
+std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;
+ListGraph::NodeMap<bool> reached(G, false);
+reached.set(t, true);
+std::queue<ListGraph::InEdgeIt> bfs_queue;
+bfs_queue.push(G.first<InEdgeIt>(t));
+BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
+while (!bfs.finished()) {
+if (InEdgeIt(bfs).valid()) {
+	std::cout << "InEdgeIt: " << bfs;
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << G.bNode(bfs) << " ";
+} else {
+	std::cout << "InEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (bfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (bfs.aNodeIsExamined()) {
+	std::cout << "aNodeIsExamined ";
+} else {
+	std::cout << "aNodeIsNotExamined ";
+}
+std::cout<<std::endl;
+bfs.next();
+}
+}
+{
+std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;
+ListGraph::NodeMap<bool> reached(G, false);
+reached.set(t, true);
+std::queue<ListGraph::SymEdgeIt> bfs_queue;
+bfs_queue.push(G.first<SymEdgeIt>(t));
+BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);
+while (!bfs.finished()) {
+if (SymEdgeIt(bfs).valid()) {
+	std::cout << "SymEdgeIt: " << bfs;
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << G.bNode(bfs) << " ";
+} else {
+	std::cout << "SymEdgeIt: " << "invalid";
+	std::cout << " aNode: " << G.aNode(bfs);
+	std::cout << " bNode: " << "invalid" << " ";
+}
+if (bfs.bNodeIsNewlyReached()) {
+	std::cout << "bNodeIsNewlyReached ";
+} else {
+	std::cout << "bNodeIsNotNewlyReached ";
+}
+if (bfs.aNodeIsExamined()) {
+	std::cout << "aNodeIsExamined ";
+} else {
+	std::cout << "aNodeIsNotExamined ";
+}
+std::cout<<std::endl;
+bfs.next();
+}
+}
+return 0;
+}

changeset 54	acd0dc288149
child 59	41c7f9c09a12