diff --git a/lemon/connectivity.h b/lemon/connectivity.h --- a/lemon/connectivity.h +++ b/lemon/connectivity.h @@ -16,8 +16,8 @@ * */ -#ifndef LEMON_TOPOLOGY_H -#define LEMON_TOPOLOGY_H +#ifndef LEMON_CONNECTIVITY_H +#define LEMON_CONNECTIVITY_H #include #include @@ -154,7 +154,7 @@ return compNum; } - namespace _topology_bits { + namespace _connectivity_bits { template struct LeaveOrderVisitor : public DfsVisitor { @@ -188,19 +188,19 @@ }; template - struct StronglyConnectedCutEdgesVisitor : public DfsVisitor { + struct StronglyConnectedCutArcsVisitor : public DfsVisitor { public: typedef typename Digraph::Node Node; typedef typename Digraph::Arc Arc; - StronglyConnectedCutEdgesVisitor(const Digraph& digraph, - ArcMap& cutMap, - int& cutNum) + StronglyConnectedCutArcsVisitor(const Digraph& digraph, + ArcMap& cutMap, + int& cutNum) : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum), - _compMap(digraph), _num(0) { + _compMap(digraph, -1), _num(-1) { } - void stop(const Node&) { + void start(const Node&) { ++_num; } @@ -248,7 +248,7 @@ typename Digraph::Node source = NodeIt(digraph); if (source == INVALID) return true; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef DfsVisitor Visitor; Visitor visitor; @@ -265,6 +265,7 @@ } typedef ReverseDigraph RDigraph; + typedef typename RDigraph::NodeIt RNodeIt; RDigraph rdigraph(digraph); typedef DfsVisitor RVisitor; @@ -275,7 +276,7 @@ rdfs.addSource(source); rdfs.start(); - for (NodeIt it(rdigraph); it != INVALID; ++it) { + for (RNodeIt it(rdigraph); it != INVALID; ++it) { if (!rdfs.reached(it)) { return false; } @@ -302,7 +303,7 @@ int countStronglyConnectedComponents(const Digraph& digraph) { checkConcept(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef typename Digraph::Node Node; typedef typename Digraph::Arc Arc; @@ -374,7 +375,7 @@ typedef typename Digraph::NodeIt NodeIt; checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef std::vector Container; typedef typename Container::iterator Iterator; @@ -438,7 +439,7 @@ typedef typename Digraph::NodeIt NodeIt; checkConcept, ArcMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef std::vector Container; typedef typename Container::iterator Iterator; @@ -463,7 +464,7 @@ int cutNum = 0; - typedef StronglyConnectedCutEdgesVisitor RVisitor; + typedef StronglyConnectedCutArcsVisitor RVisitor; RVisitor rvisitor(rgraph, cutMap, cutNum); DfsVisit rdfs(rgraph, rvisitor); @@ -478,7 +479,7 @@ return cutNum; } - namespace _topology_bits { + namespace _connectivity_bits { template class CountBiNodeConnectedComponentsVisitor : public DfsVisitor { @@ -730,7 +731,7 @@ checkConcept(); typedef typename Graph::NodeIt NodeIt; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef CountBiNodeConnectedComponentsVisitor Visitor; @@ -773,7 +774,7 @@ typedef typename Graph::Edge Edge; checkConcept, EdgeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiNodeConnectedComponentsVisitor Visitor; @@ -813,7 +814,7 @@ typedef typename Graph::NodeIt NodeIt; checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiNodeConnectedCutNodesVisitor Visitor; @@ -832,7 +833,7 @@ return cutNum; } - namespace _topology_bits { + namespace _connectivity_bits { template class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor { @@ -1053,7 +1054,7 @@ checkConcept(); typedef typename Graph::NodeIt NodeIt; - using namespace _topology_bits; + using namespace _connectivity_bits; typedef CountBiEdgeConnectedComponentsVisitor Visitor; @@ -1095,7 +1096,7 @@ typedef typename Graph::Node Node; checkConcept, NodeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiEdgeConnectedComponentsVisitor Visitor; @@ -1136,7 +1137,7 @@ typedef typename Graph::Edge Edge; checkConcept, EdgeMap>(); - using namespace _topology_bits; + using namespace _connectivity_bits; typedef BiEdgeConnectedCutEdgesVisitor Visitor; @@ -1156,7 +1157,7 @@ } - namespace _topology_bits { + namespace _connectivity_bits { template class TopologicalSortVisitor : public DfsVisitor { @@ -1193,7 +1194,7 @@ /// \see dag template void topologicalSort(const Digraph& graph, NodeMap& order) { - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); checkConcept, NodeMap>(); @@ -1234,8 +1235,8 @@ /// \see topologicalSort /// \see dag template - bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) { - using namespace _topology_bits; + bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) { + using namespace _connectivity_bits; checkConcept(); checkConcept, @@ -1245,21 +1246,23 @@ typedef typename Digraph::NodeIt NodeIt; typedef typename Digraph::Arc Arc; - order = constMap(); + for (NodeIt it(digraph); it != INVALID; ++it) { + order.set(it, -1); + } TopologicalSortVisitor - visitor(order, countNodes(graph)); + visitor(order, countNodes(digraph)); DfsVisit > - dfs(graph, visitor); + dfs(digraph, visitor); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { - Arc edge = dfs.nextArc(); - Node target = graph.target(edge); + Arc arc = dfs.nextArc(); + Node target = digraph.target(arc); if (dfs.reached(target) && order[target] == -1) { return false; } @@ -1279,7 +1282,7 @@ /// \return %False when the graph is not DAG. /// \see acyclic template - bool dag(const Digraph& graph) { + bool dag(const Digraph& digraph) { checkConcept(); @@ -1290,18 +1293,18 @@ typedef typename Digraph::template NodeMap ProcessedMap; typename Dfs::template SetProcessedMap:: - Create dfs(graph); + Create dfs(digraph); - ProcessedMap processed(graph); + ProcessedMap processed(digraph); dfs.processedMap(processed); dfs.init(); - for (NodeIt it(graph); it != INVALID; ++it) { + for (NodeIt it(digraph); it != INVALID; ++it) { if (!dfs.reached(it)) { dfs.addSource(it); while (!dfs.emptyQueue()) { Arc edge = dfs.nextArc(); - Node target = graph.target(edge); + Node target = digraph.target(edge); if (dfs.reached(target) && !processed[target]) { return false; } @@ -1380,7 +1383,7 @@ return true; } - namespace _topology_bits { + namespace _connectivity_bits { template class BipartiteVisitor : public BfsVisitor { @@ -1449,7 +1452,7 @@ /// \sa bipartitePartitions template inline bool bipartite(const Graph &graph){ - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); @@ -1489,7 +1492,7 @@ /// \return %True if \c graph is bipartite, %false otherwise. template inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){ - using namespace _topology_bits; + using namespace _connectivity_bits; checkConcept(); @@ -1520,9 +1523,9 @@ /// /// Returns true when there are not loop edges in the graph. template - bool loopFree(const Digraph& graph) { - for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) { - if (graph.source(it) == graph.target(it)) return false; + bool loopFree(const Digraph& digraph) { + for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) { + if (digraph.source(it) == digraph.target(it)) return false; } return true; } @@ -1531,15 +1534,15 @@ /// /// Returns true when there are not parallel edges in the graph. template - bool parallelFree(const Digraph& graph) { - typename Digraph::template NodeMap reached(graph, false); - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - if (reached[graph.target(e)]) return false; - reached.set(graph.target(e), true); + bool parallelFree(const Digraph& digraph) { + typename Digraph::template NodeMap reached(digraph, false); + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + if (reached[digraph.target(a)]) return false; + reached.set(digraph.target(a), true); } - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - reached.set(graph.target(e), false); + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + reached.set(digraph.target(a), false); } } return true; @@ -1551,16 +1554,16 @@ /// Returns true when there are not loop edges and parallel edges in /// the graph. template - bool simpleDigraph(const Digraph& graph) { - typename Digraph::template NodeMap reached(graph, false); - for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) { + bool simpleDigraph(const Digraph& digraph) { + typename Digraph::template NodeMap reached(digraph, false); + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) { reached.set(n, true); - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - if (reached[graph.target(e)]) return false; - reached.set(graph.target(e), true); + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + if (reached[digraph.target(a)]) return false; + reached.set(digraph.target(a), true); } - for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) { - reached.set(graph.target(e), false); + for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) { + reached.set(digraph.target(a), false); } reached.set(n, false); } @@ -1569,4 +1572,4 @@ } //namespace lemon -#endif //LEMON_TOPOLOGY_H +#endif //LEMON_CONNECTIVITY_H