RhodeCode

    ///\e

    typedef Comp Compare;

    /// \brief Type to represent the items states.

    ///

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

    /// \brief The constructor.

    ///

    /// The constructor.

    /// \param map should be given to the constructor, since it is used

    /// This concept is part of the Digraph concept.

    template <typename BAS = BaseDigraphComponent>

    class IterableDigraphComponent : public BAS {

    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.

      void first(Node&) const {}

      /// \brief Return the next node.

      ///

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

      /// given node.

      void firstOut(Arc&, const Node&) const {}

      /// \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 GraphItemIt<Digraph, Node> NodeIt;

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

    template <typename BAS = BaseGraphComponent>

    class IterableGraphComponent : public IterableDigraphComponent<BAS> {

    public:

      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;

      /// \brief Return the first edge.

      ///

      /// This function gives back the first edge in the iteration order.

      void first(Edge&) const {}

      /// \brief Gives back the next of the edges from the

      /// given node.

      ///

      /// This function gives back the next edge incident to the given 

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

      typedef GraphItemIt<Graph, Edge> EdgeIt;

      /// \brief This iterator goes trough the incident edges of a

      /// node.

      typedef typename ItemIntMap::Key Item;

      /// \brief Type to represent the states of the items.

      ///

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

      /// \c PRE_HEAP (<tt>-1</tt>) for every item.

      explicit Heap(ItemIntMap &map) {}

      /// \brief The number of items stored in the heap.

        _processed = Traits::createProcessedMap(*G);

      }

    }

  protected:

    Dfs() {}

  public:

    typedef Dfs Create;

    ///@{

    template <class T>

    struct SetPredMapTraits : public Traits {

      typedef T PredMap;

      static PredMap *createPredMap(const Digraph &)

      {

        LEMON_ASSERT(false, "PredMap is not initialized");

        return 0; // ignore warnings

      }

    };

        _heap_cross_ref = Traits::createHeapCrossRef(*G);

      }

      if (!_heap) {

        local_heap = true;

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

      {

        LEMON_ASSERT(false, "PredMap is not initialized");

        return 0; // ignore warnings

      }

    };

/// \ingroup dimacs_group

/// \file

/// \brief DIMACS file format reader.

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)

        {

        case 'p':

          if(is >> problem >> r.nodeNum >> r.edgeNum)

            {

          break;

        case 'c':

          getline(is, str);

          r.lineShift++;

          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

  /// (they are signed values). The lower bounds, capacities and costs

  /// of the arcs are written to the \c lower, \c capacity and \c cost

  /// arc maps.

  ///

            capacity.set(e, infty);

        }

        else {

          is >> i >> j;

          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

  /// \c t are set to the source and the target nodes.

  ///

  /// If the capacity of an arc is negative, it will

  /// be set to "infinite" instead. The actual value of "infinite" is

                     Digraph &g,

                     CapacityMap& capacity,

                     typename Digraph::Node &s,

                     typename Digraph::Node &t,

                     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

  /// source node.

  ///

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

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

  void readDimacsSp(std::istream& is,

                    Digraph &g,

                    LengthMap& length,

                    typename Digraph::Node &s,

                    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,

  /// it will

  /// be set to "infinite" instead. The actual value of "infinite" is

  /// contolled by the \c infty parameter. If it is 0 (the default value),

  /// \c std::numeric_limits<Capacity>::infinity() will be used if available,

              dummy<0> = 0)

  {

    g.addEdge(s,t);

  }

  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>

  void readDimacsMat(std::istream& is, Graph &g,

                     DimacsDescriptor desc=DimacsDescriptor())

  {

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

  ///Node shapes

  ///Node shapes.

  ///

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

    bool operator()(Arc a,Arc b) const

    {

      Node ai=std::min(g.source(a),g.target(a));

      Node aa=std::max(g.source(a),g.target(a));

    {

      typedef typename In::value_type::second_type Value;

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

        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

  /// put its arcs into an STL vector \c tree with a code like this.

  ///\code

  /// std::vector<Arc> tree(53);

  /// kruskal(g,cost,tree.begin());

  /// write this.

  ///\code

  /// std::vector<Arc> tree;

  /// kruskal(g,cost,std::back_inserter(tree));

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

  }

} //namespace lemon

#endif //LEMON_KRUSKAL_H

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _arcs_caption = other._arcs_caption;

      _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::MapStorageBase<Node>* storage =

        new _reader_bits::MapStorage<Node, Map>(map);

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

      return *this;

    /// Add an arc reading rule to reader.

    DigraphReader& arc(const std::string& caption, Arc& arc) {

      typedef _reader_bits::MapLookUpConverter<Arc> Converter;

      Converter converter(_arc_index);

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

    }

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

    ///

    }

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

    ///

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

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

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");

      _use_nodes = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        if (read_attr.find(it->first) == read_attr.end()) {

          std::ostringstream msg;

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

      bool nodes_done = _skip_nodes;

      bool arcs_done = _skip_arcs;

      bool attributes_done = false;

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      _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::MapStorageBase<Node>* storage =

        new _reader_bits::MapStorage<Node, Map>(map);

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

      return *this;

    /// Add an arc reading rule to reader.

    GraphReader& arc(const std::string& caption, Arc& arc) {

      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;

      Converter converter(_graph, _edge_index);

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

    }

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

    ///

    }

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

    ///

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

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

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");

      _use_nodes = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (typename Attributes::iterator it = _attributes.begin();

           it != _attributes.end(); ++it) {

        if (read_attr.find(it->first) == read_attr.end()) {

          std::ostringstream msg;

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

      bool nodes_done = _skip_nodes;

      bool edges_done = _skip_edges;

      bool attributes_done = false;

      : _is(other._is), local_is(other.local_is) {

      other._is = 0;

      other.local_is = false;

      _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

    /// and the comment lines are filtered out, and the leading

    /// whitespaces are trimmed from each processed string.

    ///

    /// For example let's see a section, which contain several

      char c;

      while (readSuccess() && line >> c && c != '@') {

        readLine();

      }

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

      std::set<std::string> extra_sections;

      line_num = 0;

    ~LgfContents() {

      if (local_is) delete _is;

    }

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

    }

    /// \brief Returns the node section name at the given position.

    ///

    /// Returns the node section name at the given position.

      return _node_sections[i];

    }

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

    ///

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

    }

    /// \brief Returns the arc/edge section name at the given position.

    ///

    }

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

    ///

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

    }

    /// \brief Returns the attribute section name at the given position.

    ///

    /// Returns the attribute section name at the given position.

      return _attribute_sections[i];

    }

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

    ///

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

    }

    /// \brief Returns the extra section type at the given position.

    ///

    /// Returns the section type at the given position.

      while (readSuccess() && line >> c && c != '@') {

        line.putback(c);

        std::string attr;

        _reader_bits::readToken(line, attr);

        attrs.push_back(attr);

        readLine();

      }

      line.putback(c);

    }

  public:

    /// @{

    /// \brief Starts the reading

    ///

    /// This function starts the reading.

    void run() {

      readLine();

      skipSection();

      while (readSuccess()) {

      _arc_maps.swap(other._arc_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

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

      _writer_bits::MapStorageBase<Node>* storage =

        new _writer_bits::MapStorage<Node, Map>(map);

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

      return *this;

    /// \brief Arc writing rule

    ///

    /// Add an arc writing rule to writer.

    DigraphWriter& arc(const std::string& caption, const Arc& arc) {

      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 \@arcs section

    ///

      _arcs_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

    ///