COIN-OR::LEMON - Graph Library

Changeset 878:86b42ec55f3e in lemon-0.x for src/hugo/graph_wrapper.h


Ignore:
Timestamp:
09/17/04 14:23:09 (18 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1185
Message:

Graph wrapper tests added.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/hugo/graph_wrapper.h

    r877 r878  
    9898    GraphWrapper(Graph& _graph) : graph(&_graph) { }
    9999    GraphWrapper(const GraphWrapper<Graph>& gw) : graph(gw.graph) { }
    100 //     Graph& getGraph() const { return *graph; }
    101100 
    102101    typedef typename Graph::Node Node;
     
    106105     public:
    107106      NodeIt() { }
    108       //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
    109107      NodeIt(Invalid i) : Node(i) { }
    110108      NodeIt(const GraphWrapper<Graph>& _gw) :
     
    124122     public:
    125123      OutEdgeIt() { }
    126       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
    127124      OutEdgeIt(Invalid i) : Edge(i) { }
    128125      OutEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     
    141138     public:
    142139      InEdgeIt() { }
    143       //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
    144140      InEdgeIt(Invalid i) : Edge(i) { }
    145141      InEdgeIt(const GraphWrapper<Graph>& _gw, const Node& n) :
     
    153149      }
    154150    };
    155     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    156151    class EdgeIt : public Edge {
    157152      const GraphWrapper<Graph>* gw;
     
    159154     public:
    160155      EdgeIt() { }
    161       //EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
    162156      EdgeIt(Invalid i) : Edge(i) { }
    163157      EdgeIt(const GraphWrapper<Graph>& _gw) :
     
    185179    }
    186180
    187 //     NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    188 //     OutEdgeIt& next(OutEdgeIt& i) const { graph->next(i.e); return i; }
    189 //     InEdgeIt& next(InEdgeIt& i) const { graph->next(i.e); return i; }
    190 //     EdgeIt& next(EdgeIt& i) const { graph->next(i.e); return i; }   
    191 
    192181    Node tail(const Edge& e) const {
    193182      return Node(graph->tail(static_cast<typename Graph::Edge>(e))); }
     
    195184      return Node(graph->head(static_cast<typename Graph::Edge>(e))); }
    196185
    197 //     bool valid(const Node& n) const {
    198 //       return graph->valid(static_cast<typename Graph::Node>(n)); }
    199 //     bool valid(const Edge& e) const {
    200 //       return graph->valid(static_cast<typename Graph::Edge>(e)); }
    201 
    202186    int nodeNum() const { return graph->nodeNum(); }
    203187    int edgeNum() const { return graph->edgeNum(); }
    204  
    205 //     Node aNode(const OutEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    206 //     Node aNode(const InEdgeIt& e) const { return Node(graph->aNode(e.e)); }
    207 //     Node bNode(const OutEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    208 //     Node bNode(const InEdgeIt& e) const { return Node(graph->bNode(e.e)); }
    209188 
    210189    Node addNode() const { return Node(graph->addNode()); }
     
    261240     public:
    262241      OutEdgeIt() { }
    263       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
    264242      OutEdgeIt(Invalid i) : Edge(i) { }
    265243      OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     
    278256     public:
    279257      InEdgeIt() { }
    280       //InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
    281258      InEdgeIt(Invalid i) : Edge(i) { }
    282259      InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
     
    298275      i=InEdgeIt(*this, p); return i;
    299276    }
    300 
    301 //     using GraphWrapper<Graph>::next;
    302 //     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    303 //     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    304 
    305 //     Node aNode(const OutEdgeIt& e) const {
    306 //       return Node(this->graph->aNode(e.e)); }
    307 //     Node aNode(const InEdgeIt& e) const {
    308 //       return Node(this->graph->aNode(e.e)); }
    309 //     Node bNode(const OutEdgeIt& e) const {
    310 //       return Node(this->graph->bNode(e.e)); }
    311 //     Node bNode(const InEdgeIt& e) const {
    312 //       return Node(this->graph->bNode(e.e)); }
    313277
    314278    Node tail(const Edge& e) const {
     
    364328    public:
    365329      NodeIt() { }
    366       //      NodeIt(const NodeIt& n) : Node(n), gw(n.gw) { }
    367330      NodeIt(Invalid i) : Node(i) { }
    368331      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     
    392355    public:
    393356      OutEdgeIt() { }
    394       //      OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
    395357      OutEdgeIt(Invalid i) : Edge(i) { }
    396358      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     
    446408    public:
    447409      EdgeIt() { }
    448       //      EdgeIt(const EdgeIt& e) : Edge(e), gw(e.gw) { }
    449410      EdgeIt(Invalid i) : Edge(i) { }
    450411      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     
    482443    }
    483444   
    484 //     NodeIt& next(NodeIt& i) const {
    485 //       this->graph->next(i.n);
    486 //       while (this->graph->valid(i) && !(*node_filter_map)[i.n]) {
    487 //      this->graph->next(i.n); }
    488 //       return i;
    489 //     }
    490 //     OutEdgeIt& next(OutEdgeIt& i) const {
    491 //       this->graph->next(i.e);
    492 //       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    493 //      this->graph->next(i.e); }
    494 //       return i;
    495 //     }
    496 //     InEdgeIt& next(InEdgeIt& i) const {
    497 //       this->graph->next(i.e);
    498 //       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    499 //      this->graph->next(i.e); }
    500 //       return i;
    501 //     }
    502 //     EdgeIt& next(EdgeIt& i) const {
    503 //       this->graph->next(i.e);
    504 //       while (this->graph->valid(i) && !(*edge_filter_map)[i.e]) {
    505 //      this->graph->next(i.e); }
    506 //       return i;
    507 //     }
    508 
    509 //     Node aNode(const OutEdgeIt& e) const {
    510 //       return Node(this->graph->aNode(e.e)); }
    511 //     Node aNode(const InEdgeIt& e) const {
    512 //       return Node(this->graph->aNode(e.e)); }
    513 //     Node bNode(const OutEdgeIt& e) const {
    514 //       return Node(this->graph->bNode(e.e)); }
    515 //     Node bNode(const InEdgeIt& e) const {
    516 //       return Node(this->graph->bNode(e.e)); }
    517 
    518445    /// This function hides \c n in the graph, i.e. the iteration
    519446    /// jumps over it. This is done by simply setting the value of \c n 
     
    563490
    564491
    565 //   /// \brief A wrapper for forgetting the orientation of a graph.
    566 //   ///
    567 //   /// A wrapper for getting an undirected graph by forgetting
    568 //   /// the orientation of a directed one.
    569 //   ///
    570 //   /// \author Marton Makai
    571 //   /// does not work in the new concept.
    572492  template<typename Graph>
    573493  class UndirGraphWrapper : public GraphWrapper<Graph> {
     
    602522    };
    603523
    604 //FIXME InEdgeIt
    605524    typedef OutEdgeIt InEdgeIt;
    606525
    607526    using GraphWrapper<Graph>::first;
    608 //     NodeIt& first(NodeIt& i) const {
    609 //       i=NodeIt(*this); return i;
    610 //     }
    611527    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    612528      i=OutEdgeIt(*this, p); return i;
    613529    }
    614 //FIXME
    615 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    616 //       i=InEdgeIt(*this, p); return i;
    617 //     }
    618 //     EdgeIt& first(EdgeIt& i) const {
    619 //       i=EdgeIt(*this); return i;
    620 //     }
    621530
    622531    using GraphWrapper<Graph>::next;
    623 //     NodeIt& next(NodeIt& n) const {
    624 //       GraphWrapper<Graph>::next(n);
    625 //       return n;
    626 //     }
     532
    627533    OutEdgeIt& next(OutEdgeIt& e) const {
    628534      if (e.out_or_in) {
     
    636542      return e;
    637543    }
    638     //FIXME InEdgeIt
    639 //     EdgeIt& next(EdgeIt& e) const {
    640 //       GraphWrapper<Graph>::next(n);
    641 // //      graph->next(e.e);
    642 //       return e;
    643 //     }
    644544
    645545    Node aNode(const OutEdgeIt& e) const {
     
    757657        Graph::Edge(e), backward(_backward) { }
    758658      Edge(Invalid i) : Graph::Edge(i), backward(true) { }
    759 //the unique invalid iterator
    760 //       friend bool operator==(const Edge& u, const Edge& v) {
    761 //      return (u.backward==v.backward &&
    762 //              static_cast<typename Graph::Edge>(u)==
    763 //              static_cast<typename Graph::Edge>(v));
    764 //       }
    765 //       friend bool operator!=(const Edge& u, const Edge& v) {
    766 //      return (u.backward!=v.backward ||
    767 //              static_cast<typename Graph::Edge>(u)!=
    768 //              static_cast<typename Graph::Edge>(v));
    769 //       }
    770659      bool operator==(const Edge& v) const {
    771660        return (this->backward==v.backward &&
     
    789678      OutEdgeIt() { }
    790679      OutEdgeIt(Invalid i) : Edge(i) { }
    791 //the unique invalid iterator
    792680      OutEdgeIt(const SubBidirGraphWrapper<Graph,
    793681                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     
    847735      InEdgeIt() { }
    848736      InEdgeIt(Invalid i) : Edge(i) { }
    849 //the unique invalid iterator
    850737      InEdgeIt(const SubBidirGraphWrapper<Graph,
    851738               ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     
    905792      EdgeIt() { }
    906793      EdgeIt(Invalid i) : Edge(i) { }
    907 //the unique invalid iterator
    908794      EdgeIt(const SubBidirGraphWrapper<Graph,
    909795             ForwardFilterMap, BackwardFilterMap>& _gw) :
     
    954840
    955841    using GraphWrapper<Graph>::first;
    956 //     NodeIt& first(NodeIt& i) const {
    957 //       i=NodeIt(*this); return i;
    958 //     }
    959842    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    960843      i=OutEdgeIt(*this, p); return i;
     
    967850    }
    968851 
    969 //     using GraphWrapper<Graph>::next;
    970 // //    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
    971 //     OutEdgeIt& next(OutEdgeIt& e) const {
    972 //       if (!e.backward) {
    973 //      Node v=this->graph->aNode(e.out);
    974 //      this->graph->next(e.out);
    975 //      while(this->graph->valid(e.out) && !(*forward_filter)[e]) {
    976 //        this->graph->next(e.out); }
    977 //      if (!this->graph->valid(e.out)) {
    978 //        e.backward=true;
    979 //        this->graph->first(e.in, v);
    980 //        while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    981 //          this->graph->next(e.in); }
    982 //      }
    983 //       } else {
    984 //      this->graph->next(e.in);
    985 //      while(this->graph->valid(e.in) && !(*backward_filter)[e]) {
    986 //        this->graph->next(e.in); }
    987 //       }
    988 //       return e;
    989 //     }
    990 // //     FIXME Not tested
    991 //     InEdgeIt& next(InEdgeIt& e) const {
    992 //       if (!e.backward) {
    993 //      Node v=this->graph->aNode(e.in);
    994 //      this->graph->next(e.in);
    995 //      while(this->graph->valid(e.in) && !(*forward_filter)[e]) {
    996 //        this->graph->next(e.in); }
    997 //      if (!this->graph->valid(e.in)) {
    998 //        e.backward=true;
    999 //        this->graph->first(e.out, v);
    1000 //        while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    1001 //          this->graph->next(e.out); }
    1002 //      }
    1003 //       } else {
    1004 //      this->graph->next(e.out);
    1005 //      while(this->graph->valid(e.out) && !(*backward_filter)[e]) {
    1006 //        this->graph->next(e.out); }
    1007 //       }
    1008 //       return e;
    1009 //     }
    1010 //     EdgeIt& next(EdgeIt& e) const {
    1011 //       if (!e.backward) {
    1012 //      this->graph->next(e.e);
    1013 //      while(this->graph->valid(e.e) && !(*forward_filter)[e]) {
    1014 //        this->graph->next(e.e); }
    1015 //      if (!this->graph->valid(e.e)) {
    1016 //        e.backward=true;
    1017 //        this->graph->first(e.e);
    1018 //        while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    1019 //          this->graph->next(e.e); }
    1020 //      }
    1021 //       } else {
    1022 //      this->graph->next(e.e);
    1023 //      while(this->graph->valid(e.e) && !(*backward_filter)[e]) {
    1024 //        this->graph->next(e.e); }
    1025 //       }
    1026 //       return e;
    1027 //     }
    1028852
    1029853    Node tail(Edge e) const {
     
    1031855    Node head(Edge e) const {
    1032856      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
    1033 
    1034 //     Node aNode(OutEdgeIt e) const {
    1035 //       return ((!e.backward) ? this->graph->aNode(e.out) :
    1036 //            this->graph->aNode(e.in)); }
    1037 //     Node bNode(OutEdgeIt e) const {
    1038 //       return ((!e.backward) ? this->graph->bNode(e.out) :
    1039 //            this->graph->bNode(e.in)); }
    1040 
    1041 //     Node aNode(InEdgeIt e) const {
    1042 //       return ((!e.backward) ? this->graph->aNode(e.in) :
    1043 //            this->graph->aNode(e.out)); }
    1044 //     Node bNode(InEdgeIt e) const {
    1045 //       return ((!e.backward) ? this->graph->bNode(e.in) :
    1046 //            this->graph->bNode(e.out)); }
    1047857
    1048858    /// Gives back the opposite edge.
     
    1096906        backward_map.update();
    1097907      }
    1098 //       T get(Edge e) const {
    1099 //      if (e.out_or_in)
    1100 //        return forward_map.get(e.out);
    1101 //      else
    1102 //        return backward_map.get(e.in);
    1103 //       }
    1104908    };
    1105909
     
    1183987      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    1184988    ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1185     //void setGraph(const Graph& _graph) { graph=&_graph; }
    1186989    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    1187990    void setFlow(const FlowMap& _flow) { flow=&_flow; }
     
    1194997           typename CapacityMap, typename FlowMap>
    1195998  class ResBackwardFilter {
    1196     //const Graph* graph;
    1197999    const CapacityMap* capacity;
    11981000    const FlowMap* flow;
     
    12021004      /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
    12031005    ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
    1204     //void setGraph(const Graph& _graph) { graph=&_graph; }
    12051006    void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
    12061007    void setFlow(const FlowMap& _flow) { flow=&_flow; }
     
    12431044      backward_filter.setFlow(_flow);
    12441045    }
    1245 //     /// \bug does graph reference needed in filtermaps??
    1246 //     void setGraph(const Graph& _graph) {
    1247 //       Parent::setGraph(_graph);
    1248 //       forward_filter.setGraph(_graph);
    1249 //       backward_filter.setGraph(_graph);
    1250 //     }
    12511046  public:
    12521047    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
     
    12621057    typedef typename Parent::Edge Edge;
    12631058
    1264     //    bool forward(const Parent::Edge& e) const { return Parent::forward(e); }
    1265     //bool backward(const Edge& e) const { return e.backward; }
    1266 
    12671059    void augment(const Edge& e, Number a) const {
    12681060      if (Parent::forward(e)) 
    1269 //      flow->set(e.out, flow->get(e.out)+a);
    12701061        flow->set(e, (*flow)[e]+a);
    12711062      else 
    1272         //flow->set(e.in, flow->get(e.in)-a);
    12731063        flow->set(e, (*flow)[e]-a);
    1274     }
    1275 
    1276     /// \deprecated
    1277     ///
    1278     Number resCap(const Edge& e) const {
    1279       if (Parent::forward(e))
    1280 //      return (capacity->get(e.out)-flow->get(e.out));
    1281         return ((*capacity)[e]-(*flow)[e]);
    1282       else
    1283 //      return (flow->get(e.in));
    1284         return ((*flow)[e]);
    12851064    }
    12861065
     
    12981077      Number operator[](const Edge& e) const {
    12991078        if (res_graph->forward(e))
    1300           //    return (capacity->get(e.out)-flow->get(e.out));
    13011079          return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
    13021080        else
    1303           //    return (flow->get(e.in));
    13041081          return (*(res_graph->flow))[e];
    13051082      }
    1306       /// \bug not needed with dynamic maps, or does it?
    1307       void update() { }
    13081083    };
    13091084
     
    13421117    public:
    13431118      OutEdgeIt() { }
    1344       //OutEdgeIt(const OutEdgeIt& e) : Edge(e), gw(e.gw) { }
    13451119      OutEdgeIt(Invalid i) : Edge(i) { }
    13461120      OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
     
    13561130      }
    13571131    };
    1358 //     class InEdgeIt {
    1359 //       friend class GraphWrapper<Graph>;
    1360 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    1361 // //      typedef typename Graph::InEdgeIt GraphInEdgeIt;
    1362 //       typename Graph::InEdgeIt e;
    1363 //     public:
    1364 //       InEdgeIt() { }
    1365 //       InEdgeIt(const typename Graph::InEdgeIt& _e) : e(_e) { }
    1366 //       InEdgeIt(const Invalid& i) : e(i) { }
    1367 //       InEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G,
    1368 //             const Node& _n) :
    1369 //      e(*(_G.graph), typename Graph::Node(_n)) { }
    1370 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1371 //     };       
    1372     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    1373 //     class EdgeIt {
    1374 //       friend class GraphWrapper<Graph>;
    1375 //       friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
    1376 // //      typedef typename Graph::EdgeIt GraphEdgeIt;
    1377 //       typename Graph::EdgeIt e;
    1378 //     public:
    1379 //       EdgeIt() { }
    1380 //       EdgeIt(const typename Graph::EdgeIt& _e) : e(_e) { }
    1381 //       EdgeIt(const Invalid& i) : e(i) { }
    1382 //       EdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _G) :
    1383 //      e(*(_G.graph)) { }
    1384 //       operator Edge() const { return Edge(typename Graph::Edge(e)); }
    1385 //     };
    13861132
    13871133    using GraphWrapper<Graph>::first;
    1388 //     NodeIt& first(NodeIt& i) const {
    1389 //       i=NodeIt(*this); return i;
    1390 //     }
    13911134    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    13921135      i=OutEdgeIt(*this, p); return i;
    13931136    }
    1394 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1395 //       i=InEdgeIt(*this, p); return i;
    1396 //     }
    1397 //     EdgeIt& first(EdgeIt& i) const {
    1398 //       i=EdgeIt(*this); return i;
    1399 //     }
    1400 
    1401 //     using GraphWrapper<Graph>::next;
    1402 // //    NodeIt& next(NodeIt& i) const { graph->next(i.n); return i; }
    1403 //     OutEdgeIt& next(OutEdgeIt& i) const { this->graph->next(i.e); return i; }
    1404 //     InEdgeIt& next(InEdgeIt& i) const { this->graph->next(i.e); return i; }
    1405 //     EdgeIt& next(EdgeIt& i) const { this->graph->next(i.e); return i; }   
    1406    
    1407 //     Node aNode(const OutEdgeIt& e) const {
    1408 //       return Node(this->graph->aNode(e.e)); }
    1409 //     Node aNode(const InEdgeIt& e) const {
    1410 //       return Node(this->graph->aNode(e.e)); }
    1411 //     Node bNode(const OutEdgeIt& e) const {
    1412 //       return Node(this->graph->bNode(e.e)); }
    1413 //     Node bNode(const InEdgeIt& e) const {
    1414 //       return Node(this->graph->bNode(e.e)); }
    1415 
    14161137    void erase(const Edge& e) const {
    14171138      Node n=tail(e);
Note: See TracChangeset for help on using the changeset viewer.