Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/iterator_bfs_demo.cc
changeset 175 ebccffe4d47b
parent 158 4f54d89fa9d2
child 234 348f8fd374ee
equal deleted inserted replaced
3:d5b3d49532e2 4:f1ee6f404fb8 
       
     1 // -*- c++ -*-
 
     1 #include <iostream>
 
     2 #include <iostream>
 
     2 #include <vector>
 
     3 #include <vector>
 
     3 #include <string>
 
     4 #include <string>
 
     4 
     5 
     5 #include <list_graph.hh>
 
     6 #include <list_graph.h>
 
     6 #include <bfs_iterator.hh>
 
     7 #include <smart_graph.h>
 
       
     8 #include <bfs_iterator.h>
 
     7 #include <graph_wrapper.h>
 
     9 #include <graph_wrapper.h>
 
     8 
    10 
     9 using namespace hugo;
 
    11 using namespace hugo;
 
    10 using std::cout; 
    12 using std::cout; 
    11 using std::endl;
 
    13 using std::endl;
 
    16   Graph& graph;
 
    18   Graph& graph;
 
    17   NodeNameMap& node_name_map;
 
    19   NodeNameMap& node_name_map;
 
    18 public:
 
    20 public:
 
    19   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 
    21   EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) : 
    20     graph(_graph), node_name_map(_node_name_map) { }
 
    22     graph(_graph), node_name_map(_node_name_map) { }
 
    21   string get(typename Graph::EdgeIt e) const { 
    23   string get(typename Graph::Edge e) const { 
    22     return 
    24     return 
    23       (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
 
    25       (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
 
    24   }
 
    26   }
 
    25 };
 
    27 };
 
    26 
    28 
    27 int main (int, char*[])
 
    29 int main (int, char*[])
 
    28 {
 
    30 {
 
    29   typedef ListGraph::NodeIt NodeIt;
 
    31   //typedef SmartGraph Graph;
 
    30   typedef ListGraph::EdgeIt EdgeIt;
 
    32   typedef ListGraph Graph;
 
    31   //typedef ListGraph::EachNodeIt EachNodeIt;
 
    33 
    32   //typedef ListGraph::EachEdgeIt EachEdgeIt;
 
    34   typedef Graph::Node Node;
 
    33   //typedef ListGraph::OutEdgeIt OutEdgeIt;
 
    35   typedef Graph::Edge Edge;
 
    34   //typedef ListGraph::InEdgeIt InEdgeIt;
 
    36   //typedef Graph::NodeIt NodeIt;
 
    35   //typedef ListGraph::SymEdgeIt SymEdgeIt;
 
    37   //typedef Graph::EdgeIt EdgeIt;
 
       
    38   //typedef Graph::OutEdgeIt OutEdgeIt;
 
       
    39   //typedef Graph::InEdgeIt InEdgeIt;
 
       
    40   //typedef Graph::SymEdgeIt SymEdgeIt;
 
    36  
    41  
    37   ListGraph G;
 
    42   Graph G;
 
    38 
    43 
    39   NodeIt s=G.addNode();
 
    44   Node s=G.addNode();
 
    40   NodeIt v1=G.addNode();
 
    45   Node v1=G.addNode();
 
    41   NodeIt v2=G.addNode();
 
    46   Node v2=G.addNode();
 
    42   NodeIt v3=G.addNode();
 
    47   Node v3=G.addNode();
 
    43   NodeIt v4=G.addNode();
 
    48   Node v4=G.addNode();
 
    44   NodeIt t=G.addNode();
 
    49   Node t=G.addNode();
 
    45   
    50   
    46   ListGraph::NodeMap<string> node_name(G);
 
    51   Graph::NodeMap<string> node_name(G);
 
    47   node_name.set(s, "s");
 
    52   node_name.set(s, "s");
 
    48   node_name.set(v1, "v1");
 
    53   node_name.set(v1, "v1");
 
    49   node_name.set(v2, "v2");
 
    54   node_name.set(v2, "v2");
 
    50   node_name.set(v3, "v3");
 
    55   node_name.set(v3, "v3");
 
    51   node_name.set(v4, "v4");
 
    56   node_name.set(v4, "v4");
 
    70   cout << " \\  |          | /    |    |     /->  "<< endl;
 
    75   cout << " \\  |          | /    |    |     /->  "<< endl;
 
    71   cout << "  \\ |       --/ /     |    |    /     "<< endl;
 
    76   cout << "  \\ |       --/ /     |    |    /     "<< endl;
 
    72   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
 
    77   cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
 
    73   cout << "    \\-->    ------------->         "<< endl;
 
    78   cout << "    \\-->    ------------->         "<< endl;
 
    74   
    79   
    75 /*
 
    80 //   typedef TrivGraphWrapper<const Graph> CGW;
 
    76   {
 
       
    77   cout << "iterator bfs demo 4 ..." << endl;
 
       
    78   BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
 
       
    79   bfs.pushAndSetReached(s);
 
       
    80   while (!bfs.finished()) {
 
       
    81   if (OutEdgeIt(bfs).valid()) {
 
       
    82   cout << "OutEdgeIt: " << bfs; 
       
    83   cout << " aNode: " << G.aNode(bfs); 
       
    84   cout << " bNode: " << G.bNode(bfs) << " ";
 
       
    85   } else { 
       
    86   cout << "OutEdgeIt: " << "invalid"; 
       
    87   cout << " aNode: " << bfs.aNode(); 
       
    88   cout << " bNode: " << "invalid" << " ";
 
       
    89   }
 
       
    90   if (bfs.isBNodeNewlyReached()) { 
       
    91   cout << "bNodeIsNewlyReached ";
 
       
    92   } else { 
       
    93   cout << "bNodeIsNotNewlyReached ";
 
       
    94   } 
       
    95   if (bfs.isANodeExamined()) { 
       
    96   cout << "aNodeIsExamined ";
 
       
    97   } else { 
       
    98   cout << "aNodeIsNotExamined ";
 
       
    99   } 
       
   100   cout << endl;
 
       
   101   ++bfs;
 
       
   102   }
 
       
   103   }
 
       
   104 
       
   105   {
 
       
   106   cout << "iterator dfs demo 4 ..." << endl;
 
       
   107   DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
 
       
   108   dfs.pushAndSetReached(s);
 
       
   109   while (!dfs.finished()) {
 
       
   110   ++dfs;
 
       
   111   if (OutEdgeIt(dfs).valid()) {
 
       
   112   cout << "OutEdgeIt: " << dfs; 
       
   113   cout << " aNode: " << G.aNode(dfs); 
       
   114   cout << " bNode: " << G.bNode(dfs) << " ";
 
       
   115   } else { 
       
   116   cout << "OutEdgeIt: " << "invalid"; 
       
   117   cout << " aNode: " << dfs.aNode(); 
       
   118   cout << " bNode: " << "invalid" << " ";
 
       
   119   }
 
       
   120   if (dfs.isBNodeNewlyReached()) { 
       
   121   cout << "bNodeIsNewlyReached ";
 
       
   122   } else { 
       
   123   cout << "bNodeIsNotNewlyReached ";
 
       
   124   } 
       
   125   if (dfs.isANodeExamined()) { 
       
   126   cout << "aNodeIsExamined ";
 
       
   127   } else { 
       
   128   cout << "aNodeIsNotExamined ";
 
       
   129   } 
       
   130   cout << endl;
 
       
   131   //++dfs;
 
       
   132   }
 
       
   133   }
 
       
   134 */
 
       
   135 
       
   136 //   typedef TrivGraphWrapper<const ListGraph> CGW;
 
       
   137 //   CGW wG(G);
 
    81 //   CGW wG(G);
 
   138 
    82 
   139 //   cout << "bfs and dfs demo on the directed graph" << endl;
 
    83 //   cout << "bfs and dfs demo on the directed graph" << endl;
 
   140 //   for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) { 
    84 //   for(CGW::NodeIt n=wG.first<CGW::NodeIt>(); n.valid(); ++n) { 
   141 //     cout << n << ": ";
 
    85 //     cout << n << ": ";
 
   142 //     cout << "out edges: ";
 
    86 //     cout << "out edges: ";
 
   143 //     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
    87 //     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e) 
   144 //       cout << e << " ";
 
    88 //       cout << e << " ";
 
   145 //     cout << "in edges: ";
 
    89 //     cout << "in edges: ";
 
   147 //       cout << e << " ";
 
    91 //       cout << e << " ";
 
   148 //     cout << endl;
 
    92 //     cout << endl;
 
   149 //   }
 
    93 //   }
 
   150 
    94 
   151   {
 
    95   {
 
   152     typedef TrivGraphWrapper<const ListGraph> GW;
 
    96     typedef TrivGraphWrapper<const Graph> GW;
 
   153     GW wG(G);
 
    97     GW wG(G);
 
   154 
    98 
   155     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
    99     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
 
   156     
   100     
   157     cout << "bfs and dfs iterator demo on the directed graph" << endl;
 
   101     cout << "bfs and dfs iterator demo on the directed graph" << endl;
 
   158     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
   102     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
   159       cout << node_name.get(n) << ": ";
 
   103       cout << node_name.get(n) << ": ";
 
   160       cout << "out edges: ";
 
   104       cout << "out edges: ";
 
   161       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   105       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   162 	cout << edge_name.get(e) << " ";
 
   106 	cout << edge_name.get(e) << " ";
 
   163       cout << "in edges: ";
 
   107       cout << "in edges: ";
 
   223     }
 
   167     }
 
   224   }
 
   168   }
 
   225 
   169 
   226 
   170 
   227   {
 
   171   {
 
   228     typedef RevGraphWrapper<const ListGraph> GW;
 
   172     typedef RevGraphWrapper<const Graph> GW;
 
   229     GW wG(G);
 
   173     GW wG(G);
 
   230     
   174     
   231     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
   175     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
 
   232     
   176     
   233     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
 
   177     cout << "bfs and dfs iterator demo on the reversed directed graph" << endl;
 
   234     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
   178     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
   235       cout << node_name.get(n) << ": ";
 
   179       cout << node_name.get(n) << ": ";
 
   236       cout << "out edges: ";
 
   180       cout << "out edges: ";
 
   237       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   181       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   238 	cout << edge_name.get(e) << " ";
 
   182 	cout << edge_name.get(e) << " ";
 
   239       cout << "in edges: ";
 
   183       cout << "in edges: ";
 
   298       cout << endl;
 
   242       cout << endl;
 
   299     }
 
   243     }
 
   300   }
 
   244   }
 
   301 
   245 
   302   {
 
   246   {
 
   303     typedef UndirGraphWrapper<const ListGraph> GW;
 
   247     typedef UndirGraphWrapper<const Graph> GW;
 
   304     GW wG(G);
 
   248     GW wG(G);
 
   305     
   249     
   306     EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
 
   250     EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(wG, node_name);
 
   307     
   251     
   308     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
 
   252     cout << "bfs and dfs iterator demo on the undirected graph" << endl;
 
   309     for(GW::EachNodeIt n=wG.first<GW::EachNodeIt>(); wG.valid(n); wG.next(n)) { 
   253     for(GW::NodeIt n=wG.first<GW::NodeIt>(); wG.valid(n); wG.next(n)) { 
   310       cout << node_name.get(n) << ": ";
 
   254       cout << node_name.get(n) << ": ";
 
   311       cout << "out edges: ";
 
   255       cout << "out edges: ";
 
   312       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   256       for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e)) 
   313 	cout << edge_name.get(e) << " ";
 
   257 	cout << edge_name.get(e) << " ";
 
   314       cout << "in edges: ";
 
   258       cout << "in edges: ";
lemon-0.x