1.1 --- a/lemon/connectivity.h Tue Dec 02 15:33:22 2008 +0000
1.2 +++ b/lemon/connectivity.h Wed Dec 03 14:23:22 2008 +0100
1.3 @@ -16,8 +16,8 @@
1.4 *
1.5 */
1.6
1.7 -#ifndef LEMON_TOPOLOGY_H
1.8 -#define LEMON_TOPOLOGY_H
1.9 +#ifndef LEMON_CONNECTIVITY_H
1.10 +#define LEMON_CONNECTIVITY_H
1.11
1.12 #include <lemon/dfs.h>
1.13 #include <lemon/bfs.h>
1.14 @@ -154,7 +154,7 @@
1.15 return compNum;
1.16 }
1.17
1.18 - namespace _topology_bits {
1.19 + namespace _connectivity_bits {
1.20
1.21 template <typename Digraph, typename Iterator >
1.22 struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
1.23 @@ -188,19 +188,19 @@
1.24 };
1.25
1.26 template <typename Digraph, typename ArcMap>
1.27 - struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
1.28 + struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
1.29 public:
1.30 typedef typename Digraph::Node Node;
1.31 typedef typename Digraph::Arc Arc;
1.32
1.33 - StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
1.34 - ArcMap& cutMap,
1.35 - int& cutNum)
1.36 + StronglyConnectedCutArcsVisitor(const Digraph& digraph,
1.37 + ArcMap& cutMap,
1.38 + int& cutNum)
1.39 : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
1.40 - _compMap(digraph), _num(0) {
1.41 + _compMap(digraph, -1), _num(-1) {
1.42 }
1.43
1.44 - void stop(const Node&) {
1.45 + void start(const Node&) {
1.46 ++_num;
1.47 }
1.48
1.49 @@ -248,7 +248,7 @@
1.50 typename Digraph::Node source = NodeIt(digraph);
1.51 if (source == INVALID) return true;
1.52
1.53 - using namespace _topology_bits;
1.54 + using namespace _connectivity_bits;
1.55
1.56 typedef DfsVisitor<Digraph> Visitor;
1.57 Visitor visitor;
1.58 @@ -265,6 +265,7 @@
1.59 }
1.60
1.61 typedef ReverseDigraph<const Digraph> RDigraph;
1.62 + typedef typename RDigraph::NodeIt RNodeIt;
1.63 RDigraph rdigraph(digraph);
1.64
1.65 typedef DfsVisitor<Digraph> RVisitor;
1.66 @@ -275,7 +276,7 @@
1.67 rdfs.addSource(source);
1.68 rdfs.start();
1.69
1.70 - for (NodeIt it(rdigraph); it != INVALID; ++it) {
1.71 + for (RNodeIt it(rdigraph); it != INVALID; ++it) {
1.72 if (!rdfs.reached(it)) {
1.73 return false;
1.74 }
1.75 @@ -302,7 +303,7 @@
1.76 int countStronglyConnectedComponents(const Digraph& digraph) {
1.77 checkConcept<concepts::Digraph, Digraph>();
1.78
1.79 - using namespace _topology_bits;
1.80 + using namespace _connectivity_bits;
1.81
1.82 typedef typename Digraph::Node Node;
1.83 typedef typename Digraph::Arc Arc;
1.84 @@ -374,7 +375,7 @@
1.85 typedef typename Digraph::NodeIt NodeIt;
1.86 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1.87
1.88 - using namespace _topology_bits;
1.89 + using namespace _connectivity_bits;
1.90
1.91 typedef std::vector<Node> Container;
1.92 typedef typename Container::iterator Iterator;
1.93 @@ -438,7 +439,7 @@
1.94 typedef typename Digraph::NodeIt NodeIt;
1.95 checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
1.96
1.97 - using namespace _topology_bits;
1.98 + using namespace _connectivity_bits;
1.99
1.100 typedef std::vector<Node> Container;
1.101 typedef typename Container::iterator Iterator;
1.102 @@ -463,7 +464,7 @@
1.103
1.104 int cutNum = 0;
1.105
1.106 - typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
1.107 + typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
1.108 RVisitor rvisitor(rgraph, cutMap, cutNum);
1.109
1.110 DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
1.111 @@ -478,7 +479,7 @@
1.112 return cutNum;
1.113 }
1.114
1.115 - namespace _topology_bits {
1.116 + namespace _connectivity_bits {
1.117
1.118 template <typename Digraph>
1.119 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.120 @@ -730,7 +731,7 @@
1.121 checkConcept<concepts::Graph, Graph>();
1.122 typedef typename Graph::NodeIt NodeIt;
1.123
1.124 - using namespace _topology_bits;
1.125 + using namespace _connectivity_bits;
1.126
1.127 typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
1.128
1.129 @@ -773,7 +774,7 @@
1.130 typedef typename Graph::Edge Edge;
1.131 checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
1.132
1.133 - using namespace _topology_bits;
1.134 + using namespace _connectivity_bits;
1.135
1.136 typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
1.137
1.138 @@ -813,7 +814,7 @@
1.139 typedef typename Graph::NodeIt NodeIt;
1.140 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
1.141
1.142 - using namespace _topology_bits;
1.143 + using namespace _connectivity_bits;
1.144
1.145 typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
1.146
1.147 @@ -832,7 +833,7 @@
1.148 return cutNum;
1.149 }
1.150
1.151 - namespace _topology_bits {
1.152 + namespace _connectivity_bits {
1.153
1.154 template <typename Digraph>
1.155 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
1.156 @@ -1053,7 +1054,7 @@
1.157 checkConcept<concepts::Graph, Graph>();
1.158 typedef typename Graph::NodeIt NodeIt;
1.159
1.160 - using namespace _topology_bits;
1.161 + using namespace _connectivity_bits;
1.162
1.163 typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
1.164
1.165 @@ -1095,7 +1096,7 @@
1.166 typedef typename Graph::Node Node;
1.167 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
1.168
1.169 - using namespace _topology_bits;
1.170 + using namespace _connectivity_bits;
1.171
1.172 typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
1.173
1.174 @@ -1136,7 +1137,7 @@
1.175 typedef typename Graph::Edge Edge;
1.176 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
1.177
1.178 - using namespace _topology_bits;
1.179 + using namespace _connectivity_bits;
1.180
1.181 typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
1.182
1.183 @@ -1156,7 +1157,7 @@
1.184 }
1.185
1.186
1.187 - namespace _topology_bits {
1.188 + namespace _connectivity_bits {
1.189
1.190 template <typename Digraph, typename IntNodeMap>
1.191 class TopologicalSortVisitor : public DfsVisitor<Digraph> {
1.192 @@ -1193,7 +1194,7 @@
1.193 /// \see dag
1.194 template <typename Digraph, typename NodeMap>
1.195 void topologicalSort(const Digraph& graph, NodeMap& order) {
1.196 - using namespace _topology_bits;
1.197 + using namespace _connectivity_bits;
1.198
1.199 checkConcept<concepts::Digraph, Digraph>();
1.200 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
1.201 @@ -1234,8 +1235,8 @@
1.202 /// \see topologicalSort
1.203 /// \see dag
1.204 template <typename Digraph, typename NodeMap>
1.205 - bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
1.206 - using namespace _topology_bits;
1.207 + bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
1.208 + using namespace _connectivity_bits;
1.209
1.210 checkConcept<concepts::Digraph, Digraph>();
1.211 checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
1.212 @@ -1245,21 +1246,23 @@
1.213 typedef typename Digraph::NodeIt NodeIt;
1.214 typedef typename Digraph::Arc Arc;
1.215
1.216 - order = constMap<Node, int, -1>();
1.217 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.218 + order.set(it, -1);
1.219 + }
1.220
1.221 TopologicalSortVisitor<Digraph, NodeMap>
1.222 - visitor(order, countNodes(graph));
1.223 + visitor(order, countNodes(digraph));
1.224
1.225 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
1.226 - dfs(graph, visitor);
1.227 + dfs(digraph, visitor);
1.228
1.229 dfs.init();
1.230 - for (NodeIt it(graph); it != INVALID; ++it) {
1.231 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.232 if (!dfs.reached(it)) {
1.233 dfs.addSource(it);
1.234 while (!dfs.emptyQueue()) {
1.235 - Arc edge = dfs.nextArc();
1.236 - Node target = graph.target(edge);
1.237 + Arc arc = dfs.nextArc();
1.238 + Node target = digraph.target(arc);
1.239 if (dfs.reached(target) && order[target] == -1) {
1.240 return false;
1.241 }
1.242 @@ -1279,7 +1282,7 @@
1.243 /// \return %False when the graph is not DAG.
1.244 /// \see acyclic
1.245 template <typename Digraph>
1.246 - bool dag(const Digraph& graph) {
1.247 + bool dag(const Digraph& digraph) {
1.248
1.249 checkConcept<concepts::Digraph, Digraph>();
1.250
1.251 @@ -1290,18 +1293,18 @@
1.252 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.253
1.254 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
1.255 - Create dfs(graph);
1.256 + Create dfs(digraph);
1.257
1.258 - ProcessedMap processed(graph);
1.259 + ProcessedMap processed(digraph);
1.260 dfs.processedMap(processed);
1.261
1.262 dfs.init();
1.263 - for (NodeIt it(graph); it != INVALID; ++it) {
1.264 + for (NodeIt it(digraph); it != INVALID; ++it) {
1.265 if (!dfs.reached(it)) {
1.266 dfs.addSource(it);
1.267 while (!dfs.emptyQueue()) {
1.268 Arc edge = dfs.nextArc();
1.269 - Node target = graph.target(edge);
1.270 + Node target = digraph.target(edge);
1.271 if (dfs.reached(target) && !processed[target]) {
1.272 return false;
1.273 }
1.274 @@ -1380,7 +1383,7 @@
1.275 return true;
1.276 }
1.277
1.278 - namespace _topology_bits {
1.279 + namespace _connectivity_bits {
1.280
1.281 template <typename Digraph>
1.282 class BipartiteVisitor : public BfsVisitor<Digraph> {
1.283 @@ -1449,7 +1452,7 @@
1.284 /// \sa bipartitePartitions
1.285 template<typename Graph>
1.286 inline bool bipartite(const Graph &graph){
1.287 - using namespace _topology_bits;
1.288 + using namespace _connectivity_bits;
1.289
1.290 checkConcept<concepts::Graph, Graph>();
1.291
1.292 @@ -1489,7 +1492,7 @@
1.293 /// \return %True if \c graph is bipartite, %false otherwise.
1.294 template<typename Graph, typename NodeMap>
1.295 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
1.296 - using namespace _topology_bits;
1.297 + using namespace _connectivity_bits;
1.298
1.299 checkConcept<concepts::Graph, Graph>();
1.300
1.301 @@ -1520,9 +1523,9 @@
1.302 ///
1.303 /// Returns true when there are not loop edges in the graph.
1.304 template <typename Digraph>
1.305 - bool loopFree(const Digraph& graph) {
1.306 - for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
1.307 - if (graph.source(it) == graph.target(it)) return false;
1.308 + bool loopFree(const Digraph& digraph) {
1.309 + for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
1.310 + if (digraph.source(it) == digraph.target(it)) return false;
1.311 }
1.312 return true;
1.313 }
1.314 @@ -1531,15 +1534,15 @@
1.315 ///
1.316 /// Returns true when there are not parallel edges in the graph.
1.317 template <typename Digraph>
1.318 - bool parallelFree(const Digraph& graph) {
1.319 - typename Digraph::template NodeMap<bool> reached(graph, false);
1.320 - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
1.321 - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
1.322 - if (reached[graph.target(e)]) return false;
1.323 - reached.set(graph.target(e), true);
1.324 + bool parallelFree(const Digraph& digraph) {
1.325 + typename Digraph::template NodeMap<bool> reached(digraph, false);
1.326 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.327 + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.328 + if (reached[digraph.target(a)]) return false;
1.329 + reached.set(digraph.target(a), true);
1.330 }
1.331 - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
1.332 - reached.set(graph.target(e), false);
1.333 + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.334 + reached.set(digraph.target(a), false);
1.335 }
1.336 }
1.337 return true;
1.338 @@ -1551,16 +1554,16 @@
1.339 /// Returns true when there are not loop edges and parallel edges in
1.340 /// the graph.
1.341 template <typename Digraph>
1.342 - bool simpleDigraph(const Digraph& graph) {
1.343 - typename Digraph::template NodeMap<bool> reached(graph, false);
1.344 - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
1.345 + bool simpleDigraph(const Digraph& digraph) {
1.346 + typename Digraph::template NodeMap<bool> reached(digraph, false);
1.347 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.348 reached.set(n, true);
1.349 - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
1.350 - if (reached[graph.target(e)]) return false;
1.351 - reached.set(graph.target(e), true);
1.352 + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.353 + if (reached[digraph.target(a)]) return false;
1.354 + reached.set(digraph.target(a), true);
1.355 }
1.356 - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
1.357 - reached.set(graph.target(e), false);
1.358 + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
1.359 + reached.set(digraph.target(a), false);
1.360 }
1.361 reached.set(n, false);
1.362 }
1.363 @@ -1569,4 +1572,4 @@
1.364
1.365 } //namespace lemon
1.366
1.367 -#endif //LEMON_TOPOLOGY_H
1.368 +#endif //LEMON_CONNECTIVITY_H
2.1 --- a/lemon/dfs.h Tue Dec 02 15:33:22 2008 +0000
2.2 +++ b/lemon/dfs.h Wed Dec 03 14:23:22 2008 +0100
2.3 @@ -1410,6 +1410,7 @@
2.4 _stack[++_stack_head] = e;
2.5 } else {
2.6 _visitor->leave(s);
2.7 + _visitor->stop(s);
2.8 }
2.9 }
2.10 }