lemon-0.x: src/work/marci/experiment/iterator_bfs

     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <vector>

     4 #include <string>

     6 #include <list_graph.h>

     7 //#include <smart_graph.h>

     8 #include <bfs_iterator.h>

     9 #include <graph_wrapper.h>

    11 using namespace lemon;

    12 using std::cout;

    13 using std::endl;

    14 using std::string;

    16 template <typename Graph, typename NodeNameMap>

    17 class EdgeNameMap {

    18   Graph& graph;

    19   NodeNameMap& node_name_map;

    20 public:

    21   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :

    22     graph(_graph), node_name_map(_node_name_map) { }

    23   string get(typename Graph::Edge e) const {

    24     return

    25       (node_name_map.get(graph.source(e))+"->"+node_name_map.get(graph.target(e)));

    26   }

    27 };

    29 int main (int, char*[])

    30 {

    31   //typedef SmartGraph Graph;

    32   typedef ListGraph Graph;

    34   typedef Graph::Node Node;

    35   typedef Graph::Edge Edge;

    37   Graph G;

    39   Node s=G.addNode();

    40   Node v1=G.addNode();

    41   Node v2=G.addNode();

    42   Node v3=G.addNode();

    43   Node v4=G.addNode();

    44   Node t=G.addNode();

    46   Graph::NodeMap<string> node_name(G);

    47   node_name.set(s, "s");

    48   node_name.set(v1, "v1");

    49   node_name.set(v2, "v2");

    50   node_name.set(v3, "v3");

    51   node_name.set(v4, "v4");

    52   node_name.set(t, "t");

    54   G.addEdge(s, v1);

    55   G.addEdge(s, v2);

    56   G.addEdge(v1, v2);

    57   G.addEdge(v2, v1);

    58   G.addEdge(v1, v3);

    59   G.addEdge(v3, v2);

    60   G.addEdge(v2, v4);

    61   G.addEdge(v4, v3);

    62   G.addEdge(v3, t);

    63   G.addEdge(v4, t);

    65   cout << "    /-->    ------------->            "<< endl;

    66   cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

    67   cout << "  / |          |    /  /->     \\     "<< endl;

    68   cout << " /  |          |   /  |    ^    \\  "<< endl;

    69   cout << "s   |          |  /   |    |     \\->  t "<< endl;

    70   cout << " \\  |          | /    |    |     /->  "<< endl;

    71   cout << "  \\ |       --/ /     |    |    /     "<< endl;

    72   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

    73   cout << "    \\-->    ------------->         "<< endl;

    75 //   typedef TrivGraphWrapper<const Graph> CGW;

    76 //   CGW gw(G);

    78 //   cout << "bfs and dfs demo on the directed graph" << endl;

    79 //   for(CGW::NodeIt n=gw.first<CGW::NodeIt>(); n.valid(); ++n) {

    80 //     cout << n << ": ";

    81 //     cout << "out edges: ";

    82 //     for(CGW::OutEdgeIt e=gw.first<CGW::OutEdgeIt>(n); e.valid(); ++e)

    83 //       cout << e << " ";

    84 //     cout << "in edges: ";

    85 //     for(CGW::InEdgeIt e=gw.first<CGW::InEdgeIt>(n); e.valid(); ++e)

    86 //       cout << e << " ";

    87 //     cout << endl;

    88 //   }

    90   {

    91     typedef TrivGraphWrapper<const Graph> GW;

    92     GW gw(G);

    94     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

    96     cout << "bfs and dfs iterator demo on the directed graph" << endl;

    97     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

    98       cout << node_name.get(n) << ": ";

    99       cout << "out edges: ";

   100       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   101 	cout << edge_name.get(e) << " ";

   102       cout << "in edges: ";

   103       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   104 	cout << edge_name.get(e) << " ";

   105       cout << endl;

   106     }

   108     cout << "bfs from s ..." << endl;

   109     BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);

   110     bfs.pushAndSetReached(s);

   111     while (!bfs.finished()) {

   112       //cout << "edge: ";

   113       if (gw.valid(bfs)) {

   114 	cout << edge_name.get(bfs) << /*endl*/", " <<

   115 	  node_name.get(gw.aNode(bfs)) <<

   116 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   117 	  node_name.get(gw.bNode(bfs)) <<

   118 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   119 	   ": is not newly reached.");

   120       } else {

   121 	cout << "invalid" << /*endl*/", " <<

   122 	  node_name.get(bfs.aNode()) <<

   123 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   125 	  "invalid.";

   126       }

   127       cout << endl;

   128       ++bfs;

   129     }

   131     cout << "    /-->    ------------->            "<< endl;

   132     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   133     cout << "  / |          |    /  /->     \\     "<< endl;

   134     cout << " /  |          |   /  |    ^    \\  "<< endl;

   135     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   136     cout << " \\  |          | /    |    |     /->  "<< endl;

   137     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   138     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   139     cout << "    \\-->    ------------->         "<< endl;

   141     cout << "dfs from s ..." << endl;

   142     DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);

   143     dfs.pushAndSetReached(s);

   144     while (!dfs.finished()) {

   145       ++dfs;

   146       //cout << "edge: ";

   147       if (gw.valid(dfs)) {

   148 	cout << edge_name.get(dfs) << /*endl*/", " <<

   149 	  node_name.get(gw.aNode(dfs)) <<

   150 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   151 	  node_name.get(gw.bNode(dfs)) <<

   152 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   153 	   ": is not newly reached.");

   154       } else {

   155 	cout << "invalid" << /*endl*/", " <<

   156 	  node_name.get(dfs.aNode()) <<

   157 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   159 	  "invalid.";

   160       }

   161       cout << endl;

   162     }

   163   }

   166   {

   167     typedef RevGraphWrapper<const TrivGraphWrapper<const Graph> > GW;

   168     GW gw(G);

   170     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

   172     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;

   173     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

   174       cout << node_name.get(n) << ": ";

   175       cout << "out edges: ";

   176       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   177 	cout << edge_name.get(e) << " ";

   178       cout << "in edges: ";

   179       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   180 	cout << edge_name.get(e) << " ";

   181       cout << endl;

   182     }

   184     cout << "bfs from t ..." << endl;

   185     BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);

   186     bfs.pushAndSetReached(t);

   187     while (!bfs.finished()) {

   188       //cout << "edge: ";

   189       if (gw.valid(bfs)) {

   190 	cout << edge_name.get(bfs) << /*endl*/", " <<

   191 	  node_name.get(gw.aNode(bfs)) <<

   192 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   193 	  node_name.get(gw.bNode(bfs)) <<

   194 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   195 	   ": is not newly reached.");

   196       } else {

   197 	cout << "invalid" << /*endl*/", " <<

   198 	  node_name.get(bfs.aNode()) <<

   199 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   201 	  "invalid.";

   202       }

   203       cout << endl;

   204       ++bfs;

   205     }

   207     cout << "    /-->    ------------->            "<< endl;

   208     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   209     cout << "  / |          |    /  /->     \\     "<< endl;

   210     cout << " /  |          |   /  |    ^    \\  "<< endl;

   211     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   212     cout << " \\  |          | /    |    |     /->  "<< endl;

   213     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   214     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   215     cout << "    \\-->    ------------->         "<< endl;

   217     cout << "dfs from t ..." << endl;

   218     DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);

   219     dfs.pushAndSetReached(t);

   220     while (!dfs.finished()) {

   221       ++dfs;

   222       //cout << "edge: ";

   223       if (gw.valid(dfs)) {

   224 	cout << edge_name.get(dfs) << /*endl*/", " <<

   225 	  node_name.get(gw.aNode(dfs)) <<

   226 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   227 	  node_name.get(gw.bNode(dfs)) <<

   228 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   229 	   ": is not newly reached.");

   230       } else {

   231 	cout << "invalid" << /*endl*/", " <<

   232 	  node_name.get(dfs.aNode()) <<

   233 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   235 	  "invalid.";

   236       }

   237       cout << endl;

   238     }

   239   }

   241   {

   242     //typedef UndirGraphWrapper<const Graph> GW;

   243     typedef UndirGraphWrapper<const TrivGraphWrapper<const Graph> > GW;

   244     GW gw(G);

   246     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);

   248     cout << "bfs and dfs iterator demo on the undirected graph" << endl;

   249     for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) {

   250       cout << node_name.get(n) << ": ";

   251       cout << "out edges: ";

   252       for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   253 	cout << edge_name.get(e) << " ";

   254       cout << "in edges: ";

   255       for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e))

   256 	cout << edge_name.get(e) << " ";

   257       cout << endl;

   258     }

   259 //     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {

   260 //       cout << edge_name.get(e) << " ";

   261 //     }

   262 //     cout << endl;

   264     cout << "bfs from t ..." << endl;

   265     BfsIterator5< GW, GW::NodeMap<bool> > bfs(gw);

   266     bfs.pushAndSetReached(t);

   267     while (!bfs.finished()) {

   268       //cout << "edge: ";

   269       if (gw.valid(GW::OutEdgeIt(bfs))) {

   270 	cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<

   271 	  node_name.get(gw.aNode(bfs)) <<

   272 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   273 	  node_name.get(gw.bNode(bfs)) <<

   274 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   275 	   ": is not newly reached.");

   276       } else {

   277 	cout << "invalid" << /*endl*/", " <<

   278 	  node_name.get(bfs.aNode()) <<

   279 	  (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   281 	  "invalid.";

   282       }

   283       cout << endl;

   284       ++bfs;

   285     }

   287     cout << "    /-->    ------------->            "<< endl;

   288     cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;

   289     cout << "  / |          |    /  /->     \\     "<< endl;

   290     cout << " /  |          |   /  |    ^    \\  "<< endl;

   291     cout << "s   |          |  /   |    |     \\->  t "<< endl;

   292     cout << " \\  |          | /    |    |     /->  "<< endl;

   293     cout << "  \\ |       --/ /     |    |    /     "<< endl;

   294     cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;

   295     cout << "    \\-->    ------------->         "<< endl;

   297     cout << "dfs from t ..." << endl;

   298     DfsIterator5< GW, GW::NodeMap<bool> > dfs(gw);

   299     dfs.pushAndSetReached(t);

   300     while (!dfs.finished()) {

   301       ++dfs;

   302       //cout << "edge: ";

   303       if (gw.valid(GW::OutEdgeIt(dfs))) {

   304 	cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<

   305 	  node_name.get(gw.aNode(dfs)) <<

   306 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   307 	  node_name.get(gw.bNode(dfs)) <<

   308 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   309 	   ": is not newly reached.");

   310       } else {

   311 	cout << "invalid" << /*endl*/", " <<

   312 	  node_name.get(dfs.aNode()) <<

   313 	  (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<

   315 	  "invalid.";

   316       }

   317       cout << endl;

   318     }

   319   }

   321   return 0;

   322 }

author	athos
	Thu, 03 Mar 2005 17:18:27 +0000
changeset 1182	a1abe9452199
parent 921	818510fa3d99
permissions	-rw-r--r--