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

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

     2 #include <iostream>

     3 #include <vector>

     4 #include <string>

     6 #include <sage_graph.h>

     7 #include <lemon/smart_graph.h>

     8 #include <bfs_dfs.h>

     9 #include <lemon/graph_wrapper.h>

    11 using namespace lemon;

    13 using std::cout;

    14 using std::endl;

    15 using std::string;

    17 template <typename Graph, typename NodeNameMap>

    18 class EdgeNameMap {

    19   Graph& graph;

    20   NodeNameMap& node_name_map;

    21 public:

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

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

    24   string operator[](typename Graph::Edge e) const {

    25     return

    26       (node_name_map[graph.source(e)]+"->"+node_name_map[graph.target(e)]);

    27   }

    28 };

    30 int main (int, char*[])

    31 {

    32   typedef SmartGraph Graph;

    33   //typedef SageGraph Graph;

    35   typedef Graph::Node Node;

    36   typedef Graph::Edge Edge;

    38   Graph G;

    40   Node s=G.addNode();

    41   Node v1=G.addNode();

    42   Node v2=G.addNode();

    43   Node v3=G.addNode();

    44   Node v4=G.addNode();

    45   Node t=G.addNode();

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

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

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

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

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

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

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

    55   G.addEdge(s, v1);

    56   G.addEdge(s, v2);

    57   G.addEdge(v1, v2);

    58   G.addEdge(v2, v1);

    59   G.addEdge(v1, v3);

    60   G.addEdge(v3, v2);

    61   G.addEdge(v2, v4);

    62   G.addEdge(v4, v3);

    63   G.addEdge(v3, t);

    64   G.addEdge(v4, t);

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

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

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

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

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

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

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

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

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

    76   {

    77     EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);

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

    80     for(Graph::NodeIt n(G); n!=INVALID; ++n) {

    81       cout << node_name[n] << ": ";

    82       cout << "out edges: ";

    83       for(Graph::OutEdgeIt e(G, n); e!=INVALID; ++e)

    84 	cout << edge_name[e] << " ";

    85       cout << "in edges: ";

    86       for(Graph::InEdgeIt e(G, n); e!=INVALID; ++e)

    87 	cout << edge_name[e] << " ";

    88       cout << endl;

    89     }

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

    92     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);

    93     bfs.pushAndSetReached(s);

    94     while (!bfs.finished()) {

    95       //cout << "edge: ";

    96       if (Graph::Edge(bfs)!=INVALID) {

    97 	cout << edge_name[bfs] << /*endl*/", " <<

    98 	  node_name[G.source(bfs)] <<

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

   100 	  node_name[G.target(bfs)] <<

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

   102 	   ": is not newly reached.");

   103       } else {

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

   105 	  node_name[bfs.source()] <<

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

   108 	  "invalid.";

   109       }

   110       cout << endl;

   111       ++bfs;

   112     }

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

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

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

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

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

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

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

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

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

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

   125     DfsIterator< Graph, Graph::NodeMap<bool> > dfs(G);

   126     dfs.pushAndSetReached(s);

   127     while (!dfs.finished()) {

   128       ++dfs;

   129       //cout << "edge: ";

   130       if (Graph::Edge(dfs)!=INVALID) {

   131 	cout << edge_name[dfs] << /*endl*/", " <<

   132 	  node_name[G.source(dfs)] <<

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

   134 	  node_name[G.target(dfs)] <<

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

   136 	   ": is not newly reached.");

   137       } else {

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

   139 	  node_name[dfs.source()] <<

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

   142 	  "invalid.";

   143       }

   144       cout << endl;

   145     }

   146   }

   149   {

   150     typedef RevGraphWrapper<const Graph> GW;

   151     GW gw(G);

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

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

   156     for(GW::NodeIt n(gw); n!=INVALID; ++n) {

   157       cout << node_name[GW::Node(n)] << ": ";

   158       cout << "out edges: ";

   159       for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)

   160 	cout << edge_name[e] << " ";

   161       cout << "in edges: ";

   162       for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)

   163 	cout << edge_name[e] << " ";

   164       cout << endl;

   165     }

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

   168     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   169     bfs.pushAndSetReached(t);

   170     while (!bfs.finished()) {

   171       //cout << "edge: ";

   172       if (GW::Edge(bfs)!=INVALID) {

   173 	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<

   174 	  node_name[gw.source(bfs)] <<

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

   176 	  node_name[gw.target(bfs)] <<

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

   178 	   ": is not newly reached.");

   179       } else {

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

   181 	  node_name[bfs.source()] <<

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

   184 	  "invalid.";

   185       }

   186       cout << endl;

   187       ++bfs;

   188     }

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

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

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

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

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

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

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

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

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

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

   201     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   202     dfs.pushAndSetReached(t);

   203     while (!dfs.finished()) {

   204       ++dfs;

   205       //cout << "edge: ";

   206       if (GW::Edge(dfs)!=INVALID) {

   207 	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<

   208 	  node_name[gw.source(dfs)] <<

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

   210 	  node_name[gw.target(dfs)] <<

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

   212 	   ": is not newly reached.");

   213       } else {

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

   215 	  node_name[dfs.source()] <<

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

   218 	  "invalid.";

   219       }

   220       cout << endl;

   221     }

   222   }

   224 //   {

   225 //     typedef UndirGraphWrapper<const Graph> GW;

   226 //     GW gw(G);

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

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

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

   232 //       cout << node_name[GW::Node(n)] << ": ";

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

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

   235 // 	cout << edge_name[e] << " ";

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

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

   238 // 	cout << edge_name[e] << " ";

   239 //       cout << endl;

   240 //     }

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

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

   243 // //     }

   244 // //     cout << endl;

   246 //     cout << "bfs from t ..." << endl;

   247 //     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   248 //     bfs.pushAndSetReached(t);

   249 //     while (!bfs.finished()) {

   250 //       //cout << "edge: ";

   251 //       if (gw.valid(GW::OutEdgeIt(bfs))) {

   252 // 	cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " <<

   253 // 	  node_name[gw.aNode(bfs)] <<

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

   255 // 	  node_name[gw.bNode(bfs)] <<

   256 // 	  (bfs.isBNodeNewlyReached() ? ": is newly reached." :

   257 // 	   ": is not newly reached.");

   258 //       } else {

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

   260 // 	  node_name[bfs.aNode()] <<

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

   263 // 	  "invalid.";

   264 //       }

   265 //       cout << endl;

   266 //       ++bfs;

   267 //     }

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

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

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

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

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

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

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

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

   277 //     cout << "    \\-->    ------------->         "<< endl;

   279 //     cout << "dfs from t ..." << endl;

   280 //     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   281 //     dfs.pushAndSetReached(t);

   282 //     while (!dfs.finished()) {

   283 //       ++dfs;

   284 //       //cout << "edge: ";

   285 //       if (gw.valid(GW::OutEdgeIt(dfs))) {

   286 // 	cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " <<

   287 // 	  node_name[gw.aNode(dfs)] <<

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

   289 // 	  node_name[gw.bNode(dfs)] <<

   290 // 	  (dfs.isBNodeNewlyReached() ? ": is newly reached." :

   291 // 	   ": is not newly reached.");

   292 //       } else {

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

   294 // 	  node_name[dfs.aNode()] <<

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

   297 // 	  "invalid.";

   298 //       }

   299 //       cout << endl;

   300 //     }

   301 //   }

   305   {

   306     typedef BidirGraphWrapper<const Graph> GW;

   307     GW gw(G);

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

   311     cout << "bfs and dfs iterator demo on the bidirected graph" << endl;

   312 //     for(GW::EdgeIt e(gw); e!=INVALID; ++e) {

   313 //       cout << node_name[gw.source(e)] << "->" << node_name[gw.target(e)] << " ";

   314 //     }

   315     for(GW::NodeIt n(gw); n!=INVALID; ++n) {

   316       cout << node_name[GW::Node(n)] << ": ";

   317       cout << "out edges: ";

   318       for(GW::OutEdgeIt e(gw, n); e!=INVALID; ++e)

   319 	cout << edge_name[e] << " ";

   320       cout << "in edges: ";

   321       for(GW::InEdgeIt e(gw, n); e!=INVALID; ++e)

   322 	cout << edge_name[e] << " ";

   323       cout << endl;

   324     }

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

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

   327 //     }

   328 //     cout << endl;

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

   331     BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);

   332     bfs.pushAndSetReached(t);

   333     while (!bfs.finished()) {

   334       //cout << "edge: ";

   335       if (GW::Edge(bfs)!=INVALID) {

   336 	cout << edge_name[GW::Edge(bfs)] << /*endl*/", " <<

   337 	  node_name[gw.source(bfs)] <<

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

   339 	  node_name[gw.target(bfs)] <<

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

   341 	   ": is not newly reached.");

   342       } else {

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

   344 	  node_name[bfs.source()] <<

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

   347 	  "invalid.";

   348       }

   349       cout << endl;

   350       ++bfs;

   351     }

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

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

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

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

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

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

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

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

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

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

   364     DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);

   365     dfs.pushAndSetReached(t);

   366     while (!dfs.finished()) {

   367       ++dfs;

   368       //cout << "edge: ";

   369       if (GW::Edge(dfs)!=INVALID) {

   370 	cout << edge_name[GW::Edge(dfs)] << /*endl*/", " <<

   371 	  node_name[gw.source(dfs)] <<

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

   373 	  node_name[gw.target(dfs)] <<

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

   375 	   ": is not newly reached.");

   376       } else {

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

   378 	  node_name[dfs.source()] <<

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

   381 	  "invalid.";

   382       }

   383       cout << endl;

   384     }

   385   }

   387   return 0;

   388 }

author	alpar
	Mon, 21 Mar 2005 11:40:08 +0000
changeset 1233	f3d856bf1ebf
parent 921	818510fa3d99
permissions	-rw-r--r--