lemon: comparison lemon/connectivity.h

equal deleted inserted replaced

-:b2957259973a
+:b0e279495dc5
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */
-#ifndef LEMON_TOPOLOGY_H
+#ifndef LEMON_CONNECTIVITY_H
-#define LEMON_TOPOLOGY_H
+#define LEMON_CONNECTIVITY_H
 #include <lemon/dfs.h>
 #include <lemon/bfs.h>
 #include <lemon/core.h>
 #include <lemon/maps.h>
 }
 }
 return compNum;
 }
-namespace _topology_bits {
+namespace _connectivity_bits {
 template <typename Digraph, typename Iterator >
 struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Node Node;
 Map& _map;
 Value& _value;
 };
 template <typename Digraph, typename ArcMap>
-struct StronglyConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
+struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Node Node;
 typedef typename Digraph::Arc Arc;
-StronglyConnectedCutEdgesVisitor(const Digraph& digraph,
+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;
 }
 void reach(const Node& node) {
 _compMap.set(node, _num);
 typedef typename Digraph::NodeIt NodeIt;
 typename Digraph::Node source = NodeIt(digraph);
 if (source == INVALID) return true;
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef DfsVisitor<Digraph> Visitor;
 Visitor visitor;
 DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 return false;
 }
 }
 typedef ReverseDigraph<const Digraph> RDigraph;
+typedef typename RDigraph::NodeIt RNodeIt;
 RDigraph rdigraph(digraph);
 typedef DfsVisitor<Digraph> RVisitor;
 RVisitor rvisitor;
 DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 rdfs.init();
 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;
 }
 }
 /// strongly connected components.
 template <typename Digraph>
 int countStronglyConnectedComponents(const Digraph& digraph) {
 checkConcept<concepts::Digraph, Digraph>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef typename Digraph::Node Node;
 typedef typename Digraph::Arc Arc;
 typedef typename Digraph::NodeIt NodeIt;
 typedef typename Digraph::ArcIt ArcIt;
 checkConcept<concepts::Digraph, Digraph>();
 typedef typename Digraph::Node Node;
 typedef typename Digraph::NodeIt NodeIt;
 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef std::vector<Node> Container;
 typedef typename Container::iterator Iterator;
 Container nodes(countNodes(digraph));
 typedef typename Digraph::Node Node;
 typedef typename Digraph::Arc Arc;
 typedef typename Digraph::NodeIt NodeIt;
 checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef std::vector<Node> Container;
 typedef typename Container::iterator Iterator;
 Container nodes(countNodes(graph));
 RDigraph rgraph(graph);
 int cutNum = 0;
-typedef StronglyConnectedCutEdgesVisitor<RDigraph, ArcMap> RVisitor;
+typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
 RVisitor rvisitor(rgraph, cutMap, cutNum);
 DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
 rdfs.init();
 }
 }
 return cutNum;
 }
-namespace _topology_bits {
+namespace _connectivity_bits {
 template <typename Digraph>
 class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Node Node;
 template <typename Graph>
 int countBiNodeConnectedComponents(const Graph& graph) {
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
 int compNum = 0;
 Visitor visitor(graph, compNum);
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
 checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
 int compNum = 0;
 Visitor visitor(graph, compMap, compNum);
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::Node Node;
 typedef typename Graph::NodeIt NodeIt;
 checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
 int cutNum = 0;
 Visitor visitor(graph, cutMap, cutNum);
 }
 }
 return cutNum;
 }
-namespace _topology_bits {
+namespace _connectivity_bits {
 template <typename Digraph>
 class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Node Node;
 template <typename Graph>
 int countBiEdgeConnectedComponents(const Graph& graph) {
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
 int compNum = 0;
 Visitor visitor(graph, compNum);
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Node Node;
 checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
 int compNum = 0;
 Visitor visitor(graph, compMap, compNum);
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
 checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
 int cutNum = 0;
 Visitor visitor(graph, cutMap, cutNum);
 }
 return cutNum;
 }
-namespace _topology_bits {
+namespace _connectivity_bits {
 template <typename Digraph, typename IntNodeMap>
 class TopologicalSortVisitor : public DfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Node Node;
 ///
 /// \see checkedTopologicalSort
 /// \see dag
 template <typename Digraph, typename NodeMap>
 void topologicalSort(const Digraph& graph, NodeMap& order) {
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 checkConcept<concepts::Digraph, Digraph>();
 checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
 typedef typename Digraph::Node Node;
 /// \return %False when the graph is not DAG.
 ///
 /// \see topologicalSort
 /// \see dag
 template <typename Digraph, typename NodeMap>
-bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
+bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 checkConcept<concepts::Digraph, Digraph>();
 checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
 NodeMap>();
 typedef typename Digraph::Node Node;
 typedef typename Digraph::NodeIt NodeIt;
 typedef typename Digraph::Arc Arc;
-order = constMap<Node, int, -1>();
+for (NodeIt it(digraph); it != INVALID; ++it) {
+order.set(it, -1);
+}
 TopologicalSortVisitor<Digraph, NodeMap>
-visitor(order, countNodes(graph));
+visitor(order, countNodes(digraph));
 DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
-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();
+Arc arc = dfs.nextArc();
-Node target = graph.target(edge);
+Node target = digraph.target(arc);
 if (dfs.reached(target) && order[target] == -1) {
 return false;
 }
 dfs.processNextArc();
 }
 /// Check that the given directed graph is a DAG. The DAG is
 /// an Directed Acyclic Digraph.
 /// \return %False when the graph is not DAG.
 /// \see acyclic
 template <typename Digraph>
-bool dag(const Digraph& graph) {
+bool dag(const Digraph& digraph) {
 checkConcept<concepts::Digraph, Digraph>();
 typedef typename Digraph::Node Node;
 typedef typename Digraph::NodeIt NodeIt;
 typedef typename Digraph::Arc Arc;
 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::
-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;
 }
 dfs.processNextArc();
 }
 }
 }
 return true;
 }
-namespace _topology_bits {
+namespace _connectivity_bits {
 template <typename Digraph>
 class BipartiteVisitor : public BfsVisitor<Digraph> {
 public:
 typedef typename Digraph::Arc Arc;
 /// \param graph The undirected graph.
 /// \return %True if \c graph is bipartite, %false otherwise.
 /// \sa bipartitePartitions
 template<typename Graph>
 inline bool bipartite(const Graph &graph){
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::ArcIt ArcIt;
 /// \retval partMap A writable bool map of nodes. It will be set as the
 /// two partitions of the graph.
 /// \return %True if \c graph is bipartite, %false otherwise.
 template<typename Graph, typename NodeMap>
 inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){
-using namespace _topology_bits;
+using namespace _connectivity_bits;
 checkConcept<concepts::Graph, Graph>();
 typedef typename Graph::Node Node;
 typedef typename Graph::NodeIt NodeIt;
 /// \brief Returns true when there are not loop edges in the graph.
 ///
 /// Returns true when there are not loop edges in the graph.
 template <typename Digraph>
-bool loopFree(const Digraph& graph) {
+bool loopFree(const Digraph& digraph) {
-for (typename Digraph::ArcIt it(graph); it != INVALID; ++it) {
+for (typename Digraph::ArcIt it(digraph); it != INVALID; ++it) {
-if (graph.source(it) == graph.target(it)) return false;
+if (digraph.source(it) == digraph.target(it)) return false;
 }
 return true;
 }
 /// \brief Returns true when there are not parallel edges in the graph.
 ///
 /// Returns true when there are not parallel edges in the graph.
 template <typename Digraph>
-bool parallelFree(const Digraph& graph) {
+bool parallelFree(const Digraph& digraph) {
-typename Digraph::template NodeMap<bool> reached(graph, false);
+typename Digraph::template NodeMap<bool> reached(digraph, false);
-for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
+for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
-for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
+for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-if (reached[graph.target(e)]) return false;
+if (reached[digraph.target(a)]) return false;
-reached.set(graph.target(e), true);
+reached.set(digraph.target(a), true);
 }
-for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
+for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-reached.set(graph.target(e), false);
+reached.set(digraph.target(a), false);
 }
 }
 return true;
 }
 /// edges in the graph.
 ///
 /// Returns true when there are not loop edges and parallel edges in
 /// the graph.
 template <typename Digraph>
-bool simpleDigraph(const Digraph& graph) {
+bool simpleDigraph(const Digraph& digraph) {
-typename Digraph::template NodeMap<bool> reached(graph, false);
+typename Digraph::template NodeMap<bool> reached(digraph, false);
-for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
+for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
 reached.set(n, true);
-for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
+for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-if (reached[graph.target(e)]) return false;
+if (reached[digraph.target(a)]) return false;
-reached.set(graph.target(e), true);
+reached.set(digraph.target(a), true);
 }
-for (typename Digraph::OutArcIt e(graph, n); e != INVALID; ++e) {
+for (typename Digraph::OutArcIt a(digraph, n); a != INVALID; ++a) {
-reached.set(graph.target(e), false);
+reached.set(digraph.target(a), false);
 }
 reached.set(n, false);
 }
 return true;
 }
 } //namespace lemon
-#endif //LEMON_TOPOLOGY_H
+#endif //LEMON_CONNECTIVITY_H

changeset 435	9afe81e4c543
parent 433	6ff53afe98b5
child 444	cace3206223b