COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 158:4f54d89fa9d2 in lemon-0.x for src/work/iterator_bfs_demo.cc


Ignore:
Timestamp:
03/08/04 13:29:07 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@223
Message:

a lot of interesting and very useful wrapper graphs

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/iterator_bfs_demo.cc

    r107 r158  
    88
    99using namespace hugo;
     10using std::cout;
     11using std::endl;
     12using std::string;
     13
     14template <typename Graph, typename NodeNameMap>
     15class EdgeNameMap {
     16  Graph& graph;
     17  NodeNameMap& node_name_map;
     18public:
     19  EdgeNameMap(Graph& _graph, NodeNameMap& _node_name_map) :
     20    graph(_graph), node_name_map(_node_name_map) { }
     21  string get(typename Graph::EdgeIt e) const {
     22    return
     23      (node_name_map.get(graph.tail(e))+"->"+node_name_map.get(graph.head(e)));
     24  }
     25};
    1026
    1127int main (int, char*[])
    … …  
    1329  typedef ListGraph::NodeIt NodeIt;
    1430  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;
     31  //typedef ListGraph::EachNodeIt EachNodeIt;
     32  //typedef ListGraph::EachEdgeIt EachEdgeIt;
     33  //typedef ListGraph::OutEdgeIt OutEdgeIt;
     34  //typedef ListGraph::InEdgeIt InEdgeIt;
     35  //typedef ListGraph::SymEdgeIt SymEdgeIt;
    2036 
    2137  ListGraph G;
    … …  
    2844  NodeIt t=G.addNode();
    2945 
     46  ListGraph::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");
     53
    3054  G.addEdge(s, v1);
    3155  G.addEdge(s, v2);
    … …  
    3963  G.addEdge(v4, t);
    4064
    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   }
     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;
    5274 
    53   {
    54     std::cout << "iterator bfs demo 4 ..." << std::endl;
    55     BfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
     75/*
     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);
     138
     139//   cout << "bfs and dfs demo on the directed graph" << endl;
     140//   for(CGW::EachNodeIt n=wG.first<CGW::EachNodeIt>(); n.valid(); ++n) {
     141//     cout << n << ": ";
     142//     cout << "out edges: ";
     143//     for(CGW::OutEdgeIt e=wG.first<CGW::OutEdgeIt>(n); e.valid(); ++e)
     144//       cout << e << " ";
     145//     cout << "in edges: ";
     146//     for(CGW::InEdgeIt e=wG.first<CGW::InEdgeIt>(n); e.valid(); ++e)
     147//       cout << e << " ";
     148//     cout << endl;
     149//   }
     150
     151  {
     152    typedef TrivGraphWrapper<const ListGraph> GW;
     153    GW wG(G);
     154
     155    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     156   
     157    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)) {
     159      cout << node_name.get(n) << ": ";
     160      cout << "out edges: ";
     161      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
     162        cout << edge_name.get(e) << " ";
     163      cout << "in edges: ";
     164      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
     165        cout << edge_name.get(e) << " ";
     166      cout << endl;
     167    }
     168
     169    cout << "bfs from s ..." << endl;
     170    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
    56171    bfs.pushAndSetReached(s);
    57172    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;
     173      //cout << "edge: ";
     174      if (wG.valid(bfs)) {
     175        cout << edge_name.get(bfs) << /*endl*/", " <<
     176          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
     177          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     178          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
     179          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     180           ": is not newly reached.");
     181      } else {
     182        cout << "invalid" << /*endl*/", " <<
     183          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
     184          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     185          /*" bNode: " <<*/
     186          "invalid.";
     187      }
     188      cout << endl;
    78189      ++bfs;
    79190    }
    80   }
    81 
    82   {
    83     std::cout << "iterator dfs demo 4 ..." << std::endl;
    84     DfsIterator4< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > dfs(G);
     191
     192    cout << "    /-->    ------------->            "<< endl;
     193    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     194    cout << "  / |          |    /  /->     \\     "<< endl;
     195    cout << " /  |          |   /  |    ^    \\  "<< endl;
     196    cout << "s   |          |  /   |    |     \\->  t "<< endl;
     197    cout << " \\  |          | /    |    |     /->  "<< endl;
     198    cout << "  \\ |       --/ /     |    |    /     "<< endl;
     199    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     200    cout << "    \\-->    ------------->         "<< endl;
     201
     202    cout << "dfs from s ..." << endl;
     203    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
    85204    dfs.pushAndSetReached(s);
    86205    while (!dfs.finished()) {
    87206      ++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   }
    111 
    112 
    113   typedef ConstTrivGraphWrapper<ListGraph> CTGW;
    114   CTGW wG(G);
    115 
    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   }
    127 
    128 
    129   {
    130     std::cout << "iterator bfs demo 5 ..." << std::endl;
    131     BfsIterator5< CTGW, CTGW::NodeMap<bool> > bfs(wG);
    132     bfs.pushAndSetReached(s);
     207      //cout << "edge: ";
     208      if (wG.valid(dfs)) {
     209        cout << edge_name.get(dfs) << /*endl*/", " <<
     210          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
     211          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     212          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
     213          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     214           ": is not newly reached.");
     215      } else {
     216        cout << "invalid" << /*endl*/", " <<
     217          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
     218          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     219          /*" bNode: " <<*/
     220          "invalid.";
     221      }
     222      cout << endl;
     223    }
     224  }
     225
     226
     227  {
     228    typedef RevGraphWrapper<const ListGraph> GW;
     229    GW wG(G);
     230   
     231    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     232   
     233    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)) {
     235      cout << node_name.get(n) << ": ";
     236      cout << "out edges: ";
     237      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
     238        cout << edge_name.get(e) << " ";
     239      cout << "in edges: ";
     240      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
     241        cout << edge_name.get(e) << " ";
     242      cout << endl;
     243    }
     244
     245    cout << "bfs from t ..." << endl;
     246    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
     247    bfs.pushAndSetReached(t);
    133248    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;
     249      //cout << "edge: ";
     250      if (wG.valid(bfs)) {
     251        cout << edge_name.get(bfs) << /*endl*/", " <<
     252          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
     253          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     254          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
     255          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     256           ": is not newly reached.");
     257      } else {
     258        cout << "invalid" << /*endl*/", " <<
     259          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
     260          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     261          /*" bNode: " <<*/
     262          "invalid.";
     263      }
     264      cout << endl;
    154265      ++bfs;
    155266    }
    156   }
    157 
     267
     268    cout << "    /-->    ------------->            "<< endl;
     269    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     270    cout << "  / |          |    /  /->     \\     "<< endl;
     271    cout << " /  |          |   /  |    ^    \\  "<< endl;
     272    cout << "s   |          |  /   |    |     \\->  t "<< endl;
     273    cout << " \\  |          | /    |    |     /->  "<< endl;
     274    cout << "  \\ |       --/ /     |    |    /     "<< endl;
     275    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     276    cout << "    \\-->    ------------->         "<< endl;
     277   
     278    cout << "dfs from t ..." << endl;
     279    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
     280    dfs.pushAndSetReached(t);
     281    while (!dfs.finished()) {
     282      ++dfs;
     283      //cout << "edge: ";
     284      if (wG.valid(dfs)) {
     285        cout << edge_name.get(dfs) << /*endl*/", " <<
     286          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
     287          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     288          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
     289          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     290           ": is not newly reached.");
     291      } else {
     292        cout << "invalid" << /*endl*/", " <<
     293          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
     294          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     295          /*" bNode: " <<*/
     296          "invalid.";
     297      }
     298      cout << endl;
     299    }
     300  }
     301
     302  {
     303    typedef UndirGraphWrapper<const ListGraph> GW;
     304    GW wG(G);
     305   
     306    EdgeNameMap< GW, ListGraph::NodeMap<string> > edge_name(wG, node_name);
     307   
     308    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)) {
     310      cout << node_name.get(n) << ": ";
     311      cout << "out edges: ";
     312      for(GW::OutEdgeIt e=wG.first<GW::OutEdgeIt>(n); wG.valid(e); wG.next(e))
     313        cout << edge_name.get(e) << " ";
     314      cout << "in edges: ";
     315      for(GW::InEdgeIt e=wG.first<GW::InEdgeIt>(n); wG.valid(e); wG.next(e))
     316        cout << edge_name.get(e) << " ";
     317      cout << endl;
     318    }
     319
     320    cout << "bfs from t ..." << endl;
     321    BfsIterator5< GW, GW::NodeMap<bool> > bfs(wG);
     322    bfs.pushAndSetReached(t);
     323    while (!bfs.finished()) {
     324      //cout << "edge: ";
     325      if (wG.valid(GW::OutEdgeIt(bfs))) {
     326        cout << edge_name.get(GW::OutEdgeIt(bfs)) << /*endl*/", " <<
     327          /*" aNode: " <<*/ node_name.get(wG.aNode(bfs)) <<
     328          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     329          /*" bNode: " <<*/ node_name.get(wG.bNode(bfs)) <<
     330          (bfs.isBNodeNewlyReached() ? ": is newly reached." :
     331           ": is not newly reached.");
     332      } else {
     333        cout << "invalid" << /*endl*/", " <<
     334          /*" aNode: " <<*/ node_name.get(bfs.aNode()) <<
     335          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     336          /*" bNode: " <<*/
     337          "invalid.";
     338      }
     339      cout << endl;
     340      ++bfs;
     341    }
     342
     343    cout << "    /-->    ------------->            "<< endl;
     344    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
     345    cout << "  / |          |    /  /->     \\     "<< endl;
     346    cout << " /  |          |   /  |    ^    \\  "<< endl;
     347    cout << "s   |          |  /   |    |     \\->  t "<< endl;
     348    cout << " \\  |          | /    |    |     /->  "<< endl;
     349    cout << "  \\ |       --/ /     |    |    /     "<< endl;
     350    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
     351    cout << "    \\-->    ------------->         "<< endl;
     352   
     353    cout << "dfs from t ..." << endl;
     354    DfsIterator5< GW, GW::NodeMap<bool> > dfs(wG);
     355    dfs.pushAndSetReached(t);
     356    while (!dfs.finished()) {
     357      ++dfs;
     358      //cout << "edge: ";
     359      if (wG.valid(GW::OutEdgeIt(dfs))) {
     360        cout << edge_name.get(GW::OutEdgeIt(dfs)) << /*endl*/", " <<
     361          /*" aNode: " <<*/ node_name.get(wG.aNode(dfs)) <<
     362          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     363          /*" bNode: " <<*/ node_name.get(wG.bNode(dfs)) <<
     364          (dfs.isBNodeNewlyReached() ? ": is newly reached." :
     365           ": is not newly reached.");
     366      } else {
     367        cout << "invalid" << /*endl*/", " <<
     368          /*" aNode: " <<*/ node_name.get(dfs.aNode()) <<
     369          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") <<
     370          /*" bNode: " <<*/
     371          "invalid.";
     372      }
     373      cout << endl;
     374    }
     375  }
    158376
    159377  return 0;
Note: See TracChangeset for help on using the changeset viewer.