RhodeCode

--without-cplex

   Disable CPLEX support.

--with-soplex[=PREFIX]

   Enable SoPlex support (default). You should specify the prefix too if

   you installed SoPlex to some non-standard location (e.g. your home

   directory). If it is not found, SoPlex support will be disabled.

--with-soplex-includedir=DIR

   The directory where the SoPlex header files are located. This is only

   useful when the SoPlex headers and libraries are not under the same

   prefix (which is unlikely).

--with-soplex-libdir=DIR

   The directory where the SoPlex libraries are located. This is only

   useful when the SoPlex headers and libraries are not under the same

   prefix (which is unlikely).

--without-soplex

   Disable SoPlex support.

--with-coin[=PREFIX]

   Enable support for COIN-OR solvers (CLP and CBC). You should

   specify the prefix too. (by default, COIN-OR tools install

   themselves to the source code directory). This command enables the

   solvers that are actually found.

--with-coin-includedir=DIR

   The directory where the COIN-OR header files are located. This is

   only useful when the COIN-OR headers and libraries are not under

   the same prefix (which is unlikely).

--with-coin-libdir=DIR

   The directory where the COIN-OR libraries are located. This is only

   useful when the COIN-OR headers and libraries are not under the

   same prefix (which is unlikely).

--without-coin

   Disable COIN-OR support.

SET(PACKAGE_NAME ${PROJECT_NAME})

SET(PACKAGE_VERSION ${PROJECT_VERSION})

SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})

SET(abs_top_builddir ${PROJECT_BINARY_DIR})

CONFIGURE_FILE(

  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in

  ${PROJECT_BINARY_DIR}/doc/Doxyfile

  @ONLY

)

IF(DOXYGEN_EXECUTABLE AND PYTHONINTERP_FOUND AND GHOSTSCRIPT_EXECUTABLE)

  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)

  SET(GHOSTSCRIPT_OPTIONS -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha)

  ADD_CUSTOM_TARGET(html

    COMMAND ${CMAKE_COMMAND} -E remove_directory gen-images

    COMMAND ${CMAKE_COMMAND} -E make_directory gen-images

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps

    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps

    COMMAND ${CMAKE_COMMAND} -E remove_directory html

    COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox

    COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile

    WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}

  )

  SET_TARGET_PROPERTIES(html PROPERTIES PROJECT_LABEL BUILD_DOC)

  IF(UNIX)

    INSTALL(

      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/

      DESTINATION share/doc/lemon/html

      COMPONENT html_documentation

    )

  ELSEIF(WIN32)

    INSTALL(

      DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/

      DESTINATION doc

      COMPONENT html_documentation

    )

  ENDIF()

ENDIF()

EXTRA_DIST += \

	doc/Doxyfile.in \

	doc/DoxygenLayout.xml \

	doc/coding_style.dox \

	doc/dirs.dox \

	doc/groups.dox \

	doc/lgf.dox \

	doc/license.dox \

	doc/mainpage.dox \

	doc/migration.dox \

	doc/min_cost_flow.dox \

	doc/named-param.dox \

	doc/namespaces.dox \

	doc/html \

	doc/CMakeLists.txt

DOC_EPS_IMAGES18 = \

	grid_graph.eps \

	nodeshape_0.eps \

	nodeshape_1.eps \

	nodeshape_2.eps \

	nodeshape_3.eps \

	nodeshape_4.eps

DOC_EPS_IMAGES27 = \

	bipartite_matching.eps \

	bipartite_partitions.eps \

	connected_components.eps \

	edge_biconnected_components.eps \

	node_biconnected_components.eps \

	strongly_connected_components.eps

DOC_EPS_IMAGES = \

	$(DOC_EPS_IMAGES18) \

	$(DOC_EPS_IMAGES27)

DOC_PNG_IMAGES = \

	$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png)

EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%)

doc/html:

	$(MAKE) $(AM_MAKEFLAGS) html

GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4

$(DOC_EPS_IMAGES18:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps

	-mkdir doc/gen-images

	if test ${gs_found} = yes; then \

	  $(GS_COMMAND) -sDEVICE=pngalpha -r18 -sOutputFile=$@ $<; \

	else \

	  echo; \

	  echo "Ghostscript not found."; \

	  echo; \

	  exit 1; \

	fi

$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps

	-mkdir doc/gen-images

	if test ${gs_found} = yes; then \

	  $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \

	else \

	  echo; \

	  echo "Ghostscript not found."; \

	  echo; \

	  exit 1; \

	fi

references.dox: doc/references.bib

	if test ${python_found} = yes; then \

	  cd doc; \

	  python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \

	  cd ..; \

	else \

	  echo; \

	  echo "Python not found."; \

	  echo; \

	  exit 1; \

    static PredMap *createPredMap(const GR& g) {

      return new PredMap(g);

    }

    /// \brief The type of the map that stores the distances of the nodes.

    ///

    /// The type of the map that stores the distances of the nodes.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;

    /// \brief Instantiates a \c DistMap.

    ///

    /// This function instantiates a \ref DistMap. 

    /// \param g is the digraph to which we would like to define the 

    /// \ref DistMap.

    static DistMap *createDistMap(const GR& g) {

      return new DistMap(g);

    }

  };

  /// \brief %BellmanFord algorithm class.

  ///

  /// \ingroup shortest_path

  /// This class provides an efficient implementation of the Bellman-Ford 

  /// algorithm. The maximum time complexity of the algorithm is

  /// <tt>O(ne)</tt>.

  ///

  /// The Bellman-Ford algorithm solves the single-source shortest path

  /// problem when the arcs can have negative lengths, but the digraph

  /// should not contain directed cycles with negative total length.

  /// If all arc costs are non-negative, consider to use the Dijkstra

  /// algorithm instead, since it is more efficient.

  ///

  /// The arc lengths are passed to the algorithm using a

  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any 

  /// kind of length. The type of the length values is determined by the

  /// \ref concepts::ReadMap::Value "Value" type of the length map.

  ///

  /// There is also a \ref bellmanFord() "function-type interface" for the

  /// Bellman-Ford algorithm, which is convenient in the simplier cases and

  /// it can be used easier.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// The default type is \ref ListDigraph.

  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies

  /// the lengths of the arcs. The default map type is

  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename LEN, typename TR>

#else

  template <typename GR=ListDigraph,

            typename LEN=typename GR::template ArcMap<int>,

            typename TR=BellmanFordDefaultTraits<GR,LEN> >

#endif

  class BellmanFord {

  public:

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

    /// \brief The type of the arc lengths.

    typedef typename TR::LengthMap::Value Value;

    /// \brief The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    /// \brief The type of the map that stores the last

    /// arcs of the shortest paths.

    typedef typename TR::PredMap PredMap;

    /// \brief The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    /// The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///\brief The \ref BellmanFordDefaultOperationTraits

    /// "operation traits class" of the algorithm.

    typedef typename TR::OperationTraits OperationTraits;

    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    // Pointer to the underlying digraph.

    const Digraph *_gr;

    // Pointer to the length map

    const LengthMap *_length;

    // Pointer to the map of predecessors arcs.

    PredMap *_pred;

    // Indicates if _pred is locally allocated (true) or not.

    bool _local_pred;

    // Pointer to the map of distances.

    DistMap *_dist;

    typedef typename Base::Digraph::Node Node;

    // Pointer to the underlying digraph.

    void *_graph;

    // Pointer to the length map

    void *_length;

    // Pointer to the map of predecessors arcs.

    void *_pred;

    // Pointer to the map of distances.

    void *_dist;

    //Pointer to the shortest path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    void *_di;

    public:

    /// Constructor.

    /// This constructor does not require parameters, it initiates

    /// all of the attributes to default values \c 0.

    BellmanFordWizardBase() :

      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}

    /// Constructor.

    /// This constructor requires two parameters,

    /// others are initiated to \c 0.

    /// \param gr The digraph the algorithm runs on.

    /// \param len The length map.

    BellmanFordWizardBase(const GR& gr, 

			  const LEN& len) :

      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))), 

      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))), 

      _pred(0), _dist(0), _path(0), _di(0) {}

  };

  /// \brief Auxiliary class for the function-type interface of the

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  ///

  /// This auxiliary class is created to implement the

  /// \ref bellmanFord() "function-type interface" of the

  /// \ref BellmanFord "Bellman-Ford" algorithm.

  /// It does not have own \ref run() method, it uses the

  /// functions and features of the plain \ref BellmanFord.

  ///

  /// This class should only be used through the \ref bellmanFord()

  /// function, which makes it easier to use the algorithm.

  template<class TR>

  class BellmanFordWizard : public TR {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt ArcIt;

    typedef typename TR::LengthMap LengthMap;

    typedef typename LengthMap::Value Value;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::Path Path;

  public:

    /// Constructor.

    BellmanFordWizard() : TR() {}

    /// \brief Constructor that requires parameters.

    ///

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    /// \param gr The digraph the algorithm runs on.

    /// \param len The length map.

    BellmanFordWizard(const Digraph& gr, const LengthMap& len) 

      : TR(gr, len) {}

    /// \brief Copy constructor

    BellmanFordWizard(const TR &b) : TR(b) {}

    ~BellmanFordWizard() {}

    /// \brief Runs the Bellman-Ford algorithm from the given source node.

    ///    

    /// This method runs the Bellman-Ford algorithm from the given source

    /// node in order to compute the shortest path to each node.

    void run(Node s) {

      BellmanFord<Digraph,LengthMap,TR> 

	bf(*reinterpret_cast<const Digraph*>(Base::_graph), 

           *reinterpret_cast<const LengthMap*>(Base::_length));

      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

      bf.run(s);

    }

    static ProcessedMap *createProcessedMap(const Digraph &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that indicates which nodes are reached.

    ///The type of the map that indicates which nodes are reached.

    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    ///Instantiates a \c ReachedMap.

    ///This function instantiates a \ref ReachedMap.

    ///\param g is the digraph, to which

    ///we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &g)

    {

      return new ReachedMap(g);

    }

    ///The type of the map that stores the distances of the nodes.

    ///The type of the map that stores the distances of the nodes.

    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a \c DistMap.

    ///This function instantiates a \ref DistMap.

    ///\param g is the digraph, to which we would like to define the

    ///\ref DistMap.

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///There is also a \ref bfs() "function-type interface" for the BFS

  ///algorithm, which is convenient in the simplier cases and it can be

  ///used easier.

  ///

  ///\tparam GR The type of the digraph the algorithm runs on.

  ///The default type is \ref ListDigraph.

#ifdef DOXYGEN

  template <typename GR,

            typename TR>

#else

  template <typename GR=ListDigraph,

            typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    ///The type of the digraph the algorithm runs on.

    typedef typename TR::Digraph Digraph;

    ///\brief The type of the map that stores the predecessor arcs of the

    ///shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map that stores the distances of the nodes.

    typedef typename TR::DistMap DistMap;

    ///The type of the map that indicates which nodes are reached.

    typedef typename TR::ReachedMap ReachedMap;

    ///The type of the map that indicates which nodes are processed.

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The type of the paths.

    typedef PredMapPath<Digraph, PredMap> Path;

    ///The \ref BfsDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *G;

    //Pointer to the map of predecessor arcs.

    PredMap *_pred;

    //Indicates if _pred is locally allocated (true) or not.

    bool local_pred;

    //Pointer to the map of distances.

    DistMap *_dist;

    //Indicates if _dist is locally allocated (true) or not.

    bool local_dist;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    typedef BfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

    //Pointer to the digraph the algorithm runs on.

    void *_g;

    //Pointer to the map of reached nodes.

    void *_reached;

    //Pointer to the map of processed nodes.

    void *_processed;

    //Pointer to the map of predecessors arcs.

    void *_pred;

    //Pointer to the map of distances.

    void *_dist;

    //Pointer to the shortest path to the target node.

    void *_path;

    //Pointer to the distance of the target node.

    int *_di;

    public:

    /// Constructor.

    /// This constructor does not require parameters, it initiates

    /// all of the attributes to \c 0.

    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),

                      _dist(0), _path(0), _di(0) {}

    /// Constructor.

    /// This constructor requires one parameter,

    /// others are initiated to \c 0.

    /// \param g The digraph the algorithm runs on.

    BfsWizardBase(const GR &g) :

      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),

      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}

  };

  /// Auxiliary class for the function-type interface of BFS algorithm.

  /// This auxiliary class is created to implement the

  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.

  /// It does not have own \ref run(Node) "run()" method, it uses the

  /// functions and features of the plain \ref Bfs.

  ///

  /// This class should only be used through the \ref bfs() function,

  /// which makes it easier to use the algorithm.

  template<class TR>

  class BfsWizard : public TR

  {

    typedef TR Base;

    typedef typename TR::Digraph Digraph;

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    typedef typename TR::PredMap PredMap;

    typedef typename TR::DistMap DistMap;

    typedef typename TR::ReachedMap ReachedMap;

    typedef typename TR::ProcessedMap ProcessedMap;

    typedef typename TR::Path Path;

  public:

    /// Constructor.

    BfsWizard() : TR() {}

    /// Constructor that requires parameters.

    /// Constructor that requires parameters.

    /// These parameters will be the default values for the traits class.

    /// \param g The digraph the algorithm runs on.

    BfsWizard(const Digraph &g) :

      TR(g) {}

    ///Copy constructor

    BfsWizard(const TR &b) : TR(b) {}

    ~BfsWizard() {}

    ///Runs BFS algorithm from the given source node.

    ///This method runs BFS algorithm from node \c s

    ///in order to compute the shortest path to each node.

    void run(Node s)

    {

      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));

      if (Base::_pred)

        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

      if (Base::_dist)

        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));

      if (Base::_reached)

  /// \tparam GR The type of the digraph the algorithm runs on.

  template<class GR>

  struct BfsVisitDefaultTraits {

    /// \brief The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    ///

    /// The type of the map that indicates which nodes are reached.

    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a ReachedMap.

    /// \param digraph is the digraph, to which

    /// we would like to define the ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///

  /// \brief BFS algorithm class with visitor interface.

  ///

  /// This class provides an efficient implementation of the BFS algorithm

  /// with visitor interface.

  ///

  /// The BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// the member functions of the \c Visitor class on every BFS event.

  ///

  /// This interface of the BFS algorithm should be used in special cases

  /// when extra actions have to be performed in connection with certain

  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()

  /// instead.

  ///

  /// \tparam GR The type of the digraph the algorithm runs on.

  /// The default type is \ref ListDigraph.

  /// The value of GR is not used directly by \ref BfsVisit,

  /// it is only passed to \ref BfsVisitDefaultTraits.

  /// \tparam VS The Visitor type that is used by the algorithm.

  /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which

  /// does not observe the BFS events. If you want to observe the BFS

  /// events, you should implement your own visitor class.

#ifdef DOXYGEN

  template <typename GR, typename VS, typename TR>

#else

  template <typename GR = ListDigraph,

            typename VS = BfsVisitor<GR>,

            typename TR = BfsVisitDefaultTraits<GR> >

#endif

  class BfsVisit {

  public:

    ///The traits class.

    typedef TR Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;

    ///The visitor type used by the algorithm.

    typedef VS Visitor;

    ///The type of the map that indicates which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    //Pointer to the underlying digraph.

    const Digraph *_digraph;

    //Pointer to the visitor object.

    Visitor *_visitor;

    //Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    //Indicates if _reached is locally allocated (true) or not.

    bool local_reached;

    std::vector<typename Digraph::Node> _list;

    int _list_front, _list_back;

    //Creates the maps if necessary.

    void create_maps() {

      if(!_reached) {

        local_reached = true;

        _reached = Traits::createReachedMap(*_digraph);

      }

    }

namespace lemon {

  /// \brief Default traits class of CapacityScaling algorithm.

  ///

  /// Default traits class of CapacityScaling algorithm.

  /// \tparam GR Digraph type.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// and supply values. By default it is \c int.

  /// \tparam C The number type used for costs and potentials.

  /// By default it is the same as \c V.

  template <typename GR, typename V = int, typename C = V>

  struct CapacityScalingDefaultTraits

  {

    /// The type of the digraph

    typedef GR Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef V Value;

    /// The type of the arc costs

    typedef C Cost;

    /// \brief The type of the heap used for internal Dijkstra computations.

    ///

    /// The type of the heap used for internal Dijkstra computations.

    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,

    /// its priority type must be \c Cost and its cross reference type

    /// must be \ref RangeMap "RangeMap<int>".

    typedef BinHeap<Cost, RangeMap<int> > Heap;

  };

  /// \addtogroup min_cost_flow_algs

  /// @{

  /// \brief Implementation of the Capacity Scaling algorithm for

  /// finding a \ref min_cost_flow "minimum cost flow".

  ///

  /// \ref CapacityScaling implements the capacity scaling version

  /// of the successive shortest path algorithm for finding a

  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,

  /// \ref edmondskarp72theoretical. It is an efficient dual

  /// solution method.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam V The number type used for flow amounts, capacity bounds

  /// \tparam C The number type used for costs and potentials in the

  ///

  /// \warning Both number types must be signed and all input data must

  /// be integer.

  /// \warning This algorithm does not support negative costs for such

  /// arcs that have infinite upper bound.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

             typename TR = CapacityScalingDefaultTraits<GR, V, C> >

#endif

  class CapacityScaling

  {

  public:

    /// The type of the digraph

    typedef typename TR::Digraph Digraph;

    /// The type of the flow amounts, capacity bounds and supply values

    typedef typename TR::Value Value;

    /// The type of the arc costs

    typedef typename TR::Cost Cost;

    /// The type of the heap used for internal Dijkstra computations

    typedef typename TR::Heap Heap;

    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm

    typedef TR Traits;

  public:

    /// \brief Problem type constants for the \c run() function.

    ///

    /// Enum type containing the problem type constants that can be

    /// returned by the \ref run() function of the algorithm.

    enum ProblemType {

      /// The problem has no feasible solution (flow).

      INFEASIBLE,

      /// The problem has optimal solution (i.e. it is feasible and

      /// bounded), and the algorithm has found optimal flow and node

      /// potentials (primal and dual solutions).

      OPTIMAL,

      /// The digraph contains an arc of negative cost and infinite

      /// upper bound. It means that the objective function is unbounded

      /// on that arc, however, note that it could actually be bounded

      /// over the feasible flows, but this algroithm cannot handle

      /// these cases.

      UNBOUNDED

    };

     The exact formulation of this problem is the following.

     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$

     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and

     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$

     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$

     denotes the signed supply values of the nodes.

     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$

     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with

     \f$-sup(u)\f$ demand.

     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$

     solution of the following problem.

     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)

     \geq sup(u) \quad \forall u\in V, \f]

     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]

     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be

     zero or negative in order to have a feasible solution (since the sum

     of the expressions on the left-hand side of the inequalities is zero).

     It means that the total demand must be greater or equal to the total

     supply and all the supplies have to be carried out from the supply nodes,

     but there could be demands that are not satisfied.

     If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand

     constraints have to be satisfied with equality, i.e. all demands

     have to be satisfied and all supplies have to be used.

     If you need the opposite inequalities in the supply/demand constraints

     (i.e. the total demand is less than the total supply and all the demands

     have to be satisfied while there could be supplies that are not used),

     then you could easily transform the problem to the above form by reversing

     the direction of the arcs and taking the negative of the supply values

     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).

     This algorithm either calculates a feasible circulation, or provides

     a \ref barrier() "barrier", which prooves that a feasible soultion

     cannot exist.

     Note that this algorithm also provides a feasible solution for the

     \ref min_cost_flow "minimum cost flow problem".

     \tparam GR The type of the digraph the algorithm runs on.

     \tparam LM The type of the lower bound map. The default

     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".

     \tparam UM The type of the upper bound (capacity) map.

     The default map type is \c LM.

     \tparam SM The type of the supply map. The default map type is

     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".

  */

#ifdef DOXYGEN

template< typename GR,

          typename LM,

          typename UM,

          typename SM,

          typename TR >

#else

template< typename GR,

          typename LM = typename GR::template ArcMap<int>,

          typename UM = LM,

          typename SM = typename GR::template NodeMap<typename UM::Value>,

          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >

#endif

  class Circulation {

  public:

    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.

    typedef TR Traits;

    ///The type of the digraph the algorithm runs on.

    typedef typename Traits::Digraph Digraph;