COIN-OR::LEMON - Graph Library

Changeset 311:6635b11938fe in lemon-0.x


Ignore:
Timestamp:
04/06/04 14:00:34 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@429
Message:

gw

Location:
src/work
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/makefile

    r220 r311  
    11CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
    22CXX2 = g++-2.95
    3 CXXFLAGS = -W -Wall -ansi -pedantic -O3 -I. -I.. -I../marci -I../alpar -I../../include 
     3CXX=$(CXX3)
     4CC=$(CXX)
     5INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos}
     6CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS)
    47LEDAROOT ?= /ledasrc/LEDA-4.1
    58
    6 BINARIES = dijkstra prim preflow
     9BINARIES = preflow #dijkstra prim
    710
    811all: $(BINARIES)
     12
     13.depend dep depend:
     14        -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
    915
    1016makefile: .depend
    1117sinclude .depend
    1218
    13 preflow:
    14         $(CXX3) $(CXXFLAGS)  -o preflow preflow.cc
    15 
    16 dijkstra:
    17         $(CXX3) $(CXXFLAGS)  -o dijkstra dijkstra.cc
    18 
    19 prim:
    20         $(CXX3) $(CXXFLAGS)  -o prim prim.cc
     19#preflow:
     20#       $(CXX3) $(CXXFLAGS)  -o preflow preflow.cc
     21#
     22#dijkstra:
     23#       $(CXX3) $(CXXFLAGS)  -o dijkstra dijkstra.cc
     24#
     25#prim:
     26#       $(CXX3) $(CXXFLAGS)  -o prim prim.cc
    2127
    2228clean:
  • src/work/marci/edmonds_karp.h

    r303 r311  
    1010#include <invalid.h>
    1111#include <graph_wrapper.h>
     12#include <maps.h>
    1213
    1314namespace hugo {
     
    354355
    355356      MG F;
    356       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
    357       FilterResGW filter_res_graph(res_graph, dist);
     357      ConstMap<typename ResGW::Node, bool> true_map(true);
     358      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     359        DistanceMap<ResGW> > FilterResGW;
     360      FilterResGW filter_res_graph(res_graph, true_map, dist);
    358361      typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
    359362      {
     
    568571
    569572      //Subgraph containing the edges on some shortest paths
    570       typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
    571       FilterResGW filter_res_graph(res_graph, dist);
     573      ConstMap<typename ResGW::Node, bool> true_map(true);
     574      typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
     575        DistanceMap<ResGW> > FilterResGW;
     576      FilterResGW filter_res_graph(res_graph, true_map, dist);
    572577
    573578      //Subgraph, which is able to delete edges which are already
     
    592597
    593598        __augment=false;
    594         //computing blocking flow with dfs
     599        //computing blocking flow with dfs
    595600        typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
    596         DfsIterator5< ErasingResGW, BlockingReachedMap >
    597           dfs(erasing_res_graph);
     601        DfsIterator5< ErasingResGW, BlockingReachedMap >
     602          dfs(erasing_res_graph);
    598603        typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
    599604          pred(erasing_res_graph);
    600605        pred.set(s, INVALID);
    601         //invalid iterators for sources
    602 
    603         typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
     606        //invalid iterators for sources
     607
     608        typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
    604609
    605610        dfs.pushAndSetReached(s);
     
    609614                /*typename ErasingResGW::OutEdgeIt*/(dfs)))
    610615          {
    611             if (dfs.isBNodeNewlyReached()) {
     616            if (dfs.isBNodeNewlyReached()) {
    612617         
    613618              typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
     
    626631                break;
    627632              }
    628             } else {
    629               erasing_res_graph.erase(dfs);
     633            } else {
     634              erasing_res_graph.erase(dfs);
    630635            }
    631636          }
    632637        }       
    633638
    634         if (__augment) {
    635           typename ErasingResGW::Node n=t;
     639        if (__augment) {
     640          typename ErasingResGW::Node n=t;
    636641          Number augment_value=free[n];
    637642          while (erasing_res_graph.valid(pred[n])) {
     
    641646            if (res_graph.resCap(e)==0)
    642647              erasing_res_graph.erase(e);
    643           }
    644         }
     648        }
     649      }
    645650     
    646651      } //while (__augment)
  • src/work/marci/edmonds_karp_demo.cc

    r305 r311  
    99#include <time_measure.h>
    1010//#include <graph_wrapper.h>
    11 
    12 class CM {
    13 public:
    14   template<typename T> int get(T) const {return 1;}
    15 };
     11#include <preflow.h>
    1612
    1713using namespace hugo;
     
    8985//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
    9086
    91 
    92   {
    93     std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
     87  {
     88    std::cout << "preflow ..." << std::endl;
     89    Graph::EdgeMap<int> flow(G); //0 flow
     90
     91    Timer ts;
     92    ts.reset();
     93
     94    Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
     95      max_flow_test(G, s, t, cap, flow);
     96    max_flow_test.run();
     97//    int i=0;
     98//    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
     99//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     100//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     101//     }
     102//     std::cout<<std::endl;
     103//      ++i;
     104//    }
     105
     106//   std::cout << "maximum flow: "<< std::endl;
     107//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     108//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     109//   }
     110//   std::cout<<std::endl;
     111    std::cout << "elapsed time: " << ts << std::endl;
     112//    std::cout << "number of augmentation phases: " << i << std::endl;
     113    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     114  }
     115
     116  {
     117    std::cout << "physical blocking flow augmentation ..." << std::endl;
    94118    Graph::EdgeMap<int> flow(G); //0 flow
    95119
     
    119143
    120144  {
    121     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     145    std::cout << "faster physical blocking flow augmentation ..." << std::endl;
    122146    Graph::EdgeMap<int> flow(G); //0 flow
    123147
     
    147171
    148172  {
    149     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
     173    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
    150174    Graph::EdgeMap<int> flow(G); //0 flow
    151175
     
    175199
    176200  {
    177     std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
     201    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
    178202    Graph::EdgeMap<int> flow(G); //0 flow
    179203
  • src/work/marci/graph_wrapper.h

    r307 r311  
    1313 
    1414  public:
     15//    typedef Graph BaseGraph;
    1516    typedef Graph ParentGraph;
    1617
     
    2526      NodeIt() { }
    2627      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     28//      NodeIt(const typename BaseGraph::NodeIt& n) : Graph::NodeIt(n) { }
    2729      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
    2830      NodeIt(const TrivGraphWrapper<Graph>& _G) :
    2931        Graph::NodeIt(*(_G.graph)) { }
     32//      operator typename BaseGraph::NodeIt() {
     33//      return typename BaseGraph::NodeIt(this->Graph::NodeIt);
     34//      }
    3035    };
    3136    typedef typename Graph::Edge Edge;
     
    5863    NodeIt& first(NodeIt& i) const {
    5964      i=NodeIt(*this);
    60       return i;
    61     }
    62     EdgeIt& first(EdgeIt& i) const {
    63       i=EdgeIt(*this);
    6465      return i;
    6566    }
     
    7677      return i;
    7778    }
     79    EdgeIt& first(EdgeIt& i) const {
     80      i=EdgeIt(*this);
     81      return i;
     82    }
    7883//     template<typename I, typename P> I& first(I& i, const P& p) const {
    7984//       i=I(*this, p);
     
    8388//    template<typename I> I getNext(const I& i) const {
    8489//      return graph->getNext(i); }
    85     template<typename I> I& next(I &i) const { graph->next(i); return i; }   
     90//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
     91    NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
     92    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
     93    InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
     94    EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }
    8695
    8796    template< typename It > It first() const {
     
    158167 
    159168  public:
     169    typedef Graph BaseGraph;
    160170    typedef Graph ParentGraph;
    161171
     
    205215      return i;
    206216    }
    207     EdgeIt& first(EdgeIt& i) const {
    208       i=EdgeIt(*this);
    209       return i;
    210     }
    211217//     template<typename I> I& first(I& i) const {       
    212218//       i=I(*this);
     
    221227      return i;
    222228    }
     229    EdgeIt& first(EdgeIt& i) const {
     230      i=EdgeIt(*this);
     231      return i;
     232    }
    223233//     template<typename I, typename P> I& first(I& i, const P& p) const {
    224234//       i=I(*this, p);
     
    228238//    template<typename I> I getNext(const I& i) const {
    229239//      return gw.getNext(i); }
    230     template<typename I> I& next(I &i) const { graph->next(i); return i; }   
     240//    template<typename I> I& next(I &i) const { graph->next(i); return i; }   
     241    NodeIt& next(NodeIt& i) const { graph->next(i); return i; }
     242    OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i); return i; }
     243    InEdgeIt& next(InEdgeIt& i) const { graph->next(i); return i; }
     244    EdgeIt& next(EdgeIt& i) const { graph->next(i); return i; }   
    231245
    232246    template< typename It > It first() const {
     
    386400
    387401  //Subgraph on the same node-set and partial edge-set
    388   template<typename Graph, typename EdgeFilterMap>
     402  template<typename Graph, typename NodeFilterMap,
     403           typename EdgeFilterMap>
    389404  class SubGraphWrapper : public GraphWrapper<Graph> {
    390405  protected:
    391     EdgeFilterMap* filter_map;
     406    NodeFilterMap* node_filter_map;
     407    EdgeFilterMap* edge_filter_map;
    392408  public:
    393     typedef typename GraphWrapper<Graph>::Node Node;
    394     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    395     typedef typename GraphWrapper<Graph>::Edge Edge;
    396     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    397     typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
    398     typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
    399 
    400409//     SubGraphWrapper() : GraphWrapper<Graph>(), filter_map(0) { }
    401     SubGraphWrapper(Graph& _graph, EdgeFilterMap& _filter_map) :
    402       GraphWrapper<Graph>(_graph), filter_map(&_filter_map) { } 
    403 
    404     template<typename I> I& first(I& i) const {
    405       graph->first(i);
    406       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
    407       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
    408       return i;
    409     }
    410     template<typename I, typename P> I& first(I& i, const P& p) const {
    411       graph->first(i, p);
    412 //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
    413       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
    414       return i;
    415     }
    416    
     410    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
     411                    EdgeFilterMap& _edge_filter_map) :
     412      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
     413      edge_filter_map(&_edge_filter_map) { } 
     414
     415
     416    typedef typename Graph::Node Node;
     417    class NodeIt : public Graph::NodeIt {
     418//      typedef typename Graph::NodeIt GraphNodeIt;
     419    public:
     420      NodeIt() { }
     421      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     422      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     423      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     424        Graph::NodeIt(*(_G.graph)) {
     425        while (_G.graph->valid((*this)/*.GraphNodeIt*/) &&
     426               !(*(_G.node_filter_map))[(*this)/*.GraphNodeIt*/])
     427          _G.graph->next((*this)/*.GraphNodeIt*/);
     428      }
     429    };
     430    typedef typename Graph::Edge Edge;
     431    class OutEdgeIt : public Graph::OutEdgeIt {
     432//      typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     433    public:
     434      OutEdgeIt() { }
     435      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
     436      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     437      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>&
     438                _G, const Node& n) :
     439        Graph::OutEdgeIt(*(_G.graph), n) {
     440        while (_G.graph->valid((*this)/*.GraphOutEdgeIt*/) &&
     441               !(*(_G.edge_filter_map))[(*this)/*.GraphOutEdgeIt*/])
     442          _G.graph->next((*this)/*.GraphOutEdgeIt*/);
     443      }
     444    };
     445    class InEdgeIt : public Graph::InEdgeIt {
     446//      typedef typename Graph::InEdgeIt GraphInEdgeIt;
     447    public:
     448      InEdgeIt() { }
     449      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
     450      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     451      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G,
     452               const Node& n) :
     453        Graph::InEdgeIt(*(_G.graph), n) {
     454        while (_G.graph->valid((*this)/*.GraphInEdgeIt*/) &&
     455               !(*(_G.edge_filter_map))[(*this)/*.GraphInEdgeIt*/])
     456          _G.graph->next((*this)/*.GraphInEdgeIt*/);
     457      }
     458    };
     459//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     460    class EdgeIt : public Graph::EdgeIt {
     461//      typedef typename Graph::EdgeIt GraphEdgeIt;
     462    public:
     463      EdgeIt() { }
     464      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
     465      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     466      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _G) :
     467        Graph::EdgeIt(*(_G.graph)) {
     468        while (_G.graph->valid((*this)/*.GraphEdgeIt*/) &&
     469               !(*(_G.edge_filter_map))[(*this)/*.GraphEdgeIt*/])
     470          _G.graph->next((*this)/*.GraphEdgeIt*/);
     471      }
     472    };
     473   
     474    NodeIt& first(NodeIt& i) const {
     475      i=NodeIt(*this);
     476      return i;
     477    }
     478    OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
     479      i=OutEdgeIt(*this, n);
     480      return i;
     481    }
     482    InEdgeIt& first(InEdgeIt& i, const Node& n) const {
     483      i=InEdgeIt(*this, n);
     484      return i;
     485    }
     486    EdgeIt& first(EdgeIt& i) const {
     487      i=EdgeIt(*this);
     488      return i;
     489    }
     490   
     491//     template<typename I> I& first(I& i) const {
     492//       graph->first(i);
     493//       //while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
     494//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     495//       return i;
     496//     }
     497//     template<typename I, typename P> I& first(I& i, const P& p) const {
     498//       graph->first(i, p);
     499// //      while (graph->valid(i) && !filter_map->get(i)) { graph->next(i); }
     500//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     501//       return i;
     502//     }
     503
     504    NodeIt& next(NodeIt& i) const {
     505      graph->next(i);
     506      while (graph->valid(i) && !(*node_filter_map)[i]) { graph->next(i); }
     507      return i;
     508    }
     509    OutEdgeIt& next(OutEdgeIt& i) const {
     510      graph->next(i);
     511      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     512      return i;
     513    }
     514    InEdgeIt& next(InEdgeIt& i) const {
     515      graph->next(i);
     516      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     517      return i;
     518    }
     519    EdgeIt& next(EdgeIt& i) const {
     520      graph->next(i);
     521      while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     522      return i;
     523    }
     524
    417525    //template<typename I> I getNext(const I& i) const {
    418526    //  return gw.getNext(i);
    419527    //}
    420     template<typename I> I& next(I &i) const {
    421       graph->next(i);
    422 //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
    423       while (graph->valid(i) && !(*filter_map)[i]) { graph->next(i); }
    424       return i;
    425     }
     528//     template<typename I> I& next(I &i) const {
     529//       graph->next(i);
     530// //      while (graph->valid(i) && !filter_map-get(i)) { graph->next(i); }
     531//       while (graph->valid(i) && !(*edge_filter_map)[i]) { graph->next(i); }
     532//       return i;
     533//     }
    426534   
    427535    template< typename It > It first() const {
     
    845953
    846954  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    847   class ResGraphWrapper : public GraphWrapper<Graph>{
    848   public:
    849     typedef typename GraphWrapper<Graph>::Node Node;
    850     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     955  class ResGraphWrapper : public GraphWrapper<Graph> {
    851956  protected:
    852957    typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
     
    866971    friend class OutEdgeIt;
    867972
     973    typedef typename GraphWrapper<Graph>::Node Node;
     974    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    868975    class Edge {
    869976      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     
    8931000      }
    8941001    };
    895 
    896 
    8971002    class OutEdgeIt : public Edge {
    8981003      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     
    9311036
    9321037    //FIXME This is just for having InEdgeIt
    933     typedef void InEdgeIt;
     1038//    class InEdgeIt : public Edge { };
    9341039
    9351040    class EdgeIt : public Edge {
     
    9941099    };
    9951100
    996     NodeIt& first(NodeIt& v) const { graph->first(v); return v; }
    997     OutEdgeIt& first(OutEdgeIt& e, Node v) const {
    998       e=OutEdgeIt(*this, v);
    999       return e;
    1000     }
     1101    NodeIt& first(NodeIt& i) const {
     1102      i=NodeIt(*this);
     1103      return i;
     1104    }
     1105    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1106      i=OutEdgeIt(*this, p);
     1107      return i;
     1108    }
     1109    //FIXME Not yet implemented
     1110    //InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1111    //i=InEdgeIt(*this, p);
     1112    //  return i;
     1113    //}
    10011114    EdgeIt& first(EdgeIt& e) const {
    10021115      e=EdgeIt(*this);
     
    10051118   
    10061119    NodeIt& next(NodeIt& n) const { graph->next(n); return n; }
    1007 
    10081120    OutEdgeIt& next(OutEdgeIt& e) const {
    10091121      if (e.out_or_in) {
     
    10221134      return e;
    10231135    }
    1024 
     1136    //FIXME Not yet implemented
     1137    //InEdgeIt& next(InEdgeIt& e) const {
     1138    //  return e;
     1139    //}
    10251140    EdgeIt& next(EdgeIt& e) const {
    10261141      if (e.out_or_in) {
     
    11701285    FirstOutEdgesMap* first_out_edges;
    11711286  public:
    1172     typedef typename GraphWrapper<Graph>::Node Node;
    1173     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    1174     typedef typename GraphWrapper<Graph>::Edge Edge;
    1175     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    1176     typedef typename GraphWrapper<Graph>::InEdgeIt InEdgeIt;
    1177     typedef typename GraphWrapper<Graph>::OutEdgeIt OutEdgeIt;
    1178 
    11791287    ErasingFirstGraphWrapper(Graph& _graph,
    11801288                             FirstOutEdgesMap& _first_out_edges) :
    11811289      GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { } 
    11821290
    1183     template<typename I> I& first(I& i) const {
    1184       graph->first(i);
    1185       return i;
    1186     }
    1187     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    1188 //      e=first_out_edges->get(n);
    1189       e=(*first_out_edges)[n];
    1190       return e;
    1191     }
    1192     template<typename I, typename P> I& first(I& i, const P& p) const {
    1193       graph->first(i, p);
    1194       return i;
    1195     }
     1291    typedef typename Graph::Node Node;
     1292    class NodeIt : public Graph::NodeIt {
     1293    public:
     1294      NodeIt() { }
     1295      NodeIt(const typename Graph::NodeIt& n) : Graph::NodeIt(n) { }
     1296      NodeIt(const Invalid& i) : Graph::NodeIt(i) { }
     1297      NodeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
     1298        Graph::NodeIt(*(_G.graph)) { }
     1299    };
     1300    typedef typename Graph::Edge Edge;
     1301    class OutEdgeIt : public Graph::OutEdgeIt {
     1302    public:
     1303      OutEdgeIt() { }
     1304      OutEdgeIt(const typename Graph::OutEdgeIt& e) : Graph::OutEdgeIt(e) { }
     1305      OutEdgeIt(const Invalid& i) : Graph::OutEdgeIt(i) { }
     1306      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
     1307                const Node& n) :
     1308        Graph::OutEdgeIt((*_G.first_out_edges)[n]) { }
     1309    };
     1310    class InEdgeIt : public Graph::InEdgeIt {
     1311    public:
     1312      InEdgeIt() { }
     1313      InEdgeIt(const typename Graph::InEdgeIt& e) : Graph::InEdgeIt(e) { }
     1314      InEdgeIt(const Invalid& i) : Graph::InEdgeIt(i) { }
     1315      InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
     1316               const Node& n) :
     1317        Graph::InEdgeIt(*(_G.graph), n) { }
     1318    };
     1319    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     1320    class EdgeIt : public Graph::EdgeIt {
     1321    public:
     1322      EdgeIt() { }
     1323      EdgeIt(const typename Graph::EdgeIt& e) : Graph::EdgeIt(e) { }
     1324      EdgeIt(const Invalid& i) : Graph::EdgeIt(i) { }
     1325      EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
     1326        Graph::EdgeIt(*(_G.graph)) { }
     1327    };
     1328
     1329    NodeIt& first(NodeIt& i) const {
     1330      i=NodeIt(*this);
     1331      return i;
     1332    }
     1333    OutEdgeIt& first(OutEdgeIt& i, const Node& n) const {
     1334      i=OutEdgeIt(*this, n);
     1335//      i=(*first_out_edges)[n];
     1336      return i;
     1337    }
     1338    InEdgeIt& first(InEdgeIt& i, const Node& n) const {
     1339      i=InEdgeIt(*this, n);
     1340      return i;
     1341    }
     1342    EdgeIt& first(EdgeIt& i) const {
     1343      i=EdgeIt(*this);
     1344      return i;
     1345    }
     1346
     1347//     template<typename I> I& first(I& i) const {
     1348//       graph->first(i);
     1349//       return i;
     1350//     }
     1351//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     1352// //      e=first_out_edges->get(n);
     1353//       e=(*first_out_edges)[n];
     1354//       return e;
     1355//     }
     1356//     template<typename I, typename P> I& first(I& i, const P& p) const {
     1357//       graph->first(i, p);
     1358//       return i;
     1359//     }
    11961360   
    11971361    //template<typename I> I getNext(const I& i) const {
    11981362    //  return gw.getNext(i);
    11991363    //}
    1200     template<typename I> I& next(I &i) const {
     1364
     1365
     1366    NodeIt& next(NodeIt& i) const {
    12011367      graph->next(i);
    12021368      return i;
    12031369    }
     1370    OutEdgeIt& next(OutEdgeIt& i) const {
     1371      graph->next(i);
     1372      return i;
     1373    }
     1374    InEdgeIt& next(InEdgeIt& i) const {
     1375      graph->next(i);
     1376      return i;
     1377    }
     1378    EdgeIt& next(EdgeIt& i) const {
     1379      graph->next(i);
     1380      return i;
     1381    }
     1382
     1383//     template<typename I> I& next(I &i) const {
     1384//       graph->next(i);
     1385//       return i;
     1386//     }
    12041387   
    12051388    template< typename It > It first() const {
Note: See TracChangeset for help on using the changeset viewer.