RhodeCode

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

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

    /// \c OperationTraits type.

    template <class T>

    struct SetOperationTraits

    ///

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

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    ///

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

    ///

    /// \pre Either \ref run() or \ref init() must be called before

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

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

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

    ///Instantiates a \c ProcessedMap.

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

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

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

    ///Instantiates a ProcessedMap.

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

      /// This iterator goes through each node of the digraph.

      /// of nodes in a digraph \c g of type \c %Digraph like this:

      ///\code

      /// This iterator goes trough the \e outgoing arcs of a certain node

      /// of a digraph.

      /// of outgoing arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      /// This iterator goes trough the \e incoming arcs of a certain node

      /// of a digraph.

      /// of incoming arcs of a node \c n

      /// in a digraph \c g of type \c %Digraph as follows.

      /// This iterator goes through each arc of the digraph.

      /// of arcs in a digraph \c g of type \c %Digraph as follows:

      ///\code

      /// This iterator goes through each node of the graph.

      /// of nodes in a graph \c g of type \c %Graph like this:

      ///\code

      /// This iterator goes through each edge of the graph.

      /// of edges in a graph \c g of type \c %Graph as follows:

      ///\code

      /// This iterator goes trough the incident undirected edges

      /// of a certain node of a graph.

      /// degree (i.e. the number of incident edges) of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      /// This iterator goes through each directed arc of the graph.

      /// of arcs in a graph \c g of type \c %Graph as follows:

      ///\code

      /// This iterator goes trough the \e outgoing directed arcs of a

      /// certain node of a graph.

      /// of outgoing arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      /// This iterator goes trough the \e incoming directed arcs of a

      /// certain node of a graph.

      /// of incoming arcs of a node \c n

      /// in a graph \c g of type \c %Graph as follows.

      /// Returns the first node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

      /// Returns the second node of the given edge.

      ///

      /// u() and v() are used to query the two end-nodes of an edge.

      /// The orientation of an edge that arises this way is called

///\ingroup graph_concepts

///\file

#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H

///\ingroup concept

///\file

///

    /// A skeleton structure for representing directed paths in a

    /// digraph.

    /// \tparam GR The digraph type in which the path is.

    template <typename GR>

    class Path {

      Path() {}

      template <typename CPath>

      Path(const CPath& cpath) {}

      template <typename CPath>

      Path& operator=(const CPath& cpath) {

      }

      int length() const { return 0;}

      void clear() {}

      ///

      class ArcIt {

      public:

        /// Invalid constructor

        ArcIt(Invalid) {}

        ArcIt(const Path &) {}

        operator Arc() const { return INVALID; }

    ///

    /// A skeleton structure for path dumpers. The path dumpers are

    ///

    /// The main purpose of this concept is that the shortest path

    /// an adaptor class to the predecessor map.

    ///

    /// \tparam GR The digraph type in which the path is.

    template <typename GR>

    class PathDumper {

      typedef typename Digraph::Arc Arc;

      int length() const { return 0;}

      /// \brief Forward or reverse dumping

      ///

      typedef False RevPathTag;

      ///

      class ArcIt {

      public:

        /// Invalid constructor

        ArcIt(Invalid) {}

        ArcIt(const PathDumper&) {}

        operator Arc() const { return INVALID; }

      };

      ///

      class RevArcIt {

      public:

        /// Invalid constructor

        RevArcIt(Invalid) {}

        RevArcIt(const PathDumper &) {}

        operator Arc() const { return INVALID; }

  /// 'Do nothing' version of Counter.

  /// does not count at all and does not print report on destruction.

  ///

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

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

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

    ///Instantiates a \c ProcessedMap.

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

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

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

    ///Instantiates a ProcessedMap.

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

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

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

    ///Instantiates a \c ProcessedMap.

    ///passed to the constructor of the cross reference and the cross

    ///reference should be passed to the constructor of the heap).

    ///passed to the algorithm using the \ref heap() function before

    ///calling \ref run(Node) "run()" or \ref init().

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

    ///\c OperationTraits type.

    template <class T>

    struct SetOperationTraits

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

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

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

    ///Instantiates a ProcessedMap.

    /// \pre \ref run() must be called before using this function.

    template <typename CutMap>

                    const Node& t,

                    CutMap& cutMap

                    ) const {

      Node sn = s, tn = t;

                   /// \endcode

                   /// does not necessarily give the same set of nodes.

                   /// \code

                   /// MinCutNodeIt(gomory, s, t, true);

  ///\param gr  Reference to the graph to be printed.

  ///\param ost Reference to the output stream.

  ///\param pros If it is \c true, then the \c ostream referenced by \c os

  ///will be explicitly deallocated by the destructor.

  ///Turn on/off pre-scaling

  ///very big or very small bounding boxes.

  ///

///\param g Reference to the graph to be printed.

///\param os Reference to the output stream.

///

///This function also has a lot of

///\endcode

///

///

///\warning Don't forget to put the \ref GraphToEps::run() "run()"

  /// differ only on one position in the binary form.

  /// This class is completely static and it needs constant memory space.

  /// the structure can be resized using resize().

  ///

  ///\endcode

  ///

  /// proper type. If a section has an optional name, then it can be

  /// selected for reading by giving an optional name parameter to the

    /// whitespaces are trimmed from each processed string.

    ///

    /// integers, which should be inserted into a vector.

    ///\code

    ///

    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///

    ///\note \c InArcIt iterators referencing the changed arc remain

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    /// reversing, contracting, splitting arcs or nodes) cannot be

    /// restored. These events invalidate the snapshot.

    /// making the current snapshot can be removed without invalidating it.

    class Snapshot {

    ///

    ///\note \c EdgeIt iterators referencing the changed edge remain

    ///all other iterators whose base node is the changed node are also

    ///invalidated.

    /// (e.g. changing the end-nodes of edges or contracting nodes)

    /// cannot be restored. These events invalidate the snapshot.

    /// making the current snapshot can be removed without invalidating it.

    class Snapshot {

    ///Iterator for iterate over the columns of an LP problem

    /// of columns in an LP \c lp:

    ///\code

    ///Iterator for iterate over the rows of an LP problem

    /// of rows in an LP \c lp:

    ///\code

  /// This map is essentially a wrapper for \c std::vector. It assigns

  /// values to integer keys from the range <tt>[0..size-1]</tt>.

  /// integers. This map conforms to the \ref concepts::ReferenceMap

  ///

  /// The simplest way of using this map is through the rangeMap()

  /// The name of this type also refers to this important usage.

  ///

  /// is based on \c std::map, which is a general associative container.

  /// maps.

  ///

  /// The most important usage of it is storing certain nodes or arcs

  /// that were marked \c true by an algorithm.

  /// order of Dfs algorithm, as the following examples show.

  /// \code

  ///

  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so

  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.

  ///

  /// Otherwise consider to use \c IterableValueMap, which is more 

  /// suitable and more efficient for such cases. It provides iterators

  /// it does not have \c InverseMap.

  ///

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of InDegMap is not guarantied if these additional

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// may provide alternative ways to modify the digraph.

  /// The correct behavior of OutDegMap is not guarantied if these additional

  /// \ref ListDigraph::changeSource() "changeSource()",

  /// \ref ListDigraph::changeTarget() "changeTarget()" and

  /// in LEMON for the minimum cost flow problem.

  /// Moreover it supports both directions of the supply/demand inequality

  ///

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

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

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

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

  ///

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

  /// \note %NetworkSimplex provides five different pivot rule

  /// implementations, from which the most efficient one is used

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

  class NetworkSimplex

    /// implementations that significantly affect the running time

    /// of the algorithm.

    /// proved to be the most efficient and the most robust on various

    /// test inputs according to our benchmark tests.

    /// function with the proper parameter.

    enum PivotRule {

      /// The next eligible arc is selected in a wraparound fashion

      /// in every iteration.

      FIRST_ELIGIBLE,

      /// The best eligible arc is selected in every iteration.

      BEST_ELIGIBLE,

      /// A specified number of arcs are examined in every iteration

      /// in a wraparound fashion and the best eligible arc is selected

      BLOCK_SEARCH,

      /// In a major iteration a candidate list is built from eligible arcs

      /// in a wraparound fashion and in the following minor iterations

      CANDIDATE_LIST,

      /// It is a modified version of the Candidate List method.

      /// It keeps only the several best eligible arcs from the former

    /// type will be used.

    ///

    ///

    /// \return <tt>(*this)</tt>

    /// \ref reset() is called, thus only the modified parameters

    /// have to be set again. See \ref reset() for examples.

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// \param pivot_rule The pivot rule that will be used during the

    ///

    /// \return \c INFEASIBLE if no feasible flow exists,

    /// used, all the parameters given before are kept for the next

    /// \ref run() call.

    /// class have been constructed, since it copies and extends the graph.

    ///

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

    ///This function returns the number of stop() exections that is

    ///necessary to really stop the timer.

    ///is running if and only if the return value is \c true

    ///(i.e. greater than

  /// This is a very simple but efficient implementation, providing

  /// only four methods: join (union), find, insert and size.

  ///

  /// It is primarily used in Kruskal algorithm for finding minimal