1.1 --- a/lemon/graph_utils.h Mon Mar 27 16:25:14 2006 +0000
1.2 +++ b/lemon/graph_utils.h Thu Mar 30 08:38:41 2006 +0000
1.3 @@ -102,8 +102,9 @@
1.4 /// The complexity of the function is O(n) because
1.5 /// it iterates on all of the items.
1.6
1.7 - template <typename Graph, typename ItemIt>
1.8 + template <typename Graph, typename Item>
1.9 inline int countItems(const Graph& g) {
1.10 + typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
1.11 int num = 0;
1.12 for (ItemIt it(g); it != INVALID; ++it) {
1.13 ++num;
1.14 @@ -113,15 +114,24 @@
1.15
1.16 // Node counting:
1.17
1.18 - template <typename Graph>
1.19 - inline typename enable_if<typename Graph::NodeNumTag, int>::type
1.20 - _countNodes(const Graph &g) {
1.21 - return g.nodeNum();
1.22 - }
1.23 + namespace _graph_utils_bits {
1.24 +
1.25 + template <typename Graph, typename Enable = void>
1.26 + struct CountNodesSelector {
1.27 + static int count(const Graph &g) {
1.28 + return countItems<Graph, typename Graph::Node>(g);
1.29 + }
1.30 + };
1.31
1.32 - template <typename Graph>
1.33 - inline int _countNodes(Wrap<Graph> w) {
1.34 - return countItems<Graph, typename Graph::NodeIt>(w.value);
1.35 + template <typename Graph>
1.36 + struct CountNodesSelector<
1.37 + Graph, typename
1.38 + enable_if<typename Graph::NodeNumTag, void>::type>
1.39 + {
1.40 + static int count(const Graph &g) {
1.41 + return g.nodeNum();
1.42 + }
1.43 + };
1.44 }
1.45
1.46 /// \brief Function to count the nodes in the graph.
1.47 @@ -134,20 +144,30 @@
1.48
1.49 template <typename Graph>
1.50 inline int countNodes(const Graph& g) {
1.51 - return _countNodes<Graph>(g);
1.52 + return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
1.53 }
1.54
1.55 +
1.56 // Edge counting:
1.57
1.58 - template <typename Graph>
1.59 - inline typename enable_if<typename Graph::EdgeNumTag, int>::type
1.60 - _countEdges(const Graph &g) {
1.61 - return g.edgeNum();
1.62 - }
1.63 + namespace _graph_utils_bits {
1.64 +
1.65 + template <typename Graph, typename Enable = void>
1.66 + struct CountEdgesSelector {
1.67 + static int count(const Graph &g) {
1.68 + return countItems<Graph, typename Graph::Edge>(g);
1.69 + }
1.70 + };
1.71
1.72 - template <typename Graph>
1.73 - inline int _countEdges(Wrap<Graph> w) {
1.74 - return countItems<Graph, typename Graph::EdgeIt>(w.value);
1.75 + template <typename Graph>
1.76 + struct CountEdgesSelector<
1.77 + Graph,
1.78 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.79 + {
1.80 + static int count(const Graph &g) {
1.81 + return g.edgeNum();
1.82 + }
1.83 + };
1.84 }
1.85
1.86 /// \brief Function to count the edges in the graph.
1.87 @@ -158,21 +178,28 @@
1.88
1.89 template <typename Graph>
1.90 inline int countEdges(const Graph& g) {
1.91 - return _countEdges<Graph>(g);
1.92 + return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
1.93 }
1.94
1.95 // Undirected edge counting:
1.96 + namespace _graph_utils_bits {
1.97 +
1.98 + template <typename Graph, typename Enable = void>
1.99 + struct CountUEdgesSelector {
1.100 + static int count(const Graph &g) {
1.101 + return countItems<Graph, typename Graph::UEdge>(g);
1.102 + }
1.103 + };
1.104
1.105 - template <typename Graph>
1.106 - inline
1.107 - typename enable_if<typename Graph::EdgeNumTag, int>::type
1.108 - _countUEdges(const Graph &g) {
1.109 - return g.uEdgeNum();
1.110 - }
1.111 -
1.112 - template <typename Graph>
1.113 - inline int _countUEdges(Wrap<Graph> w) {
1.114 - return countItems<Graph, typename Graph::UEdgeIt>(w.value);
1.115 + template <typename Graph>
1.116 + struct CountUEdgesSelector<
1.117 + Graph,
1.118 + typename enable_if<typename Graph::EdgeNumTag, void>::type>
1.119 + {
1.120 + static int count(const Graph &g) {
1.121 + return g.uEdgeNum();
1.122 + }
1.123 + };
1.124 }
1.125
1.126 /// \brief Function to count the undirected edges in the graph.
1.127 @@ -183,11 +210,11 @@
1.128
1.129 template <typename Graph>
1.130 inline int countUEdges(const Graph& g) {
1.131 - return _countUEdges<Graph>(g);
1.132 + return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
1.133 +
1.134 }
1.135
1.136
1.137 -
1.138 template <typename Graph, typename DegIt>
1.139 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
1.140 int num = 0;
1.141 @@ -224,32 +251,36 @@
1.142 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
1.143 }
1.144
1.145 + namespace _graph_utils_bits {
1.146 +
1.147 + template <typename Graph, typename Enable = void>
1.148 + struct FindEdgeSelector {
1.149 + typedef typename Graph::Node Node;
1.150 + typedef typename Graph::Edge Edge;
1.151 + static Edge find(const Graph &g, Node u, Node v, Edge e) {
1.152 + if (e == INVALID) {
1.153 + g.firstOut(e, u);
1.154 + } else {
1.155 + g.nextOut(e);
1.156 + }
1.157 + while (e != INVALID && g.target(e) != v) {
1.158 + g.nextOut(e);
1.159 + }
1.160 + return e;
1.161 + }
1.162 + };
1.163
1.164 - template <typename Graph>
1.165 - inline
1.166 - typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type
1.167 - _findEdge(const Graph &g,
1.168 - typename Graph::Node u, typename Graph::Node v,
1.169 - typename Graph::Edge prev = INVALID) {
1.170 - return g.findEdge(u, v, prev);
1.171 - }
1.172 -
1.173 - template <typename Graph>
1.174 - inline typename Graph::Edge
1.175 - _findEdge(Wrap<Graph> w,
1.176 - typename Graph::Node u,
1.177 - typename Graph::Node v,
1.178 - typename Graph::Edge prev = INVALID) {
1.179 - const Graph& g = w.value;
1.180 - if (prev == INVALID) {
1.181 - typename Graph::OutEdgeIt e(g, u);
1.182 - while (e != INVALID && g.target(e) != v) ++e;
1.183 - return e;
1.184 - } else {
1.185 - typename Graph::OutEdgeIt e(g, prev); ++e;
1.186 - while (e != INVALID && g.target(e) != v) ++e;
1.187 - return e;
1.188 - }
1.189 + template <typename Graph>
1.190 + struct FindEdgeSelector<
1.191 + Graph,
1.192 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.193 + {
1.194 + typedef typename Graph::Node Node;
1.195 + typedef typename Graph::Edge Edge;
1.196 + static Edge find(const Graph &g, Node u, Node v, Edge prev) {
1.197 + return g.findEdge(u, v, prev);
1.198 + }
1.199 + };
1.200 }
1.201
1.202 /// \brief Finds an edge between two nodes of a graph.
1.203 @@ -267,14 +298,12 @@
1.204 /// ...
1.205 /// }
1.206 ///\endcode
1.207 - // /// \todo We may want to use the "GraphBase"
1.208 - // /// interface here...
1.209 template <typename Graph>
1.210 inline typename Graph::Edge findEdge(const Graph &g,
1.211 typename Graph::Node u,
1.212 typename Graph::Node v,
1.213 typename Graph::Edge prev = INVALID) {
1.214 - return _findEdge<Graph>(g, u, v, prev);
1.215 + return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
1.216 }
1.217
1.218 /// \brief Iterator for iterating on edges connected the same nodes.
1.219 @@ -325,38 +354,57 @@
1.220 const Graph& graph;
1.221 };
1.222
1.223 - template <typename Graph>
1.224 - inline
1.225 - typename enable_if<
1.226 - typename Graph::FindEdgeTag,
1.227 - typename Graph::UEdge>::type
1.228 - _findUEdge(const Graph &g,
1.229 - typename Graph::Node u, typename Graph::Node v,
1.230 - typename Graph::UEdge prev = INVALID) {
1.231 - return g.findUEdge(u, v, prev);
1.232 - }
1.233 + namespace _graph_utils_bits {
1.234 +
1.235 + template <typename Graph, typename Enable = void>
1.236 + struct FindUEdgeSelector {
1.237 + typedef typename Graph::Node Node;
1.238 + typedef typename Graph::UEdge UEdge;
1.239 + static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
1.240 + bool b;
1.241 + if (u != v) {
1.242 + if (e == INVALID) {
1.243 + g.firstInc(e, u, b);
1.244 + } else {
1.245 + b = g.source(e) == u;
1.246 + g.nextInc(e, b);
1.247 + }
1.248 + while (e != INVALID && g.target(e) != v) {
1.249 + g.nextInc(e, b);
1.250 + }
1.251 + } else {
1.252 + if (e == INVALID) {
1.253 + g.firstInc(e, u, b);
1.254 + } else {
1.255 + b = true;
1.256 + g.nextInc(e, b);
1.257 + }
1.258 + while (e != INVALID && (!b || g.target(e) != v)) {
1.259 + g.nextInc(e, b);
1.260 + }
1.261 + }
1.262 + return e;
1.263 + }
1.264 + };
1.265
1.266 - template <typename Graph>
1.267 - inline typename Graph::UEdge
1.268 - _findUEdge(Wrap<Graph> w,
1.269 - typename Graph::Node u,
1.270 - typename Graph::Node v,
1.271 - typename Graph::UEdge prev = INVALID) {
1.272 - const Graph& g = w.value;
1.273 - if (prev == INVALID) {
1.274 - typename Graph::OutEdgeIt e(g, u);
1.275 - while (e != INVALID && g.target(e) != v) ++e;
1.276 - return e;
1.277 - } else {
1.278 - typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
1.279 - while (e != INVALID && g.target(e) != v) ++e;
1.280 - return e;
1.281 - }
1.282 + template <typename Graph>
1.283 + struct FindUEdgeSelector<
1.284 + Graph,
1.285 + typename enable_if<typename Graph::FindEdgeTag, void>::type>
1.286 + {
1.287 + typedef typename Graph::Node Node;
1.288 + typedef typename Graph::UEdge UEdge;
1.289 + static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
1.290 + return g.findUEdge(u, v, prev);
1.291 + }
1.292 + };
1.293 }
1.294
1.295 /// \brief Finds an uedge between two nodes of a graph.
1.296 ///
1.297 /// Finds an uedge from node \c u to node \c v in graph \c g.
1.298 + /// If the node \c u and node \c v is equal then each loop edge
1.299 + /// will be enumerated.
1.300 ///
1.301 /// If \c prev is \ref INVALID (this is the default value), then
1.302 /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.303 @@ -370,15 +418,12 @@
1.304 /// ...
1.305 /// }
1.306 ///\endcode
1.307 - // /// \todo We may want to use the "GraphBase"
1.308 - // /// interface here...
1.309 template <typename Graph>
1.310 - inline typename Graph::UEdge
1.311 - findUEdge(const Graph &g,
1.312 - typename Graph::Node u,
1.313 - typename Graph::Node v,
1.314 - typename Graph::UEdge prev = INVALID) {
1.315 - return _findUEdge<Graph>(g, u, v, prev);
1.316 + inline typename Graph::UEdge findEdge(const Graph &g,
1.317 + typename Graph::Node u,
1.318 + typename Graph::Node v,
1.319 + typename Graph::UEdge prev = INVALID) {
1.320 + return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev);
1.321 }
1.322
1.323 /// \brief Iterator for iterating on uedges connected the same nodes.