RhodeCode

@ingroup datas

\brief Auxiliary data structures implemented in LEMON.

This group contains some data structures implemented in LEMON in

order to make it easier to implement combinatorial algorithms.

*/

/**

@defgroup algs Algorithms

\brief This group contains the several algorithms

implemented in LEMON.

This group contains the several algorithms

implemented in LEMON.

*/

   for solving the \e all-pairs \e shortest \e paths \e problem when arc

   lenghts can be either positive or negative, but the digraph should

   not contain directed cycles with negative total length.

 - \ref Suurballe A successive shortest path algorithm for finding

   arc-disjoint paths between two nodes having minimum total length.

*/

/**

@defgroup max_flow Maximum Flow Algorithms

@ingroup algs

\brief Algorithms for finding maximum flows.

This group contains the algorithms for finding maximum flows and

feasible circulations.

The \e maximum \e flow \e problem is to find a flow of maximum value between

The \e minimum \e cut \e problem is to find a non-empty and non-complete

\f$X\f$ subset of the nodes with minimum overall capacity on

outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

cut is the \f$X\f$ solution of the next optimization problem:

\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

LEMON contains several algorithms related to minimum cut problems:

- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

  in directed graphs.

- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for

  calculating minimum cut in undirected graphs.

- \ref GomoryHu "Gomory-Hu tree computation" for calculating

  all-pairs minimum cut in undirected graphs.

If you want to find minimum cut just between two distinict nodes,

see the \ref max_flow "maximum flow problem".

*/

/**

@defgroup matching Matching Algorithms

@ingroup algs

\brief Algorithms for finding matchings in graphs and bipartite graphs.

This group contains the algorithms for calculating

matchings in graphs and bipartite graphs. The general matching problem is

finding a subset of the edges for which each node has at most one incident

edge.

  Edmond's blossom shrinking algorithm for calculating maximum weighted

  perfect matching in general graphs.

\image html bipartite_matching.png

\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

*/

/**

@ingroup algs

*/

/**

@defgroup auxalg Auxiliary Algorithms

@ingroup algs

\brief Auxiliary algorithms implemented in LEMON.

This group contains some algorithms implemented in LEMON

in order to make it easier to implement complex algorithms.

*/

/**

@defgroup gen_opt_group General Optimization Tools

\brief This group contains some general optimization frameworks

implemented in LEMON.

This group contains some general optimization frameworks

implemented in LEMON.

*/

@ingroup io_group

\brief General \c EPS drawer and graph exporter

This group contains general \c EPS drawing methods and special

graph exporting tools.

*/

/**

@ingroup io_group

\brief Read and write files in DIMACS format

Tools to read a digraph from or write it to a file in DIMACS format data.

*/

/**

@defgroup nauty_group NAUTY Format

@defgroup map_concepts Map Concepts

@ingroup concept

\brief Skeleton and concept checking classes for maps

This group contains the skeletons and concept checking classes of maps.

*/

/**

\anchor demoprograms

@defgroup demos Demo Programs

Some demo programs are listed here. Their full source codes can be found in

the \c demo subdirectory of the source tree.

In order to compile them, use the <tt>make demo</tt> or the

<tt>make check</tt> commands.

*/

}

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

    typedef GR Digraph;

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

    ///arcs of the shortest paths.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \c PredMap.

    ///This function instantiates a \ref PredMap.

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

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

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

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#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.

    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.

    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 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c PredMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c PredMap type.

    template <class T>

    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {

      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c DistMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c DistMap type.

    template <class T>

    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {

      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c ReachedMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c ReachedMap type.

    template <class T>

    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {

      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;

    };

    template <class T>

    struct SetProcessedMapTraits : public Traits {

      typedef T ProcessedMap;

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c ProcessedMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c ProcessedMap type.

    template <class T>

    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {

      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;

    };

    struct SetStandardProcessedMapTraits : public Traits {

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

      static ProcessedMap *createProcessedMap(const Digraph &g)

      return *this;

    }

  public:

    ///\name Execution Control

    ///The simplest way to execute the BFS algorithm is to use one of the

    ///member functions called \ref run(Node) "run()".\n

    ///\ref addSource(). Finally the actual path computation can be

    ///performed with one of the \ref start() functions.

    ///@{

    ///\brief Initializes the internal data structures.

    ///

    ///Initializes the internal data structures.

    ///\name Query Functions

    ///The results of the BFS algorithm can be obtained using these

    ///functions.\n

    ///Either \ref run(Node) "run()" or \ref start() should be called

    ///before using them.

    ///@{

    ///

    ///\warning \c t should be reached from the root(s).

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Path path(Node t) const { return Path(*G, *_pred, t); }

    ///

    ///\warning If node \c v is not reached from the root(s), then

    ///the return value of this function is undefined.

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    int dist(Node v) const { return (*_dist)[v]; }

    ///This function returns the 'previous arc' of the shortest path

    ///tree for the node \c v, i.e. it returns the last arc of a

    ///shortest path from a root to \c v. It is \c INVALID if \c v

    ///is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Arc predArc(Node v) const { return (*_pred)[v];}

    ///This function returns the 'previous node' of the shortest path

    ///tree for the node \c v, i.e. it returns the last but one node

    ///if \c v is not reached from the root(s) or if \c v is a root.

    ///

    ///The shortest path tree used here is equal to the shortest path

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:

                                  G->source((*_pred)[v]); }

    ///\brief Returns a const reference to the node map that stores the

    /// distances of the nodes.

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    const DistMap &distMap() const { return *_dist;}

    ///\brief Returns a const reference to the node map that stores the

    ///predecessor arcs.

    ///

    ///Returns a const reference to the node map that stores the predecessor

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    const PredMap &predMap() const { return *_pred;}

    ///Returns \c true if \c v is reached from the root(s).

    ///

    ///\pre Either \ref run(Node) "run()" or \ref init()

    ///must be called before using this function.

    bool reached(Node v) const { return (*_reached)[v]; }

    ///@}

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

    typedef GR Digraph;

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

    ///arcs of the shortest paths.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the shortest paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a PredMap.

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

    ///PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    ///By default it is a NullMap.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a ProcessedMap.

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

    ///we would like to define the ProcessedMap.

#ifdef DOXYGEN

#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.

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

    ///Instantiates a ReachedMap.

    ///This function instantiates a ReachedMap.

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

    ///we would like to define the 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.

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

    ///Instantiates a DistMap.

    ///This function instantiates a DistMap.

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

    ///the DistMap

    static DistMap *createDistMap(const Digraph &g)

    {

      return new DistMap(g);

    }

    ///The type of the shortest paths.

    ///The type of the shortest paths.

    typedef lemon::Path<Digraph> Path;

  };

  /// Default traits class used by BfsWizard

  template<class GR>

  class BfsWizardBase : public BfsWizardDefaultTraits<GR>

  {

    typedef BfsWizardDefaultTraits<GR> Base;

  protected:

    //The type of the nodes in the digraph.

    typedef typename Base::Digraph::Node Node;

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

    void *_path;

    //Pointer to the distance of the target node.

    int *_di;

    public:

    /// Constructor.

    /// 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.

  ///

  /// 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.

    }

    template<class T>

    struct SetPredMapBase : public Base {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &) { return 0; };

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

    };

    ///

    template<class T>

    BfsWizard<SetPredMapBase<T> > predMap(const T &t)

    {

      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<SetPredMapBase<T> >(*this);

    }

    template<class T>

    struct SetReachedMapBase : public Base {

      typedef T ReachedMap;

      static ReachedMap *createReachedMap(const Digraph &) { return 0; };

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

    };

    ///

    template<class T>

    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)

    {

      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<SetReachedMapBase<T> >(*this);

    }

    template<class T>

    struct SetDistMapBase : public Base {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph &) { return 0; };

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

    };

    ///

    template<class T>

    BfsWizard<SetDistMapBase<T> > distMap(const T &t)

    {

      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<SetDistMapBase<T> >(*this);

    }

    template<class T>

    struct SetProcessedMapBase : public Base {

      typedef T ProcessedMap;

      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };

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

    };

    ///

    template<class T>

    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)

    {

      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));

      return BfsWizard<SetProcessedMapBase<T> >(*this);

    }

    template<class T>

  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.

    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 *this;

    }

  public:

    /// \name Execution Control

    /// The simplest way to execute the BFS algorithm is to use one of the

    /// member functions called \ref run(Node) "run()".\n

    /// \ref addSource(). Finally the actual path computation can be

    /// performed with one of the \ref start() functions.

    /// @{

    /// \brief Initializes the internal data structures.

    ///

    /// Initializes the internal data structures.

    /// \name Query Functions

    /// The results of the BFS algorithm can be obtained using these

    /// functions.\n

    /// Either \ref run(Node) "run()" or \ref start() should be called

    /// before using them.

    ///@{

    ///

    /// Returns \c true if \c v is reached from the root(s).

    ///

    /// \pre Either \ref run(Node) "run()" or \ref init()

    /// must be called before using this function.

    bool reached(Node v) const { return (*_reached)[v]; }

    ///@}

    typedef MapExtender Map;

    typedef typename Parent::Key Item;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    typedef typename Parent::Reference Reference;

    typedef typename Parent::ConstReference ConstReference;

    class MapIt;

    class ConstMapIt;

    friend class MapIt;

    friend class ConstMapIt;

  public:

    typedef SubMapExtender Map;

    typedef typename Parent::Key Item;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    typedef typename Parent::Reference Reference;

    typedef typename Parent::ConstReference ConstReference;

    class MapIt;

    class ConstMapIt;

    friend class MapIt;

    friend class ConstMapIt;

  public:

    /// \brief The type of the flow and supply values.

    typedef typename SupplyMap::Value Value;

    /// \brief The type of the map that stores the flow values.

    ///

    /// The type of the map that stores the flow values.

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

    /// concept.

    typedef typename Digraph::template ArcMap<Value> FlowMap;

    /// \brief Instantiates a FlowMap.

    ///

    /// This function instantiates a \ref FlowMap.

    /// \param digraph The digraph for which we would like to define

    /// the flow map.

    static FlowMap* createFlowMap(const Digraph& digraph) {

      return new FlowMap(digraph);

    }

    /// \brief The elevator type used by the algorithm.

    ///

    /// The elevator type used by the algorithm.

    ///

    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;

    /// \brief Instantiates an Elevator.

    ///

    /// This function instantiates an \ref Elevator.

    /// \param digraph The digraph for which we would like to define

    /// the elevator.

    /// \param max_level The maximum level of the elevator.

    static Elevator* createElevator(const Digraph& digraph, int max_level) {

    /// Returns a const reference to the tolerance object used by

    /// the algorithm.

    const Tolerance& tolerance() const {

      return _tol;

    }

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call \ref run().\n

    /// the \ref start() function.

    ///@{

    /// Initializes the internal data structures.

    /// Initializes the internal data structures and sets all flow values

    /// to the lower bound.

        return *static_cast<Value *>(0);

      }

      /// Sets the value associated with the given key.

      void set(const Key &k,const Value &t) { operator[](k)=t; }

      template<typename _ReferenceMap>

      struct Constraints {

          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();

          ref = m[key];

          m[key] = val;

          m[key] = ref;

          m[key] = cref;

          own_ref = m[own_key];

          m[own_key] = own_val;

          m[own_key] = own_ref;

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

    typedef GR Digraph;

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

    ///arcs of the %DFS paths.

    ///

    ///The type of the map that stores the predecessor

    ///arcs of the %DFS paths.

    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;

    ///Instantiates a \c PredMap.

    ///This function instantiates a \ref PredMap.

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

    ///\ref PredMap.

    static PredMap *createPredMap(const Digraph &g)

    {

      return new PredMap(g);

    }

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

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

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a \c ProcessedMap.

    ///This function instantiates a \ref ProcessedMap.

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

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

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const Digraph &g)

#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.

    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.

    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 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c PredMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c PredMap type.

    template <class T>

    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {

      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c DistMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c DistMap type.

    template <class T>

    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {

      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetReachedMapTraits : public Traits {

      typedef T ReachedMap;

        return 0; // ignore warnings

      }

    };

    ///\brief \ref named-templ-param "Named parameter" for setting

    ///\c ReachedMap type.

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\c ReachedMap type.

    template <class T>

    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {