COIN-OR::LEMON - Graph Library

Changeset 1704:467d7927a901 in lemon-0.x for lemon/bits


Ignore:
Timestamp:
10/05/05 15:17:42 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2231
Message:

findUndirEdge, ConUndirEdgeIt?
some modification in the undir graph extenders

Location:
lemon/bits
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/iterable_graph_extender.h

    r1627 r1704  
    217217    class IncEdgeIt : public Parent::UndirEdge {
    218218      const Graph* graph;
    219       bool forward;
     219      bool direction;
    220220      friend class IterableUndirGraphExtender;
    221       template <typename G>
    222       friend class UndirGraphExtender;
    223221    public:
    224222
    225223      IncEdgeIt() { }
    226224
    227       IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
    228 
    229       IncEdgeIt(const Graph& _graph, const Node &n)
    230         : graph(&_graph)
    231       {
    232         _graph._dirFirstOut(*this, n);
     225      IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }
     226
     227      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     228        _graph.firstInc(*this, direction, n);
    233229      }
    234230
    235231      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
    236         : graph(&_graph), UndirEdge(ue)
    237       {
    238         forward = (_graph.source(ue) == n);
     232        : graph(&_graph), UndirEdge(ue) {
     233        direction = (_graph.source(ue) == n);
    239234      }
    240235
    241236      IncEdgeIt& operator++() {
    242         graph->_dirNextOut(*this);
     237        graph->nextInc(*this, direction);
    243238        return *this;
    244239      }
     
    252247    /// Returns the base node of the iterator
    253248    Node baseNode(const IncEdgeIt &e) const {
    254       return _dirSource(e);
     249      return e.direction ? source(e) : target(e);
    255250    }
    256251    /// Running node of the iterator
     
    258253    /// Returns the running node of the iterator
    259254    Node runningNode(const IncEdgeIt &e) const {
    260       return _dirTarget(e);
     255      return e.direction ? target(e) : source(e);
    261256    }
    262257
  • lemon/bits/undir_graph_extender.h

    r1627 r1704  
    7272    }
    7373
    74   protected:
    75 
    76     template <typename E>
    77     Node _dirSource(const E &e) const {
    78       return e.forward ? Parent::source(e) : Parent::target(e);
    79     }
    80 
    81     template <typename E>
    82     Node _dirTarget(const E &e) const {
    83       return e.forward ? Parent::target(e) : Parent::source(e);
    84     }
    85 
    8674  public:
    8775    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
     
    9179    /// Source of the given Edge.
    9280    Node source(const Edge &e) const {
    93       return _dirSource(e);
     81      return e.forward ? Parent::source(e) : Parent::target(e);
    9482    }
    9583
     
    10088    /// Target of the given Edge.
    10189    Node target(const Edge &e) const {
    102       return _dirTarget(e);
     90      return e.forward ? Parent::target(e) : Parent::source(e);
    10391    }
    10492
     
    155143    }
    156144
    157    
    158   protected:
    159 
    160     template <typename E>
    161     void _dirFirstOut(E &e, const Node &n) const {
     145  public:
     146
     147    void firstOut(Edge &e, const Node &n) const {
    162148      Parent::firstIn(e,n);
    163149      if( UndirEdge(e) != INVALID ) {
     
    169155      }
    170156    }
    171     template <typename E>
    172     void _dirFirstIn(E &e, const Node &n) const {
    173       Parent::firstOut(e,n);
    174       if( UndirEdge(e) != INVALID ) {
    175         e.forward = false;
    176       }
    177       else {
    178         Parent::firstIn(e,n);
    179         e.forward = true;
    180       }
    181     }
    182 
    183     template <typename E>
    184     void _dirNextOut(E &e) const {
     157    void nextOut(Edge &e) const {
    185158      if( ! e.forward ) {
    186159        Node n = Parent::target(e);
     
    195168      }
    196169    }
    197     template <typename E>
    198     void _dirNextIn(E &e) const {
     170
     171    void firstIn(Edge &e, const Node &n) const {
     172      Parent::firstOut(e,n);
     173      if( UndirEdge(e) != INVALID ) {
     174        e.forward = false;
     175      }
     176      else {
     177        Parent::firstIn(e,n);
     178        e.forward = true;
     179      }
     180    }
     181    void nextIn(Edge &e) const {
    199182      if( ! e.forward ) {
    200183        Node n = Parent::source(e);
     
    210193    }
    211194
    212   public:
    213 
    214     void firstOut(Edge &e, const Node &n) const {
    215       _dirFirstOut(e, n);
    216     }
    217     void firstIn(Edge &e, const Node &n) const {
    218       _dirFirstIn(e, n);
    219     }
    220 
    221     void nextOut(Edge &e) const {
    222       _dirNextOut(e);
    223     }
    224     void nextIn(Edge &e) const {
    225       _dirNextIn(e);
     195    void firstInc(UndirEdge &e, const Node &n) const {
     196      Parent::firstOut(e, n);
     197      if (e != INVALID) return;
     198      Parent::firstIn(e, n);
     199    }
     200    void nextInc(UndirEdge &e, const Node &n) const {
     201      if (Parent::source(e) == n) {
     202        Parent::nextOut(e);
     203        if (e != INVALID) return;
     204        Parent::firstIn(e, n);
     205      } else {
     206        Parent::nextIn(e);
     207      }
     208    }
     209
     210    void firstInc(UndirEdge &e, bool &d, const Node &n) const {
     211      d = true;
     212      Parent::firstOut(e, n);
     213      if (e != INVALID) return;
     214      d = false;
     215      Parent::firstIn(e, n);
     216    }
     217    void nextInc(UndirEdge &e, bool &d) const {
     218      if (d) {
     219        Node s = Parent::source(e);
     220        Parent::nextOut(e);
     221        if (e != INVALID) return;
     222        d = false;
     223        Parent::firstIn(e, s);
     224      } else {
     225        Parent::nextIn(e);
     226      }
    226227    }
    227228
     
    263264      return 2 * Parent::edgeNum();
    264265    }
     266
    265267    int undirEdgeNum() const {
    266268      return Parent::edgeNum();
    267269    }
    268270
     271    Edge findEdge(Node source, Node target, Edge prev) const {
     272      if (prev == INVALID) {
     273        UndirEdge edge = Parent::findEdge(source, target);
     274        if (edge != INVALID) return direct(edge, true);
     275        edge = Parent::findEdge(target, source);
     276        if (edge != INVALID) return direct(edge, false);
     277      } else if (direction(prev)) {
     278        UndirEdge edge = Parent::findEdge(source, target, prev);
     279        if (edge != INVALID) return direct(edge, true);
     280        edge = Parent::findEdge(target, source);
     281        if (edge != INVALID) return direct(edge, false);       
     282      } else {
     283        UndirEdge edge = Parent::findEdge(target, source, prev);
     284        if (edge != INVALID) return direct(edge, false);             
     285      }
     286      return INVALID;
     287    }
     288
     289    UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
     290      if (prev == INVALID) {
     291        UndirEdge edge = Parent::findEdge(source, target);
     292        if (edge != INVALID) return edge;
     293        edge = Parent::findEdge(target, source);
     294        if (edge != INVALID) return edge;
     295      } else if (Parent::source(prev) == source) {
     296        UndirEdge edge = Parent::findEdge(source, target, prev);
     297        if (edge != INVALID) return edge;
     298        edge = Parent::findEdge(target, source);
     299        if (edge != INVALID) return edge;       
     300      } else {
     301        UndirEdge edge = Parent::findEdge(target, source, prev);
     302        if (edge != INVALID) return edge;             
     303      }
     304      return INVALID;
     305    }
     306
    269307  };
    270308
Note: See TracChangeset for help on using the changeset viewer.