COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
10/05/05 15:17:42 (14 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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.