COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 650:588ff2ca55bd in lemon-0.x for src/hugo


Ignore:
Timestamp:
05/20/04 17:40:59 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@850
Message:

a

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/graph_wrapper.h

    r626 r650  
    1212
    1313#include <hugo/invalid.h>
     14#include <hugo/maps.h>
    1415//#include <iter_map.h>
    1516
    … …  
    104105      Node() { }
    105106      Node(const typename Graph::Node& _n) : Graph::Node(_n) { }
     107      // /// \bug construction throughrthr multiple levels should be
     108      // /// handled better
     109      // Node(const typename ParentGraph::ParentGraph::Node& _n) :
     110      // Graph::Node(_n) { }
    106111      Node(const Invalid& i) : Graph::Node(i) { }
    107112    };
    … …  
    203208    void clear() const { graph->clear(); }
    204209   
     210    bool forward(const Edge& e) const { graph->forward(e); }
     211    bool backward(const Edge& e) const { graph->backward(e); }
     212   
     213    Edge opposite(const Edge& e) const { Edge(graph->opposite(e)); }
     214
    205215    template<typename T> class NodeMap : public Graph::template NodeMap<T> {
    206216      typedef typename Graph::template NodeMap<T> Parent;
    … …  
    228238  template<typename Graph>
    229239  class RevGraphWrapper : public GraphWrapper<Graph> {
     240  public:
     241    typedef GraphWrapper<Graph> Parent;
    230242  protected:
    231243    RevGraphWrapper() : GraphWrapper<Graph>() { }
    … …  
    308320           typename EdgeFilterMap>
    309321  class SubGraphWrapper : public GraphWrapper<Graph> {
     322  public:
     323    typedef GraphWrapper<Graph> Parent;
    310324  protected:
    311325    NodeFilterMap* node_filter_map;
    … …  
    322336   
    323337  public:
    324 
    325338    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
    326339                    EdgeFilterMap& _edge_filter_map) :
    … …  
    497510  template<typename Graph>
    498511  class UndirGraphWrapper : public GraphWrapper<Graph> {
     512  public:
     513    typedef GraphWrapper<Graph> Parent;
    499514  protected:
    500515    UndirGraphWrapper() : GraphWrapper<Graph>() { }
    … …  
    592607
    593608
    594   ///\brief A wrapper for composing bidirected graph from a directed one.
     609
     610  ///\brief A wrapper for composing a subgraph of a
     611  /// bidirected graph composed from a directed one.
    595612  /// experimental, for fezso's sake.
    596613  ///
    597   /// A wrapper for composing bidirected graph from a directed one.
     614  /// A wrapper for composing a subgraps of a
     615  /// bidirected graph composed from a directed one.
    598616  /// experimental, for fezso's sake.
    599617  /// A bidirected graph is composed over the directed one without physical
    600618  /// storage. As the oppositely directed edges are logically different ones
    601619  /// the maps are able to attach different values for them.
    602   template<typename Graph>
    603   class BidirGraphWrapper : public GraphWrapper<Graph> {
     620  template<typename Graph,
     621           typename ForwardFilterMap, typename BackwardFilterMap>
     622  class SubBidirGraphWrapper : public GraphWrapper<Graph> {
     623  public:
     624    typedef GraphWrapper<Graph> Parent;
    604625  protected:
    605626    //const CapacityMap* capacity;
    606627    //FlowMap* flow;
    607628
    608     BidirGraphWrapper() : GraphWrapper<Graph>()/*,
     629    ForwardFilterMap* forward_filter;
     630    BackwardFilterMap* backward_filter;
     631
     632    SubBidirGraphWrapper() : GraphWrapper<Graph>()/*,
    609633                                                 capacity(0), flow(0)*/ { }
    610 //     void setCapacityMap(const CapacityMap& _capacity) {
    611 //       capacity=&_capacity;
    612 //     }
    613 //     void setFlowMap(FlowMap& _flow) {
    614 //       flow=&_flow;
    615 //     }
    616 
    617   public:
    618 
    619     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
    620                                      FlowMap& _flow*/) :
    621       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
     634    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
     635      forward_filter=&_forward_filter;
     636    }
     637    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
     638      backward_filter=&_backward_filter;
     639    }
     640
     641  public:
     642
     643    SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
     644                         BackwardFilterMap& _backward_filter) :
     645      GraphWrapper<Graph>(_graph),
     646      forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
    622647
    623648    class Edge;
    … …  
    633658
    634659    class Edge : public Graph::Edge {
    635       friend class BidirGraphWrapper<Graph>;
     660      friend class SubBidirGraphWrapper<Graph,
     661                                        ForwardFilterMap, BackwardFilterMap>;
    636662      ///\bug ez nem is kell
    637663      //template<typename T> friend class NodeMap;
    … …  
    660686
    661687    class OutEdgeIt {
    662       friend class BidirGraphWrapper<Graph>;
     688      friend class SubBidirGraphWrapper<Graph,
     689                                        ForwardFilterMap, BackwardFilterMap>;
    663690    protected:
    664691      typename Graph::OutEdgeIt out;
    … …  
    671698      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    672699//the unique invalid iterator
    673       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
     700      OutEdgeIt(const SubBidirGraphWrapper<Graph,
     701                ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    674702        backward=false;
    675703        _G.graph->first(out, v);
    676         while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     704        while(_G.graph->valid(out) && !(*_G.forward_filter)[*this]) { _G.graph->next(out); }
    677705        if (!_G.graph->valid(out)) {
    678706          backward=true;
    679707          _G.graph->first(in, v);
    680           while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     708          while(_G.graph->valid(in) && !(*_G.backward_filter)[*this]) { _G.graph->next(in); }
    681709        }
    682710      }
    … …  
    694722
    695723    class InEdgeIt {
    696       friend class BidirGraphWrapper<Graph>;
     724      friend class SubBidirGraphWrapper<Graph,
     725                                        ForwardFilterMap, BackwardFilterMap>;
    697726    protected:
    698727      typename Graph::OutEdgeIt out;
    … …  
    705734      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    706735//the unique invalid iterator
    707       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
     736      InEdgeIt(const SubBidirGraphWrapper<Graph,
     737               ForwardFilterMap, BackwardFilterMap>& _G, Node v) {
    708738        backward=false;
    709739        _G.graph->first(in, v);
    710         while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     740        while(_G.graph->valid(in) && !(*_G.forward_filter)[*this]) { _G.graph->next(in); }
    711741        if (!_G.graph->valid(in)) {
    712742          backward=true;
    713743          _G.graph->first(out, v);
    714           while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     744          while(_G.graph->valid(out) && !(*_G.backward_filter)[*this]) { _G.graph->next(out); }
    715745        }
    716746      }
    … …  
    728758
    729759    class EdgeIt {
    730       friend class BidirGraphWrapper<Graph>;
     760      friend class SubBidirGraphWrapper<Graph,
     761                                        ForwardFilterMap, BackwardFilterMap>;
    731762    protected:
    732763      typename Graph::EdgeIt e;
    … …  
    735766      EdgeIt() { }
    736767      EdgeIt(const Invalid& i) : e(i), backward(true) { }
    737       EdgeIt(const BidirGraphWrapper<Graph>& _G) {
     768      EdgeIt(const SubBidirGraphWrapper<Graph,
     769             ForwardFilterMap, BackwardFilterMap>& _G) {
    738770        backward=false;
    739771        _G.graph->first(e);
    740         while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     772        while (_G.graph->valid(e) && !(*_G.forward_filter)[*this]) _G.graph->next(e);
    741773        if (!_G.graph->valid(e)) {
    742774          backward=true;
    743775          _G.graph->first(e);
    744           while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     776          while (_G.graph->valid(e) && !(*_G.backward_filter)[*this]) _G.graph->next(e);
    745777        }
    746778      }
    … …  
    771803        Node v=this->graph->aNode(e.out);
    772804        this->graph->next(e.out);
    773         while(this->graph->valid(e.out) && !enabled(e)) {
     805        while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
    774806          this->graph->next(e.out); }
    775807        if (!this->graph->valid(e.out)) {
    776808          e.backward=true;
    777809          this->graph->first(e.in, v);
    778           while(this->graph->valid(e.in) && !enabled(e)) {
     810          while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    779811            this->graph->next(e.in); }
    780812        }
    781813      } else {
    782814        this->graph->next(e.in);
    783         while(this->graph->valid(e.in) && !enabled(e)) {
     815        while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    784816          this->graph->next(e.in); }
    785817      }
    … …  
    791823        Node v=this->graph->aNode(e.in);
    792824        this->graph->next(e.in);
    793         while(this->graph->valid(e.in) && !enabled(e)) {
     825        while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
    794826          this->graph->next(e.in); }
    795827        if (!this->graph->valid(e.in)) {
    796828          e.backward=true;
    797829          this->graph->first(e.out, v);
    798           while(this->graph->valid(e.out) && !enabled(e)) {
     830          while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    799831            this->graph->next(e.out); }
    800832        }
    801833      } else {
    802834        this->graph->next(e.out);
    803         while(this->graph->valid(e.out) && !enabled(e)) {
     835        while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    804836          this->graph->next(e.out); }
    805837      }
    … …  
    809841      if (!e.backward) {
    810842        this->graph->next(e.e);
    811         while(this->graph->valid(e.e) && !enabled(e)) {
     843        while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
    812844          this->graph->next(e.e); }
    813845        if (!this->graph->valid(e.e)) {
    814846          e.backward=true;
    815847          this->graph->first(e.e);
    816           while(this->graph->valid(e.e) && !enabled(e)) {
     848          while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    817849            this->graph->next(e.e); }
    818850        }
    819851      } else {
    820852        this->graph->next(e.e);
    821         while(this->graph->valid(e.e) && !enabled(e)) {
     853        while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    822854          this->graph->next(e.e); }
    823855      }
    … …  
    877909//     }
    878910
    879     bool enabled(const Edge& e) const {
    880       if (!e.backward)
    881 //      return (capacity->get(e.out)-flow->get(e.out));
    882         //return ((*capacity)[e]-(*flow)[e]);
    883         return true;
    884       else
    885 //      return (flow->get(e.in));
    886         //return ((*flow)[e]);
    887         return true;
    888     }
     911//     bool enabled(const Edge& e) const {
     912//       if (!e.backward)
     913// //   return (capacity->get(e.out)-flow->get(e.out));
     914//      //return ((*capacity)[e]-(*flow)[e]);
     915//      return true;
     916//       else
     917// //   return (flow->get(e.in));
     918//      //return ((*flow)[e]);
     919//      return true;
     920//     }
    889921
    890922//     Number enabled(typename Graph::OutEdgeIt out) const {
    … …  
    904936      typedef T ValueType;
    905937      typedef Edge KeyType;
    906       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
    907       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     938      EdgeMap(const SubBidirGraphWrapper<Graph,
     939              ForwardFilterMap, BackwardFilterMap>& _G) :
     940        forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     941      EdgeMap(const SubBidirGraphWrapper<Graph,
     942              ForwardFilterMap, BackwardFilterMap>& _G, T a) :
     943        forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
    908944      void set(Edge e, T a) {
    909945        if (!e.backward)
    … …  
    930966    };
    931967  };
     968
     969
     970
     971  ///\brief A wrapper for composing bidirected graph from a directed one.
     972  /// experimental, for fezso's sake.
     973  ///
     974  /// A wrapper for composing bidirected graph from a directed one.
     975  /// experimental, for fezso's sake.
     976  /// A bidirected graph is composed over the directed one without physical
     977  /// storage. As the oppositely directed edges are logically different ones
     978  /// the maps are able to attach different values for them.
     979  template<typename Graph>
     980  class BidirGraphWrapper :
     981    public SubBidirGraphWrapper<
     982    Graph,
     983    ConstMap<typename Graph::Edge, bool>,
     984    ConstMap<typename Graph::Edge, bool> > {
     985  public:
     986    typedef  SubBidirGraphWrapper<
     987      Graph,
     988      ConstMap<typename Graph::Edge, bool>,
     989      ConstMap<typename Graph::Edge, bool> > Parent;
     990  protected:
     991    ConstMap<typename Graph::Edge, bool> cm;
     992    //const CapacityMap* capacity;
     993    //FlowMap* flow;
     994
     995    BidirGraphWrapper() : Parent(), cm(true) { }
     996//     void setCapacityMap(const CapacityMap& _capacity) {
     997//       capacity=&_capacity;
     998//     }
     999//     void setFlowMap(FlowMap& _flow) {
     1000//       flow=&_flow;
     1001//     }
     1002
     1003  public:
     1004
     1005    BidirGraphWrapper(Graph& _graph) : Parent() {
     1006      Parent::setGraph(_graph);
     1007      Parent::setForwardFilterMap(cm);
     1008      Parent::setBackwardFilterMap(cm);
     1009    }
     1010  };
     1011
     1012
     1013
     1014
     1015//   ///\brief A wrapper for composing bidirected graph from a directed one.
     1016//   /// experimental, for fezso's sake.
     1017//   ///
     1018//   /// A wrapper for composing bidirected graph from a directed one.
     1019//   /// experimental, for fezso's sake.
     1020//   /// A bidirected graph is composed over the directed one without physical
     1021//   /// storage. As the oppositely directed edges are logically different ones
     1022//   /// the maps are able to attach different values for them.
     1023//   template<typename Graph>
     1024//   class BidirGraphWrapper : public GraphWrapper<Graph> {
     1025//   public:
     1026//     typedef GraphWrapper<Graph> Parent;
     1027//   protected:
     1028//     //const CapacityMap* capacity;
     1029//     //FlowMap* flow;
     1030
     1031//     BidirGraphWrapper() : GraphWrapper<Graph>()/*,
     1032//                                               capacity(0), flow(0)*/ { }
     1033// //     void setCapacityMap(const CapacityMap& _capacity) {
     1034// //       capacity=&_capacity;
     1035// //     }
     1036// //     void setFlowMap(FlowMap& _flow) {
     1037// //       flow=&_flow;
     1038// //     }
     1039
     1040//   public:
     1041
     1042//     BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
     1043//                                   FlowMap& _flow*/) :
     1044//       GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
     1045
     1046//     class Edge;
     1047//     class OutEdgeIt;
     1048//     friend class Edge;
     1049//     friend class OutEdgeIt;
     1050
     1051//     //template<typename T> class NodeMap;   
     1052//     template<typename T> class EdgeMap;
     1053
     1054//     typedef typename GraphWrapper<Graph>::Node Node;
     1055//     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     1056
     1057//     class Edge : public Graph::Edge {
     1058//       friend class BidirGraphWrapper<Graph>;
     1059//       ///\bug ez nem is kell
     1060//       //template<typename T> friend class NodeMap;
     1061//       template<typename T> friend class EdgeMap;
     1062//     protected:
     1063//       bool backward; //true, iff backward
     1064// //      typename Graph::Edge e;
     1065//     public:
     1066//       Edge() { }
     1067//       ///\bug =false kell-e? zsoltnak kell az addEdge miatt
     1068//       Edge(const typename Graph::Edge& _e, bool _backward=false) :
     1069//      Graph::Edge(_e), backward(_backward) { }
     1070//       Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
     1071// //the unique invalid iterator
     1072//       friend bool operator==(const Edge& u, const Edge& v) {
     1073//      return (v.backward==u.backward &&
     1074//              static_cast<typename Graph::Edge>(u)==
     1075//              static_cast<typename Graph::Edge>(v));
     1076//       }
     1077//       friend bool operator!=(const Edge& u, const Edge& v) {
     1078//      return (v.backward!=u.backward ||
     1079//              static_cast<typename Graph::Edge>(u)!=
     1080//              static_cast<typename Graph::Edge>(v));
     1081//       }
     1082//     };
     1083
     1084//     class OutEdgeIt {
     1085//       friend class BidirGraphWrapper<Graph>;
     1086//     protected:
     1087//       typename Graph::OutEdgeIt out;
     1088//       typename Graph::InEdgeIt in;
     1089//       bool backward;
     1090//     public:
     1091//       OutEdgeIt() { }
     1092//       //FIXME
     1093// //      OutEdgeIt(const Edge& e) : Edge(e) { }
     1094//       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     1095// //the unique invalid iterator
     1096//       OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
     1097//      backward=false;
     1098//      _G.graph->first(out, v);
     1099//      while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     1100//      if (!_G.graph->valid(out)) {
     1101//        backward=true;
     1102//        _G.graph->first(in, v);
     1103//        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     1104//      }
     1105//       }
     1106//       operator Edge() const {
     1107// //   Edge e;
     1108// //   e.forward=this->forward;
     1109// //   if (this->forward) e=out; else e=in;
     1110// //   return e;
     1111//      if (this->backward)
     1112//        return Edge(in, this->backward);
     1113//      else
     1114//        return Edge(out, this->backward);
     1115//       }
     1116//     };
     1117
     1118//     class InEdgeIt {
     1119//       friend class BidirGraphWrapper<Graph>;
     1120//     protected:
     1121//       typename Graph::OutEdgeIt out;
     1122//       typename Graph::InEdgeIt in;
     1123//       bool backward;
     1124//     public:
     1125//       InEdgeIt() { }
     1126//       //FIXME
     1127// //      OutEdgeIt(const Edge& e) : Edge(e) { }
     1128//       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     1129// //the unique invalid iterator
     1130//       InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) {
     1131//      backward=false;
     1132//      _G.graph->first(in, v);
     1133//      while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     1134//      if (!_G.graph->valid(in)) {
     1135//        backward=true;
     1136//        _G.graph->first(out, v);
     1137//        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     1138//      }
     1139//       }
     1140//       operator Edge() const {
     1141// //   Edge e;
     1142// //   e.forward=this->forward;
     1143// //   if (this->forward) e=out; else e=in;
     1144// //   return e;
     1145//      if (this->backward)
     1146//        return Edge(out, this->backward);
     1147//      else
     1148//        return Edge(in, this->backward);
     1149//       }
     1150//     };
     1151
     1152//     class EdgeIt {
     1153//       friend class BidirGraphWrapper<Graph>;
     1154//     protected:
     1155//       typename Graph::EdgeIt e;
     1156//       bool backward;
     1157//     public:
     1158//       EdgeIt() { }
     1159//       EdgeIt(const Invalid& i) : e(i), backward(true) { }
     1160//       EdgeIt(const BidirGraphWrapper<Graph>& _G) {
     1161//      backward=false;
     1162//      _G.graph->first(e);
     1163//      while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     1164//      if (!_G.graph->valid(e)) {
     1165//        backward=true;
     1166//        _G.graph->first(e);
     1167//        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     1168//      }
     1169//       }
     1170//       operator Edge() const {
     1171//      return Edge(e, this->backward);
     1172//       }
     1173//     };
     1174
     1175//     using GraphWrapper<Graph>::first;
     1176// //     NodeIt& first(NodeIt& i) const {
     1177// //       i=NodeIt(*this); return i;
     1178// //     }
     1179//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1180//       i=OutEdgeIt(*this, p); return i;
     1181//     }
     1182// //    FIXME not tested
     1183//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1184//       i=InEdgeIt(*this, p); return i;
     1185//     }
     1186//     EdgeIt& first(EdgeIt& i) const {
     1187//       i=EdgeIt(*this); return i;
     1188//     }
     1189 
     1190//     using GraphWrapper<Graph>::next;
     1191// //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
     1192//     OutEdgeIt& next(OutEdgeIt& e) const {
     1193//       if (!e.backward) {
     1194//      Node v=this->graph->aNode(e.out);
     1195//      this->graph->next(e.out);
     1196//      while(this->graph->valid(e.out) && !enabled(e)) {
     1197//        this->graph->next(e.out); }
     1198//      if (!this->graph->valid(e.out)) {
     1199//        e.backward=true;
     1200//        this->graph->first(e.in, v);
     1201//        while(this->graph->valid(e.in) && !enabled(e)) {
     1202//          this->graph->next(e.in); }
     1203//      }
     1204//       } else {
     1205//      this->graph->next(e.in);
     1206//      while(this->graph->valid(e.in) && !enabled(e)) {
     1207//        this->graph->next(e.in); }
     1208//       }
     1209//       return e;
     1210//     }
     1211// //     FIXME Not tested
     1212//     InEdgeIt& next(InEdgeIt& e) const {
     1213//       if (!e.backward) {
     1214//      Node v=this->graph->aNode(e.in);
     1215//      this->graph->next(e.in);
     1216//      while(this->graph->valid(e.in) && !enabled(e)) {
     1217//        this->graph->next(e.in); }
     1218//      if (!this->graph->valid(e.in)) {
     1219//        e.backward=true;
     1220//        this->graph->first(e.out, v);
     1221//        while(this->graph->valid(e.out) && !enabled(e)) {
     1222//          this->graph->next(e.out); }
     1223//      }
     1224//       } else {
     1225//      this->graph->next(e.out);
     1226//      while(this->graph->valid(e.out) && !enabled(e)) {
     1227//        this->graph->next(e.out); }
     1228//       }
     1229//       return e;
     1230//     }
     1231//     EdgeIt& next(EdgeIt& e) const {
     1232//       if (!e.backward) {
     1233//      this->graph->next(e.e);
     1234//      while(this->graph->valid(e.e) && !enabled(e)) {
     1235//        this->graph->next(e.e); }
     1236//      if (!this->graph->valid(e.e)) {
     1237//        e.backward=true;
     1238//        this->graph->first(e.e);
     1239//        while(this->graph->valid(e.e) && !enabled(e)) {
     1240//          this->graph->next(e.e); }
     1241//      }
     1242//       } else {
     1243//      this->graph->next(e.e);
     1244//      while(this->graph->valid(e.e) && !enabled(e)) {
     1245//        this->graph->next(e.e); }
     1246//       }
     1247//       return e;
     1248//     }
     1249
     1250//     Node tail(Edge e) const {
     1251//       return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
     1252//     Node head(Edge e) const {
     1253//       return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
     1254
     1255//     Node aNode(OutEdgeIt e) const {
     1256//       return ((!e.backward) ? this->graph->aNode(e.out) :
     1257//            this->graph->aNode(e.in)); }
     1258//     Node bNode(OutEdgeIt e) const {
     1259//       return ((!e.backward) ? this->graph->bNode(e.out) :
     1260//            this->graph->bNode(e.in)); }
     1261
     1262//     Node aNode(InEdgeIt e) const {
     1263//       return ((!e.backward) ? this->graph->aNode(e.in) :
     1264//            this->graph->aNode(e.out)); }
     1265//     Node bNode(InEdgeIt e) const {
     1266//       return ((!e.backward) ? this->graph->bNode(e.in) :
     1267//            this->graph->bNode(e.out)); }
     1268
     1269//     /// Gives back the opposite edge.
     1270//     Edge opposite(const Edge& e) const {
     1271//       Edge f=e;
     1272//       f.backward=!f.backward;
     1273//       return f;
     1274//     }
     1275
     1276// //    int nodeNum() const { return graph->nodeNum(); }
     1277//     //FIXME
     1278//     void edgeNum() const { }
     1279//     //int edgeNum() const { return graph->edgeNum(); }
     1280
     1281
     1282// //    int id(Node v) const { return graph->id(v); }
     1283
     1284//     bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
     1285//     bool valid(Edge e) const {
     1286//       return this->graph->valid(e);
     1287//      //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     1288//     }
     1289
     1290//     bool forward(const Edge& e) const { return !e.backward; }
     1291//     bool backward(const Edge& e) const { return e.backward; }
     1292
     1293// //     void augment(const Edge& e, Number a) const {
     1294// //       if (!e.backward) 
     1295// // //        flow->set(e.out, flow->get(e.out)+a);
     1296// //   flow->set(e, (*flow)[e]+a);
     1297// //       else 
     1298// // //        flow->set(e.in, flow->get(e.in)-a);
     1299// //   flow->set(e, (*flow)[e]-a);
     1300// //     }
     1301
     1302//     bool enabled(const Edge& e) const {
     1303//       if (!e.backward)
     1304// //   return (capacity->get(e.out)-flow->get(e.out));
     1305//      //return ((*capacity)[e]-(*flow)[e]);
     1306//      return true;
     1307//       else
     1308// //   return (flow->get(e.in));
     1309//      //return ((*flow)[e]);
     1310//      return true;
     1311//     }
     1312
     1313// //     Number enabled(typename Graph::OutEdgeIt out) const {
     1314// // //      return (capacity->get(out)-flow->get(out));
     1315// //       return ((*capacity)[out]-(*flow)[out]);
     1316// //     }
     1317   
     1318// //     Number enabled(typename Graph::InEdgeIt in) const {
     1319// // //      return (flow->get(in));
     1320// //       return ((*flow)[in]);
     1321// //     }
     1322
     1323//     template <typename T>
     1324//     class EdgeMap {
     1325//       typename Graph::template EdgeMap<T> forward_map, backward_map;
     1326//     public:
     1327//       typedef T ValueType;
     1328//       typedef Edge KeyType;
     1329//       EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1330//       EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1331//       void set(Edge e, T a) {
     1332//      if (!e.backward)
     1333//        forward_map.set(e/*.out*/, a);
     1334//      else
     1335//        backward_map.set(e/*.in*/, a);
     1336//       }
     1337//       T operator[](Edge e) const {
     1338//      if (!e.backward)
     1339//        return forward_map[e/*.out*/];
     1340//      else
     1341//        return backward_map[e/*.in*/];
     1342//       }
     1343//       void update() {
     1344//      forward_map.update();
     1345//      backward_map.update();
     1346//       }
     1347// //       T get(Edge e) const {
     1348// //   if (e.out_or_in)
     1349// //     return forward_map.get(e.out);
     1350// //   else
     1351// //     return backward_map.get(e.in);
     1352// //       }
     1353//     };
     1354//   };
    9321355
    9331356  /// \brief A bidirected graph template.
    … …  
    9421365  template<typename Graph>
    9431366  class BidirGraph : public BidirGraphWrapper<Graph> {
     1367  public:
    9441368    typedef UndirGraphWrapper<Graph> Parent;
    9451369  protected:
    … …  
    9501374    }
    9511375  };
     1376
     1377
     1378
     1379  /// An experiment for ResGraphWrapper.
     1380  template<typename Graph, typename Number,
     1381           typename CapacityMap, typename FlowMap>
     1382  class ForwardFilter {
     1383    const Graph* graph;
     1384    const CapacityMap* capacity;
     1385    const FlowMap* flow;
     1386  public:
     1387    ForwardFilter(const Graph& _graph,
     1388                  const CapacityMap& _capacity, const FlowMap& _flow) :
     1389      graph(&_graph), capacity(&_capacity), flow(&_flow) { }
     1390    bool operator[](const typename Graph::Edge& e) const {
     1391      return ((*flow)[e] < (*capacity)[e]);
     1392    }
     1393  };
     1394
     1395  /// An experiment for ResGraphWrapper.
     1396  template<typename Graph, typename Number,
     1397           typename CapacityMap, typename FlowMap>
     1398  class BackwardFilter {
     1399    const Graph* graph;
     1400    const CapacityMap* capacity;
     1401    const FlowMap* flow;
     1402  public:
     1403    BackwardFilter(const Graph& _graph,
     1404                   const CapacityMap& _capacity, const FlowMap& _flow) :
     1405      graph(&_graph), capacity(&_capacity), flow(&_flow) { }
     1406    bool operator[](const typename Graph::Edge& e) const {
     1407      return (0 < (*flow)[e]);
     1408    }
     1409  };
     1410
     1411
     1412  /// An experiment for ResGraphWrapper.
     1413  template<typename Graph, typename Number,
     1414           typename CapacityMap, typename FlowMap>
     1415  class ExpResGraphWrapper :
     1416    public SubBidirGraphWrapper<
     1417    Graph,
     1418    ForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
     1419    BackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
     1420  public:
     1421    typedef SubBidirGraphWrapper<
     1422      Graph,
     1423      ForwardFilter<Graph, Number, CapacityMap, FlowMap>, 
     1424      BackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
     1425  protected:
     1426    const CapacityMap* capacity;
     1427    FlowMap* flow;
     1428    ForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
     1429    BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
     1430  public:
     1431    ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     1432                       FlowMap& _flow) :
     1433      Parent(), capacity(&_capacity), flow(&_flow),
     1434      forward_filter(_graph, _capacity, _flow),
     1435      backward_filter(_graph, _capacity, _flow) {
     1436      Parent::setGraph(_graph);
     1437      Parent::setForwardFilterMap(forward_filter);
     1438      Parent::setBackwardFilterMap(backward_filter);
     1439    }
     1440
     1441    //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
     1442    //bool backward(const Edge& e) const { return e.backward; }
     1443
     1444    void augment(const typename Parent::Edge& e, Number a) const {
     1445      if (Parent::forward(e)) 
     1446//      flow->set(e.out, flow->get(e.out)+a);
     1447        flow->set(e, (*flow)[e]+a);
     1448      else 
     1449        //flow->set(e.in, flow->get(e.in)-a);
     1450        flow->set(e, (*flow)[e]-a);
     1451    }
     1452
     1453    Number resCap(const typename Parent::Edge& e) const {
     1454      if (Parent::forward(e))
     1455//      return (capacity->get(e.out)-flow->get(e.out));
     1456        return ((*capacity)[e]-(*flow)[e]);
     1457      else
     1458//      return (flow->get(e.in));
     1459        return ((*flow)[e]);
     1460    }
     1461
     1462  };
     1463
     1464
     1465
     1466
     1467//   /// An experiment for ResGraphWrapper.
     1468//   template<typename Graph, typename Number,
     1469//         typename CapacityMap, typename FlowMap>
     1470//   class ExpResGraphWrapper :
     1471//     public SubGraphWrapper< BidirGraphWrapper<Graph>,
     1472//                          ConstMap<typename BidirGraphWrapper<Graph>::Node,
     1473//                                   bool>,
     1474//                          EdgeFilter< BidirGraphWrapper<Graph>,
     1475//                                      CapacityMap, FlowMap> > {
     1476//   public:
     1477//     typedef SubGraphWrapper< BidirGraphWrapper<Graph>,
     1478//                           ConstMap<typename BidirGraphWrapper<Graph>::Node,
     1479//                                    bool>,
     1480//                           EdgeFilter< BidirGraphWrapper<Graph>,
     1481//                                       CapacityMap, FlowMap> > Parent;
     1482//   protected:
     1483//     const CapacityMap* capacity;
     1484//     FlowMap* flow;
     1485//     BidirGraphWrapper<Graph> bidir_graph;
     1486//     ConstMap<typename BidirGraphWrapper<Graph>::Node, bool> node_filter;
     1487//     EdgeFilter< BidirGraphWrapper<Graph>, CapacityMap, FlowMap> edge_filter;
     1488//   public:
     1489//     ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     1490//                     FlowMap& _flow) :
     1491//       Parent(), capacity(&_capacity), flow(&_flow),
     1492//       bidir_graph(_graph),
     1493//       node_filter(true),
     1494//       edge_filter(bidir_graph, *capacity, *flow) {
     1495//       Parent::setGraph(bidir_graph);
     1496//       Parent::setNodeFilterMap(node_filter);
     1497//       Parent::setEdgeFilterMap(edge_filter);
     1498//     }
     1499
     1500//     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
     1501//     //bool backward(const Edge& e) const { return e.backward; }
     1502
     1503//     void augment(const typename Parent::Edge& e, Number a) const {
     1504//       if (Parent::forward(e)) 
     1505// //   flow->set(e.out, flow->get(e.out)+a);
     1506//      flow->set(e, (*flow)[e]+a);
     1507//       else 
     1508// //   flow->set(e.in, flow->get(e.in)-a);
     1509//      flow->set(e, (*flow)[e]-a);
     1510//     }
     1511
     1512//     Number resCap(const typename Parent::Edge& e) const {
     1513//       if (Parent::forward(e))
     1514// //   return (capacity->get(e.out)-flow->get(e.out));
     1515//      return ((*capacity)[e]-(*flow)[e]);
     1516//       else
     1517// //   return (flow->get(e.in));
     1518//      return ((*flow)[e]);
     1519//     }
     1520
     1521//   };
     1522
    9521523
    9531524
    … …  
    9581529           typename CapacityMap, typename FlowMap>
    9591530  class ResGraphWrapper : public GraphWrapper<Graph> {
     1531  public:
     1532    typedef GraphWrapper<Graph> Parent;
    9601533  protected:
    9611534    const CapacityMap* capacity;
    … …  
    12841857  template<typename Graph, typename FirstOutEdgesMap>
    12851858  class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
     1859  public:
     1860    typedef GraphWrapper<Graph> Parent;
    12861861  protected:
    12871862    FirstOutEdgesMap* first_out_edges;
Note: See TracChangeset for help on using the changeset viewer.