RhodeCode

    ///

    /// Each Item element have a state associated to it. It may be "in heap",

    /// "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;

  public:

    public:

      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 first node in the iteration order.

      /// \brief Return the next arc outgoing form the given 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.

      ///

      /// This iterator goes through each node.

      typedef BAS Base;

      typedef typename Base::Node 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>::next;

      /// node. The bool parameter should be used as \c firstInc() use it.

      void nextInc(Edge&, bool&) const {}

      using IterableDigraphComponent<Base>::baseNode;

      using IterableDigraphComponent<Base>::runningNode;

      /// @}

      ///

      /// This interface provides iterator classes for edges.

      ///

      /// @{

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

      ///

      /// This iterator goes through each edge.

      /// Each item has a state associated to it. It can be "in heap",

      /// "pre heap" or "post heap". The later two are indifferent

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

      /// \c Item. It is used internally by the heap implementations to

      /// handle the cross references. The assigned value must be

  protected:

    Dfs() {}

  public:

    typedef Dfs Create;

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &)

      {

        _heap = Traits::createHeap(*_heap_cross_ref);

      }

    }

  public:

    typedef Dijkstra Create;

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &)

      {

namespace lemon {

  /// \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;

    while (is >> c)

      switch(c)

          break;

        default:

          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

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

  /// amount of the nodes are written to the \c supply node map

          getline(is, str);

          g.addArc(nodes[i], nodes[j]);

        }

        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

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

  /// capacities are written to the \c capacity arc map and \c s and

                     typename CapacityMap::Value infty = 0,

                     DimacsDescriptor desc=DimacsDescriptor()) {

    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

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

  /// lengths are written to the \c length arc map and \c s is set to the

                    DimacsDescriptor desc=DimacsDescriptor()) {

    typename Digraph::Node t;

    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.

  ///

  /// In case of the 'max' format, if the capacity of an arc is negative,

  template<typename Graph>

  typename disable_if<lemon::UndirectedTagIndicator<Graph>,void>::type

  _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

  /// the descriptor struct should be given by the \c dest parameter.

  template<typename Graph>

  enum NodeShapes {

    /// = 0

    ///\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;

  public:

    arcLess(const Graph &_g) : g(_g) {}

        return _kruskal_bits::kruskal(graph, in, out);

      }

    };

  }

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

  /// found tree into this sequence.  For example, if we know that the

  /// spanning tree of the graph \c g has say 53 arcs, then we can

  ///\endcode

  ///

  /// \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);

  }

      _attributes_caption = other._attributes_caption;

    }

    DigraphReader& operator=(const DigraphReader&);

  public:

    /// @{

    /// \brief Node map reading rule

    ///

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

    template <typename Map>

    DigraphReader& nodeMap(const std::string& caption, Map& map) {

      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();

      _reader_bits::ValueStorageBase* storage =

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

      _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) {

      _nodes_caption = caption;

      return *this;

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

    DigraphReader& attributes(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.

    template <typename Map>

    DigraphReader& useNodes(const Map& map) {

          msg << "Attribute not found: " << it->first;

          throw FormatError(msg.str());

        }

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing

    void run() {

      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");

      _attributes_caption = other._attributes_caption;

    }

    GraphReader& operator=(const GraphReader&);

  public:

    /// @{

    /// \brief Node map reading rule

    ///

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

    template <typename Map>

    GraphReader& nodeMap(const std::string& caption, Map& map) {

      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();

      _reader_bits::ValueStorageBase* storage =

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

      _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) {

      _nodes_caption = caption;

      return *this;

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

    GraphReader& attributes(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.

    template <typename Map>

    GraphReader& useNodes(const Map& map) {

          msg << "Attribute not found: " << it->first;

          throw FormatError(msg.str());

        }

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing

    void run() {

      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");

      _sections.swap(other._sections);

    }

    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

    /// parameter. At the reading process, each line of the section

    /// will be given to the functor object. However, the empty lines

      if (readSuccess()) {

        line.putback(c);

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");

  private:

    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 {

      return _node_sections.size();

    }

    ///

    /// Gives back the node maps for the given section.

    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().

    int arcSectionNum() const {

      return _edge_sections.size();

    /// Gives back the edge maps for the given section.

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

    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 {

      return _attribute_sections.size();

    }

    ///

    /// Gives back the attributes for the given section.

    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 {

      return _extra_sections.size();

    }

        attrs.push_back(attr);

        readLine();

      }

      line.putback(c);

    }

  public:

    /// @{

    /// \brief Starts the reading

    ///

    /// This function starts the reading.

    void run() {

      readLine();

      _arcs_caption = other._arcs_caption;

      _attributes_caption = other._attributes_caption;

    }

    DigraphWriter& operator=(const DigraphWriter&);

  public:

    /// @{

    /// \brief Node map writing rule

    ///

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

    template <typename Map>

    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      typedef _writer_bits::MapLookUpConverter<Arc> Converter;

      Converter converter(_arc_index);

      _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) {

      _nodes_caption = caption;

      return *this;

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

    ///

    /// 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() {

      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");

      _skip_nodes = true;

        _writer_bits::writeToken(*_os, it->first) << ' ';

        _writer_bits::writeToken(*_os, it->second->get());

        *_os << std::endl;

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      if (!_skip_nodes) {

        writeNodes();

      _edges_caption = other._edges_caption;

      _attributes_caption = other._attributes_caption;

    }

    GraphWriter& operator=(const GraphWriter&);

  public:

    /// @{

    /// \brief Node map writing rule

    ///

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

    template <typename Map>

    GraphWriter& nodeMap(const std::string& caption, const Map& map) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;

      Converter converter(_graph, _edge_index);

      _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) {

      _nodes_caption = caption;

      return *this;

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

    ///

    /// 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() {

      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");

      _skip_nodes = true;

        _writer_bits::writeToken(*_os, it->first) << ' ';

        _writer_bits::writeToken(*_os, it->second->get());

        *_os << std::endl;

      }

    }

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      if (!_skip_nodes) {

        writeNodes();

      _sections.swap(other._sections);

    }

    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

    /// process, the returned \c std::string will be written into the

    /// output file until it is an empty string.

      return *this;

    }

    /// @}

  public:

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");

    _solver_bits::VarIndex rows;

    _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

      MIN,

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

    ///The infinity constant

    static const Value INF;

  public:

    /// 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;}

    ///\brief Adds several new columns (i.e variables) at once

    ///

  /// default LP solver. However, if you would like to handle LP

  /// solvers as reference or pointer in a generic way, you can use

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

      BASIC, 

      /// The variable is free, but not basic

    ///

    ///\return The result of the optimization procedure. Possible

    ///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();

    }

  /// default MIP solver. However, if you would like to handle MIP

  /// solvers as reference or pointer in a generic way, you can use

  /// this class directly.

  class MipSolver : virtual public LpBase {

  public:

    /// The problem types for MIP problems

    enum ProblemType {