COIN-OR::LEMON - Graph Library

Changeset 1565:96244ea562a3 in lemon-0.x


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

Improve findEdge interface
ConEdgeIt? is a high level replacement of findEdge

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1555 r1565  
    161161
    162162
    163   /// Finds an edge between two nodes of a graph.
    164 
     163  template <typename Graph>
     164  inline
     165  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
     166  _findEdge(const Graph &g,
     167            typename Graph::Node u, typename Graph::Node v,
     168            typename Graph::Edge prev = INVALID) {
     169    return g.findEdge(u, v, prev);
     170  }
     171
     172  template <typename Graph>
     173  inline typename Graph::Edge
     174  _findEdge(Wrap<Graph> w,
     175            typename Graph::Node u,
     176            typename Graph::Node v,
     177            typename Graph::Edge prev = INVALID) {
     178    const Graph& g = w.value;
     179    if (prev == INVALID) {
     180      typename Graph::OutEdgeIt e(g, u);
     181      while (e != INVALID && g.target(e) != v) ++e;
     182      return e;
     183    } else {
     184      typename Graph::OutEdgeIt e(g, prev); ++e;
     185      while (e != INVALID && g.target(e) != v) ++e;
     186      return e;
     187    }
     188  }
     189
     190  /// \brief Finds an edge between two nodes of a graph.
     191  ///
    165192  /// Finds an edge from node \c u to node \c v in graph \c g.
    166193  ///
     
    176203  /// }
    177204  /// \endcode
    178   /// \todo We may want to use the "GraphBase"
    179   /// interface here...
    180   /// \bug Untested ...
    181   template <typename Graph>
    182   typename Graph::Edge findEdge(const Graph &g,
    183                                 typename Graph::Node u, typename Graph::Node v,
    184                                 typename Graph::Edge prev = INVALID)
    185   {
    186     typename Graph::OutEdgeIt e(g,prev);
    187     //    if(prev==INVALID) g.first(e,u);
    188     if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u);
    189     else ++e;
    190     while(e!=INVALID && g.target(e)!=v) ++e;
    191     return e;
    192   }
     205  // /// \todo We may want to use the "GraphBase"
     206  // /// interface here...
     207  // /// It would not work with the undirected graphs.
     208  template <typename Graph>
     209  inline typename Graph::Edge findEdge(const Graph &g,
     210                                       typename Graph::Node u,
     211                                       typename Graph::Node v,
     212                                       typename Graph::Edge prev = INVALID) {
     213    return _findEdge<Graph>(g, u, v, prev);
     214  }
     215
     216  /// \brief Iterator for iterating on edges connected the same nodes.
     217  ///
     218  /// Iterator for iterating on edges connected the same nodes. It is
     219  /// higher level interface for the findEdge() function. You can
     220  /// use it the next way:
     221  /// \code
     222  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     223  ///   ...
     224  /// }
     225  /// \endcode
     226  ///
     227  /// \author Balazs Dezso
     228  template <typename _Graph>
     229  class ConEdgeIt : public _Graph::Edge {
     230  public:
     231
     232    typedef _Graph Graph;
     233    typedef typename Graph::Edge Parent;
     234
     235    typedef typename Graph::Edge Edge;
     236    typedef typename Graph::Node Node;
     237
     238    /// \brief Constructor.
     239    ///
     240    /// Construct a new ConEdgeIt iterating on the edges which
     241    /// connects the \c u and \c v node.
     242    ConEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
     243      Parent::operator=(findEdge(graph, u, v));
     244    }
     245
     246    /// \brief Constructor.
     247    ///
     248    /// Construct a new ConEdgeIt which continues the iterating from
     249    /// the \c e edge.
     250    ConEdgeIt(const Graph& g, Edge e) : Parent(e), graph(g) {}
     251   
     252    /// \brief Increment operator.
     253    ///
     254    /// It increments the iterator and gives back the next edge.
     255    ConEdgeIt& operator++() {
     256      Parent::operator=(findEdge(graph, graph.source(*this),
     257                                 graph.target(*this), *this));
     258      return *this;
     259    }
     260  private:
     261    const Graph& graph;
     262  };
    193263
    194264  /// \brief Copy a map.
Note: See TracChangeset for help on using the changeset viewer.