LEMON/LEMON-official Changeset - r435:9afe81e4c543

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r435:9afe81e4c543

« 434:ad483a

438:0f2091 »

r435:9afe81e4c543

Wed, 03 Dec 2008 14:23:22

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Renamings in connectivity.h and bug fix in DfsVisit (#61) - The include guard, the private namespace and some local varibles are renamed - The stop() must be called in DfsVisit, if there are not outgoing arcs from the added node

0 2 0

default

2 files changed with 63 insertions and 59 deletions:

lemon/connectivity.h

lemon/dfs.h

↑ Collapse diff ↑

lemon/connectivity.h

Show inline comments

@@ -15,10 +15,10 @@
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_TOPOLOGY_H
 		#define LEMON_TOPOLOGY_H
 		#ifndef LEMON_CONNECTIVITY_H
 		#define LEMON_CONNECTIVITY_H
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/core.h>
@@ -153,9 +153,9 @@
+		    }
 		    return compNum;
+		  }
-		  namespace _topology_bits {
+		  namespace _connectivity_bits {
 		    template <typename Digraph, typename Iterator >
 		    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
 		    public:
@@ -187,21 +187,21 @@
 		      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) {
@@ -247,9 +247,9 @@
 		    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;
@@ -264,8 +264,9 @@
+		      }
+		    }
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    typedef typename RDigraph::NodeIt RNodeIt;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<Digraph> RVisitor;
 		    RVisitor rvisitor;
@@ -274,9 +275,9 @@
 		    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;
+		      }
+		    }
@@ -301,9 +302,9 @@
 		  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;
@@ -373,9 +374,9 @@
 		    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;
@@ -437,9 +438,9 @@
 		    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;
@@ -462,9 +463,9 @@
 		    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);
@@ -477,9 +478,9 @@
+		    }
 		    return cutNum;
+		  }
-		  namespace _topology_bits {
+		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
@@ -729,9 +730,9 @@
 		  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;
@@ -772,9 +773,9 @@
 		    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;
@@ -812,9 +813,9 @@
 		    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;
@@ -831,9 +832,9 @@
+		    }
 		    return cutNum;
+		  }
-		  namespace _topology_bits {
+		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
@@ -1052,9 +1053,9 @@
 		  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;
@@ -1094,9 +1095,9 @@
 		    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;
@@ -1135,9 +1136,9 @@
 		    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;
@@ -1155,9 +1156,9 @@
 		    return cutNum;
+		  }
-		  namespace _topology_bits {
+		  namespace _connectivity_bits {
 		    template <typename Digraph, typename IntNodeMap>
 		    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
 		    public:
@@ -1192,9 +1193,9 @@
 		  /// \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>();
@@ -1233,10 +1234,10 @@
 		  ///
 		  /// \see topologicalSort
 		  /// \see dag
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& graph, NodeMap& order) {
 		    using namespace _topology_bits;
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
 		      NodeMap>();
@@ -1244,23 +1245,25 @@
 		    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();
 		           Node target = graph.target(edge);
 		           Arc arc = dfs.nextArc();
 		           Node target = digraph.target(arc);
 		           if (dfs.reached(target) && order[target] == -1) {
 		             return false;
+		           }
 		           dfs.processNextArc();
@@ -1278,9 +1281,9 @@
 		  /// 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;
@@ -1289,20 +1292,20 @@
 		    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();
@@ -1379,9 +1382,9 @@
+		    }
 		    return true;
+		  }
-		  namespace _topology_bits {
+		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class BipartiteVisitor : public BfsVisitor<Digraph> {
 		    public:
@@ -1448,9 +1451,9 @@
 		  /// \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;
@@ -1488,9 +1491,9 @@
 		  /// 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;
@@ -1519,28 +1522,28 @@
 		  /// \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) {
 		    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;
+		  }
 		  /// \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) {
 		    typename Digraph::template NodeMap<bool> 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<bool> 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;
+		  }
@@ -1550,23 +1553,23 @@
 		  ///
 		  /// Returns true when there are not loop edges and parallel edges in
 		  /// the graph.
 		  template <typename Digraph>
 		  bool simpleDigraph(const Digraph& graph) {
 		    typename Digraph::template NodeMap<bool> reached(graph, false);
-		    for (typename Digraph::NodeIt n(graph); n != INVALID; ++n) {
+		  bool simpleDigraph(const Digraph& digraph) {
 		    typename Digraph::template NodeMap<bool> 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);
+		    }
 		    return true;
+		  }
 		} //namespace lemon
-		#endif //LEMON_TOPOLOGY_H
+		#endif //LEMON_CONNECTIVITY_H

lemon/dfs.h

Show inline comments

@@ -1409,8 +1409,9 @@
          if (e != INVALID) {
            _stack[++_stack_head] = e;
          } else {
            _visitor->leave(s);
            _visitor->stop(s);
          }
        }
    }


0 comments (0 inline)

...	...	@@ -1409,8 +1409,9 @@
1409	1409	if (e != INVALID) {
1410	1410	_stack[++_stack_head] = e;
1411	1411	} else {
1412	1412	_visitor->leave(s);
	1413	_visitor->stop(s);
1413	1414	}
1414	1415	}
1415	1416	}
1416	1417

RhodeCode

Login to your account