COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1025:3b1ad8bc21da in lemon-0.x for src


Ignore:
Timestamp:
11/29/04 18:55:46 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1415
Message:

MergeGraphWrapper? bug fixes

Location:
src/work/marci
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/lp/max_flow_by_lp.cc

    r1017 r1025  
    2222
    2323  typedef ListGraph MutableGraph;
    24   typedef SmartGraph Graph;
     24  typedef ListGraph Graph;
    2525  typedef Graph::Node Node;
    2626  typedef Graph::Edge Edge;
    … …  
    179179  MinCostGenFlow<Graph, int, Excess, LCap>
    180180    min_cost(g, excess, lcap, cap, flow, cost);
     181  min_cost.feasible();
    181182  min_cost.run();
    182183

  • src/work/marci/lp/min_cost_gen_flow.h

    r1017 r1025  
    22#ifndef LEMON_MIN_COST_GEN_FLOW_H
    33#define LEMON_MIN_COST_GEN_FLOW_H
    4 //#include <iostream>
     4#include <iostream>
    55//#include <fstream>
    66
    7 //#include <lemon/smart_graph.h>
    8 //#include <lemon/list_graph.h>
     7#include <lemon/smart_graph.h>
     8#include <lemon/list_graph.h>
    99//#include <lemon/dimacs.h>
    1010//#include <lemon/time_measure.h>
    1111//#include <graph_wrapper.h>
    12 //#include <lemon/preflow.h>
     12#include <lemon/preflow.h>
    1313//#include <augmenting_flow.h>
    1414//#include <preflow_res.h>
     15#include <../merge_node_graph_wrapper.h>
    1516#include <lemon/../work/marci/lp/lp_solver_wrapper.h>
    1617
    … …  
    5253      g(_g), excess(_excess), lcapacity(_lcapacity),
    5354      capacity(_capacity), flow(_flow), cost(_cost) { }
     55    bool feasible() {
     56      //      std::cout << "making new vertices..." << std::endl;
     57      typedef ListGraph Graph2;
     58      Graph2 g2;
     59      typedef MergeEdgeGraphWrapper<const Graph, Graph2> GW;
     60      //      std::cout << "merging..." << std::endl;
     61      GW gw(g, g2);
     62      typename GW::Node s(INVALID, g2.addNode(), true);
     63      typename GW::Node t(INVALID, g2.addNode(), true);
     64      typedef SmartGraph Graph3;
     65      //      std::cout << "making extender graph..." << std::endl;
     66      typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
     67//       {
     68//      checkConcept<StaticGraph, GWW>();   
     69//       }
     70      GWW gww(gw);
     71      typedef AugmentingGraphWrapper<GW, GWW> GWWW;
     72      GWWW gwww(gw, gww);
     73
     74      //      std::cout << "making new edges..." << std::endl;
     75      typename GWWW::template EdgeMap<Num> translated_cap(gwww);
     76
     77      for (typename GW::EdgeIt e(gw); e!=INVALID; ++e)
     78      translated_cap.set(typename GWWW::Edge(e,INVALID,false),
     79                         capacity[e]-lcapacity[e]);
     80
     81      Num expected=0;
     82
     83      //      std::cout << "making new edges 2..." << std::endl;
     84      for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
     85        Num a=0;
     86        for (typename Graph::InEdgeIt e(g, n); e!=INVALID; ++e)
     87          a+=lcapacity[e];
     88        for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
     89          a-=lcapacity[e];
     90        if (excess[n]>a) {
     91          typename GWW::Edge e=
     92            gww.addEdge(typename GW::Node(n,INVALID,false), t);
     93          translated_cap.set(typename GWWW::Edge(INVALID, e, true),
     94                             excess[n]-a);
     95        }
     96        if (excess[n]<a) {
     97          typename GWW::Edge e=
     98            gww.addEdge(s, typename GW::Node(n,INVALID,false));
     99          translated_cap.set(typename GWWW::Edge(INVALID, e, true),
     100                             a-excess[n]);
     101          expected+=a-excess[n];
     102        }
     103      }
     104
     105      //      std::cout << "preflow..." << std::endl;
     106      typename GWWW::template EdgeMap<Num> translated_flow(gwww, 0);
     107      Preflow<GWWW, Num> preflow(gwww, s, t,
     108                                 translated_cap, translated_flow);
     109      preflow.run();
     110      //      std::cout << "fv: " << preflow.flowValue() << std::endl;
     111      //      std::cout << "expected: " << expected << std::endl;
     112
     113      for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
     114        typename GW::Edge ew(e, INVALID, false);
     115        typename GWWW::Edge ewww(ew, INVALID, false);
     116        flow.set(e, translated_flow[ewww]+lcapacity[e]);
     117      }
     118      return (expected>=preflow.flowValue());
     119    }
    54120    void run() {
    55121      LPSolverWrapper lp;

  • src/work/marci/merge_node_graph_wrapper.h

    r1016 r1025  
    4141
    4242
    43   /*! A graph wrapper base class
    44     for merging the node-set of two node-disjoint graphs
    45     into the node-set of one graph.
    46     Generic implementation for unrelated _Graph1::Node and _Graph2::Node.
    47    */
    4843  template <typename _Graph1, typename _Graph2, typename Enable=void>
    49   class MergeNodeGraphWrapperBase :
     44  class MergeNodeGraphWrapperBaseBase :
    5045    public P1<_Graph1>, public P2<_Graph2> {
    5146  public:
    … …  
    5853    typedef typename Parent2::Node Graph2Node;
    5954  protected:
    60     MergeNodeGraphWrapperBase() { }
    61   public:
    62     template <typename _Value> class NodeMap;
     55    MergeNodeGraphWrapperBaseBase() { }
     56  public:
    6357
    6458    class Node : public Graph1Node, public Graph2Node {
    65       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    66       template <typename _Value> friend class NodeMap;
     59      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
    6760    protected:
    6861      bool backward; //true, iff backward
    … …  
    8982    };
    9083
    91     //typedef void Edge;
    92     class Edge { };
    93    
    94     void first(Node& i) const {
    95       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
    96       i.backward=false;
    97       if (*static_cast<Graph1Node*>(&i)==INVALID) {
    98         Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    99         i.backward=true;
    100       }
    101     }
    102     void next(Node& i) const {
    103       if (!(i.backward)) {
    104         Parent1::graph->next(*static_cast<Graph1Node*>(&i));
    105         if (*static_cast<Graph1Node*>(&i)==INVALID) {
    106           Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    107           i.backward=true;
    108         }
    109       } else {
    110         Parent2::graph->next(*static_cast<Graph2Node*>(&i));
    111       }
    112     }
    113 
    114     int id(const Node& n) const {
    115       if (!n.backward)
    116         return this->Parent1::graph->id(n);
    117       else
    118         return this->Parent2::graph->id(n);
    119     }
    120 
    121     template <typename _Value>
    122     class NodeMap {
    123     protected:
    124       typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
    125       typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
    126       ParentMap1 forward_map;
    127       ParentMap2 backward_map;
    128     public:
    129       typedef _Value Value;
    130       typedef Node Key;
    131       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
    132         forward_map(*(gw.Parent1::graph)),
    133         backward_map(*(gw.Parent2::graph)) { }
    134       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
    135               const _Value& value) :
    136         forward_map(*(gw.Parent1::graph), value),
    137         backward_map(*(gw.Parent2::graph), value) { }
    138       _Value operator[](const Node& n) const {
    139         if (!n.backward)
    140           return forward_map[n];
    141         else
    142           return backward_map[n];
    143       }
    144       void set(const Node& n, const _Value& value) {
    145         if (!n.backward)
    146           forward_map.set(n, value);
    147         else
    148           backward_map.set(n, value);
    149       }
    150 //       using ParentMap1::operator[];
    151 //       using ParentMap2::operator[];
    152     };
    153 
    154   };
    155 
    156 
    157   /*! A graph wrapper base class
    158     for merging the node-set of two node-disjoint graphs
    159     into the node-set of one graph.
    160     Specialization for the case when _Graph1::Node are the same _Graph2::Node.
    161    */
     84    static bool forward(const Node& n) { return !n.backward; }
     85    static bool backward(const Node& n) { return n.backward; }
     86    static void setForward(Node& n) { n.backward=false; }
     87    static void setBackward(Node& n) { n.backward=true; }   
     88  };
     89
     90
    16291  template <typename _Graph1, typename _Graph2>
    163   class MergeNodeGraphWrapperBase<
     92  class MergeNodeGraphWrapperBaseBase<
    16493    _Graph1, _Graph2, typename boost::enable_if<
    16594    boost::is_same<typename _Graph1::Node, typename _Graph2::Node> >::type> :
    … …  
    174103    typedef typename Parent2::Node Graph2Node;
    175104  protected:
    176     MergeNodeGraphWrapperBase() { }
    177   public:
    178     template <typename _Value> class NodeMap;
     105    MergeNodeGraphWrapperBaseBase() { }
     106  public:
    179107
    180108    class Node : public Graph1Node {
    181       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    182       template <typename _Value> friend class NodeMap;
     109      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
    183110    protected:
    184111      bool backward; //true, iff backward
    … …  
    190117      Node(const Graph1Node& n1,
    191118           const Graph2Node& n2, bool _backward) :
    192         Graph1Node(!backward ? n1 : n2), backward(_backward) { }
     119        Graph1Node(!_backward ? n1 : n2), backward(_backward) { }
    193120      Node(Invalid i) : Graph1Node(i), backward(true) { }
    194121      bool operator==(const Node& v) const {
    … …  
    201128    };
    202129
    203     //typedef void Edge;
    204     class Edge { };
    205    
    206     void first(Node& i) const {
    207       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
    208       i.backward=false;
    209       if (*static_cast<Graph1Node*>(&i)==INVALID) {
    210         Parent2::graph->first(*static_cast<Graph1Node*>(&i));
    211         i.backward=true;
    212       }
    213     }
    214     void next(Node& i) const {
    215       if (!(i.backward)) {
    216         Parent1::graph->next(*static_cast<Graph1Node*>(&i));
    217         if (*static_cast<Graph1Node*>(&i)==INVALID) {
    218           Parent2::graph->first(*static_cast<Graph1Node*>(&i));
    219           i.backward=true;
    220         }
    221       } else {
    222         Parent2::graph->next(*static_cast<Graph1Node*>(&i));
    223       }
    224     }
    225 
    226     int id(const Node& n) const {
    227       if (!n.backward)
    228         return this->Parent1::graph->id(n);
    229       else
    230         return this->Parent2::graph->id(n);
    231     }
    232 
    233     template <typename _Value>
    234     class NodeMap {
    235     protected:
    236       typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
    237       typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
    238       ParentMap1 forward_map;
    239       ParentMap2 backward_map;
    240     public:
    241       typedef _Value Value;
    242       typedef Node Key;
    243       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
    244         forward_map(*(gw.Parent1::graph)),
    245         backward_map(*(gw.Parent2::graph)) { }
    246       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
    247               const _Value& value) :
    248         forward_map(*(gw.Parent1::graph), value),
    249         backward_map(*(gw.Parent2::graph), value) { }
    250       _Value operator[](const Node& n) const {
    251         if (!n.backward)
    252           return forward_map[n];
    253         else
    254           return backward_map[n];
    255       }
    256       void set(const Node& n, const _Value& value) {
    257         if (!n.backward)
    258           forward_map.set(n, value);
    259         else
    260           backward_map.set(n, value);
    261       }
    262 //       using ParentMap1::operator[];
    263 //       using ParentMap2::operator[];
    264     };
    265 
    266   };
    267 
    268 
    269   /*! A graph wrapper base class
    270     for merging the node-set of two node-disjoint graphs
    271     into the node-set of one graph.
    272     Specialization for the case when
    273     _Graph1::Node is a base class and _Graph2::Node is derived from it.
    274    */
     130    static bool forward(const Node& n) { return !n.backward; }
     131    static bool backward(const Node& n) { return n.backward; }
     132    static void setForward(Node& n) { n.backward=false; }
     133    static void setBackward(Node& n) { n.backward=true; }
     134  };
     135
     136
    275137  template <typename _Graph1, typename _Graph2>
    276   class MergeNodeGraphWrapperBase<
     138  class MergeNodeGraphWrapperBaseBase<
    277139    _Graph1, _Graph2, typename boost::enable_if<
    278140    boost::is_base_and_derived<typename _Graph1::Node, typename _Graph2::Node> >::type> :
    … …  
    287149    typedef typename Parent2::Node Graph2Node;
    288150  protected:
    289     MergeNodeGraphWrapperBase() { }
    290   public:
    291     template <typename _Value> class NodeMap;
     151    MergeNodeGraphWrapperBaseBase() { }
     152  public:
    292153
    293154    class Node : public Graph2Node {
    294       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    295       template <typename _Value> friend class NodeMap;
     155      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
    296156    protected:
    297157      bool backward; //true, iff backward
    … …  
    320180    };
    321181
    322     //typedef void Edge;
    323     class Edge { };
    324    
    325     void first(Node& i) const {
    326       Parent1::graph->first(*static_cast<Graph1Node*>(&i));
    327       i.backward=false;
    328       if (*static_cast<Graph1Node*>(&i)==INVALID) {
    329         Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    330         i.backward=true;
    331       }
    332     }
    333     void next(Node& i) const {
    334       if (!(i.backward)) {
    335         Parent1::graph->next(*static_cast<Graph1Node*>(&i));
    336         if (*static_cast<Graph1Node*>(&i)==INVALID) {
    337           Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    338           i.backward=true;
    339         }
    340       } else {
    341         Parent2::graph->next(*static_cast<Graph2Node*>(&i));
    342       }
    343     }
    344 
    345     int id(const Node& n) const {
    346       if (!n.backward)
    347         return this->Parent1::graph->id(n);
    348       else
    349         return this->Parent2::graph->id(n);
    350     }
    351 
    352     template <typename _Value>
    353     class NodeMap {
    354     protected:
    355       typedef typename _Graph1::template NodeMap<_Value> ParentMap1;
    356       typedef typename _Graph2::template NodeMap<_Value> ParentMap2;
    357       ParentMap1 forward_map;
    358       ParentMap2 backward_map;
    359     public:
    360       typedef _Value Value;
    361       typedef Node Key;
    362       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw) :
    363         forward_map(*(gw.Parent1::graph)),
    364         backward_map(*(gw.Parent2::graph)) { }
    365       NodeMap(const MergeNodeGraphWrapperBase<_Graph1, _Graph2>& gw,
    366               const _Value& value) :
    367         forward_map(*(gw.Parent1::graph), value),
    368         backward_map(*(gw.Parent2::graph), value) { }
    369       _Value operator[](const Node& n) const {
    370         if (!n.backward)
    371           return forward_map[n];
    372         else
    373           return backward_map[n];
    374       }
    375       void set(const Node& n, const _Value& value) {
    376         if (!n.backward)
    377           forward_map.set(n, value);
    378         else
    379           backward_map.set(n, value);
    380       }
    381 //       using ParentMap1::operator[];
    382 //       using ParentMap2::operator[];
    383     };
    384 
    385   };
    386 
    387 
    388   /*! A graph wrapper base class
    389     for merging the node-set of two node-disjoint graphs
    390     into the node-set of one graph.
    391     Specialized implementaton for the case when _Graph1::Node is derived
    392     from _Graph2::Node.
    393    */
     182    static bool forward(const Node& n) { return !n.backward; }
     183    static bool backward(const Node& n) { return n.backward; }
     184    static void setForward(Node& n) { n.backward=false; }
     185    static void setBackward(Node& n) { n.backward=true; }
     186  };
     187 
     188
    394189  template <typename _Graph1, typename _Graph2>
    395   class MergeNodeGraphWrapperBase<
     190  class MergeNodeGraphWrapperBaseBase<
    396191    _Graph1, _Graph2, typename boost::enable_if<
    397192    boost::is_base_and_derived<typename _Graph2::Node, typename _Graph1::Node> >::type> :
    … …  
    406201    typedef typename Parent2::Node Graph2Node;
    407202  protected:
    408     MergeNodeGraphWrapperBase() { }
    409   public:
    410     template <typename _Value> class NodeMap;
     203    MergeNodeGraphWrapperBaseBase() { }
     204  public:
    411205
    412206    class Node : public Graph1Node {
    413       friend class MergeNodeGraphWrapperBase<_Graph1, _Graph2>;
    414       template <typename _Value> friend class NodeMap;
     207      friend class MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2>;
    415208    protected:
    416209      bool backward; //true, iff backward
    … …  
    439232    };
    440233
    441     //typedef void Edge;
     234    static bool forward(const Node& n) { return !n.backward; }
     235    static bool backward(const Node& n) { return n.backward; }
     236    static void setForward(Node& n) { n.backward=false; }
     237    static void setBackward(Node& n) { n.backward=true; }
     238  };
     239
     240
     241  template <typename _Graph1, typename _Graph2>
     242  class MergeNodeGraphWrapperBase :
     243    public MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> {
     244  public:
     245    typedef MergeNodeGraphWrapperBaseBase<_Graph1, _Graph2> Parent;
     246    typedef _Graph1 Graph1;
     247    typedef _Graph2 Graph2;
     248    typedef P1<_Graph1> Parent1;
     249    typedef P2<_Graph2> Parent2;
     250    typedef typename Parent1::Node Graph1Node;
     251    typedef typename Parent2::Node Graph2Node;
     252
     253    typedef typename Parent::Node Node;
    442254    class Edge { };
    443255   
    444256    void first(Node& i) const {
    445257      Parent1::graph->first(*static_cast<Graph1Node*>(&i));
    446       i.backward=false;
     258      this->setForward(i);
    447259      if (*static_cast<Graph1Node*>(&i)==INVALID) {
    448260        Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    449         i.backward=true;
     261        this->setBackward(i);
    450262      }
    451263    }
    452264    void next(Node& i) const {
    453       if (!(i.backward)) {
     265      if (this->forward(i)) {
    454266        Parent1::graph->next(*static_cast<Graph1Node*>(&i));
    455267        if (*static_cast<Graph1Node*>(&i)==INVALID) {
    456268          Parent2::graph->first(*static_cast<Graph2Node*>(&i));
    457           i.backward=true;
     269          this->setBackward(i);
    458270        }
    459271      } else {
    … …  
    463275
    464276    int id(const Node& n) const {
    465       if (!n.backward)
     277      if (this->forward(n))
    466278        return this->Parent1::graph->id(n);
    467279      else
    … …  
    487299        backward_map(*(gw.Parent2::graph), value) { }
    488300      _Value operator[](const Node& n) const {
    489         if (!n.backward)
     301        if (Parent::forward(n))
    490302          return forward_map[n];
    491303        else
    … …  
    493305      }
    494306      void set(const Node& n, const _Value& value) {
    495         if (!n.backward)
     307        if (Parent::forward(n))
    496308          forward_map.set(n, value);
    497309        else
    … …  
    506318
    507319  /*! A graph wrapper class
    508     fors merging the node-set of two node-disjoint graphs
    509     into one node-set. It does not satisfy
     320    for merging the node-set of two node-disjoint graphs
     321    into the node-set of one graph.
     322    Different implementations are according to the relation of
     323    _Graph1::Node and _Graph2::Node.
     324    If _Graph1::Node and _Graph2::Node are unrelated, then
     325    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
     326    is derived from both.
     327    If _Graph1::Node and _Graph2::Node are the same type, then
     328    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
     329    is derived from _Graph1::Node.
     330    If one of _Graph1::Node and _Graph2::Node
     331    is derived from the other one, then
     332    MergeNodeGraphWrapper<_Graph1, _Graph2>::Node
     333    is derived from the derived type.
     334    It does not satisfy
    510335    StaticGraph concept as it has no edge-set which
    511336    works together with the node-set.
    512    */
     337  */
    513338  template <typename _Graph1, typename _Graph2>
    514339  class MergeNodeGraphWrapper : public
    … …  
    583408    };
    584409
     410    using Parent::forward;
     411    using Parent::backward;
     412    bool forward(const Edge& e) const { return !e.backward; }
     413    bool backward(const Edge& e) const { return e.backward; }
     414
    585415    using Parent::first;
    586416    void first(Edge& i) const {
    … …  
    593423    }
    594424    void firstIn(Edge& i, const Node& n) const {
    595       Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
    596       i.backward=false;
    597       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     425      if (!backward(n)) {
     426        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     427        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     428          i=INVALID;
     429        else
     430          i.backward=false;
     431      } else {
    598432        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
    599433        i.backward=true;
    … …  
    601435    }
    602436    void firstOut(Edge& i, const Node& n) const {
    603       Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
    604       i.backward=false;
    605       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     437      if (!backward(n)) {
     438        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     439        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     440          i=INVALID;
     441        else
     442          i.backward=false;
     443      } else {
    606444        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
    607445        i.backward=true;
    … …  
    624462      if (!(i.backward)) {
    625463        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    626         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    627           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    628           i.backward=true;
    629         }
     464        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    630465      } else {
    631466        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
    … …  
    635470      if (!(i.backward)) {
    636471        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    637         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    638           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    639           i.backward=true;
    640         }
     472        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    641473      } else {
    642474        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
    … …  
    750582      Edge(const Graph1Edge& n1,
    751583           const Graph2Edge& n2, bool _backward) :
    752         Graph1Edge(!backward ? n1 : n2), backward(_backward) { }
     584        Graph1Edge(!_backward ? n1 : n2), backward(_backward) { }
    753585      Edge(Invalid i) : Graph1Edge(i), backward(true) { }
    754586      bool operator==(const Edge& v) const {
    … …  
    760592      }
    761593    };
     594
     595    using Parent::forward;
     596    using Parent::backward;
     597    bool forward(const Edge& e) const { return !e.backward; }
     598    bool backward(const Edge& e) const { return e.backward; }
    762599
    763600    using Parent::first;
    … …  
    771608    }
    772609    void firstIn(Edge& i, const Node& n) const {
    773       Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
    774       i.backward=false;
    775       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     610      if (!backward(n)) {
     611        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     612        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     613          i=INVALID;
     614        else
     615          i.backward=false;
     616      } else {
    776617        Parent2::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
    777618        i.backward=true;
    … …  
    779620    }
    780621    void firstOut(Edge& i, const Node& n) const {
    781       Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
    782       i.backward=false;
    783       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     622      if (!backward(n)) {
     623        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     624        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     625          i=INVALID;
     626        else
     627          i.backward=false;
     628      } else {
    784629        Parent2::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
    785630        i.backward=true;
    … …  
    802647      if (!(i.backward)) {
    803648        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    804         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    805           Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
    806           i.backward=true;
    807         }
     649        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    808650      } else {
    809651        Parent2::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    … …  
    813655      if (!(i.backward)) {
    814656        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    815         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    816           Parent2::graph->first(*static_cast<Graph1Edge*>(&i));
    817           i.backward=true;
    818         }
     657        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    819658      } else {
    820659        Parent2::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    … …  
    946785    };
    947786
     787    using Parent::forward;
     788    using Parent::backward;
     789    bool forward(const Edge& e) const { return !e.backward; }
     790    bool backward(const Edge& e) const { return e.backward; }
     791
    948792    using Parent::first;
    949793    void first(Edge& i) const {
    … …  
    956800    }
    957801    void firstIn(Edge& i, const Node& n) const {
    958       Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
    959       i.backward=false;
    960       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     802      if (!backward(n)) {
     803        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     804        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     805          i=INVALID;
     806        else
     807          i.backward=false;
     808      } else {
    961809        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
    962810        i.backward=true;
    … …  
    964812    }
    965813    void firstOut(Edge& i, const Node& n) const {
    966       Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
    967       i.backward=false;
    968       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     814      if (!backward(n)) {
     815        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     816        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     817          i=INVALID;
     818        else   
     819          i.backward=false;
     820      } else {
    969821        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
    970822        i.backward=true;
    … …  
    987839      if (!(i.backward)) {
    988840        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    989         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    990           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    991           i.backward=true;
    992         }
     841        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    993842      } else {
    994843        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
    … …  
    998847      if (!(i.backward)) {
    999848        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    1000         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    1001           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    1002           i.backward=true;
    1003         }
     849        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    1004850      } else {
    1005851        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
    … …  
    1130976    };
    1131977
     978    using Parent::forward;
     979    using Parent::backward;
     980    bool forward(const Edge& e) const { return !e.backward; }
     981    bool backward(const Edge& e) const { return e.backward; }
     982
    1132983    using Parent::first;
    1133984    void first(Edge& i) const {
    … …  
    1140991    }
    1141992    void firstIn(Edge& i, const Node& n) const {
    1142       Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
    1143       i.backward=false;
    1144       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     993      if (!backward(n)) {
     994        Parent1::graph->firstIn(*static_cast<Graph1Edge*>(&i), n);
     995        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     996          i=INVALID;
     997        else
     998          i.backward=false;
     999      } else {
    11451000        Parent2::graph->firstIn(*static_cast<Graph2Edge*>(&i), n);
    11461001        i.backward=true;
    … …  
    11481003    }
    11491004    void firstOut(Edge& i, const Node& n) const {
    1150       Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
    1151       i.backward=false;
    1152       if (*static_cast<Graph1Edge*>(&i)==INVALID) {
     1005      if (!backward(n)) {
     1006        Parent1::graph->firstOut(*static_cast<Graph1Edge*>(&i), n);
     1007        if (*static_cast<Graph1Edge*>(&i)==INVALID)
     1008          i=INVALID;
     1009        else   
     1010          i.backward=false;
     1011      } else {
    11531012        Parent2::graph->firstOut(*static_cast<Graph2Edge*>(&i), n);
    11541013        i.backward=true;
    … …  
    11711030      if (!(i.backward)) {
    11721031        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    1173         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    1174           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    1175           i.backward=true;
    1176         }
     1032        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    11771033      } else {
    11781034        Parent2::graph->nextIn(*static_cast<Graph2Edge*>(&i));
    … …  
    11821038      if (!(i.backward)) {
    11831039        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    1184         if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    1185           Parent2::graph->first(*static_cast<Graph2Edge*>(&i));
    1186           i.backward=true;
    1187         }
     1040        if (*static_cast<Graph1Edge*>(&i)==INVALID) i=INVALID;
    11881041      } else {
    11891042        Parent2::graph->nextOut(*static_cast<Graph2Edge*>(&i));
    … …  
    13481201    int edgeNum() const { return edge_set_graph->edgeNum(); }
    13491202
     1203//     NNode addOldNode() {
     1204//       return Parent::addNode();
     1205//     }
     1206
     1207//     ENode addNewNode() {
     1208//       return edge_set_graph->addNode();
     1209//     }
     1210
    13501211    Edge addEdge(const Node& u, const Node& v) {
    13511212      return edge_set_graph->addEdge((*e_node)[u], (*e_node)[v]);
    … …  
    13931254    typedef _EdgeSetGraph EdgeSetGraph;
    13941255    typedef IterableGraphExtender<
    1395       NewEdgeSetGraphWrapper<_Graph, _EdgeSetGraph> > Parent;
     1256      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
    13961257  protected:
    13971258    NewEdgeSetGraphWrapper() { }
    … …  
    14101271  };
    14111272
     1273  /*! A graph wrapper class for the following functionality.
     1274    The same as NewEdgeSetGrapWrapper, but the bijection and the graph of
     1275    new edges is andled inthe class.
     1276   */
     1277  template <typename _Graph, typename _EdgeSetGraph>
     1278  class NewEdgeSetGraphWrapper2 :
     1279    public IterableGraphExtender<
     1280    NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > {
     1281  public:
     1282    typedef _Graph Graph;
     1283    typedef _EdgeSetGraph EdgeSetGraph;
     1284    typedef IterableGraphExtender<
     1285      NewEdgeSetGraphWrapperBase<_Graph, _EdgeSetGraph> > Parent;
     1286  protected:
     1287    _EdgeSetGraph _edge_set_graph;
     1288    typename Graph::template NodeMap<typename EdgeSetGraph::Node> _e_node;
     1289    typename EdgeSetGraph::template NodeMap<typename Graph::Node> _n_node;
     1290    NewEdgeSetGraphWrapper2() { }
     1291  public:
     1292    typedef typename Graph::Node Node;
     1293    //    typedef typename Parent::Edge Edge;
     1294
     1295    NewEdgeSetGraphWrapper2(_Graph& _graph) :
     1296      _edge_set_graph(),
     1297      _e_node(_graph), _n_node(_edge_set_graph) {
     1298      setGraph(_graph);
     1299      setEdgeSetGraph(_edge_set_graph);
     1300      setNodeMap(_n_node); setENodeMap(_e_node);
     1301      Node n;
     1302      for (this->first(n); n!=INVALID; this->next(n)) {
     1303        typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
     1304        _e_node.set(n, e);
     1305        _n_node.set(e, n);
     1306      }
     1307    }
     1308
     1309//     Node addNode() {
     1310//       Node n=(*this).Parent::addNode();
     1311//       typename EdgeSetGraph::Node e=_edge_set_graph.addNode();
     1312//       _e_node.set(n, e);
     1313//       _n_node.set(e, n);
     1314//       return n;
     1315//     }
     1316
     1317  };
    14121318
    14131319  /*! A graph wrapper base class
    … …  
    14181324    In an other point of view, _Graph1 is extended with
    14191325    the edge-set of _Graph2.
     1326    \warning we need specialize dimplementations
     1327    \todo we need specialize dimplementations
     1328    \bug we need specialize dimplementations
    14201329   */
    14211330  template <typename _Graph1, typename _Graph2, typename Enable=void>
    … …  
    15071416    void nextIn(Edge& i) const {
    15081417      if (!(i.backward)) {
     1418        Node n=target(i);
    15091419        Parent1::graph->nextIn(*static_cast<Graph1Edge*>(&i));
    15101420        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    1511           graph2->first(*static_cast<Graph2Edge*>(&i));
     1421          graph2->firstIn(*static_cast<Graph2Edge*>(&i), n);
    15121422          i.backward=true;
    15131423        }
    … …  
    15181428    void nextOut(Edge& i) const {
    15191429      if (!(i.backward)) {
     1430        Node n=source(i);
    15201431        Parent1::graph->nextOut(*static_cast<Graph1Edge*>(&i));
    15211432        if (*static_cast<Graph1Edge*>(&i)==INVALID) {
    1522           graph2->first(*static_cast<Graph2Edge*>(&i));
     1433          graph2->firstOut(*static_cast<Graph2Edge*>(&i), n);
    15231434          i.backward=true;
    15241435        }

  • src/work/marci/merge_node_graph_wrapper_test.cc

    r1016 r1025  
    55#include <lemon/smart_graph.h>
    66#include <lemon/dimacs.h>
     7#include <lemon/preflow.h>
    78#include <lemon/full_graph.h>
    89#include <merge_node_graph_wrapper.h>
    … …  
    2728  cout << " nodes:" << endl;
    2829  for (typename Graph::NodeIt n(g); n!=INVALID; ++n) {
    29     cout << "  " << g.id(n) << endl;
     30    cout << "  " << g.id(n) << ": out edges:" << endl;
     31    for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e)
     32      cout << "   " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
    3033  }
    3134  cout << " edges:" << endl;
    32   for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) {
    33     cout << "  " << g.id(n) << ": "
    34          << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl;
     35  for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) {
     36    cout << "   " << g.id(e) << ": "
     37         << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl;
    3538  } 
    3639}
    … …  
    3942  {
    4043    cout << "FIRST TEST" << endl;
    41     typedef SmartGraph Graph1;
     44    //typedef SmartGraph Graph1;
     45    typedef ListGraph Graph1;
    4246    typedef ListGraph Graph2;
     47    typedef SmartGraph Graph3;
    4348   
    44     {
    45       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
    46       MergeEdgeGraphWrapper<Graph1, Graph2>::printNode();
    47       MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge();
    48       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
    49       MergeEdgeGraphWrapper<Graph1, Graph1>::printNode();
    50       MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge();
    51       typedef ResGraphWrapper<Graph1, int,
    52         ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
    53       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();   
    54       MergeEdgeGraphWrapper<Graph1, Graph4>::printNode();
    55       MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
    56       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();   
    57       MergeEdgeGraphWrapper<Graph4, Graph1>::printNode();
    58       MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge(); 
    59     }
     49//     {
     50//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >();   
     51//       MergeEdgeGraphWrapper<Graph1, Graph2>::printNode();
     52//       MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge();
     53//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >();   
     54//       MergeEdgeGraphWrapper<Graph1, Graph1>::printNode();
     55//       MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge();
     56//       typedef ResGraphWrapper<Graph1, int,
     57//      ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4;
     58//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >();   
     59//       MergeEdgeGraphWrapper<Graph1, Graph4>::printNode();
     60//       MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge();
     61//       checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >();   
     62//       MergeEdgeGraphWrapper<Graph4, Graph1>::printNode();
     63//       MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge(); 
     64//     }
    6065 
    6166    Graph1 g1;
    … …  
    6368    typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
    6469    GW gw(g1, g2);
     70    Graph1::Node s1, t1;
     71    Graph2::Node s2, t2;
     72    Graph1::EdgeMap<int> cap1(g1);
     73    Graph2::EdgeMap<int> cap2(g2);
    6574
    6675    std::ifstream f1("graph1.dim");
    … …  
    6877    readDimacs(f1, g1);
    6978    readDimacs(f2, g2);
     79
     80//     GW::NodeMap<int> ize(gw, 8);
     81//     for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9);
     82//     GW::EdgeMap<int> mize(gw, 8);
     83//     for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7);
     84
     85//     std::ifstream f1("flow-1.dim");
     86//     std::ifstream f2("flow2.dim");
     87//     readDimacs(f1, g1, cap1, s1, t1);
     88//     readDimacs(f2, g2, cap2, s2, t2);
    7089   
    71     cout << "1st graph" << endl;
    72     printGraph(g1);
    73 
    74     cout << "2nd graph" << endl;
    75     printGraph(g2);
    76 
    77     cout << "merged graph" << endl;
    78     printGraph(gw);
    79 
     90//     GW::EdgeMap<int> cap(gw);
     91//     for (GW::EdgeIt e(gw); e!=INVALID; ++e) {
     92//       if (gw.forward(e)) cap.set(e, cap1[e]);
     93//       if (gw.backward(e)) cap.set(e, cap2[e]);
     94//     }
     95
     96//     {
     97//       GW::EdgeMap<int> flow(gw, 0);
     98//       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false),
     99//                             GW::Node(t1, INVALID, false), cap, flow);
     100//       preflow.run();
     101//       std::cout << "s1->t1: " << preflow.flowValue() << std::endl;
     102//     }
     103//     {
     104//       GW::EdgeMap<int> flow(gw, 0);
     105//       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true),
     106//                             GW::Node(INVALID, t2, true), cap, flow);
     107//       preflow.run();
     108//       std::cout << "s2->t2: " << preflow.flowValue() << std::endl;
     109//     }
     110//     {
     111//       GW::EdgeMap<int> flow(gw, 0);
     112//       Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false),
     113//                             GW::Node(INVALID, t2, true), cap, flow);
     114//       preflow.run();
     115//       std::cout << "s1->t2: " << preflow.flowValue() << std::endl;
     116//     }
     117//     {
     118//       GW::EdgeMap<int> flow(gw, 0);
     119//       Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true),
     120//                             GW::Node(s1, INVALID, false), cap, flow);
     121//       preflow.run();
     122//       std::cout << "s2->t1: " << preflow.flowValue() << std::endl;
     123//     }
     124     cout << "1st graph" << endl;
     125     printGraph(g1);
     126
     127     cout << "2nd graph" << endl;
     128     printGraph(g2);
     129
     130     cout << "merged graph" << endl;
     131     printGraph(gw);
     132     
     133//      for (GW::NodeIt n(gw); n!=INVALID; ++n)
     134//        std::cout << ize[n] << std::endl;
     135//      for (GW::EdgeIt n(gw); n!=INVALID; ++n)
     136//        std::cout << mize[n] << std::endl;
     137     
     138     typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW;
     139//     {
     140//       checkConcept<StaticGraph, GWW>();   
     141//     }
     142
     143     GWW gww(gw);
     144 
     145     cout << "new edges graph" << endl;
     146     printGraph(gww);
     147
     148     GWW::NodeIt n(gww);
     149     GWW::Node n1=n;
     150     ++n;
     151     GWW::Node n2=n;
     152     gww.addEdge(n1, n2);
     153     //     gww.addNode();
     154     //     gww.addNode();
     155
     156     cout << "new edges graph" << endl;
     157     printGraph(gww);
     158
     159     typedef AugmentingGraphWrapper<GW, GWW> GWWW;
     160     //     {
     161     //       checkConcept<StaticGraph, GWWW>();   
     162     //     }
     163     GWWW gwww(gw, gww);
     164
     165     cout << "fully merged graph" << endl;
     166     printGraph(gwww);
    80167  }
    81168
    … …  
    84171    cout << "SECOND TEST" << endl;
    85172    typedef SmartGraph Graph1;
    86     {
    87       checkConcept<StaticGraph, Graph1>();
    88     }
     173//     {
     174//       checkConcept<StaticGraph, Graph1>();
     175//     }
    89176
    90177    Graph1 g1;
    … …  
    94181    typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> >
    95182      Graph2;
    96     {
    97       checkConcept<StaticGraph, Graph2>();
    98     }
     183//     {
     184//       checkConcept<StaticGraph, Graph2>();
     185//     }
    99186
    100187    Graph2 g2(pre_g2, const_false_map);
    101188
    102189    typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW;
    103     {
    104       checkConcept<StaticGraph, GW>();   
    105     }
     190//     {
     191//       checkConcept<StaticGraph, GW>();   
     192//     }
    106193    GW gw(g1, g2);
    107194    GW::Node sw;
    … …  
    138225
    139226    typedef NewEdgeSetGraphWrapper<GW, Graph3> GWW;
    140     {
    141       checkConcept<StaticGraph, GWW>();   
    142     }
     227//     {
     228//       checkConcept<StaticGraph, GWW>();   
     229//     }
    143230
    144231    GWW gww(gw, g3, gwn, g3n);
    … …  
    159246
    160247    typedef AugmentingGraphWrapper<GW, GWW> GWWW;
    161     {
    162       checkConcept<StaticGraph, GWWW>();   
    163     }
     248//     {
     249//       checkConcept<StaticGraph, GWWW>();   
     250//     }
    164251    GWWW gwww(gw, gww);
    165252
Note: See TracChangeset for help on using the changeset viewer.