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

    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   }

   185   {

   186     std::cout << "iterator dfs demo 1..." << std::endl;

   187     ListGraph::NodeMap<bool> reached(G, false);

   188     reached.set(s, true);

   189     std::stack<ListGraph::OutEdgeIt> dfs_stack;

   190     dfs_stack.push(G.first<OutEdgeIt>(s));

   191     DfsIterator1< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G, dfs_stack, reached);

   192     do {

   193       dfs.next();

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

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

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

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

   198       } else {

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

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

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

   202       }

   203       if (dfs.bNodeIsNewlyReached()) {

   204 	std::cout << "bNodeIsNewlyReached ";

   205       } else {

   206 	std::cout << "bNodeIsNotNewlyReached ";

   207       }

   208       if (dfs.aNodeIsLeaved()) {

   209 	std::cout << "aNodeIsLeaved ";

   210       } else {

   211 	std::cout << "aNodeIsNotLeaved ";

   212       }

   213       std::cout<<std::endl;

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

   215   }

   218   {

   219     std::cout << "iterator bfs demo from node 5 with replacing \n OutEdgeIt by InEdgeIt ..." << std::endl;

   220     ListGraph::NodeMap<bool> reached(G, false);

   221     reached.set(t, true);

   222     std::queue<ListGraph::InEdgeIt> bfs_queue;

   223     bfs_queue.push(G.first<InEdgeIt>(t));

   224     BfsIterator1< ListGraph, ListGraph::InEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);

   225     while (!bfs.finished()) {

   226       if (InEdgeIt(bfs).valid()) {

   227 	std::cout << "InEdgeIt: " << bfs;

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

   229 	std::cout << " bNode: " << G.bNode(bfs) << " ";

   230       } else {

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

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

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

   234       }

   235       if (bfs.bNodeIsNewlyReached()) {

   236 	std::cout << "bNodeIsNewlyReached ";

   237       } else {

   238 	std::cout << "bNodeIsNotNewlyReached ";

   239       }

   240       if (bfs.aNodeIsExamined()) {

   241 	std::cout << "aNodeIsExamined ";

   242       } else {

   243 	std::cout << "aNodeIsNotExamined ";

   244       }

   245       std::cout<<std::endl;

   246       bfs.next();

   247     }

   248   }

   251   {

   252     std::cout << "the graph is considered as an undirected graph \n by replacing InEdgeIt by SymEdgeIt ..." << std::endl;

   253     ListGraph::NodeMap<bool> reached(G, false);

   254     reached.set(t, true);

   255     std::queue<ListGraph::SymEdgeIt> bfs_queue;

   256     bfs_queue.push(G.first<SymEdgeIt>(t));

   257     BfsIterator1< ListGraph, ListGraph::SymEdgeIt, ListGraph::NodeMap<bool> > bfs(G, bfs_queue, reached);

   258     while (!bfs.finished()) {

   259       if (SymEdgeIt(bfs).valid()) {

   260 	std::cout << "SymEdgeIt: " << bfs;

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

   262 	std::cout << " bNode: " << G.bNode(bfs) << " ";

   263       } else {

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

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

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

   267       }

   268       if (bfs.bNodeIsNewlyReached()) {

   269 	std::cout << "bNodeIsNewlyReached ";

   270       } else {

   271 	std::cout << "bNodeIsNotNewlyReached ";

   272       }

   273       if (bfs.aNodeIsExamined()) {

   274 	std::cout << "aNodeIsExamined ";

   275       } else {

   276 	std::cout << "aNodeIsNotExamined ";

   277       }

   278       std::cout<<std::endl;

   279       bfs.next();

   280     }

   281   }

   283   return 0;

   284 }

author	alpar
	Tue, 03 Feb 2004 13:29:49 +0000
changeset 54	acd0dc288149
child 59	41c7f9c09a12
permissions	-rw-r--r--