lemon-0.x: src/work/iterator_bfs

     1 #include <iostream>

     2 #include <vector>

     3 #include <string>

     5 #include <list_graph.hh>

     6 #include <bfs_iterator.hh>

     7 #include <graph_wrapper.h>

     9 using namespace marci;

    11 int main (int, char*[])

    12 {

    13   typedef ListGraph::NodeIt NodeIt;

    14   typedef ListGraph::EdgeIt EdgeIt;

    15   typedef ListGraph::EachNodeIt EachNodeIt;

    16   typedef ListGraph::EachEdgeIt EachEdgeIt;

    17   typedef ListGraph::OutEdgeIt OutEdgeIt;

    18   typedef ListGraph::InEdgeIt InEdgeIt;

    19   typedef ListGraph::SymEdgeIt SymEdgeIt;

    21   ListGraph G;

    23   NodeIt s=G.addNode();

    24   NodeIt v1=G.addNode();

    25   NodeIt v2=G.addNode();

    26   NodeIt v3=G.addNode();

    27   NodeIt v4=G.addNode();

    28   NodeIt t=G.addNode();

    30   G.addEdge(s, v1);

    31   G.addEdge(s, v2);

    32   G.addEdge(v1, v2);

    33   G.addEdge(v2, v1);

    34   G.addEdge(v1, v3);

    35   G.addEdge(v3, v2);

    36   G.addEdge(v2, v4);

    37   G.addEdge(v4, v3);

    38   G.addEdge(v3, t);

    39   G.addEdge(v4, t);

    41   std::cout << "bfs and dfs demo on the directed graph" << std::endl;

    42   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {

    43     std::cout << i << ": ";

    44     std::cout << "out edges: ";

    45     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j)

    46       std::cout << j << " ";

    47     std::cout << "in edges: ";

    48     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j)

    49       std::cout << j << " ";

    50     std::cout << std::endl;

    51   }

    53   {

    54     std::cout << "iterator bfs demo 4 ..." << std::endl;

    55     BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);

    56     bfs.pushAndSetReached(s);

    57     while (!bfs.finished()) {

    58       if (OutEdgeIt(bfs).valid()) {

    59 	std::cout << "OutEdgeIt: " << bfs;

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

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

    62       } else {

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

    64 	std::cout << " aNode: " << bfs.aNode();

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

    66       }

    67       if (bfs.isBNodeNewlyReached()) {

    68 	std::cout << "bNodeIsNewlyReached ";

    69       } else {

    70 	std::cout << "bNodeIsNotNewlyReached ";

    71       }

    72       if (bfs.isANodeExamined()) {

    73 	std::cout << "aNodeIsExamined ";

    74       } else {

    75 	std::cout << "aNodeIsNotExamined ";

    76       }

    77       std::cout<<std::endl;

    78       ++bfs;

    79     }

    80   }

    82   {

    83     std::cout << "iterator dfs demo 4 ..." << std::endl;

    84     DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);

    85     dfs.pushAndSetReached(s);

    86     while (!dfs.finished()) {

    87       ++dfs;

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

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

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

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

    92       } else {

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

    94 	std::cout << " aNode: " << dfs.aNode();

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

    96       }

    97       if (dfs.isBNodeNewlyReached()) {

    98 	std::cout << "bNodeIsNewlyReached ";

    99       } else {

   100 	std::cout << "bNodeIsNotNewlyReached ";

   101       }

   102       if (dfs.isANodeExamined()) {

   103 	std::cout << "aNodeIsExamined ";

   104       } else {

   105 	std::cout << "aNodeIsNotExamined ";

   106       }

   107       std::cout<<std::endl;

   108       //++dfs;

   109     }

   110   }

   113   typedef ConstTrivGraphWrapper<ListGraph> CTGW;

   114   CTGW wG(G);

   116   std::cout << "bfs and dfs demo on the directed graph" << std::endl;

   117   for(CTGW::EachNodeIt i=wG.first<CTGW::EachNodeIt>(); i.valid(); ++i) {

   118     std::cout << i << ": ";

   119     std::cout << "out edges: ";

   120     for(CTGW::OutEdgeIt j=wG.first<CTGW::OutEdgeIt>(i); j.valid(); ++j)

   121       std::cout << j << " ";

   122     std::cout << "in edges: ";

   123     for(CTGW::InEdgeIt j=wG.first<CTGW::InEdgeIt>(i); j.valid(); ++j)

   124       std::cout << j << " ";

   125     std::cout << std::endl;

   126   }

   129   {

   130     std::cout << "iterator bfs demo 5 ..." << std::endl;

   131     BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);

   132     bfs.pushAndSetReached(s);

   133     while (!bfs.finished()) {

   134       if (OutEdgeIt(bfs).valid()) {

   135 	std::cout << "OutEdgeIt: " << bfs;

   136 	std::cout << " aNode: " << wG.aNode(bfs);

   137 	std::cout << " bNode: " << wG.bNode(bfs) << " ";

   138       } else {

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

   140 	std::cout << " aNode: " << bfs.aNode();

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

   142       }

   143       if (bfs.isBNodeNewlyReached()) {

   144 	std::cout << "bNodeIsNewlyReached ";

   145       } else {

   146 	std::cout << "bNodeIsNotNewlyReached ";

   147       }

   148       if (bfs.isANodeExamined()) {

   149 	std::cout << "aNodeIsExamined ";

   150       } else {

   151 	std::cout << "aNodeIsNotExamined ";

   152       }

   153       std::cout<<std::endl;

   154       ++bfs;

   155     }

   156   }

   159   return 0;

   160 }

author	alpar
	Fri, 20 Feb 2004 21:45:07 +0000
changeset 105	a3c73e9b9b2e
parent 75	87623302a68f
child 107	8d62f0072ff0
permissions	-rw-r--r--