COIN-OR::LEMON - Graph Library

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


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
Files:
3 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
  • lemon/graph_utils.h

    r1695 r1704  
    161161  }
    162162
    163   /// \brief Function to count the number of the in-edges to node \c n.
    164   ///
    165   /// This function counts the number of the in-edges to node \c n
     163  /// \brief Function to count the number of the inc-edges to node \c n.
     164  ///
     165  /// This function counts the number of the inc-edges to node \c n
    166166  /// in the graph. 
    167167  template <typename Graph>
     
    215215  // /// \todo We may want to use the "GraphBase"
    216216  // /// interface here...
    217   // /// It would not work with the undirected graphs.
    218217  template <typename Graph>
    219218  inline typename Graph::Edge findEdge(const Graph &g,
     
    265264    ConEdgeIt& operator++() {
    266265      Parent::operator=(findEdge(graph, graph.source(*this),
     266                                 graph.target(*this), *this));
     267      return *this;
     268    }
     269  private:
     270    const Graph& graph;
     271  };
     272
     273  template <typename Graph>
     274  inline
     275  typename enable_if<
     276    typename Graph::FindEdgeTag,
     277    typename Graph::UndirEdge>::type
     278  _findUndirEdge(const Graph &g,
     279            typename Graph::Node u, typename Graph::Node v,
     280            typename Graph::UndirEdge prev = INVALID) {
     281    return g.findUndirEdge(u, v, prev);
     282  }
     283
     284  template <typename Graph>
     285  inline typename Graph::UndirEdge
     286  _findUndirEdge(Wrap<Graph> w,
     287            typename Graph::Node u,
     288            typename Graph::Node v,
     289            typename Graph::UndirEdge prev = INVALID) {
     290    const Graph& g = w.value;
     291    if (prev == INVALID) {
     292      typename Graph::OutEdgeIt e(g, u);
     293      while (e != INVALID && g.target(e) != v) ++e;
     294      return e;
     295    } else {
     296      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
     297      while (e != INVALID && g.target(e) != v) ++e;
     298      return e;
     299    }
     300  }
     301
     302  /// \brief Finds an undir edge between two nodes of a graph.
     303  ///
     304  /// Finds an undir edge from node \c u to node \c v in graph \c g.
     305  ///
     306  /// If \c prev is \ref INVALID (this is the default value), then
     307  /// it finds the first edge from \c u to \c v. Otherwise it looks for
     308  /// the next edge from \c u to \c v after \c prev.
     309  /// \return The found edge or \ref INVALID if there is no such an edge.
     310  ///
     311  /// Thus you can iterate through each edge from \c u to \c v as it follows.
     312  /// \code
     313  /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
     314  ///     e = findUndirEdge(g,u,v,e)) {
     315  ///   ...
     316  /// }
     317  /// \endcode
     318  // /// \todo We may want to use the "GraphBase"
     319  // /// interface here...
     320  template <typename Graph>
     321  inline typename Graph::UndirEdge
     322  findUndirEdge(const Graph &g,
     323                typename Graph::Node u,
     324                typename Graph::Node v,
     325                typename Graph::UndirEdge prev = INVALID) {
     326    return _findUndirEdge<Graph>(g, u, v, prev);
     327  }
     328
     329  /// \brief Iterator for iterating on undir edges connected the same nodes.
     330  ///
     331  /// Iterator for iterating on undir edges connected the same nodes. It is
     332  /// higher level interface for the findUndirEdge() function. You can
     333  /// use it the following way:
     334  /// \code
     335  /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     336  ///   ...
     337  /// }
     338  /// \endcode
     339  ///
     340  /// \author Balazs Dezso
     341  template <typename _Graph>
     342  class ConUndirEdgeIt : public _Graph::UndirEdge {
     343  public:
     344
     345    typedef _Graph Graph;
     346    typedef typename Graph::UndirEdge Parent;
     347
     348    typedef typename Graph::UndirEdge UndirEdge;
     349    typedef typename Graph::Node Node;
     350
     351    /// \brief Constructor.
     352    ///
     353    /// Construct a new ConUndirEdgeIt iterating on the edges which
     354    /// connects the \c u and \c v node.
     355    ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
     356      Parent::operator=(findUndirEdge(graph, u, v));
     357    }
     358
     359    /// \brief Constructor.
     360    ///
     361    /// Construct a new ConUndirEdgeIt which continues the iterating from
     362    /// the \c e edge.
     363    ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
     364   
     365    /// \brief Increment operator.
     366    ///
     367    /// It increments the iterator and gives back the next edge.
     368    ConUndirEdgeIt& operator++() {
     369      Parent::operator=(findUndirEdge(graph, graph.source(*this),
    267370                                 graph.target(*this), *this));
    268371      return *this;
     
    553656    typedef _Item Key;
    554657
    555     typedef True NeedCopy;
    556 
    557658    /// \brief Constructor.
    558659    ///
     
    577678    class InverseMap {
    578679    public:
    579 
    580       typedef True NeedCopy;
    581680
    582681      /// \brief Constructor.
     
    9071006  public:
    9081007
    909     typedef True NeedCopy;
    910 
    9111008    typedef typename Graph::Node Value;
    9121009    typedef typename Graph::Edge Key;
     
    9481045  public:
    9491046
    950     typedef True NeedCopy;
    951 
    9521047    typedef typename Graph::Node Value;
    9531048    typedef typename Graph::Edge Key;
     
    9891084  public:
    9901085
    991     typedef True NeedCopy;
    992 
    9931086    typedef typename Graph::Edge Value;
    9941087    typedef typename Graph::UndirEdge Key;
     
    10291122  class BackwardMap {
    10301123  public:
    1031     typedef True NeedCopy;
    10321124
    10331125    typedef typename Graph::Edge Value;
     
    12971389
    12981390    static int index(int i, int j) {
    1299       int m = i > j ? i : j;
    13001391      if (i < j) {
    1301         return m * m + i;
     1392        return j * j + i;
    13021393      } else {
    1303         return m * m + m + j;
     1394        return i * i + i + j;
    13041395      }
    13051396    }
Note: See TracChangeset for help on using the changeset viewer.