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 <hugo/smart_graph.h>

     8 #include <bfs_dfs.h>

     9 #include <hugo/graph_wrapper.h>

    11 using namespace hugo;

    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 operator[](typename Graph::Edge e) const {

    24     return

    25       (node_name_map[graph.tail(e)]+"->"+node_name_map[graph.head(e)]);

    26   }

    27 };

    29 int main (int, char*[])

    30 {

    31   typedef SmartGraph Graph;

    32   //typedef SageGraph 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     EdgeNameMap< Graph, Graph::NodeMap<string> > edge_name(G, node_name);

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

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

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

    96       cout << "out edges: ";

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

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

    99       cout << "in edges: ";

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

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

   102       cout << endl;

   103     }

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

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

   107     bfs.pushAndSetReached(s);

   108     while (!bfs.finished()) {

   109       //cout << "edge: ";

   110       if (Graph::Edge(Graph::OutEdgeIt(bfs))!=INVALID) {

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

   112 	  node_name[G.tail(bfs)] <<

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

   114 	  node_name[G.head(bfs)] <<

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

   116 	   ": is not newly reached.");

   117       } else {

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

   119 	  node_name[bfs.aNode()] <<

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

   122 	  "invalid.";

   123       }

   124       cout << endl;

   125       ++bfs;

   126     }

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

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

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

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

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

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

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

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

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

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

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

   140     dfs.pushAndSetReached(s);

   141     while (!dfs.finished()) {

   142       ++dfs;

   143       //cout << "edge: ";

   144       if (Graph::Edge(Graph::OutEdgeIt(dfs))!=INVALID) {

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

   146 	  node_name[G.tail(dfs)] <<

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

   148 	  node_name[G.head(dfs)] <<

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

   150 	   ": is not newly reached.");

   151       } else {

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

   153 	  node_name[dfs.aNode()] <<

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

   156 	  "invalid.";

   157       }

   158       cout << endl;

   159     }

   160   }

   163   {

   164     typedef RevGraphWrapper<const Graph> GW;

   165     GW gw(G);

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

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

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

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

   172       cout << "out edges: ";

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

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

   175       cout << "in edges: ";

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

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

   178       cout << endl;

   179     }

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

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

   183     bfs.pushAndSetReached(t);

   184     while (!bfs.finished()) {

   185       //cout << "edge: ";

   186       if (GW::Edge(GW::OutEdgeIt(bfs))!=INVALID) {

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

   188 	  node_name[gw.tail(bfs)] <<

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

   190 	  node_name[gw.head(bfs)] <<

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

   192 	   ": is not newly reached.");

   193       } else {

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

   195 	  node_name[bfs.aNode()] <<

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

   198 	  "invalid.";

   199       }

   200       cout << endl;

   201       ++bfs;

   202     }

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

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

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

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

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

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

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

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

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

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

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

   216     dfs.pushAndSetReached(t);

   217     while (!dfs.finished()) {

   218       ++dfs;

   219       //cout << "edge: ";

   220       if (GW::OutEdgeIt(dfs)!=INVALID) {

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

   222 	  node_name[gw.tail(dfs)] <<

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

   224 	  node_name[gw.head(dfs)] <<

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

   226 	   ": is not newly reached.");

   227       } else {

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

   229 	  node_name[dfs.aNode()] <<

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

   232 	  "invalid.";

   233       }

   234       cout << endl;

   235     }

   236   }

   238 //   {

   239 //     typedef UndirGraphWrapper<const Graph> GW;

   240 //     GW gw(G);

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

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

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

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

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

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

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

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

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

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

   253 //       cout << endl;

   254 //     }

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

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

   257 // //     }

   258 // //     cout << endl;

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

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

   262 //     bfs.pushAndSetReached(t);

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

   264 //       //cout << "edge: ";

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

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

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

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

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

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

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

   272 //       } else {

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

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

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

   277 // 	  "invalid.";

   278 //       }

   279 //       cout << endl;

   280 //       ++bfs;

   281 //     }

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

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

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

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

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

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

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

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

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

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

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

   295 //     dfs.pushAndSetReached(t);

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

   297 //       ++dfs;

   298 //       //cout << "edge: ";

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

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

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

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

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

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

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

   306 //       } else {

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

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

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

   311 // 	  "invalid.";

   312 //       }

   313 //       cout << endl;

   314 //     }

   315 //   }

   319   {

   320     typedef BidirGraphWrapper<const Graph> GW;

   321     GW gw(G);

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

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

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

   327 //       cout << node_name[gw.tail(e)] << "->" << node_name[gw.head(e)] << " ";

   328 //     }

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

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

   331       cout << "out edges: ";

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

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

   334       cout << "in edges: ";

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

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

   337       cout << endl;

   338     }

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

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

   341 //     }

   342 //     cout << endl;

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

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

   346     bfs.pushAndSetReached(t);

   347     while (!bfs.finished()) {

   348       //cout << "edge: ";

   349       if (GW::OutEdgeIt(bfs)!=INVALID) {

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

   351 	  node_name[gw.tail(bfs)] <<

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

   353 	  node_name[gw.head(bfs)] <<

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

   355 	   ": is not newly reached.");

   356       } else {

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

   358 	  node_name[bfs.aNode()] <<

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

   361 	  "invalid.";

   362       }

   363       cout << endl;

   364       ++bfs;

   365     }

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

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

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

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

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

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

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

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

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

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

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

   379     dfs.pushAndSetReached(t);

   380     while (!dfs.finished()) {

   381       ++dfs;

   382       //cout << "edge: ";

   383       if (GW::OutEdgeIt(dfs)!=INVALID) {

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

   385 	  node_name[gw.tail(dfs)] <<

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

   387 	  node_name[gw.head(dfs)] <<

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

   389 	   ": is not newly reached.");

   390       } else {

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

   392 	  node_name[dfs.aNode()] <<

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

   395 	  "invalid.";

   396       }

   397       cout << endl;

   398     }

   399   }

   401   return 0;

   402 }

author	hegyi
	Tue, 31 Aug 2004 13:40:07 +0000
changeset 776	f2994a2b10b2
parent 642	e812963087f0
child 777	a82713ed19f3
permissions	-rw-r--r--