RhodeCode

    /// "pre heap" or "post heap". The latter two are indifferent from the

    /// heap's point of view, but may be useful to the user.

    ///

    /// The item-int map must be initialized in such way that it assigns

    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.

    enum State {

    };

  private:

    std::vector<Pair> _data;

    Compare _comp;

    ItemIntMap &_iim;

      typedef BAS Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      typedef IterableDigraphComponent Digraph;

      ///

      /// This interface provides functions for iteration on digraph items.

      ///

      /// @{

      /// \brief Return the first node.

      /// This function gives back the next arc outgoing form the

      /// given node.

      void nextOut(Arc&) const {}

      /// @}

      ///

      /// This interface provides iterator classes for digraph items.

      ///

      /// @{

      /// \brief This iterator goes through each node.

      typedef typename Base::Arc Arc;

      typedef typename Base::Edge Edge;

      typedef IterableGraphComponent Graph;

      ///

      /// This interface provides functions for iteration on edges.

      ///

      /// @{

      using IterableDigraphComponent<Base>::first;

      using IterableDigraphComponent<Base>::baseNode;

      using IterableDigraphComponent<Base>::runningNode;

      /// @}

      ///

      /// This interface provides iterator classes for edges.

      ///

      /// @{

      /// \brief This iterator goes through each edge.

      /// from the point of view of the heap, but may be useful for

      /// the user.

      ///

      /// The item-int map must be initialized in such way that it assigns

      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.

      enum State {

      };

      /// \brief The constructor.

      ///

      /// The constructor.

      /// \param map A map that assigns \c int values to keys of type

    Dfs() {}

  public:

    typedef Dfs Create;

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

    }

  public:

    typedef Dijkstra Create;

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

  /// \addtogroup dimacs_group

  /// @{

  /// DIMACS file type descriptor.

  struct DimacsDescriptor

  {

    ///The file type

    Type type;

    ///The number of nodes in the graph

    int nodeNum;

    ///The number of edges in the graph

    int edgeNum;

    int lineShift;

    DimacsDescriptor() : type(NONE) {}

  };

  ///Discover the type of a DIMACS file

  DimacsDescriptor dimacsType(std::istream& is)

  {

    DimacsDescriptor r;

    std::string problem,str;

    char c;

    r.lineShift=0;

          throw FormatError("Unknown DIMACS declaration.");

        }

    throw FormatError("Missing problem type declaration.");

  }

  ///

  /// This function reads a minimum cost flow instance from DIMACS format,

  /// i.e. from a DIMACS file having a line starting with

  /// \code

  ///   p min

  /// \endcode

        }

        break;

      }

    }

  }

  ///

  /// This function reads a maximum flow instance from DIMACS format,

  /// i.e. from a DIMACS file having a line starting with

  /// \code

  ///   p max

  /// \endcode

    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);

    if(desc.type!=DimacsDescriptor::MAX)

      throw FormatError("Problem type mismatch");

    _readDimacs(is,g,capacity,s,t,infty,desc);

  }

  ///

  /// This function reads a shortest path instance from DIMACS format,

  /// i.e. from a DIMACS file having a line starting with

  /// \code

  ///   p sp

  /// \endcode

    if(desc.type==DimacsDescriptor::NONE) desc=dimacsType(is);

    if(desc.type!=DimacsDescriptor::SP)

      throw FormatError("Problem type mismatch");

    _readDimacs(is, g, length, s, t, 0, desc);

  }

  ///

  /// This function reads an arc capacitated digraph instance from

  /// DIMACS 'max' or 'sp' format.

  /// At the beginning, \c g is cleared by \c g.clear()

  /// and the arc capacities/lengths are written to the \c capacity

  /// arc map.

  _addArcEdge(Graph &g, typename Graph::Node s, typename Graph::Node t,

              dummy<1> = 1)

  {

    g.addArc(s,t);

  }

  ///

  /// \code

  ///   p mat

  /// \endcode

  /// At the beginning, \c g is cleared by \c g.clear().

  ///

  /// If the file type was previously evaluated by dimacsType(), then

    ///\image html nodeshape_0.png

    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm

    CIRCLE=0,

    /// = 1

    ///\image html nodeshape_1.png

    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm

    SQUARE=1,

    /// = 2

    ///\image html nodeshape_2.png

    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm

    DIAMOND=2,

    /// = 3

    ///\image html nodeshape_3.png

    MALE=3,

    /// = 4

    ///\image html nodeshape_4.png

    FEMALE=4

  };

private:

  class arcLess {

    const Graph &g;

    };

  }

  /// \ingroup spantree

  ///

  /// a graph.

  ///

  /// This function runs Kruskal's algorithm to find a minimum cost

  /// Due to some C++ hacking, it accepts various input and output types.

  ///

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

  /// It can be either \ref concepts::Digraph "directed" or

  /// \ref concepts::Graph "undirected".

  /// If the graph is directed, the algorithm consider it to be

  /// undirected by disregarding the direction of the arcs.

  ///

  /// \param in This object is used to describe the arc/edge costs.

  /// It can be one of the following choices.

  /// - An STL compatible 'Forward Container' with

  /// along with the assigned cost. <em>They must be in a

  /// cost-ascending order.</em>

  /// - Any readable arc/edge map. The values of the map indicate the

  /// arc/edge costs.

  ///

  /// \retval out Here we also have a choice.

  /// tree: the value of an arc/edge will be set to \c true if it belongs

  /// to the tree, otherwise it will be set to \c false. The value of

  /// each arc/edge will be set exactly once.

  /// - It can also be an iteraror of an STL Container with

  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its

  /// <tt>value_type</tt>.  The algorithm copies the elements of the

  /// \return The total cost of the found spanning tree.

  ///

  /// \note If the input graph is not (weakly) connected, a spanning

  /// forest is calculated instead of a spanning tree.

#ifdef DOXYGEN

#else

  template <class Graph, class In, class Out>

  inline typename _kruskal_bits::KruskalValueSelector<In>::Value

  kruskal(const Graph& graph, const In& in, Out& out)

#endif

  {

    return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::

      kruskal(graph, in, out);

  }

  template <class Graph, class In, class Out>

  inline typename _kruskal_bits::KruskalValueSelector<In>::Value

  kruskal(const Graph& graph, const In& in, const Out& out)

  {

    return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::

      kruskal(graph, in, out);

    }

    DigraphReader& operator=(const DigraphReader&);

  public:

    /// @{

    /// \brief Node map reading rule

    ///

    /// Add a node map reading rule to the reader.

    template <typename Map>

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// @}

    /// @{

    /// \brief Set \c \@nodes section to be read

    ///

    /// Set \c \@nodes section to be read

    DigraphReader& nodes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @}

    /// @{

    /// \brief Use previously constructed node set

    ///

    /// Use previously constructed node set, and specify the node

    /// label map.

        }

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing

    void run() {

    }

    GraphReader& operator=(const GraphReader&);

  public:

    /// @{

    /// \brief Node map reading rule

    ///

    /// Add a node map reading rule to the reader.

    template <typename Map>

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// @}

    /// @{

    /// \brief Set \c \@nodes section to be read

    ///

    /// Set \c \@nodes section to be read.

    GraphReader& nodes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @}

    /// @{

    /// \brief Use previously constructed node set

    ///

    /// Use previously constructed node set, and specify the node

    /// label map.

        }

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing

    void run() {

    }

    SectionReader& operator=(const SectionReader&);

  public:

    /// @{

    /// \brief Add a section processor with line oriented reading

    ///

    /// The first parameter is the type descriptor of the section, the

    /// second is a functor, which takes just one \c std::string

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

    LgfContents(const LgfContents&);

    LgfContents& operator=(const LgfContents&);

  public:

    /// @{

    /// \brief Gives back the number of node sections in the file.

    ///

    /// Gives back the number of node sections in the file.

    int nodeSectionNum() const {

    const std::vector<std::string>& nodeMapNames(int i) const {

      return _node_maps[i];

    }

    /// @}

    /// @{

    /// \brief Gives back the number of arc/edge sections in the file.

    ///

    /// Gives back the number of arc/edge sections in the file.

    /// \note It is synonym of \c edgeSectionNum().

    const std::vector<std::string>& edgeMapNames(int i) const {

      return _edge_maps[i];

    }

    /// @}

    /// @{

    /// \brief Gives back the number of attribute sections in the file.

    ///

    /// Gives back the number of attribute sections in the file.

    int attributeSectionNum() const {

    const std::vector<std::string>& attributes(int i) const {

      return _attributes[i];

    }

    /// @}

    /// @{

    /// \brief Gives back the number of extra sections in the file.

    ///

    /// Gives back the number of extra sections in the file.

    int extraSectionNum() const {

      }

      line.putback(c);

    }

  public:

    /// @{

    /// \brief Starts the reading

    ///

    /// This function starts the reading.

    void run() {

    }

    DigraphWriter& operator=(const DigraphWriter&);

  public:

    /// @{

    /// \brief Node map writing rule

    ///

    /// Add a node map writing rule to the writer.

    template <typename Map>

      _writer_bits::ValueStorageBase* storage =

        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// @{

    /// \brief Add an additional caption to the \c \@nodes section

    ///

    /// Add an additional caption to the \c \@nodes section.

    DigraphWriter& nodes(const std::string& caption) {

    /// Add an additional caption to the \c \@attributes section.

    DigraphWriter& attributes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @{

    /// \brief Skip writing the node set

    ///

    /// The \c \@nodes section will not be written to the stream.

    DigraphWriter& skipNodes() {

        *_os << std::endl;

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

    }

    GraphWriter& operator=(const GraphWriter&);

  public:

    /// @{

    /// \brief Node map writing rule

    ///

    /// Add a node map writing rule to the writer.

    template <typename Map>

      _writer_bits::ValueStorageBase* storage =

        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// @{

    /// \brief Add an additional caption to the \c \@nodes section

    ///

    /// Add an additional caption to the \c \@nodes section.

    GraphWriter& nodes(const std::string& caption) {

    /// Add an additional caption to the \c \@attributes section.

    GraphWriter& attributes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @{

    /// \brief Skip writing the node set

    ///

    /// The \c \@nodes section will not be written to the stream.

    GraphWriter& skipNodes() {

        *_os << std::endl;

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

    }

    SectionWriter& operator=(const SectionWriter&);

  public:

    /// @{

    /// \brief Add a section writer with line oriented writing

    ///

    /// The first parameter is the type descriptor of the section, the

    /// second is a generator with std::string values. At the writing

    /// @}

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

    _solver_bits::VarIndex cols;

  public:

    ///Possible outcomes of an LP solving procedure

    enum SolveExitStatus {

      ///an optimal solution has been found or infeasibility/unboundedness

      ///has been proved.

      SOLVED = 0,

      UNSOLVED = 1

    };

    ///Direction of the optimization

    enum Sense {

      /// Minimization

      /// Maximization

      MAX

    };

    ///Enum for \c messageLevel() parameter

    enum MessageLevel {

      MESSAGE_NOTHING,

      MESSAGE_ERROR,

      MESSAGE_WARNING,

      MESSAGE_NORMAL,

      MESSAGE_VERBOSE

    };

    ///The floating point type used by the solver

    typedef double Value;

    /// Virtual destructor

    virtual ~LpBase() {}

    ///Gives back the name of the solver.

    const char* solverName() const {return _solverName();}

    ///@{

    ///Add a new empty column (i.e a new variable) to the LP

    Col addCol() { Col c; c._id = _addColId(_addCol()); return c;}

  /// this class directly.

  class LpSolver : virtual public LpBase {

  public:

    /// The problem types for primal and dual problems

    enum ProblemType {

      UNDEFINED = 0,

      INFEASIBLE = 1,

      FEASIBLE = 2,

      OPTIMAL = 3,

      UNBOUNDED = 4

    };

    ///The basis status of variables

    enum VarStatus {

      /// The variable is in the basis

    ///values and their meanings can be found in the documentation of

    ///\ref SolveExitStatus.

    SolveExitStatus solve() { return _solve(); }

    ///@}

    ///@{

    /// The type of the primal problem

    ProblemType primalType() const {

      return _getPrimalType();

  /// this class directly.

  class MipSolver : virtual public LpBase {

  public:

    /// The problem types for MIP problems

    enum ProblemType {

      UNDEFINED = 0,

      INFEASIBLE = 1,

      FEASIBLE = 2,

      OPTIMAL = 3,

      UNBOUNDED = 4

    };

    ///Allocate a new MIP problem instance

    virtual MipSolver* newSolver() const = 0;

    ///Make a copy of the MIP problem

    ///values and their meanings can be found in the documentation of

    ///\ref SolveExitStatus.

    SolveExitStatus solve() { return _solve(); }

    ///@}

    ///@{

    ///Possible variable (column) types (e.g. real, integer, binary etc.)

    enum ColTypes {

      REAL = 0,

      INTEGER = 1

    };

    ///Sets the type of the given column to the given type

    ///Sets the type of the given column to the given type.

    ///

    ColTypes colType(Col c) const {

      return _getColType(cols(id(c)));

    }

    ///@}

    ///@{

    /// The type of the MIP problem

    ProblemType type() const {

      return _getType();

    const Digraph& _digraph;

    AutoNodeMap _deg;

  };

  /// \brief Potential difference map

  ///

  /// \code

  ///   potential[gr.target(arc)] - potential[gr.source(arc)].

  /// \endcode

  /// \tparam GR The digraph type.

  /// \tparam POT A node map storing the potentials.

  template <typename GR, typename POT>

    }

  };

  /// \ingroup spantree

  ///

  ///

  /// This class provides an efficient implementation of

  /// which is directed from a given source node of the digraph. One or

  /// more sources should be given for the algorithm and it will calculate

  /// the minimum cost subgraph which are union of arborescences with the

  /// given sources and spans all the nodes which are reachable from the

  /// sources. The time complexity of the algorithm is O(n<sup>2</sup>+e).

  ///

      }

    }

  public:

    /// @{

    template <class T>

    struct DefArborescenceMapTraits : public Traits {

      typedef T ArborescenceMap;

      const MinCostArborescence* _algorithm;

      int _index, _last;

    };

    /// @}

    /// The simplest way to execute the algorithm is to use

    /// one of the member functions called \c run(...). \n

    /// If you need more control on the execution,

    /// first you must call \ref init(), then you can add several

    /// source nodes with \ref addSource().

    /// Finally \ref start() will perform the arborescence

#endif

      return true;

    }

    /// @}

    ///

    /// @{

    /// \brief Returns a random real number from the range [0, 1)

    ///

    /// It returns a random real number from the range [0, 1). The

    bool boolean() {

      return bool_producer.convert(core);

    }

    /// @}

    ///

    ///@{

    /// \brief Returns a random bool with given probability of true result.

    ///

    /// It returns a random bool with given probability of true result.

      } while (p>=l);

      return k-1;

    }

    ///@}