COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 653:c3ad7c661a49 in lemon-0.x for src/hugo


Ignore:
Timestamp:
05/21/04 10:15:45 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@853
Message:

misc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/hugo/graph_wrapper.h

    r650 r653  
    10131013
    10141014
    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 //      }
     1015  template<typename Graph>
     1016  class OldBidirGraphWrapper : public GraphWrapper<Graph> {
     1017  public:
     1018    typedef GraphWrapper<Graph> Parent;
     1019  protected:
     1020    //const CapacityMap* capacity;
     1021    //FlowMap* flow;
     1022
     1023    OldBidirGraphWrapper() : GraphWrapper<Graph>()/*,
     1024                                                 capacity(0), flow(0)*/ { }
     1025//     void setCapacityMap(const CapacityMap& _capacity) {
     1026//       capacity=&_capacity;
     1027//     }
     1028//     void setFlowMap(FlowMap& _flow) {
     1029//       flow=&_flow;
     1030//     }
     1031
     1032  public:
     1033
     1034    OldBidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity,
     1035                                     FlowMap& _flow*/) :
     1036      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
     1037
     1038    class Edge;
     1039    class OutEdgeIt;
     1040    friend class Edge;
     1041    friend class OutEdgeIt;
     1042
     1043    //template<typename T> class NodeMap;   
     1044    template<typename T> class EdgeMap;
     1045
     1046    typedef typename GraphWrapper<Graph>::Node Node;
     1047    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     1048
     1049    class Edge : public Graph::Edge {
     1050      friend class OldBidirGraphWrapper<Graph>;
     1051      ///\bug ez nem is kell
     1052      //template<typename T> friend class NodeMap;
     1053      template<typename T> friend class EdgeMap;
     1054    protected:
     1055      bool backward; //true, iff backward
     1056//      typename Graph::Edge e;
     1057    public:
     1058      Edge() { }
     1059      ///\bug =false kell-e? zsoltnak kell az addEdge miatt
     1060      Edge(const typename Graph::Edge& _e, bool _backward=false) :
     1061        Graph::Edge(_e), backward(_backward) { }
     1062      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
     1063//the unique invalid iterator
     1064      friend bool operator==(const Edge& u, const Edge& v) {
     1065        return (v.backward==u.backward &&
     1066                static_cast<typename Graph::Edge>(u)==
     1067                static_cast<typename Graph::Edge>(v));
     1068      }
     1069      friend bool operator!=(const Edge& u, const Edge& v) {
     1070        return (v.backward!=u.backward ||
     1071                static_cast<typename Graph::Edge>(u)!=
     1072                static_cast<typename Graph::Edge>(v));
     1073      }
     1074    };
     1075
     1076    class OutEdgeIt {
     1077      friend class OldBidirGraphWrapper<Graph>;
     1078    protected:
     1079      typename Graph::OutEdgeIt out;
     1080      typename Graph::InEdgeIt in;
     1081      bool backward;
     1082    public:
     1083      OutEdgeIt() { }
     1084      //FIXME
     1085//      OutEdgeIt(const Edge& e) : Edge(e) { }
     1086      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     1087//the unique invalid iterator
     1088      OutEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
     1089        backward=false;
     1090        _G.graph->first(out, v);
     1091        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     1092        if (!_G.graph->valid(out)) {
     1093          backward=true;
     1094          _G.graph->first(in, v);
     1095          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     1096        }
     1097      }
     1098      operator Edge() const {
     1099//      Edge e;
     1100//      e.forward=this->forward;
     1101//      if (this->forward) e=out; else e=in;
     1102//      return e;
     1103        if (this->backward)
     1104          return Edge(in, this->backward);
     1105        else
     1106          return Edge(out, this->backward);
     1107      }
     1108    };
     1109
     1110    class InEdgeIt {
     1111      friend class OldBidirGraphWrapper<Graph>;
     1112    protected:
     1113      typename Graph::OutEdgeIt out;
     1114      typename Graph::InEdgeIt in;
     1115      bool backward;
     1116    public:
     1117      InEdgeIt() { }
     1118      //FIXME
     1119//      OutEdgeIt(const Edge& e) : Edge(e) { }
     1120      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
     1121//the unique invalid iterator
     1122      InEdgeIt(const OldBidirGraphWrapper<Graph>& _G, Node v) {
     1123        backward=false;
     1124        _G.graph->first(in, v);
     1125        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
     1126        if (!_G.graph->valid(in)) {
     1127          backward=true;
     1128          _G.graph->first(out, v);
     1129          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
     1130        }
     1131      }
     1132      operator Edge() const {
     1133//      Edge e;
     1134//      e.forward=this->forward;
     1135//      if (this->forward) e=out; else e=in;
     1136//      return e;
     1137        if (this->backward)
     1138          return Edge(out, this->backward);
     1139        else
     1140          return Edge(in, this->backward);
     1141      }
     1142    };
     1143
     1144    class EdgeIt {
     1145      friend class OldBidirGraphWrapper<Graph>;
     1146    protected:
     1147      typename Graph::EdgeIt e;
     1148      bool backward;
     1149    public:
     1150      EdgeIt() { }
     1151      EdgeIt(const Invalid& i) : e(i), backward(true) { }
     1152      EdgeIt(const OldBidirGraphWrapper<Graph>& _G) {
     1153        backward=false;
     1154        _G.graph->first(e);
     1155        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     1156        if (!_G.graph->valid(e)) {
     1157          backward=true;
     1158          _G.graph->first(e);
     1159          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
     1160        }
     1161      }
     1162      operator Edge() const {
     1163        return Edge(e, this->backward);
     1164      }
     1165    };
     1166
     1167    using GraphWrapper<Graph>::first;
     1168//     NodeIt& first(NodeIt& i) const {
     1169//       i=NodeIt(*this); return i;
     1170//     }
     1171    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1172      i=OutEdgeIt(*this, p); return i;
     1173    }
     1174//    FIXME not tested
     1175    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1176      i=InEdgeIt(*this, p); return i;
     1177    }
     1178    EdgeIt& first(EdgeIt& i) const {
     1179      i=EdgeIt(*this); return i;
     1180    }
     1181 
     1182    using GraphWrapper<Graph>::next;
     1183//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
     1184    OutEdgeIt& next(OutEdgeIt& e) const {
     1185      if (!e.backward) {
     1186        Node v=this->graph->aNode(e.out);
     1187        this->graph->next(e.out);
     1188        while(this->graph->valid(e.out) && !enabled(e)) {
     1189          this->graph->next(e.out); }
     1190        if (!this->graph->valid(e.out)) {
     1191          e.backward=true;
     1192          this->graph->first(e.in, v);
     1193          while(this->graph->valid(e.in) && !enabled(e)) {
     1194            this->graph->next(e.in); }
     1195        }
     1196      } else {
     1197        this->graph->next(e.in);
     1198        while(this->graph->valid(e.in) && !enabled(e)) {
     1199          this->graph->next(e.in); }
     1200      }
     1201      return e;
     1202    }
     1203//     FIXME Not tested
     1204    InEdgeIt& next(InEdgeIt& e) const {
     1205      if (!e.backward) {
     1206        Node v=this->graph->aNode(e.in);
     1207        this->graph->next(e.in);
     1208        while(this->graph->valid(e.in) && !enabled(e)) {
     1209          this->graph->next(e.in); }
     1210        if (!this->graph->valid(e.in)) {
     1211          e.backward=true;
     1212          this->graph->first(e.out, v);
     1213          while(this->graph->valid(e.out) && !enabled(e)) {
     1214            this->graph->next(e.out); }
     1215        }
     1216      } else {
     1217        this->graph->next(e.out);
     1218        while(this->graph->valid(e.out) && !enabled(e)) {
     1219          this->graph->next(e.out); }
     1220      }
     1221      return e;
     1222    }
     1223    EdgeIt& next(EdgeIt& e) const {
     1224      if (!e.backward) {
     1225        this->graph->next(e.e);
     1226        while(this->graph->valid(e.e) && !enabled(e)) {
     1227          this->graph->next(e.e); }
     1228        if (!this->graph->valid(e.e)) {
     1229          e.backward=true;
     1230          this->graph->first(e.e);
     1231          while(this->graph->valid(e.e) && !enabled(e)) {
     1232            this->graph->next(e.e); }
     1233        }
     1234      } else {
     1235        this->graph->next(e.e);
     1236        while(this->graph->valid(e.e) && !enabled(e)) {
     1237          this->graph->next(e.e); }
     1238      }
     1239      return e;
     1240    }
     1241
     1242    Node tail(Edge e) const {
     1243      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
     1244    Node head(Edge e) const {
     1245      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
     1246
     1247    Node aNode(OutEdgeIt e) const {
     1248      return ((!e.backward) ? this->graph->aNode(e.out) :
     1249              this->graph->aNode(e.in)); }
     1250    Node bNode(OutEdgeIt e) const {
     1251      return ((!e.backward) ? this->graph->bNode(e.out) :
     1252              this->graph->bNode(e.in)); }
     1253
     1254    Node aNode(InEdgeIt e) const {
     1255      return ((!e.backward) ? this->graph->aNode(e.in) :
     1256              this->graph->aNode(e.out)); }
     1257    Node bNode(InEdgeIt e) const {
     1258      return ((!e.backward) ? this->graph->bNode(e.in) :
     1259              this->graph->bNode(e.out)); }
     1260
     1261    /// Gives back the opposite edge.
     1262    Edge opposite(const Edge& e) const {
     1263      Edge f=e;
     1264      f.backward=!f.backward;
     1265      return f;
     1266    }
     1267
     1268//    int nodeNum() const { return graph->nodeNum(); }
     1269    //FIXME
     1270    void edgeNum() const { }
     1271    //int edgeNum() const { return graph->edgeNum(); }
     1272
     1273
     1274//    int id(Node v) const { return graph->id(v); }
     1275
     1276    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
     1277    bool valid(Edge e) const {
     1278      return this->graph->valid(e);
     1279        //return e.forward ? graph->valid(e.out) : graph->valid(e.in);
     1280    }
     1281
     1282    bool forward(const Edge& e) const { return !e.backward; }
     1283    bool backward(const Edge& e) const { return e.backward; }
     1284
     1285//     void augment(const Edge& e, Number a) const {
     1286//       if (!e.backward) 
     1287// //   flow->set(e.out, flow->get(e.out)+a);
     1288//      flow->set(e, (*flow)[e]+a);
     1289//       else 
     1290// //   flow->set(e.in, flow->get(e.in)-a);
     1291//      flow->set(e, (*flow)[e]-a);
     1292//     }
     1293
     1294    bool enabled(const Edge& e) const {
     1295      if (!e.backward)
     1296//      return (capacity->get(e.out)-flow->get(e.out));
     1297        //return ((*capacity)[e]-(*flow)[e]);
     1298        return true;
     1299      else
     1300//      return (flow->get(e.in));
     1301        //return ((*flow)[e]);
     1302        return true;
     1303    }
     1304
     1305//     Number enabled(typename Graph::OutEdgeIt out) const {
     1306// //      return (capacity->get(out)-flow->get(out));
     1307//       return ((*capacity)[out]-(*flow)[out]);
     1308//     }
     1309   
     1310//     Number enabled(typename Graph::InEdgeIt in) const {
     1311// //      return (flow->get(in));
     1312//       return ((*flow)[in]);
     1313//     }
     1314
     1315    template <typename T>
     1316    class EdgeMap {
     1317      typename Graph::template EdgeMap<T> forward_map, backward_map;
     1318    public:
     1319      typedef T ValueType;
     1320      typedef Edge KeyType;
     1321      EdgeMap(const OldBidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1322      EdgeMap(const OldBidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1323      void set(Edge e, T a) {
     1324        if (!e.backward)
     1325          forward_map.set(e/*.out*/, a);
     1326        else
     1327          backward_map.set(e/*.in*/, a);
     1328      }
     1329      T operator[](Edge e) const {
     1330        if (!e.backward)
     1331          return forward_map[e/*.out*/];
     1332        else
     1333          return backward_map[e/*.in*/];
     1334      }
     1335      void update() {
     1336        forward_map.update();
     1337        backward_map.update();
     1338      }
     1339//       T get(Edge e) const {
     1340//      if (e.out_or_in)
     1341//        return forward_map.get(e.out);
     1342//      else
     1343//        return backward_map.get(e.in);
    11051344//       }
    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 //   };
     1345    };
     1346  };
     1347
     1348
    13551349
    13561350  /// \brief A bidirected graph template.
    … …  
    13771371
    13781372
    1379   /// An experiment for ResGraphWrapper.
    13801373  template<typename Graph, typename Number,
    13811374           typename CapacityMap, typename FlowMap>
    … …  
    13931386  };
    13941387
    1395   /// An experiment for ResGraphWrapper.
    13961388  template<typename Graph, typename Number,
    13971389           typename CapacityMap, typename FlowMap>
    … …  
    14091401  };
    14101402
    1411 
    1412   /// An experiment for ResGraphWrapper.
     1403 
     1404  /// A wrapper for composing the residual graph for directed flow and circulation problems.
     1405
     1406  /// A wrapper for composing the residual graph for directed flow and circulation problems.
    14131407  template<typename Graph, typename Number,
    14141408           typename CapacityMap, typename FlowMap>
    1415   class ExpResGraphWrapper :
     1409  class ResGraphWrapper :
    14161410    public SubBidirGraphWrapper<
    14171411    Graph,
    … …  
    14291423    BackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
    14301424  public:
    1431     ExpResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     1425    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
    14321426                       FlowMap& _flow) :
    14331427      Parent(), capacity(&_capacity), flow(&_flow),
    … …  
    14651459
    14661460
    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 
    1523 
    1524 
    1525   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    1526 
    1527   /// A wrapper for composing the residual graph for directed flow and circulation problems.
    15281461  template<typename Graph, typename Number,
    15291462           typename CapacityMap, typename FlowMap>
    1530   class ResGraphWrapper : public GraphWrapper<Graph> {
     1463  class OldResGraphWrapper : public GraphWrapper<Graph> {
    15311464  public:
    15321465    typedef GraphWrapper<Graph> Parent;
    … …  
    15351468    FlowMap* flow;
    15361469
    1537     ResGraphWrapper() : GraphWrapper<Graph>(0),
     1470    OldResGraphWrapper() : GraphWrapper<Graph>(0),
    15381471                        capacity(0), flow(0) { }
    15391472    void setCapacityMap(const CapacityMap& _capacity) {
    … …  
    15461479  public:
    15471480
    1548     ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     1481    OldResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
    15491482                    FlowMap& _flow) :
    15501483      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
    … …  
    15581491    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    15591492    class Edge : public Graph::Edge {
    1560       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     1493      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    15611494    protected:
    15621495      bool backward; //true, iff backward
    … …  
    15811514
    15821515    class OutEdgeIt {
    1583       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     1516      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    15841517    protected:
    15851518      typename Graph::OutEdgeIt out;
    … …  
    15921525      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    15931526//the unique invalid iterator
    1594       OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
     1527      OutEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
    15951528        backward=false;
    15961529        _G.graph->first(out, v);
    … …  
    16151548
    16161549    class InEdgeIt {
    1617       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     1550      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    16181551    protected:
    16191552      typename Graph::OutEdgeIt out;
    … …  
    16261559      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
    16271560//the unique invalid iterator
    1628       InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
     1561      InEdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) {
    16291562        backward=false;
    16301563        _G.graph->first(in, v);
    … …  
    16491582
    16501583    class EdgeIt {
    1651       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     1584      friend class OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
    16521585    protected:
    16531586      typename Graph::EdgeIt e;
    … …  
    16561589      EdgeIt() { }
    16571590      EdgeIt(const Invalid& i) : e(i), backward(true) { }
    1658       EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
     1591      EdgeIt(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) {
    16591592        backward=false;
    16601593        _G.graph->first(e);
    … …  
    18161749      typedef T ValueType;
    18171750      typedef Edge KeyType;
    1818       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
    1819       EdgeMap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
     1751      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
     1752      EdgeMap(const OldResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
    18201753      void set(Edge e, T a) {
    18211754        if (!e.backward)
Note: See TracChangeset for help on using the changeset viewer.