Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 05 Dec 2008 10:38:32 +0000
changeset 4210f2091856dab
parent 420 6a2a33ad261b
parent 419 9afe81e4c543
child 422 62c1ed05e83f
Merge
lemon/dfs.h
     1.1 --- a/lemon/connectivity.h	Fri Dec 05 00:22:47 2008 +0100
     1.2 +++ b/lemon/connectivity.h	Fri Dec 05 10:38:32 2008 +0000
     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	Fri Dec 05 00:22:47 2008 +0100
     2.2 +++ b/lemon/dfs.h	Fri Dec 05 10:38:32 2008 +0000
     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      }