1.1 --- a/lemon/graph_utils.h Wed Oct 05 13:15:47 2005 +0000
1.2 +++ b/lemon/graph_utils.h Wed Oct 05 13:17:42 2005 +0000
1.3 @@ -160,9 +160,9 @@
1.4 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
1.5 }
1.6
1.7 - /// \brief Function to count the number of the in-edges to node \c n.
1.8 + /// \brief Function to count the number of the inc-edges to node \c n.
1.9 ///
1.10 - /// This function counts the number of the in-edges to node \c n
1.11 + /// This function counts the number of the inc-edges to node \c n
1.12 /// in the graph.
1.13 template <typename Graph>
1.14 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
1.15 @@ -214,7 +214,6 @@
1.16 /// \endcode
1.17 // /// \todo We may want to use the "GraphBase"
1.18 // /// interface here...
1.19 - // /// It would not work with the undirected graphs.
1.20 template <typename Graph>
1.21 inline typename Graph::Edge findEdge(const Graph &g,
1.22 typename Graph::Node u,
1.23 @@ -271,6 +270,110 @@
1.24 const Graph& graph;
1.25 };
1.26
1.27 + template <typename Graph>
1.28 + inline
1.29 + typename enable_if<
1.30 + typename Graph::FindEdgeTag,
1.31 + typename Graph::UndirEdge>::type
1.32 + _findUndirEdge(const Graph &g,
1.33 + typename Graph::Node u, typename Graph::Node v,
1.34 + typename Graph::UndirEdge prev = INVALID) {
1.35 + return g.findUndirEdge(u, v, prev);
1.36 + }
1.37 +
1.38 + template <typename Graph>
1.39 + inline typename Graph::UndirEdge
1.40 + _findUndirEdge(Wrap<Graph> w,
1.41 + typename Graph::Node u,
1.42 + typename Graph::Node v,
1.43 + typename Graph::UndirEdge prev = INVALID) {
1.44 + const Graph& g = w.value;
1.45 + if (prev == INVALID) {
1.46 + typename Graph::OutEdgeIt e(g, u);
1.47 + while (e != INVALID && g.target(e) != v) ++e;
1.48 + return e;
1.49 + } else {
1.50 + typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
1.51 + while (e != INVALID && g.target(e) != v) ++e;
1.52 + return e;
1.53 + }
1.54 + }
1.55 +
1.56 + /// \brief Finds an undir edge between two nodes of a graph.
1.57 + ///
1.58 + /// Finds an undir edge from node \c u to node \c v in graph \c g.
1.59 + ///
1.60 + /// If \c prev is \ref INVALID (this is the default value), then
1.61 + /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.62 + /// the next edge from \c u to \c v after \c prev.
1.63 + /// \return The found edge or \ref INVALID if there is no such an edge.
1.64 + ///
1.65 + /// Thus you can iterate through each edge from \c u to \c v as it follows.
1.66 + /// \code
1.67 + /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
1.68 + /// e = findUndirEdge(g,u,v,e)) {
1.69 + /// ...
1.70 + /// }
1.71 + /// \endcode
1.72 + // /// \todo We may want to use the "GraphBase"
1.73 + // /// interface here...
1.74 + template <typename Graph>
1.75 + inline typename Graph::UndirEdge
1.76 + findUndirEdge(const Graph &g,
1.77 + typename Graph::Node u,
1.78 + typename Graph::Node v,
1.79 + typename Graph::UndirEdge prev = INVALID) {
1.80 + return _findUndirEdge<Graph>(g, u, v, prev);
1.81 + }
1.82 +
1.83 + /// \brief Iterator for iterating on undir edges connected the same nodes.
1.84 + ///
1.85 + /// Iterator for iterating on undir edges connected the same nodes. It is
1.86 + /// higher level interface for the findUndirEdge() function. You can
1.87 + /// use it the following way:
1.88 + /// \code
1.89 + /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
1.90 + /// ...
1.91 + /// }
1.92 + /// \endcode
1.93 + ///
1.94 + /// \author Balazs Dezso
1.95 + template <typename _Graph>
1.96 + class ConUndirEdgeIt : public _Graph::UndirEdge {
1.97 + public:
1.98 +
1.99 + typedef _Graph Graph;
1.100 + typedef typename Graph::UndirEdge Parent;
1.101 +
1.102 + typedef typename Graph::UndirEdge UndirEdge;
1.103 + typedef typename Graph::Node Node;
1.104 +
1.105 + /// \brief Constructor.
1.106 + ///
1.107 + /// Construct a new ConUndirEdgeIt iterating on the edges which
1.108 + /// connects the \c u and \c v node.
1.109 + ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
1.110 + Parent::operator=(findUndirEdge(graph, u, v));
1.111 + }
1.112 +
1.113 + /// \brief Constructor.
1.114 + ///
1.115 + /// Construct a new ConUndirEdgeIt which continues the iterating from
1.116 + /// the \c e edge.
1.117 + ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
1.118 +
1.119 + /// \brief Increment operator.
1.120 + ///
1.121 + /// It increments the iterator and gives back the next edge.
1.122 + ConUndirEdgeIt& operator++() {
1.123 + Parent::operator=(findUndirEdge(graph, graph.source(*this),
1.124 + graph.target(*this), *this));
1.125 + return *this;
1.126 + }
1.127 + private:
1.128 + const Graph& graph;
1.129 + };
1.130 +
1.131 /// \brief Copy a map.
1.132 ///
1.133 /// This function copies the \c source map to the \c target map. It uses the
1.134 @@ -552,8 +655,6 @@
1.135 typedef _Item Item;
1.136 typedef _Item Key;
1.137
1.138 - typedef True NeedCopy;
1.139 -
1.140 /// \brief Constructor.
1.141 ///
1.142 /// Constructor for creating id map.
1.143 @@ -577,8 +678,6 @@
1.144 class InverseMap {
1.145 public:
1.146
1.147 - typedef True NeedCopy;
1.148 -
1.149 /// \brief Constructor.
1.150 ///
1.151 /// Constructor for creating an id-to-item map.
1.152 @@ -906,8 +1005,6 @@
1.153 class SourceMap {
1.154 public:
1.155
1.156 - typedef True NeedCopy;
1.157 -
1.158 typedef typename Graph::Node Value;
1.159 typedef typename Graph::Edge Key;
1.160
1.161 @@ -947,8 +1044,6 @@
1.162 class TargetMap {
1.163 public:
1.164
1.165 - typedef True NeedCopy;
1.166 -
1.167 typedef typename Graph::Node Value;
1.168 typedef typename Graph::Edge Key;
1.169
1.170 @@ -988,8 +1083,6 @@
1.171 class ForwardMap {
1.172 public:
1.173
1.174 - typedef True NeedCopy;
1.175 -
1.176 typedef typename Graph::Edge Value;
1.177 typedef typename Graph::UndirEdge Key;
1.178
1.179 @@ -1028,7 +1121,6 @@
1.180 template <typename Graph>
1.181 class BackwardMap {
1.182 public:
1.183 - typedef True NeedCopy;
1.184
1.185 typedef typename Graph::Edge Value;
1.186 typedef typename Graph::UndirEdge Key;
1.187 @@ -1296,11 +1388,10 @@
1.188 protected:
1.189
1.190 static int index(int i, int j) {
1.191 - int m = i > j ? i : j;
1.192 if (i < j) {
1.193 - return m * m + i;
1.194 + return j * j + i;
1.195 } else {
1.196 - return m * m + m + j;
1.197 + return i * i + i + j;
1.198 }
1.199 }
1.200