lemon-0.x: src/work/iterator_bfs_dfs

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.hh>

     6 #include <bfs_iterator.hh>

     8 using namespace lemon;

    10 int main (int, char*[])

    11 {

    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;

    20   ListGraph G;

    22   NodeIt s=G.addNode();

    23   NodeIt v1=G.addNode();

    24   NodeIt v2=G.addNode();

    25   NodeIt v3=G.addNode();

    26   NodeIt v4=G.addNode();

    27   NodeIt t=G.addNode();

    29   G.addEdge(s, v1);

    30   G.addEdge(s, v2);

    31   G.addEdge(v1, v2);

    32   G.addEdge(v2, v1);

    33   G.addEdge(v1, v3);

    34   G.addEdge(v3, v2);

    35   G.addEdge(v2, v4);

    36   G.addEdge(v4, v3);

    37   G.addEdge(v3, t);

    38   G.addEdge(v4, t);

    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;

    50   }

    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);

    64   //u=G.first(s);

    65   //u=G.first_ize(s, OutEdgeIt());

    66   //std::cout << "ize " << u << std::endl;

    68   /*

    69   {

    70     std::cout << "iterator bfs demo..." << std::endl;

    71     NodePropertyVector<ListGraph, bool> reached(G, false);

    72     reached.set(s, true);

    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) << " ";

    81       } else {

    82 	std::cout << "OutEdgeIt: " << "invalid";

    83 	std::cout << " aNode: " << G.aNode(bfs);

    84 	std::cout << " bNode: " << "invalid" << " ";

    85       }

    86       if (bfs.bNodeIsNewlyReached()) {

    87 	std::cout << "bNodeIsNewlyReached ";

    88       } else {

    89 	std::cout << "bNodeIsNotNewlyReached ";

    90       }

    91       if (bfs.aNodeIsExamined()) {

    92 	std::cout << "aNodeIsExamined ";

    93       } else {

    94 	std::cout << "aNodeIsNotExamined ";

    95       }

    96       std::cout<<std::endl;

    97     }

    98   }

   100   {

   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) << " ";

   112       } else {

   113 	std::cout << "OutEdgeIt: " << "invalid";

   114 	std::cout << " aNode: " << G.aNode(dfs);

   115 	std::cout << " bNode: " << "invalid" << " ";

   116       }

   117       if (dfs.bNodeIsNewlyReached()) {

   118 	std::cout << "bNodeIsNewlyReached ";

   119       } else {

   120 	std::cout << "bNodeIsNotNewlyReached ";

   121       }

   122       if (dfs.aNodeIsLeaved()) {

   123 	std::cout << "aNodeIsLeaved ";

   124       } else {

   125 	std::cout << "aNodeIsNotLeaved ";

   126       }

   127       std::cout<<std::endl;

   128     }

   129     if (OutEdgeIt(dfs).valid()) {

   130       std::cout << "OutEdgeIt: " << dfs;

   131       std::cout << " aNode: " << G.aNode(dfs);

   132       std::cout << " bNode: " << G.bNode(dfs) << " ";

   133     } else {

   134       std::cout << "OutEdgeIt: " << "invalid";

   135       std::cout << " aNode: " << G.aNode(dfs);

   136       std::cout << " bNode: " << "invalid" << " ";

   137     }

   138     if (dfs.bNodeIsNewlyReached()) {

   139       std::cout << "bNodeIsNewlyReached ";

   140     } else {

   141       std::cout << "bNodeIsNotNewlyReached ";

   142     }

   143     if (dfs.aNodeIsLeaved()) {

   144       std::cout << "aNodeIsLeaved ";

   145     } else {

   146       std::cout << "aNodeIsNotLeaved ";

   147     }

   148     std::cout<<std::endl;

   149   }

   150   */

   152   {

   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) << " ";

   164       } else {

   165 	std::cout << "OutEdgeIt: " << "invalid";

   166 	std::cout << " aNode: " << G.aNode(bfs);

   167 	std::cout << " bNode: " << "invalid" << " ";

   168       }

   169       if (bfs.bNodeIsNewlyReached()) {

   170 	std::cout << "bNodeIsNewlyReached ";

   171       } else {

   172 	std::cout << "bNodeIsNotNewlyReached ";

   173       }

   174       if (bfs.aNodeIsExamined()) {

   175 	std::cout << "aNodeIsExamined ";

   176       } else {

   177 	std::cout << "aNodeIsNotExamined ";

   178       }

   179       std::cout<<std::endl;

   180       bfs.next();

   181     }

   182   }

   184   {

   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) << " ";

   197       } else {

   198 	std::cout << "OutEdgeIt: " << "invalid";

   199 	std::cout << " aNode: " << G.aNode(bfs);

   200 	std::cout << " bNode: " << "invalid" << " ";

   201       }

   202       if (bfs.isBNodeNewlyReached()) {

   203 	std::cout << "bNodeIsNewlyReached ";

   204       } else {

   205 	std::cout << "bNodeIsNotNewlyReached ";

   206       }

   207       if (bfs.isANodeExamined()) {

   208 	std::cout << "aNodeIsExamined ";

   209       } else {

   210 	std::cout << "aNodeIsNotExamined ";

   211       }

   212       std::cout<<std::endl;

   213       ++bfs;

   214     }

   215   }

   220   {

   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);

   227     do {

   228       dfs.next();

   229       if (OutEdgeIt(dfs).valid()) {

   230 	std::cout << "OutEdgeIt: " << dfs;

   231 	std::cout << " aNode: " << G.aNode(dfs);

   232 	std::cout << " bNode: " << G.bNode(dfs) << " ";

   233       } else {

   234 	std::cout << "OutEdgeIt: " << "invalid";

   235 	std::cout << " aNode: " << G.aNode(dfs);

   236 	std::cout << " bNode: " << "invalid" << " ";

   237       }

   238       if (dfs.bNodeIsNewlyReached()) {

   239 	std::cout << "bNodeIsNewlyReached ";

   240       } else {

   241 	std::cout << "bNodeIsNotNewlyReached ";

   242       }

   243       if (dfs.aNodeIsLeaved()) {

   244 	std::cout << "aNodeIsLeaved ";

   245       } else {

   246 	std::cout << "aNodeIsNotLeaved ";

   247       }

   248       std::cout<<std::endl;

   249     } while (!dfs.finished());

   250   }

   253   {

   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) << " ";

   265       } else {

   266 	std::cout << "InEdgeIt: " << "invalid";

   267 	std::cout << " aNode: " << G.aNode(bfs);

   268 	std::cout << " bNode: " << "invalid" << " ";

   269       }

   270       if (bfs.bNodeIsNewlyReached()) {

   271 	std::cout << "bNodeIsNewlyReached ";

   272       } else {

   273 	std::cout << "bNodeIsNotNewlyReached ";

   274       }

   275       if (bfs.aNodeIsExamined()) {

   276 	std::cout << "aNodeIsExamined ";

   277       } else {

   278 	std::cout << "aNodeIsNotExamined ";

   279       }

   280       std::cout<<std::endl;

   281       bfs.next();

   282     }

   283   }

   286   {

   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) << " ";

   298       } else {

   299 	std::cout << "SymEdgeIt: " << "invalid";

   300 	std::cout << " aNode: " << G.aNode(bfs);

   301 	std::cout << " bNode: " << "invalid" << " ";

   302       }

   303       if (bfs.bNodeIsNewlyReached()) {

   304 	std::cout << "bNodeIsNewlyReached ";

   305       } else {

   306 	std::cout << "bNodeIsNotNewlyReached ";

   307       }

   308       if (bfs.aNodeIsExamined()) {

   309 	std::cout << "aNodeIsExamined ";

   310       } else {

   311 	std::cout << "aNodeIsNotExamined ";

   312       }

   313       std::cout<<std::endl;

   314       bfs.next();

   315     }

   316   }

   318   return 0;

   319 }

author	deba
	Sat, 09 Apr 2005 19:27:48 +0000
changeset 1330	52ef02524468
parent 107	8d62f0072ff0
permissions	-rw-r--r--