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


Ignore:
Timestamp:
03/08/04 13:29:07 (21 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

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • src/work/bfs_iterator.hh

    r148 r158  
    624624
    625625
    626   template <typename GraphWrapper, typename OutEdgeIt,
     626  template <typename GraphWrapper, /*typename OutEdgeIt,*/
    627627            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
    628628  class BfsIterator5 {
    629629    typedef typename GraphWrapper::NodeIt NodeIt;
     630    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    630631    GraphWrapper G;
    631632    std::queue<NodeIt> bfs_queue;
    … …  
    641642      G(_G), reached(*(new ReachedMap(G /*, false*/))),
    642643      own_reached_map(true) { }
     644//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
     645//               ReachedMap& _reached) :
     646//       G(_G), reached(_reached),
     647//       own_reached_map(false) { }
     648//     BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
     649//       G(_G), reached(*(new ReachedMap(G /*, false*/))),
     650//       own_reached_map(true) { }
    643651    ~BfsIterator5() { if (own_reached_map) delete &reached; }
    644652    void pushAndSetReached(NodeIt s) {
    … …  
    661669      }
    662670    }
    663     BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
     671    BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
    664672    operator++() {
    665673      if (G.valid(actual_edge)/*.valid()*/) {
    … …  
    759767  };
    760768
    761   template <typename GraphWrapper, typename OutEdgeIt,
     769  template <typename GraphWrapper, /*typename OutEdgeIt,*/
    762770            typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
    763771  class DfsIterator5 {
    764772    typedef typename GraphWrapper::NodeIt NodeIt;
     773    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
    765774    GraphWrapper G;
    766775    std::stack<OutEdgeIt> dfs_stack;
    … …  
    783792      dfs_stack.push(G.template first<OutEdgeIt>(s));
    784793    }
    785     DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>&
     794    DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
    786795    operator++() {
    787796      actual_edge=dfs_stack.top();

  • 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;

  • src/work/marci/graph_wrapper.h

    r156 r158  
    6363    public:
    6464      NodeMap(const TrivGraphWrapper<Graph>& _G) :
    65         Graph::NodeMap<T>(*(_G.G)) { }
     65        Graph::NodeMap<T>(_G.getGraph()) { }
    6666      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    67         Graph::NodeMap<T>(*(_G.G), a) { }
     67        Graph::NodeMap<T>(_G.getGraph(), a) { }
    6868    };
    6969    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    7070    public:
    7171      EdgeMap(const TrivGraphWrapper<Graph>& _G) :
    72         Graph::EdgeMap<T>(*(_G.G)) { }
     72        Graph::EdgeMap<T>(_G.getGraph()) { }
    7373      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    74         Graph::EdgeMap<T>(*(_G.G), a) { }
     74        Graph::EdgeMap<T>(_G.getGraph(), a) { }
    7575    };
    7676   
    … …  
    141141    public:
    142142      NodeMap(const RevGraphWrapper<Graph>& _G) :
    143         Graph::NodeMap<T>(*(_G.G)) { }
     143        Graph::NodeMap<T>(_G.getGraph()) { }
    144144      NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
    145         Graph::NodeMap<T>(*(_G.G), a) { }
     145        Graph::NodeMap<T>(_G.getGraph(), a) { }
    146146    };
    147147    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    148148    public:
    149149      EdgeMap(const RevGraphWrapper<Graph>& _G) :
    150         Graph::EdgeMap<T>(*(_G.G)) { }
     150        Graph::EdgeMap<T>(_G.getGraph()) { }
    151151      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
    152         Graph::EdgeMap<T>(*(_G.G), a) { }
     152        Graph::EdgeMap<T>(_G.getGraph(), a) { }
    153153    };
    154154
    … …  
    159159    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
    160160  };
     161
     162
     163  template<typename Graph>
     164  class UndirGraphWrapper {
     165    Graph* graph;
     166 
     167  public:
     168    typedef Graph BaseGraph;
     169
     170    typedef typename Graph::NodeIt NodeIt;
     171    typedef typename Graph::EachNodeIt EachNodeIt;
     172
     173    //typedef typename Graph::EdgeIt EdgeIt;
     174    //typedef typename Graph::OutEdgeIt OutEdgeIt;
     175    //typedef typename Graph::InEdgeIt InEdgeIt;
     176    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     177    //typedef typename Graph::EachEdgeIt EachEdgeIt;
     178
     179    //private:
     180    typedef typename Graph::EdgeIt GraphEdgeIt;
     181    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     182    typedef typename Graph::InEdgeIt GraphInEdgeIt;
     183    //public:
     184
     185    class EdgeIt {
     186      friend class UndirGraphWrapper<Graph>;
     187      bool out_or_in; //true iff out
     188      GraphOutEdgeIt out;
     189      GraphInEdgeIt in;
     190    public:
     191      EdgeIt() : out_or_in(true), out(), in() { }
     192      operator GraphEdgeIt() const {
     193        if (out_or_in) return(out); else return(in);
     194      }
     195    };
     196
     197    class OutEdgeIt : public EdgeIt {
     198      friend class UndirGraphWrapper<Graph>;
     199      //bool out_or_in; //true iff out
     200      //GraphOutEdgeIt out;
     201      //GraphInEdgeIt in;
     202    public:
     203      OutEdgeIt() : EdgeIt() { }
     204      OutEdgeIt(const UndirGraphWrapper& _G, const NodeIt& n) : EdgeIt() {
     205        _G.graph->getFirst(out, n);
     206        if (!(_G.graph->valid(out))) {
     207          out_or_in=false;
     208          _G.graph->getFirst(in, n);
     209        }
     210      }
     211    };
     212
     213    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
     214      e.out_or_in=true;
     215      graph->getFirst(e.out, n);
     216      if (!(graph->valid(e.out))) {
     217        e.out_or_in=false;
     218        graph->getFirst(e.in, n);
     219      }
     220      return e;
     221    }
     222
     223    OutEdgeIt& next(OutEdgeIt& e) const {
     224      if (e.out_or_in) {
     225        NodeIt n=graph->tail(e.out);
     226        graph->next(e.out);
     227        if (!graph->valid(e.out)) {
     228          e.out_or_in=false;
     229          graph->getFirst(e.in, n);
     230        }
     231      } else {
     232        graph->next(e.in);
     233      }
     234      return e;
     235    }
     236
     237    NodeIt aNode(const OutEdgeIt& e) const {
     238      if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
     239    NodeIt bNode(const OutEdgeIt& e) const {
     240      if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
     241
     242    typedef OutEdgeIt InEdgeIt;
     243
     244    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     245//     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
     246//       return graph->getFirst(i, p); }
     247   
     248    template<typename I> I getNext(const I& i) const {
     249      return graph->getNext(i); }
     250    template<typename I> I& next(I &i) const { return graph->next(i); }   
     251
     252    template< typename It > It first() const {
     253      It e; getFirst(e); return e; }
     254
     255    template< typename It > It first(const NodeIt& v) const {
     256      It e; getFirst(e, v); return e; }
     257
     258    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     259    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     260
     261    template<typename I> bool valid(const I& i) const
     262      { return graph->valid(i); }
     263 
     264    //template<typename I> void setInvalid(const I &i);
     265    //{ return graph->setInvalid(i); }
     266
     267    int nodeNum() const { return graph->nodeNum(); }
     268    int edgeNum() const { return graph->edgeNum(); }
     269 
     270//     template<typename I> NodeIt aNode(const I& e) const {
     271//       return graph->aNode(e); }
     272//     template<typename I> NodeIt bNode(const I& e) const {
     273//       return graph->bNode(e); }
     274 
     275    NodeIt addNode() const { return graph->addNode(); }
     276    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     277      return graph->addEdge(tail, head); }
     278 
     279    template<typename I> void erase(const I& i) const { graph->erase(i); }
     280 
     281    void clear() const { graph->clear(); }
     282   
     283    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     284    public:
     285      NodeMap(const UndirGraphWrapper<Graph>& _G) :
     286        Graph::NodeMap<T>(_G.getGraph()) { }
     287      NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
     288        Graph::NodeMap<T>(_G.getGraph(), a) { }
     289    };
     290    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     291    public:
     292      EdgeMap(const UndirGraphWrapper<Graph>& _G) :
     293        Graph::EdgeMap<T>(_G.getGraph()) { }
     294      EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
     295        Graph::EdgeMap<T>(_G.getGraph(), a) { }
     296    };
     297   
     298    void setGraph(Graph& _graph) { graph = &_graph; }
     299    Graph& getGraph() const { return (*graph); }
     300 
     301    //TrivGraphWrapper() : graph(0) { }
     302    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
     303  };
     304
    161305
    162306
    … …  
    248392//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
    249393//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
     394    void setGraph(Graph& _graph) { graph = &_graph; }
     395    Graph& getGraph() const { return (*graph); }
    250396    class EdgeIt;
    251397    class OutEdgeIt;
    … …  
    500646    public:
    501647      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
    502         : Graph::NodeMap<T>(*(_G.G)) { }
     648        : Graph::NodeMap<T>(_G.getGraph()) { }
    503649      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
    504               T a) : Graph::NodeMap<T>(*(_G.G), a) { }
     650              T a) : Graph::NodeMap<T>(_G.getGraph(), a) { }
    505651    };
    506652
    … …  
    519665      typename Graph::EdgeMap<T> forward_map, backward_map;
    520666    public:
    521       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
    522       EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
     667      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.getGraph()), backward_map(_G.getGraph()) { }
     668      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.getGraph(), a), backward_map(_G.getGraph(), a) { }
    523669      void set(EdgeIt e, T a) {
    524670        if (e.out_or_in)
Note: See TracChangeset for help on using the changeset viewer.