LEMON/LEMON-main Changeset - r425:cace3206223b

Repositories » LEMON » LEMON-main

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

Changeset - r425:cace3206223b

« 422:62c1ed

426:b25645 »

r425:cace3206223b

Mon, 08 Dec 2008 11:06:39

[Not Reviewed]

0 comments (0 inline)

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

Fix typos (ticket #192)

0 3 0

default

3 files changed with 4 insertions and 4 deletions:

lemon/connectivity.h

lemon/max_matching.h

lemon/suurballe.h

↑ Collapse diff ↑

lemon/connectivity.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONNECTIVITY_H
 		#define LEMON_CONNECTIVITY_H
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concept_check.h>
 		#include <stack>
 		#include <functional>
 		/// \ingroup connectivity
 		/// \file
 		/// \brief Connectivity algorithms
 		///
 		/// Connectivity algorithms
 		namespace lemon {
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check whether the given undirected graph is connected.
 		  ///
 		  /// Check whether the given undirected graph is connected.
 		  /// \param graph The undirected graph.
 		  /// \return %True when there is path between any two nodes in the graph.
 		  /// \note By definition, the empty graph is connected.
 		  template <typename Graph>
 		  bool connected(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    if (NodeIt(graph) == INVALID) return true;
 		    Dfs<Graph> dfs(graph);
 		    dfs.run(NodeIt(graph));
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the number of connected components of an undirected graph
 		  ///
 		  /// Count the number of connected components of an undirected graph
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \return The number of components
 		  /// \note By definition, the empty graph consists
 		  /// of zero connected components.
 		  template <typename Graph>
 		  int countConnectedComponents(const Graph &graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if (!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        bfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the connected components of an undirected graph
 		  ///
 		  /// Find the connected components of an undirected graph.
 		  ///
 		  /// \param graph The graph. It must be undirected.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the connected components minus one. Each values of the map
 		  /// will be set exactly once, the values of a certain component will be
 		  /// set continuously.
 		  /// \return The number of components
 		  ///
 		  template <class Graph, class NodeMap>
 		  int connectedComponents(const Graph &graph, NodeMap &compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::Arc Arc;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    typedef NullMap<Node, Arc> PredMap;
 		    typedef NullMap<Node, int> DistMap;
 		    int compNum = 0;
 		    typename Bfs<Graph>::
 		      template SetPredMap<PredMap>::
 		      template SetDistMap<DistMap>::
 		      Create bfs(graph);
 		    PredMap predMap;
 		    bfs.predMap(predMap);
 		    DistMap distMap;
 		    bfs.distMap(distMap);
 		    bfs.init();
 		    for(typename Graph::NodeIt n(graph); n != INVALID; ++n) {
 		      if(!bfs.reached(n)) {
 		        bfs.addSource(n);
 		        while (!bfs.emptyQueue()) {
 		          compMap.set(bfs.nextNode(), compNum);
 		          bfs.processNextNode();
+		        }
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph, typename Iterator >
 		    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      LeaveOrderVisitor(Iterator it) : _it(it) {}
 		      void leave(const Node& node) {
 		        *(_it++) = node;
+		      }
 		    private:
 		      Iterator _it;
 		    };
 		    template <typename Digraph, typename Map>
 		    struct FillMapVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Map::Value Value;
 		      FillMapVisitor(Map& map, Value& value)
 		        : _map(map), _value(value) {}
 		      void reach(const Node& node) {
 		        _map.set(node, _value);
+		      }
 		    private:
 		      Map& _map;
 		      Value& _value;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    struct StronglyConnectedCutArcsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      StronglyConnectedCutArcsVisitor(const Digraph& digraph,
 		                                      ArcMap& cutMap,
 		                                      int& cutNum)
 		        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),
 		          _compMap(digraph, -1), _num(-1) {
+		      }
 		      void start(const Node&) {
 		        ++_num;
+		      }
 		      void reach(const Node& node) {
 		        _compMap.set(node, _num);
+		      }
 		      void examine(const Arc& arc) {
 		         if (_compMap[_digraph.source(arc)] !=
 		             _compMap[_digraph.target(arc)]) {
 		           _cutMap.set(arc, true);
 		           ++_cutNum;
+		         }
+		      }
 		    private:
 		      const Digraph& _digraph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _compMap;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check whether the given directed graph is strongly connected.
 		  ///
 		  /// Check whether the given directed graph is strongly connected. The
 		  /// graph is strongly connected when any two nodes of the graph are
 		  /// connected with directed paths in both direction.
 		  /// \return %False when the graph is not strongly connected.
 		  /// \see connected
 		  ///
 		  /// \note By definition, the empty graph is strongly connected.
 		  template <typename Digraph>
 		  bool stronglyConnected(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typename Digraph::Node source = NodeIt(digraph);
 		    if (source == INVALID) return true;
 		    using namespace _connectivity_bits;
 		    typedef DfsVisitor<Digraph> Visitor;
 		    Visitor visitor;
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    dfs.addSource(source);
 		    dfs.start();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        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 (RNodeIt it(rdigraph); it != INVALID; ++it) {
 		      if (!rdfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the strongly connected components of a directed graph
 		  ///
 		  /// Count the strongly connected components of a directed graph.
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of the graph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
-		  /// \param graph The graph.
+		  /// \param digraph The graph.
 		  /// \return The number of components
 		  /// \note By definition, the empty graph has zero
 		  /// strongly connected components.
 		  template <typename Digraph>
 		  int countStronglyConnectedComponents(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    using namespace _connectivity_bits;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::ArcIt ArcIt;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<Digraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    int compNum = 0;
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the strongly connected components of a directed graph
 		  ///
 		  /// Find the strongly connected components of a directed graph.  The
 		  /// strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in
 		  /// relationship when there are directed paths between them in both
 		  /// direction. In addition, the numbering of components will satisfy
 		  /// that there is no arc going from a higher numbered component to
 		  /// a lower.
 		  ///
 		  /// \param digraph The digraph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the strongly connected components minus one. Each value
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components
 		  ///
 		  template <typename Digraph, typename NodeMap>
 		  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(digraph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rdigraph(digraph);
 		    int compNum = 0;
 		    typedef FillMapVisitor<RDigraph, NodeMap> RVisitor;
 		    RVisitor rvisitor(compMap, compNum);
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
 		        ++compNum;
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the cut arcs of the strongly connected components.
 		  ///
 		  /// Find the cut arcs of the strongly connected components.
 		  /// The strongly connected components are the classes of an equivalence
 		  /// relation on the nodes of the graph. Two nodes are in relationship
 		  /// when there are directed paths between them in both direction.
 		  /// The strongly connected components are separated by the cut arcs.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
 		  /// arc is a cut arc.
 		  ///
 		  /// \return The number of cut arcs
 		  template <typename Digraph, typename ArcMap>
 		  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();
 		    using namespace _connectivity_bits;
 		    typedef std::vector<Node> Container;
 		    typedef typename Container::iterator Iterator;
 		    Container nodes(countNodes(graph));
 		    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;
 		    Visitor visitor(nodes.begin());
 		    DfsVisit<Digraph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    typedef typename Container::reverse_iterator RIterator;
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    RDigraph rgraph(graph);
 		    int cutNum = 0;
 		    typedef StronglyConnectedCutArcsVisitor<RDigraph, ArcMap> RVisitor;
 		    RVisitor rvisitor(rgraph, cutMap, cutNum);
 		    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);
 		    rdfs.init();
 		    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {
 		      if (!rdfs.reached(*it)) {
 		        rdfs.addSource(*it);
 		        rdfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), _graph.source(edge));
+		      }
 		      void examine(const Arc& edge) {
 		        if (_graph.source(edge) == _graph.target(edge) &&
 		            _graph.direction(edge)) {
 		          ++_compNum;
 		          return;
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
 		        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
 		          ++_compNum;
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      int _num;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    class BiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiNodeConnectedComponentsVisitor(const Digraph& graph,
 		                                       ArcMap& compMap, int &compNum)
 		        : _graph(graph), _compMap(compMap), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        Node target = _graph.target(edge);
 		        _predMap.set(target, edge);
 		        _edgeStack.push(edge);
+		      }
 		      void examine(const Arc& edge) {
 		        Node source = _graph.source(edge);
 		        Node target = _graph.target(edge);
 		        if (source == target && _graph.direction(edge)) {
 		          _compMap.set(edge, _compNum);
 		          ++_compNum;
 		          return;
+		        }
 		        if (_numMap[target] < _numMap[source]) {
 		          if (_predMap[source] != _graph.oppositeArc(edge)) {
 		            _edgeStack.push(edge);
+		          }
+		        }
 		        if (_predMap[source] != INVALID &&
 		            target == _graph.source(_predMap[source])) {
 		          return;
+		        }
 		        if (_retMap[source] > _numMap[target]) {
 		          _retMap.set(source, _numMap[target]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        Node source = _graph.source(edge);
 		        Node target = _graph.target(edge);
 		        if (_retMap[source] > _retMap[target]) {
 		          _retMap.set(source, _retMap[target]);
+		        }
 		        if (_numMap[source] <= _retMap[target]) {
 		          while (_edgeStack.top() != edge) {
 		            _compMap.set(_edgeStack.top(), _compNum);
 		            _edgeStack.pop();
+		          }
 		          _compMap.set(edge, _compNum);
 		          _edgeStack.pop();
 		          ++_compNum;
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _compMap;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		    };
 		    template <typename Digraph, typename NodeMap>
 		    class BiNodeConnectedCutNodesVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiNodeConnectedCutNodesVisitor(const Digraph& graph, NodeMap& cutMap,
 		                                     int& cutNum)
 		        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
 		        rootCut = false;
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), _graph.source(edge));
+		      }
 		      void examine(const Arc& edge) {
 		        if (_graph.source(edge) == _graph.target(edge) &&
 		            _graph.direction(edge)) {
 		          if (!_cutMap[_graph.source(edge)]) {
 		            _cutMap.set(_graph.source(edge), true);
 		            ++_cutNum;
+		          }
 		          return;
+		        }
 		        if (_predMap[_graph.source(edge)] == _graph.target(edge)) return;
 		        if (_retMap[_graph.source(edge)] > _numMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _numMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
 		        if (_numMap[_graph.source(edge)] <= _retMap[_graph.target(edge)]) {
 		          if (_predMap[_graph.source(edge)] != INVALID) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else if (rootCut) {
 		            if (!_cutMap[_graph.source(edge)]) {
 		              _cutMap.set(_graph.source(edge), true);
 		              ++_cutNum;
+		            }
 		          } else {
 		            rootCut = true;
+		          }
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		      bool rootCut;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph);
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Checks the graph is bi-node-connected.
 		  ///
 		  /// This function checks that the undirected graph is bi-node-connected
 		  /// graph. The graph is bi-node-connected if any two undirected edge is
 		  /// on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return %True when the graph bi-node-connected.
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the biconnected components.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The biconnected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge is in relationship
 		  /// when they are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_bits;
 		    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-node-connected components.
 		  ///
 		  /// This function finds the bi-node-connected components in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edge are in relationship
 		  /// when they are on same circle.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval compMap A writable uedge map. The values will be set from 0
 		  /// to the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  ///
 		  template <typename Graph, typename EdgeMap>
 		  int biNodeConnectedComponents(const Graph& graph,
 		                                EdgeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-node-connected cut nodes.
 		  ///
 		  /// This function finds the bi-node-connected cut nodes in an undirected
 		  /// graph. The bi-node-connected components are the classes of an equivalence
 		  /// relation on the undirected edges. Two undirected edges are in
 		  /// relationship when they are on same circle. The biconnected components
 		  /// are separted by nodes which are the cut nodes of the components.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable edge map. The values will be set true when
 		  /// the node separate two or more components.
 		  /// \return The number of the cut nodes.
 		  template <typename Graph, typename NodeMap>
 		  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)
 		        : _graph(graph), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          ++_compNum;
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
 		    template <typename Digraph, typename NodeMap>
 		    class BiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiEdgeConnectedComponentsVisitor(const Digraph& graph,
 		                                       NodeMap& compMap, int &compNum)
 		        : _graph(graph), _compMap(compMap), _compNum(compNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap.set(node, INVALID);
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        _nodeStack.push(node);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          while (_nodeStack.top() != node) {
 		            _compMap.set(_nodeStack.top(), _compNum);
 		            _nodeStack.pop();
+		          }
 		          _compMap.set(node, _compNum);
 		          _nodeStack.pop();
 		          ++_compNum;
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _compMap;
 		      int& _compNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      std::stack<Node> _nodeStack;
 		      int _num;
 		    };
 		    template <typename Digraph, typename ArcMap>
 		    class BiEdgeConnectedCutEdgesVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Edge Edge;
 		      BiEdgeConnectedCutEdgesVisitor(const Digraph& graph,
 		                                     ArcMap& cutMap, int &cutNum)
 		        : _graph(graph), _cutMap(cutMap), _cutNum(cutNum),
 		          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}
 		      void start(const Node& node) {
 		        _predMap[node] = INVALID;
+		      }
 		      void reach(const Node& node) {
 		        _numMap.set(node, _num);
 		        _retMap.set(node, _num);
 		        ++_num;
+		      }
 		      void leave(const Node& node) {
 		        if (_numMap[node] <= _retMap[node]) {
 		          if (_predMap[node] != INVALID) {
 		            _cutMap.set(_predMap[node], true);
 		            ++_cutNum;
+		          }
+		        }
+		      }
 		      void discover(const Arc& edge) {
 		        _predMap.set(_graph.target(edge), edge);
+		      }
 		      void examine(const Arc& edge) {
 		        if (_predMap[_graph.source(edge)] == _graph.oppositeArc(edge)) {
 		          return;
+		        }
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		      void backtrack(const Arc& edge) {
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph);
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Checks that the graph is bi-edge-connected.
 		  ///
 		  /// This function checks that the graph is bi-edge-connected. The undirected
 		  /// graph is bi-edge-connected when any two nodes are connected with two
 		  /// edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  bool biEdgeConnected(const Graph& graph) {
 		    return countBiEdgeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Count the bi-edge-connected components.
 		  ///
 		  /// This function count the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \return The number of components.
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_bits;
 		    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-edge-connected components.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected at least two edge-disjoint paths.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval compMap A writable node map. The values will be set from 0 to
 		  /// the number of the biconnected components minus one. Each values
 		  /// of the map will be set exactly once, the values of a certain component
 		  /// will be set continuously.
 		  /// \return The number of components.
 		  ///
 		  template <typename Graph, typename NodeMap>
 		  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Node Node;
 		    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges.
 		  ///
 		  /// This function finds the bi-edge-connected components in an undirected
 		  /// graph. The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes. Two nodes are in relationship when they are
 		  /// connected with at least two edge-disjoint paths. The bi-edge-connected
 		  /// components are separted by edges which are the cut edges of the
 		  /// components.
 		  ///
 		  /// \param graph The graph.
 		  /// \retval cutMap A writable node map. The values will be set true when the
 		  /// edge is a cut edge.
 		  /// \return The number of cut edges.
 		  template <typename Graph, typename EdgeMap>
 		  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return cutNum;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph, typename IntNodeMap>
 		    class TopologicalSortVisitor : public DfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Node Node;
 		      typedef typename Digraph::Arc edge;
 		      TopologicalSortVisitor(IntNodeMap& order, int num)
 		        : _order(order), _num(num) {}
 		      void leave(const Node& node) {
 		        _order.set(node, --_num);
+		      }
 		    private:
 		      IntNodeMap& _order;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// \param graph The graph. It must be directed and acyclic.
 		  /// \retval order A writable node map. The values will be set from 0 to
 		  /// the number of the nodes in the graph minus one. Each values of the map
 		  /// will be set exactly once, the values  will be set descending order.
 		  ///
 		  /// \see checkedTopologicalSort
 		  /// \see dag
 		  template <typename Digraph, typename NodeMap>
 		  void topologicalSort(const Digraph& graph, NodeMap& order) {
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(graph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// Sort the nodes of a DAG into topolgical order. It also checks
 		  /// that the given graph is DAG.
 		  ///
-		  /// \param graph The graph. It must be directed and acyclic.
+		  /// \param digraph The graph. It must be directed and acyclic.
 		  /// \retval order A readable - writable node map. The values will be set
 		  /// from 0 to the number of the nodes in the graph minus one. Each values
 		  /// of the map will be set exactly once, the values will be set descending
 		  /// order.
 		  /// \return %False when the graph is not DAG.
 		  ///
 		  /// \see topologicalSort
 		  /// \see dag
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    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;
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      order.set(it, -1);
+		    }
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		           Arc arc = dfs.nextArc();
 		           Node target = digraph.target(arc);
 		           if (dfs.reached(target) && order[target] == -1) {
 		             return false;
+		           }
 		           dfs.processNextArc();
+		         }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given directed graph is a DAG.
 		  ///
 		  /// 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& 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(digraph);
 		    ProcessedMap processed(digraph);
 		    dfs.processedMap(processed);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node target = digraph.target(edge);
 		          if (dfs.reached(target) && !processed[target]) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given undirected graph is acyclic.
 		  ///
 		  /// Check that the given undirected graph acyclic.
 		  /// \param graph The undirected graph.
 		  /// \return %True when there is no circle in the graph.
 		  /// \see dag
 		  template <typename Graph>
 		  bool acyclic(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        while (!dfs.emptyQueue()) {
 		          Arc edge = dfs.nextArc();
 		          Node source = graph.source(edge);
 		          Node target = graph.target(edge);
 		          if (dfs.reached(target) &&
 		              dfs.predArc(source) != graph.oppositeArc(edge)) {
 		            return false;
+		          }
 		          dfs.processNextArc();
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check that the given undirected graph is tree.
 		  ///
 		  /// Check that the given undirected graph is tree.
 		  /// \param graph The undirected graph.
 		  /// \return %True when the graph is acyclic and connected.
 		  template <typename Graph>
 		  bool tree(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Arc Arc;
 		    Dfs<Graph> dfs(graph);
 		    dfs.init();
 		    dfs.addSource(NodeIt(graph));
 		    while (!dfs.emptyQueue()) {
 		      Arc edge = dfs.nextArc();
 		      Node source = graph.source(edge);
 		      Node target = graph.target(edge);
 		      if (dfs.reached(target) &&
 		          dfs.predArc(source) != graph.oppositeArc(edge)) {
 		        return false;
+		      }
 		      dfs.processNextArc();
+		    }
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  namespace _connectivity_bits {
 		    template <typename Digraph>
 		    class BipartiteVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartiteVisitor(const Digraph& graph, bool& bipartite)
 		        : _graph(graph), _part(graph), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part[node] = true;
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      typename Digraph::template NodeMap<bool> _part;
 		      bool& _bipartite;
 		    };
 		    template <typename Digraph, typename PartMap>
 		    class BipartitePartitionsVisitor : public BfsVisitor<Digraph> {
 		    public:
 		      typedef typename Digraph::Arc Arc;
 		      typedef typename Digraph::Node Node;
 		      BipartitePartitionsVisitor(const Digraph& graph,
 		                                 PartMap& part, bool& bipartite)
 		        : _graph(graph), _part(part), _bipartite(bipartite) {}
 		      void start(const Node& node) {
 		        _part.set(node, true);
+		      }
 		      void discover(const Arc& edge) {
 		        _part.set(_graph.target(edge), !_part[_graph.source(edge)]);
+		      }
 		      void examine(const Arc& edge) {
 		        _bipartite = _bipartite &&
 		          _part[_graph.target(edge)] != _part[_graph.source(edge)];
+		      }
 		    private:
 		      const Digraph& _graph;
 		      PartMap& _part;
 		      bool& _bipartite;
 		    };
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check if the given undirected graph is bipartite or not
 		  ///
 		  /// The function checks if the given undirected \c graph graph is bipartite
 		  /// or not. The \ref Bfs algorithm is used to calculate the result.
 		  /// \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 _connectivity_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartiteVisitor<Graph>
 		      visitor(graph, bipartite);
 		    BfsVisit<Graph, BipartiteVisitor<Graph> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup connectivity
 		  ///
 		  /// \brief Check if the given undirected graph is bipartite or not
 		  ///
 		  /// The function checks if the given undirected graph is bipartite
 		  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.
 		  /// During the execution, the \c partMap will be set as the two
 		  /// partitions of the graph.
 		  /// \param graph The undirected graph.
 		  /// \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 _connectivity_bits;
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::ArcIt ArcIt;
 		    bool bipartite = true;
 		    BipartitePartitionsVisitor<Graph, NodeMap>
 		      visitor(graph, partMap, bipartite);
 		    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >
 		      bfs(graph, visitor);
 		    bfs.init();
 		    for(NodeIt it(graph); it != INVALID; ++it) {
 		      if(!bfs.reached(it)){
 		        bfs.addSource(it);
 		        while (!bfs.emptyQueue()) {
 		          bfs.processNextNode();
 		          if (!bipartite) return false;
+		        }
+		      }
+		    }
 		    return true;
+		  }
 		  /// \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& 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& 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 a(digraph, n); a != INVALID; ++a) {
 		        reached.set(digraph.target(a), false);
+		      }
+		    }
 		    return true;
+		  }
 		  /// \brief Returns true when there are not loop edges and parallel
 		  /// 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& 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 a(digraph, n); a != INVALID; ++a) {
 		        if (reached[digraph.target(a)]) return false;
 		        reached.set(digraph.target(a), true);
+		      }
 		      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_CONNECTIVITY_H

lemon/max_matching.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_MAX_MATCHING_H
 		#define LEMON_MAX_MATCHING_H
 		#include <vector>
 		#include <queue>
 		#include <set>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/unionfind.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/maps.h>
 		///\ingroup matching
 		///\file
 		///\brief Maximum matching algorithms in general graphs.
 		namespace lemon {
 		  /// \ingroup matching
 		  ///
 		  /// \brief Edmonds' alternating forest maximum matching algorithm.
 		  ///
 		  /// This class implements Edmonds' alternating forest matching
 		  /// algorithm. The algorithm can be started from an arbitrary initial
 		  /// matching (the default is the empty one)
 		  ///
 		  /// The dual solution of the problem is a map of the nodes to
 		  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
 		  /// MATCHED/C showing the Gallai-Edmonds decomposition of the
 		  /// graph. The nodes in \c EVEN/D induce a graph with
 		  /// factor-critical components, the nodes in \c ODD/A form the
 		  /// barrier, and the nodes in \c MATCHED/C induce a graph having a
 		  /// perfect matching. The number of the factor-critical components
 		  /// minus the number of barrier nodes is a lower bound on the
 		  /// unmatched nodes, and the matching is optimal if and only if this bound is
 		  /// tight. This decomposition can be attained by calling \c
 		  /// decomposition() after running the algorithm.
 		  ///
 		  /// \param _Graph The graph type the algorithm runs on.
 		  template <typename _Graph>
 		  class MaxMatching {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
 		    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
 		    ///
 		    ///Indicates the Gallai-Edmonds decomposition of the graph. The
 		    ///nodes with Status \c EVEN/D induce a graph with factor-critical
 		    ///components, the nodes in \c ODD/A form the canonical barrier,
 		    ///and the nodes in \c MATCHED/C induce a graph having a perfect
 		    ///matching.
 		    enum Status {
 		      EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2
 		    };
 		    typedef typename Graph::template NodeMap<Status> StatusMap;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    typedef UnionFindEnum<IntNodeMap> BlossomSet;
 		    typedef ExtendFindEnum<IntNodeMap> TreeSet;
 		    typedef RangeMap<Node> NodeIntMap;
 		    typedef MatchingMap EarMap;
 		    typedef std::vector<Node> NodeQueue;
 		    const Graph& _graph;
 		    MatchingMap* _matching;
 		    StatusMap* _status;
 		    EarMap* _ear;
 		    IntNodeMap* _blossom_set_index;
 		    BlossomSet* _blossom_set;
 		    NodeIntMap* _blossom_rep;
 		    IntNodeMap* _tree_set_index;
 		    TreeSet* _tree_set;
 		    NodeQueue _node_queue;
 		    int _process, _postpone, _last;
 		    int _node_num;
 		  private:
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_status) {
 		        _status = new StatusMap(_graph);
+		      }
 		      if (!_ear) {
 		        _ear = new EarMap(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_set_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_set_index);
+		      }
 		      if (!_blossom_rep) {
 		        _blossom_rep = new NodeIntMap(_node_num);
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntNodeMap(_graph);
 		        _tree_set = new TreeSet(*_tree_set_index);
+		      }
 		      _node_queue.resize(_node_num);
+		    }
 		    void destroyStructures() {
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_status) {
 		        delete _status;
+		      }
 		      if (_ear) {
 		        delete _ear;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_set;
 		        delete _blossom_set_index;
+		      }
 		      if (_blossom_rep) {
 		        delete _blossom_rep;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
 		        delete _tree_set;
+		      }
+		    }
 		    void processDense(const Node& n) {
 		      _process = _postpone = _last = 0;
 		      _node_queue[_last++] = n;
 		      while (_process != _last) {
 		        Node u = _node_queue[_process++];
 		        for (OutArcIt a(_graph, u); a != INVALID; ++a) {
 		          Node v = _graph.target(a);
 		          if ((*_status)[v] == MATCHED) {
 		            extendOnArc(a);
 		          } else if ((*_status)[v] == UNMATCHED) {
 		            augmentOnArc(a);
 		            return;
+		          }
+		        }
+		      }
 		      while (_postpone != _last) {
 		        Node u = _node_queue[_postpone++];
 		        for (OutArcIt a(_graph, u); a != INVALID ; ++a) {
 		          Node v = _graph.target(a);
 		          if ((*_status)[v] == EVEN) {
 		            if (_blossom_set->find(u) != _blossom_set->find(v)) {
 		              shrinkOnEdge(a);
+		            }
+		          }
 		          while (_process != _last) {
 		            Node w = _node_queue[_process++];
 		            for (OutArcIt b(_graph, w); b != INVALID; ++b) {
 		              Node x = _graph.target(b);
 		              if ((*_status)[x] == MATCHED) {
 		                extendOnArc(b);
 		              } else if ((*_status)[x] == UNMATCHED) {
 		                augmentOnArc(b);
 		                return;
+		              }
+		            }
+		          }
+		        }
+		      }
+		    }
 		    void processSparse(const Node& n) {
 		      _process = _last = 0;
 		      _node_queue[_last++] = n;
 		      while (_process != _last) {
 		        Node u = _node_queue[_process++];
 		        for (OutArcIt a(_graph, u); a != INVALID; ++a) {
 		          Node v = _graph.target(a);
 		          if ((*_status)[v] == EVEN) {
 		            if (_blossom_set->find(u) != _blossom_set->find(v)) {
 		              shrinkOnEdge(a);
+		            }
 		          } else if ((*_status)[v] == MATCHED) {
 		            extendOnArc(a);
 		          } else if ((*_status)[v] == UNMATCHED) {
 		            augmentOnArc(a);
 		            return;
+		          }
+		        }
+		      }
+		    }
 		    void shrinkOnEdge(const Edge& e) {
 		      Node nca = INVALID;
+		      {
 		        std::set<Node> left_set, right_set;
 		        Node left = (*_blossom_rep)[_blossom_set->find(_graph.u(e))];
 		        left_set.insert(left);
 		        Node right = (*_blossom_rep)[_blossom_set->find(_graph.v(e))];
 		        right_set.insert(right);
 		        while (true) {
 		          if ((*_matching)[left] == INVALID) break;
 		          left = _graph.target((*_matching)[left]);
 		          left = (*_blossom_rep)[_blossom_set->
 		                                 find(_graph.target((*_ear)[left]))];
 		          if (right_set.find(left) != right_set.end()) {
 		            nca = left;
 		            break;
+		          }
 		          left_set.insert(left);
 		          if ((*_matching)[right] == INVALID) break;
 		          right = _graph.target((*_matching)[right]);
 		          right = (*_blossom_rep)[_blossom_set->
 		                                  find(_graph.target((*_ear)[right]))];
 		          if (left_set.find(right) != left_set.end()) {
 		            nca = right;
 		            break;
+		          }
 		          right_set.insert(right);
+		        }
 		        if (nca == INVALID) {
 		          if ((*_matching)[left] == INVALID) {
 		            nca = right;
 		            while (left_set.find(nca) == left_set.end()) {
 		              nca = _graph.target((*_matching)[nca]);
 		              nca =(*_blossom_rep)[_blossom_set->
 		                                   find(_graph.target((*_ear)[nca]))];
+		            }
 		          } else {
 		            nca = left;
 		            while (right_set.find(nca) == right_set.end()) {
 		              nca = _graph.target((*_matching)[nca]);
 		              nca = (*_blossom_rep)[_blossom_set->
 		                                   find(_graph.target((*_ear)[nca]))];
+		            }
+		          }
+		        }
+		      }
+		      {
 		        Node node = _graph.u(e);
 		        Arc arc = _graph.direct(e, true);
 		        Node base = (*_blossom_rep)[_blossom_set->find(node)];
 		        while (base != nca) {
 		          _ear->set(node, arc);
 		          Node n = node;
 		          while (n != base) {
 		            n = _graph.target((*_matching)[n]);
 		            Arc a = (*_ear)[n];
 		            n = _graph.target(a);
 		            _ear->set(n, _graph.oppositeArc(a));
+		          }
 		          node = _graph.target((*_matching)[base]);
 		          _tree_set->erase(base);
 		          _tree_set->erase(node);
 		          _blossom_set->insert(node, _blossom_set->find(base));
 		          _status->set(node, EVEN);
 		          _node_queue[_last++] = node;
 		          arc = _graph.oppositeArc((*_ear)[node]);
 		          node = _graph.target((*_ear)[node]);
 		          base = (*_blossom_rep)[_blossom_set->find(node)];
 		          _blossom_set->join(_graph.target(arc), base);
+		        }
+		      }
 		      _blossom_rep->set(_blossom_set->find(nca), nca);
+		      {
 		        Node node = _graph.v(e);
 		        Arc arc = _graph.direct(e, false);
 		        Node base = (*_blossom_rep)[_blossom_set->find(node)];
 		        while (base != nca) {
 		          _ear->set(node, arc);
 		          Node n = node;
 		          while (n != base) {
 		            n = _graph.target((*_matching)[n]);
 		            Arc a = (*_ear)[n];
 		            n = _graph.target(a);
 		            _ear->set(n, _graph.oppositeArc(a));
+		          }
 		          node = _graph.target((*_matching)[base]);
 		          _tree_set->erase(base);
 		          _tree_set->erase(node);
 		          _blossom_set->insert(node, _blossom_set->find(base));
 		          _status->set(node, EVEN);
 		          _node_queue[_last++] = node;
 		          arc = _graph.oppositeArc((*_ear)[node]);
 		          node = _graph.target((*_ear)[node]);
 		          base = (*_blossom_rep)[_blossom_set->find(node)];
 		          _blossom_set->join(_graph.target(arc), base);
+		        }
+		      }
 		      _blossom_rep->set(_blossom_set->find(nca), nca);
+		    }
 		    void extendOnArc(const Arc& a) {
 		      Node base = _graph.source(a);
 		      Node odd = _graph.target(a);
 		      _ear->set(odd, _graph.oppositeArc(a));
 		      Node even = _graph.target((*_matching)[odd]);
 		      _blossom_rep->set(_blossom_set->insert(even), even);
 		      _status->set(odd, ODD);
 		      _status->set(even, EVEN);
 		      int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]);
 		      _tree_set->insert(odd, tree);
 		      _tree_set->insert(even, tree);
 		      _node_queue[_last++] = even;
+		    }
 		    void augmentOnArc(const Arc& a) {
 		      Node even = _graph.source(a);
 		      Node odd = _graph.target(a);
 		      int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]);
 		      _matching->set(odd, _graph.oppositeArc(a));
 		      _status->set(odd, MATCHED);
 		      Arc arc = (*_matching)[even];
 		      _matching->set(even, a);
 		      while (arc != INVALID) {
 		        odd = _graph.target(arc);
 		        arc = (*_ear)[odd];
 		        even = _graph.target(arc);
 		        _matching->set(odd, arc);
 		        arc = (*_matching)[even];
 		        _matching->set(even, _graph.oppositeArc((*_matching)[odd]));
+		      }
 		      for (typename TreeSet::ItemIt it(*_tree_set, tree);
 		           it != INVALID; ++it) {
 		        if ((*_status)[it] == ODD) {
 		          _status->set(it, MATCHED);
 		        } else {
 		          int blossom = _blossom_set->find(it);
 		          for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);
 		               jt != INVALID; ++jt) {
 		            _status->set(jt, MATCHED);
+		          }
 		          _blossom_set->eraseClass(blossom);
+		        }
+		      }
 		      _tree_set->eraseClass(tree);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    MaxMatching(const Graph& graph)
 		      : _graph(graph), _matching(0), _status(0), _ear(0),
 		        _blossom_set_index(0), _blossom_set(0), _blossom_rep(0),
 		        _tree_set_index(0), _tree_set(0) {}
 		    ~MaxMatching() {
 		      destroyStructures();
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to use the
 		    /// \c run() member function.
 		    /// \n
 		    /// If you need better control on the execution, you must call
 		    /// \ref init(), \ref greedyInit() or \ref matchingInit()
 		    /// functions first, then you can start the algorithm with the \ref
-		    /// startParse() or startDense() functions.
+		    /// startSparse() or startDense() functions.
 		    ///@{
 		    /// \brief Sets the actual matching to the empty matching.
 		    ///
 		    /// Sets the actual matching to the empty matching.
 		    ///
 		    void init() {
 		      createStructures();
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        _matching->set(n, INVALID);
 		        _status->set(n, UNMATCHED);
+		      }
+		    }
 		    ///\brief Finds an initial matching in a greedy way
 		    ///
 		    ///It finds an initial matching in a greedy way.
 		    void greedyInit() {
 		      createStructures();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _matching->set(n, INVALID);
 		        _status->set(n, UNMATCHED);
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] == INVALID) {
 		          for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
 		            Node v = _graph.target(a);
 		            if ((*_matching)[v] == INVALID && v != n) {
 		              _matching->set(n, a);
 		              _status->set(n, MATCHED);
 		              _matching->set(v, _graph.oppositeArc(a));
 		              _status->set(v, MATCHED);
 		              break;
+		            }
+		          }
+		        }
+		      }
+		    }
 		    /// \brief Initialize the matching from a map containing.
 		    ///
 		    /// Initialize the matching from a \c bool valued \c Edge map. This
 		    /// map must have the property that there are no two incident edges
 		    /// with true value, ie. it contains a matching.
 		    /// \return %True if the map contains a matching.
 		    template <typename MatchingMap>
 		    bool matchingInit(const MatchingMap& matching) {
 		      createStructures();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _matching->set(n, INVALID);
 		        _status->set(n, UNMATCHED);
+		      }
 		      for(EdgeIt e(_graph); e!=INVALID; ++e) {
 		        if (matching[e]) {
 		          Node u = _graph.u(e);
 		          if ((*_matching)[u] != INVALID) return false;
 		          _matching->set(u, _graph.direct(e, true));
 		          _status->set(u, MATCHED);
 		          Node v = _graph.v(e);
 		          if ((*_matching)[v] != INVALID) return false;
 		          _matching->set(v, _graph.direct(e, false));
 		          _status->set(v, MATCHED);
+		        }
+		      }
 		      return true;
+		    }
 		    /// \brief Starts Edmonds' algorithm
 		    ///
 		    /// If runs the original Edmonds' algorithm.
 		    void startSparse() {
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          _status->set(n, EVEN);
 		          processSparse(n);
+		        }
+		      }
+		    }
 		    /// \brief Starts Edmonds' algorithm.
 		    ///
 		    /// It runs Edmonds' algorithm with a heuristic of postponing
 		    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
 		    void startDense() {
 		      for(NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_status)[n] == UNMATCHED) {
 		          (*_blossom_rep)[_blossom_set->insert(n)] = n;
 		          _tree_set->insert(n);
 		          _status->set(n, EVEN);
 		          processDense(n);
+		        }
+		      }
+		    }
 		    /// \brief Runs Edmonds' algorithm
 		    ///
 		    /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)
 		    /// or Edmonds' algorithm with a heuristic of
 		    /// postponing shrinks for dense graphs.
 		    void run() {
 		      if (countEdges(_graph) < 2 * countNodes(_graph)) {
 		        greedyInit();
 		        startSparse();
 		      } else {
 		        init();
 		        startDense();
+		      }
+		    }
 		    /// @}
 		    /// \name Primal solution
 		    /// Functions to get the primal solution, ie. the matching.
 		    /// @{
 		    ///\brief Returns the size of the current matching.
 		    ///
 		    ///Returns the size of the current matching. After \ref
 		    ///run() it returns the size of the maximum matching in the graph.
 		    int matchingSize() const {
 		      int size = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if ((*_matching)[n] != INVALID) {
 		          ++size;
+		        }
+		      }
 		      return size / 2;
+		    }
 		    /// \brief Returns true when the edge is in the matching.
 		    ///
 		    /// Returns true when the edge is in the matching.
 		    bool matching(const Edge& edge) const {
 		      return edge == (*_matching)[_graph.u(edge)];
+		    }
 		    /// \brief Returns the matching edge incident to the given node.
 		    ///
 		    /// Returns the matching edge of a \c node in the actual matching or
 		    /// INVALID if the \c node is not covered by the actual matching.
 		    Arc matching(const Node& n) const {
 		      return (*_matching)[n];
+		    }
 		    ///\brief Returns the mate of a node in the actual matching.
 		    ///
 		    ///Returns the mate of a \c node in the actual matching or
 		    ///INVALID if the \c node is not covered by the actual matching.
 		    Node mate(const Node& n) const {
 		      return (*_matching)[n] != INVALID ?
 		        _graph.target((*_matching)[n]) : INVALID;
+		    }
 		    /// @}
 		    /// \name Dual solution
 		    /// Functions to get the dual solution, ie. the decomposition.
 		    /// @{
 		    /// \brief Returns the class of the node in the Edmonds-Gallai
 		    /// decomposition.
 		    ///
 		    /// Returns the class of the node in the Edmonds-Gallai
 		    /// decomposition.
 		    Status decomposition(const Node& n) const {
 		      return (*_status)[n];
+		    }
 		    /// \brief Returns true when the node is in the barrier.
 		    ///
 		    /// Returns true when the node is in the barrier.
 		    bool barrier(const Node& n) const {
 		      return (*_status)[n] == ODD;
+		    }
 		    /// @}
 		  };
 		  /// \ingroup matching
 		  ///
 		  /// \brief Weighted matching in general graphs
 		  ///
 		  /// This class provides an efficient implementation of Edmond's
 		  /// maximum weighted matching algorithm. The implementation is based
 		  /// on extensive use of priority queues and provides
 		  /// \f$O(nm\log(n))\f$ time complexity.
 		  ///
 		  /// The maximum weighted matching problem is to find undirected
 		  /// edges in the graph with maximum overall weight and no two of
 		  /// them shares their ends. The problem can be formulated with the
 		  /// following linear program.
 		  /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
 		  /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
 		      \quad \forall B\in\mathcal{O}\f] */
 		  /// \f[x_e \ge 0\quad \forall e\in E\f]
 		  /// \f[\max \sum_{e\in E}x_ew_e\f]
 		  /// where \f$\delta(X)\f$ is the set of edges incident to a node in
 		  /// \f$X\f$, \f$\gamma(X)\f$ is the set of edges with both ends in
 		  /// \f$X\f$ and \f$\mathcal{O}\f$ is the set of odd cardinality
 		  /// subsets of the nodes.
 		  ///
 		  /// The algorithm calculates an optimal matching and a proof of the
 		  /// optimality. The solution of the dual problem can be used to check
 		  /// the result of the algorithm. The dual linear problem is the
 		  /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
 		      z_B \ge w_{uv} \quad \forall uv\in E\f] */
 		  /// \f[y_u \ge 0 \quad \forall u \in V\f]
 		  /// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
 		  /** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
 		      \frac{\vert B \vert - 1}{2}z_B\f] */
 		  ///
 		  /// The algorithm can be executed with \c run() or the \c init() and
 		  /// then the \c start() member functions. After it the matching can
 		  /// be asked with \c matching() or mate() functions. The dual
 		  /// solution can be get with \c nodeValue(), \c blossomNum() and \c
 		  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
 		  /// "BlossomIt" nested class, which is able to iterate on the nodes
 		  /// of a blossom. If the value type is integral then the dual
 		  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
 		  template <typename _Graph,
 		            typename _WeightMap = typename _Graph::template EdgeMap<int> >
 		  class MaxWeightedMatching {
 		  public:
 		    typedef _Graph Graph;
 		    typedef _WeightMap WeightMap;
 		    typedef typename WeightMap::Value Value;
 		    /// \brief Scaling factor for dual solution
 		    ///
 		    /// Scaling factor for dual solution, it is equal to 4 or 1
 		    /// according to the value type.
 		    static const int dualScale =
 		      std::numeric_limits<Value>::is_integer ? 4 : 1;
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    typedef typename Graph::template NodeMap<Value> NodePotential;
 		    typedef std::vector<Node> BlossomNodeList;
 		    struct BlossomVariable {
 		      int begin, end;
 		      Value value;
 		      BlossomVariable(int _begin, int _end, Value _value)
 		        : begin(_begin), end(_end), value(_value) {}
 		    };
 		    typedef std::vector<BlossomVariable> BlossomPotential;
 		    const Graph& _graph;
 		    const WeightMap& _weight;
 		    MatchingMap* _matching;
 		    NodePotential* _node_potential;
 		    BlossomPotential _blossom_potential;
 		    BlossomNodeList _blossom_node_list;
 		    int _node_num;
 		    int _blossom_num;
 		    typedef RangeMap<int> IntIntMap;
 		    enum Status {
 		      EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2
 		    };
 		    typedef HeapUnionFind<Value, IntNodeMap> BlossomSet;
 		    struct BlossomData {
 		      int tree;
 		      Status status;
 		      Arc pred, next;
 		      Value pot, offset;
 		      Node base;
 		    };
 		    IntNodeMap *_blossom_index;
 		    BlossomSet *_blossom_set;
 		    RangeMap<BlossomData>* _blossom_data;
 		    IntNodeMap *_node_index;
 		    IntArcMap *_node_heap_index;
 		    struct NodeData {
 		      NodeData(IntArcMap& node_heap_index)
 		        : heap(node_heap_index) {}
 		      int blossom;
 		      Value pot;
 		      BinHeap<Value, IntArcMap> heap;
 		      std::map<int, Arc> heap_index;
 		      int tree;
 		    };
 		    RangeMap<NodeData>* _node_data;
 		    typedef ExtendFindEnum<IntIntMap> TreeSet;
 		    IntIntMap *_tree_set_index;
 		    TreeSet *_tree_set;
 		    IntNodeMap *_delta1_index;
 		    BinHeap<Value, IntNodeMap> *_delta1;
 		    IntIntMap *_delta2_index;
 		    BinHeap<Value, IntIntMap> *_delta2;
 		    IntEdgeMap *_delta3_index;
 		    BinHeap<Value, IntEdgeMap> *_delta3;
 		    IntIntMap *_delta4_index;
 		    BinHeap<Value, IntIntMap> *_delta4;
 		    Value _delta_sum;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_node_potential) {
 		        _node_potential = new NodePotential(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_index);
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
+		      }
 		      if (!_node_index) {
 		        _node_index = new IntNodeMap(_graph);
 		        _node_heap_index = new IntArcMap(_graph);
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                              NodeData(*_node_heap_index));
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntIntMap(_blossom_num);
 		        _tree_set = new TreeSet(*_tree_set_index);
+		      }
 		      if (!_delta1) {
 		        _delta1_index = new IntNodeMap(_graph);
 		        _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
+		      }
 		      if (!_delta2) {
 		        _delta2_index = new IntIntMap(_blossom_num);
 		        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
+		      }
 		      if (!_delta3) {
 		        _delta3_index = new IntEdgeMap(_graph);
 		        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
+		      }
 		      if (!_delta4) {
 		        _delta4_index = new IntIntMap(_blossom_num);
 		        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
+		      }
+		    }
 		    void destroyStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_node_potential) {
 		        delete _node_potential;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_index;
 		        delete _blossom_set;
 		        delete _blossom_data;
+		      }
 		      if (_node_index) {
 		        delete _node_index;
 		        delete _node_heap_index;
 		        delete _node_data;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
 		        delete _tree_set;
+		      }
 		      if (_delta1) {
 		        delete _delta1_index;
 		        delete _delta1;
+		      }
 		      if (_delta2) {
 		        delete _delta2_index;
 		        delete _delta2;
+		      }
 		      if (_delta3) {
 		        delete _delta3_index;
 		        delete _delta3;
+		      }
 		      if (_delta4) {
 		        delete _delta4_index;
 		        delete _delta4;
+		      }
+		    }
 		    void matchedToEven(int blossom, int tree) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      if (!_blossom_set->trivial(blossom)) {
 		        (*_blossom_data)[blossom].pot -=
 * (_delta_sum - (*_blossom_data)[blossom].offset);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        int ni = (*_node_index)[n];
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        (*_node_data)[ni].pot += _delta_sum - (*_blossom_data)[blossom].offset;
 		        _delta1->push(n, (*_node_data)[ni].pot);
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.source(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 		              _delta3->push(e, rw / 2);
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[vi].heap_index.find(tree);
 		            if (it != (*_node_data)[vi].heap_index.end()) {
 		              if ((*_node_data)[vi].heap[it->second] > rw) {
 		                (*_node_data)[vi].heap.replace(it->second, e);
 		                (*_node_data)[vi].heap.decrease(e, rw);
 		                it->second = e;
+		              }
 		            } else {
 		              (*_node_data)[vi].heap.push(e, rw);
 		              (*_node_data)[vi].heap_index.insert(std::make_pair(tree, e));
+		            }
 		            if ((*_blossom_set)[v] > (*_node_data)[vi].heap.prio()) {
 		              _blossom_set->decrease(v, (*_node_data)[vi].heap.prio());
 		              if ((*_blossom_data)[vb].status == MATCHED) {
 		                if (_delta2->state(vb) != _delta2->IN_HEAP) {
 		                  _delta2->push(vb, _blossom_set->classPrio(vb) -
 		                               (*_blossom_data)[vb].offset);
 		                } else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) -
 		                           (*_blossom_data)[vb].offset){
 		                  _delta2->decrease(vb, _blossom_set->classPrio(vb) -
 		                                   (*_blossom_data)[vb].offset);
+		                }
+		              }
+		            }
+		          }
+		        }
+		      }
 		      (*_blossom_data)[blossom].offset = 0;
+		    }
 		    void matchedToOdd(int blossom) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      (*_blossom_data)[blossom].offset += _delta_sum;
 		      if (!_blossom_set->trivial(blossom)) {
 		        _delta4->push(blossom, (*_blossom_data)[blossom].pot / 2 +
 		                     (*_blossom_data)[blossom].offset);
+		      }
+		    }
 		    void evenToMatched(int blossom, int tree) {
 		      if (!_blossom_set->trivial(blossom)) {
 		        (*_blossom_data)[blossom].pot += 2 * _delta_sum;
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        (*_node_data)[ni].pot -= _delta_sum;
 		        _delta1->erase(n);
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.source(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if (vb == blossom) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		          } else if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		            int vt = _tree_set->find(vb);
 		            if (vt != tree) {
 		              Arc r = _graph.oppositeArc(e);
 		              typename std::map<int, Arc>::iterator it =
 		                (*_node_data)[ni].heap_index.find(vt);
 		              if (it != (*_node_data)[ni].heap_index.end()) {
 		                if ((*_node_data)[ni].heap[it->second] > rw) {
 		                  (*_node_data)[ni].heap.replace(it->second, r);
 		                  (*_node_data)[ni].heap.decrease(r, rw);
 		                  it->second = r;
+		                }
 		              } else {
 		                (*_node_data)[ni].heap.push(r, rw);
 		                (*_node_data)[ni].heap_index.insert(std::make_pair(vt, r));
+		              }
 		              if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
 		                _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
 		                if (_delta2->state(blossom) != _delta2->IN_HEAP) {
 		                  _delta2->push(blossom, _blossom_set->classPrio(blossom) -
 		                               (*_blossom_data)[blossom].offset);
 		                } else if ((*_delta2)[blossom] >
 		                           _blossom_set->classPrio(blossom) -
 		                           (*_blossom_data)[blossom].offset){
 		                  _delta2->decrease(blossom, _blossom_set->classPrio(blossom) -
 		                                   (*_blossom_data)[blossom].offset);
+		                }
+		              }
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[vi].heap_index.find(tree);
 		            if (it != (*_node_data)[vi].heap_index.end()) {
 		              (*_node_data)[vi].heap.erase(it->second);
 		              (*_node_data)[vi].heap_index.erase(it);
 		              if ((*_node_data)[vi].heap.empty()) {
 		                _blossom_set->increase(v, std::numeric_limits<Value>::max());
 		              } else if ((*_blossom_set)[v] < (*_node_data)[vi].heap.prio()) {
 		                _blossom_set->increase(v, (*_node_data)[vi].heap.prio());
+		              }
 		              if ((*_blossom_data)[vb].status == MATCHED) {
 		                if (_blossom_set->classPrio(vb) ==
 		                    std::numeric_limits<Value>::max()) {
 		                  _delta2->erase(vb);
 		                } else if ((*_delta2)[vb] < _blossom_set->classPrio(vb) -
 		                           (*_blossom_data)[vb].offset) {
 		                  _delta2->increase(vb, _blossom_set->classPrio(vb) -
 		                                   (*_blossom_data)[vb].offset);
+		                }
+		              }
+		            }
+		          }
+		        }
+		      }
+		    }
 		    void oddToMatched(int blossom) {
 		      (*_blossom_data)[blossom].offset -= _delta_sum;
 		      if (_blossom_set->classPrio(blossom) !=
 		          std::numeric_limits<Value>::max()) {
 		        _delta2->push(blossom, _blossom_set->classPrio(blossom) -
 		                       (*_blossom_data)[blossom].offset);
+		      }
 		      if (!_blossom_set->trivial(blossom)) {
 		        _delta4->erase(blossom);
+		      }
+		    }
 		    void oddToEven(int blossom, int tree) {
 		      if (!_blossom_set->trivial(blossom)) {
 		        _delta4->erase(blossom);
 		        (*_blossom_data)[blossom].pot -=
 * (2 * _delta_sum - (*_blossom_data)[blossom].offset);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        (*_node_data)[ni].pot +=
 * _delta_sum - (*_blossom_data)[blossom].offset;
 		        _delta1->push(n, (*_node_data)[ni].pot);
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.source(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 		              _delta3->push(e, rw / 2);
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[vi].heap_index.find(tree);
 		            if (it != (*_node_data)[vi].heap_index.end()) {
 		              if ((*_node_data)[vi].heap[it->second] > rw) {
 		                (*_node_data)[vi].heap.replace(it->second, e);
 		                (*_node_data)[vi].heap.decrease(e, rw);
 		                it->second = e;
+		              }
 		            } else {
 		              (*_node_data)[vi].heap.push(e, rw);
 		              (*_node_data)[vi].heap_index.insert(std::make_pair(tree, e));
+		            }
 		            if ((*_blossom_set)[v] > (*_node_data)[vi].heap.prio()) {
 		              _blossom_set->decrease(v, (*_node_data)[vi].heap.prio());
 		              if ((*_blossom_data)[vb].status == MATCHED) {
 		                if (_delta2->state(vb) != _delta2->IN_HEAP) {
 		                  _delta2->push(vb, _blossom_set->classPrio(vb) -
 		                               (*_blossom_data)[vb].offset);
 		                } else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) -
 		                           (*_blossom_data)[vb].offset) {
 		                  _delta2->decrease(vb, _blossom_set->classPrio(vb) -
 		                                   (*_blossom_data)[vb].offset);
+		                }
+		              }
+		            }
+		          }
+		        }
+		      }
 		      (*_blossom_data)[blossom].offset = 0;
+		    }
 		    void matchedToUnmatched(int blossom) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.target(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
+		          }
+		        }
+		      }
+		    }
 		    void unmatchedToMatched(int blossom) {
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.source(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if (vb == blossom) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		          } else if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		            int vt = _tree_set->find(vb);
 		            Arc r = _graph.oppositeArc(e);
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[ni].heap_index.find(vt);
 		            if (it != (*_node_data)[ni].heap_index.end()) {
 		              if ((*_node_data)[ni].heap[it->second] > rw) {
 		                (*_node_data)[ni].heap.replace(it->second, r);
 		                (*_node_data)[ni].heap.decrease(r, rw);
 		                it->second = r;
+		              }
 		            } else {
 		              (*_node_data)[ni].heap.push(r, rw);
 		              (*_node_data)[ni].heap_index.insert(std::make_pair(vt, r));
+		            }

lemon/suurballe.h

Show inline comments

 		/* -*- C++ -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_SUURBALLE_H
 		#define LEMON_SUURBALLE_H
 		///\ingroup shortest_path
 		///\file
 		///\brief An algorithm for finding arc-disjoint paths between two
 		/// nodes having minimum total length.
 		#include <vector>
 		#include <lemon/bin_heap.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  /// \addtogroup shortest_path
 		  /// @{
 		  /// \brief Algorithm for finding arc-disjoint paths between two nodes
 		  /// having minimum total length.
 		  ///
 		  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
 		  /// finding arc-disjoint paths having minimum total length (cost)
 		  /// from a given source node to a given target node in a digraph.
 		  ///
 		  /// In fact, this implementation is the specialization of the
 		  /// \ref CapacityScaling "successive shortest path" algorithm.
 		  ///
 		  /// \tparam Digraph The digraph type the algorithm runs on.
 		  /// The default value is \c ListDigraph.
 		  /// \tparam LengthMap The type of the length (cost) map.
 		  /// The default value is <tt>Digraph::ArcMap<int></tt>.
 		  ///
 		  /// \warning Length values should be \e non-negative \e integers.
 		  ///
 		  /// \note For finding node-disjoint paths this algorithm can be used
-		  /// with \ref SplitDigraphAdaptor.
+		  /// with \ref SplitNodes.
 		#ifdef DOXYGEN
 		  template <typename Digraph, typename LengthMap>
 		#else
 		  template < typename Digraph = ListDigraph,
 		             typename LengthMap = typename Digraph::template ArcMap<int> >
 		#endif
 		  class Suurballe
+		  {
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    typedef typename LengthMap::Value Length;
 		    typedef ConstMap<Arc, int> ConstArcMap;
 		    typedef typename Digraph::template NodeMap<Arc> PredMap;
 		  public:
 		    /// The type of the flow map.
 		    typedef typename Digraph::template ArcMap<int> FlowMap;
 		    /// The type of the potential map.
 		    typedef typename Digraph::template NodeMap<Length> PotentialMap;
 		    /// The type of the path structures.
 		    typedef SimplePath<Digraph> Path;
 		  private:
 		    /// \brief Special implementation of the Dijkstra algorithm
 		    /// for finding shortest paths in the residual network.
 		    ///
 		    /// \ref ResidualDijkstra is a special implementation of the
 		    /// \ref Dijkstra algorithm for finding shortest paths in the
 		    /// residual network of the digraph with respect to the reduced arc
 		    /// lengths and modifying the node potentials according to the
 		    /// distance of the nodes.
 		    class ResidualDijkstra
+		    {
 		      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		      typedef BinHeap<Length, HeapCrossRef> Heap;
 		    private:
 		      // The digraph the algorithm runs on
 		      const Digraph &_graph;
 		      // The main maps
 		      const FlowMap &_flow;
 		      const LengthMap &_length;
 		      PotentialMap &_potential;
 		      // The distance map
 		      PotentialMap _dist;
 		      // The pred arc map
 		      PredMap &_pred;
 		      // The processed (i.e. permanently labeled) nodes
 		      std::vector<Node> _proc_nodes;
 		      Node _s;
 		      Node _t;
 		    public:
 		      /// Constructor.
 		      ResidualDijkstra( const Digraph &digraph,
 		                        const FlowMap &flow,
 		                        const LengthMap &length,
 		                        PotentialMap &potential,
 		                        PredMap &pred,
 		                        Node s, Node t ) :
 		        _graph(digraph), _flow(flow), _length(length), _potential(potential),
 		        _dist(digraph), _pred(pred), _s(s), _t(t) {}
 		      /// \brief Run the algorithm. It returns \c true if a path is found
 		      /// from the source node to the target node.
 		      bool run() {
 		        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(_s, 0);
 		        _pred[_s] = INVALID;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && heap.top() != _t) {
 		          Node u = heap.top(), v;
 		          Length d = heap.prio() + _potential[u], nd;
 		          _dist[u] = heap.prio();
 		          heap.pop();
 		          _proc_nodes.push_back(u);
 		          // Traverse outgoing arcs
 		          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 0) {
 		              v = _graph.target(e);
 		              switch(heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d + _length[e] - _potential[v]);
 		                _pred[v] = e;
 		                break;
 		              case Heap::IN_HEAP:
 		                nd = d + _length[e] - _potential[v];
 		                if (nd < heap[v]) {
 		                  heap.decrease(v, nd);
 		                  _pred[v] = e;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		              }
+		            }
+		          }
 		          // Traverse incoming arcs
 		          for (InArcIt e(_graph, u); e != INVALID; ++e) {
 		            if (_flow[e] == 1) {
 		              v = _graph.source(e);
 		              switch(heap.state(v)) {
 		              case Heap::PRE_HEAP:
 		                heap.push(v, d - _length[e] - _potential[v]);
 		                _pred[v] = e;
 		                break;
 		              case Heap::IN_HEAP:
 		                nd = d - _length[e] - _potential[v];
 		                if (nd < heap[v]) {
 		                  heap.decrease(v, nd);
 		                  _pred[v] = e;
+		                }
 		                break;
 		              case Heap::POST_HEAP:
 		                break;
+		              }
+		            }
+		          }
+		        }
 		        if (heap.empty()) return false;
 		        // Update potentials of processed nodes
 		        Length t_dist = heap.prio();
 		        for (int i = 0; i < int(_proc_nodes.size()); ++i)
 		          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
 		        return true;
+		      }
 		    }; //class ResidualDijkstra
 		  private:
 		    // The digraph the algorithm runs on
 		    const Digraph &_graph;
 		    // The length map
 		    const LengthMap &_length;
 		    // Arc map of the current flow
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    // Node map of the current potentials
 		    PotentialMap *_potential;
 		    bool _local_potential;
 		    // The source node
 		    Node _source;
 		    // The target node
 		    Node _target;
 		    // Container to store the found paths
 		    std::vector< SimplePath<Digraph> > paths;
 		    int _path_num;
 		    // The pred arc map
 		    PredMap _pred;
 		    // Implementation of the Dijkstra algorithm for finding augmenting
 		    // shortest paths in the residual network
 		    ResidualDijkstra *_dijkstra;
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    ///
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param length The length (cost) values of the arcs.
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    Suurballe( const Digraph &digraph,
 		               const LengthMap &length,
 		               Node s, Node t ) :
 		      _graph(digraph), _length(length), _flow(0), _local_flow(false),
 		      _potential(0), _local_potential(false), _source(s), _target(t),
 		      _pred(digraph) {}
 		    /// Destructor.
 		    ~Suurballe() {
 		      if (_local_flow) delete _flow;
 		      if (_local_potential) delete _potential;
 		      delete _dijkstra;
+		    }
 		    /// \brief Set the flow map.
 		    ///
 		    /// This function sets the flow map.
 		    ///
 		    /// The found flow contains only 0 and 1 values. It is the union of
 		    /// the found arc-disjoint paths.
 		    ///
 		    /// \return \c (*this)
 		    Suurballe& flowMap(FlowMap &map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Set the potential map.
 		    ///
 		    /// This function sets the potential map.
 		    ///
 		    /// The potentials provide the dual solution of the underlying
 		    /// minimum cost flow problem.
 		    ///
 		    /// \return \c (*this)
 		    Suurballe& potentialMap(PotentialMap &map) {
 		      if (_local_potential) {
 		        delete _potential;
 		        _local_potential = false;
+		      }
 		      _potential = &map;
 		      return *this;
+		    }
 		    /// \name Execution control
 		    /// The simplest way to execute the algorithm is to call the run()
 		    /// function.
 		    /// \n
 		    /// If you only need the flow that is the union of the found
 		    /// arc-disjoint paths, you may call init() and findFlow().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    ///
 		    /// \param k The number of paths to be found.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
 		    /// shortcut of the following code.
 		    /// \code
 		    ///   s.init();
 		    ///   s.findFlow(k);
 		    ///   s.findPaths();
 		    /// \endcode
 		    int run(int k = 2) {
 		      init();
 		      findFlow(k);
 		      findPaths();
 		      return _path_num;
+		    }
 		    /// \brief Initialize the algorithm.
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      // Initialize maps
 		      if (!_flow) {
 		        _flow = new FlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_potential) {
 		        _potential = new PotentialMap(_graph);
 		        _local_potential = true;
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
 		      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
 		                                        *_potential, _pred,
 		                                        _source, _target );
+		    }
 		    /// \brief Execute the successive shortest path algorithm to find
 		    /// an optimal flow.
 		    ///
 		    /// This function executes the successive shortest path algorithm to
 		    /// find a minimum cost flow, which is the union of \c k or less
 		    /// arc-disjoint paths.
 		    ///
 		    /// \return \c k if there are at least \c k arc-disjoint paths from
 		    /// \c s to \c t in the digraph. Otherwise it returns the number of
 		    /// arc-disjoint paths found.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    int findFlow(int k = 2) {
 		      // Find shortest paths
 		      _path_num = 0;
 		      while (_path_num < k) {
 		        // Run Dijkstra
 		        if (!_dijkstra->run()) break;
 		        ++_path_num;
 		        // Set the flow along the found shortest path
 		        Node u = _target;
 		        Arc e;
 		        while ((e = _pred[u]) != INVALID) {
 		          if (u == _graph.target(e)) {
 		            (*_flow)[e] = 1;
 		            u = _graph.source(e);
 		          } else {
 		            (*_flow)[e] = 0;
 		            u = _graph.target(e);
+		          }
+		        }
+		      }
 		      return _path_num;
+		    }
 		    /// \brief Compute the paths from the flow.
 		    ///
 		    /// This function computes the paths from the flow.
 		    ///
 		    /// \pre \ref init() and \ref findFlow() must be called before using
 		    /// this function.
 		    void findPaths() {
 		      // Create the residual flow map (the union of the paths not found
 		      // so far)
 		      FlowMap res_flow(_graph);
 		      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
 		      paths.clear();
 		      paths.resize(_path_num);
 		      for (int i = 0; i < _path_num; ++i) {
 		        Node n = _source;
 		        while (n != _target) {
 		          OutArcIt e(_graph, n);
 		          for ( ; res_flow[e] == 0; ++e) ;
 		          n = _graph.target(e);
 		          paths[i].addBack(e);
 		          res_flow[e] = 0;
+		        }
+		      }
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.
 		    /// \n The algorithm should be executed before using them.
 		    /// @{
 		    /// \brief Return a const reference to the arc map storing the
 		    /// found flow.
 		    ///
 		    /// This function returns a const reference to the arc map storing
 		    /// the flow that is the union of the found arc-disjoint paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Return a const reference to the node map storing the
 		    /// found potentials (the dual solution).
 		    ///
 		    /// This function returns a const reference to the node map storing
 		    /// the found potentials that provide the dual solution of the
 		    /// underlying minimum cost flow problem.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    const PotentialMap& potentialMap() const {
 		      return *_potential;
+		    }
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    /// It is \c 1 if the arc is involved in one of the found paths,
 		    /// otherwise it is \c 0.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Return the potential of the given node.
 		    ///
 		    /// This function returns the potential of the given node.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length potential(const Node& node) const {
 		      return (*_potential)[node];
+		    }
 		    /// \brief Return the total length (cost) of the found paths (flow).
 		    ///
 		    /// This function returns the total length (cost) of the found paths
 		    /// (flow). The complexity of the function is \f$ O(e) \f$.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    Length totalLength() const {
 		      Length c = 0;
 		      for (ArcIt e(_graph); e != INVALID; ++e)
 		        c += (*_flow)[e] * _length[e];
 		      return c;
+		    }
 		    /// \brief Return the number of the found paths.
 		    ///
 		    /// This function returns the number of the found paths.
 		    ///
 		    /// \pre \ref run() or \ref findFlow() must be called before using
 		    /// this function.
 		    int pathNum() const {
 		      return _path_num;
+		    }
 		    /// \brief Return a const reference to the specified path.
 		    ///
 		    /// This function returns a const reference to the specified path.
 		    ///
 		    /// \param i The function returns the \c i-th path.
 		    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
 		    ///
 		    /// \pre \ref run() or \ref findPaths() must be called before using
 		    /// this function.
 		    Path path(int i) const {
 		      return paths[i];
+		    }
 		    /// @}
 		  }; //class Suurballe
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_SUURBALLE_H

0 comments (0 inline)

RhodeCode

Login to your account