RhodeCode

LEMON code without an explicit copyright is covered by the following

copyright/license.

Kutatocsoport (Egervary Combinatorial Optimization Research Group,

EGRES).

Permission is hereby granted, free of charge, to any person or organization

obtaining a copy of the software and accompanying documentation covered by

this license (the "Software") to use, reproduce, display, distribute,

execute, and transmit the Software, and to prepare derivative works of the

Software, and to permit third-parties to whom the Software is furnished to

do so, all subject to the following:

The copyright notices in the Software and this entire statement, including

the above license grant, this restriction and the following disclaimer,

must be included in all copies of the Software, in whole or in part, and

all derivative works of the Software, unless such copies or derivative

works are solely in the form of machine-executable object code generated by

a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT

SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE

FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,

ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

DEALINGS IN THE SOFTWARE.

===========================================================================

This license is a verbatim copy of the Boost Software License, Version 1.0.

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_ALTERATION_NOTIFIER_H

#define LEMON_BITS_ALTERATION_NOTIFIER_H

#include <vector>

#include <list>

#include <lemon/bits/utility.h>

///\ingroup graphbits

///\file

///\brief Observer notifier for graph alteration observers.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Notifier class to notify observes about alterations in 

  /// a container.

  ///

  /// The simple graph's can be refered as two containers, one node container

  /// and one edge container. But they are not standard containers they

  /// does not store values directly they are just key continars for more

  /// value containers which are the node and edge maps.

  ///

  /// The graph's node and edge sets can be changed as we add or erase

  /// nodes and edges in the graph. Lemon would like to handle easily

  /// that the node and edge maps should contain values for all nodes or

  /// edges. If we want to check on every indicing if the map contains

  /// the current indicing key that cause a drawback in the performance

  /// in the library. We use another solution we notify all maps about

  /// an alteration in the graph, which cause only drawback on the

  /// alteration of the graph.

  ///

  /// This class provides an interface to the container. The \e first() and \e 

  /// next() member functions make possible to iterate on the keys of the

  /// container. The \e id() function returns an integer id for each key.

  /// The \e maxId() function gives back an upper bound of the ids.

  ///

  /// For the proper functonality of this class, we should notify it

  /// about each alteration in the container. The alterations have four type

  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and

  /// \e erase() signals that only one or few items added or erased to or

  /// from the graph. If all items are erased from the graph or from an empty

  /// graph a new graph is builded then it can be signaled with the

  /// clear() and build() members. Important rule that if we erase items 

  /// from graph we should first signal the alteration and after that erase

  /// them from the container, on the other way on item addition we should

  /// first extend the container and just after that signal the alteration.

  ///

  /// The alteration can be observed with a class inherited from the

  /// \e ObserverBase nested class. The signals can be handled with

  /// overriding the virtual functions defined in the base class.  The

  /// observer base can be attached to the notifier with the 

  /// \e attach() member and can be detached with detach() function. The

  /// alteration handlers should not call any function which signals

  /// an other alteration in the same notifier and should not

  /// detach any observer from the notifier.

  ///

  /// Alteration observers try to be exception safe. If an \e add() or

  /// a \e clear() function throws an exception then the remaining

  /// observeres will not be notified and the fulfilled additions will

  /// be rolled back by calling the \e erase() or \e clear()

  /// functions. Thence the \e erase() and \e clear() should not throw

  /// exception. Actullay, it can be throw only 

  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach

  /// exception which detach the observer from the notifier.

  ///

  /// There are some place when the alteration observing is not completly

  /// reliable. If we want to carry out the node degree in the graph

  /// as in the \ref InDegMap and we use the reverseEdge that cause 

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  /// be watched in any way.

  ///

  /// \param _Container The container which is observed.

  /// \param _Item The item type which is obserbved.

  ///

  /// \author Balazs Dezso

  template <typename _Container, typename _Item>

  class AlterationNotifier {

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_ARRAY_MAP_H

#define LEMON_BITS_ARRAY_MAP_H

#include <memory>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

/// \ingroup graphbits

/// \file

/// \brief Graph map based on the array storage.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the array storage.

  ///

  /// The ArrayMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map uses the allocators to implement 

  /// the container functionality.

  ///

  /// The template parameters are the Graph the current Item type and

  /// the Value type of the map.

  template <typename _Graph, typename _Item, typename _Value>

  class ArrayMap 

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  public:

    /// The graph type of the maps. 

    typedef _Graph Graph;

    /// The item type of the map.

    typedef _Item Item;

    /// The reference map tag.

    typedef True ReferenceMapTag;

    /// The key type of the maps.

    typedef _Item Key;

    /// The value type of the map.

    typedef _Value Value;

    /// The const reference type of the map.

    typedef const _Value& ConstReference;

    /// The reference type of the map.

    typedef _Value& Reference;

    /// The notifier type.

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

    /// The MapBase of the Map which imlements the core regisitry function.

    typedef typename Notifier::ObserverBase Parent;

  private:

    typedef std::allocator<Value> Allocator;

  public:

    /// \brief Graph initialized map constructor.

    ///

    /// Graph initialized map constructor.

    explicit ArrayMap(const Graph& graph) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

	allocator.construct(&(values[id]), Value());

      }								

    }

    /// \brief Constructor to use default value to initialize the map. 

    ///

    /// It constructs a map and initialize all of the the map. 

    ArrayMap(const Graph& graph, const Value& value) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_BASE_EXTENDER_H

#define LEMON_BITS_BASE_EXTENDER_H

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/bits/map_extender.h>

#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup digraphbits

///\file

///\brief Extenders for the digraph types

namespace lemon {

  /// \ingroup digraphbits

  ///

  /// \brief BaseDigraph to BaseGraph extender

  template <typename Base>

  class UndirDigraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef typename Parent::Arc Edge;

    typedef typename Parent::Node Node;

    typedef True UndirectedTag;

    class Arc : public Edge {

      friend class UndirDigraphExtender;

    protected:

      bool forward;

      Arc(const Edge &ue, bool _forward) :

        Edge(ue), forward(_forward) {}

    public:

      Arc() {}

      /// Invalid arc constructor

      Arc(Invalid i) : Edge(i), forward(true) {}

      bool operator==(const Arc &that) const {

	return forward==that.forward && Edge(*this)==Edge(that);

      }

      bool operator!=(const Arc &that) const {

	return forward!=that.forward || Edge(*this)!=Edge(that);

      }

      bool operator<(const Arc &that) const {

	return forward<that.forward ||

	  (!(that.forward<forward) && Edge(*this)<Edge(that));

      }

    };

    using Parent::source;

    /// Source of the given Arc.

    Node source(const Arc &e) const {

      return e.forward ? Parent::source(e) : Parent::target(e);

    }

    using Parent::target;

    /// Target of the given Arc.

    Node target(const Arc &e) const {

      return e.forward ? Parent::target(e) : Parent::source(e);

    }

    /// \brief Directed arc from an edge.

    ///

    /// Returns a directed arc corresponding to the specified Edge.

    /// If the given bool is true the given edge and the

    /// returned arc have the same source node.

    static Arc direct(const Edge &ue, bool d) {

      return Arc(ue, d);

    }

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_DEFAULT_MAP_H

#define LEMON_BITS_DEFAULT_MAP_H

#include <lemon/bits/array_map.h>

#include <lemon/bits/vector_map.h>

//#include <lemon/bits/debug_map.h>

///\ingroup graphbits

///\file

///\brief Graph maps that construct and destruct their elements dynamically.

namespace lemon {

  //#ifndef LEMON_USE_DEBUG_MAP

  template <typename _Graph, typename _Item, typename _Value>

  struct DefaultMapSelector {

    typedef ArrayMap<_Graph, _Item, _Value> Map;

  };

  // bool

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, bool> {

    typedef VectorMap<_Graph, _Item, bool> Map;

  };

  // char

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, char> {

    typedef VectorMap<_Graph, _Item, char> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed char> {

    typedef VectorMap<_Graph, _Item, signed char> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned char> {

    typedef VectorMap<_Graph, _Item, unsigned char> Map;

  };

  // int

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed int> {

    typedef VectorMap<_Graph, _Item, signed int> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned int> {

    typedef VectorMap<_Graph, _Item, unsigned int> Map;

  };

  // short

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed short> {

    typedef VectorMap<_Graph, _Item, signed short> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned short> {

    typedef VectorMap<_Graph, _Item, unsigned short> Map;

  };

  // long

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed long> {

    typedef VectorMap<_Graph, _Item, signed long> Map;

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned long> {

    typedef VectorMap<_Graph, _Item, unsigned long> Map;

  };

#if defined __GNUC__ && !defined __STRICT_ANSI__

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_GRAPH_EXTENDER_H

#define LEMON_BITS_GRAPH_EXTENDER_H

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/bits/map_extender.h>

#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup graphbits

///\file

///\brief Extenders for the digraph types

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Extender for the Digraphs

  template <typename Base>

  class DigraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef DigraphExtender Digraph;

    // Base extensions

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

    Node fromId(int id, Node) const {

      return Parent::nodeFromId(id);

    }

    Arc fromId(int id, Arc) const {

      return Parent::arcFromId(id);

    }

    Node oppositeNode(const Node &node, const Arc &arc) const {

      if (node == Parent::source(arc))

	return Parent::target(arc);

      else if(node == Parent::target(arc))

	return Parent::source(arc);

      else

	return INVALID;

    }

    // Alterable extension

    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

  protected:

    mutable NodeNotifier node_notifier;

    mutable ArcNotifier arc_notifier;

  public:

    NodeNotifier& notifier(Node) const {

      return node_notifier;

    }

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

    }

    class NodeIt : public Node { 

      const Digraph* _digraph;

    public:

      NodeIt() {}

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_MAP_EXTENDER_H

#define LEMON_BITS_MAP_EXTENDER_H

#include <iterator>

#include <lemon/bits/traits.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\file

///\brief Extenders for iterable maps.

namespace lemon {

  /// \ingroup graphbits

  /// 

  /// \brief Extender for maps

  template <typename _Map>

  class MapExtender : public _Map {

  public:

    typedef _Map Parent;

    typedef MapExtender Map;

    typedef typename Parent::Graph Graph;

    typedef typename Parent::Key Item;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    class MapIt;

    class ConstMapIt;

    friend class MapIt;

    friend class ConstMapIt;

  public:

    MapExtender(const Graph& graph) 

      : Parent(graph) {}

    MapExtender(const Graph& graph, const Value& value) 

      : Parent(graph, value) {}

    MapExtender& operator=(const MapExtender& cmap) {

      return operator=<MapExtender>(cmap);

    }

    template <typename CMap>

    MapExtender& operator=(const CMap& cmap) {

      Parent::operator=(cmap);

      return *this;

    } 

    class MapIt : public Item {

    public:

      typedef Item Parent;

      typedef typename Map::Value Value;

      MapIt() {}

      MapIt(Invalid i) : Parent(i) { }

      explicit MapIt(Map& _map) : map(_map) {

        map.notifier()->first(*this);

      }

      MapIt(const Map& _map, const Item& item) 

	: Parent(item), map(_map) {}

      MapIt& operator++() { 

	map.notifier()->next(*this);

	return *this; 

      }

      typename MapTraits<Map>::ConstReturnValue operator*() const {

	return map[*this];

      }

      typename MapTraits<Map>::ReturnValue operator*() {

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_TRAITS_H

#define LEMON_BITS_TRAITS_H

#include <lemon/bits/utility.h>

///\file

///\brief Traits for graphs and maps

///

namespace lemon {

  template <typename _Graph, typename _Item>

  class ItemSetTraits {};

  template <typename Graph, typename Enable = void>

  struct NodeNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct NodeNotifierIndicator<

    Graph, 

    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type

  > { 

    typedef typename Graph::NodeNotifier Type;

  };

  template <typename _Graph>

  class ItemSetTraits<_Graph, typename _Graph::Node> {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Node Item;

    typedef typename Graph::NodeIt ItemIt;

    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

    class Map : public Graph::template NodeMap<_Value> {

    public:

      typedef typename Graph::template NodeMap<_Value> Parent; 

      typedef typename Graph::template NodeMap<_Value> Type; 

      typedef typename Parent::Value Value;

      Map(const Graph& _digraph) : Parent(_digraph) {}

      Map(const Graph& _digraph, const Value& _value) 

	: Parent(_digraph, _value) {}

     };

  };

  template <typename Graph, typename Enable = void>

  struct ArcNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct ArcNotifierIndicator<

    Graph, 

    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type

  > { 

    typedef typename Graph::ArcNotifier Type;

  };

  template <typename _Graph>

  class ItemSetTraits<_Graph, typename _Graph::Arc> {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Arc Item;

    typedef typename Graph::ArcIt ItemIt;

    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

    class Map : public Graph::template ArcMap<_Value> {

    public:

      typedef typename Graph::template ArcMap<_Value> Parent; 

      typedef typename Graph::template ArcMap<_Value> Type; 

      typedef typename Parent::Value Value;

      Map(const Graph& _digraph) : Parent(_digraph) {}

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_VECTOR_MAP_H

#define LEMON_BITS_VECTOR_MAP_H

#include <vector>

#include <algorithm>

#include <lemon/bits/traits.h>

#include <lemon/bits/utility.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup graphbits

///

///\file

///\brief Vector based graph maps.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the std::vector storage.

  ///

  /// The VectorMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map type uses the std::vector to store the values.

  ///

  /// \param Notifier The AlterationNotifier that will notify this map.

  /// \param Item The item type of the graph items.

  /// \param Value The value type of the map.

  /// 

  /// \author Balazs Dezso  	

  template <typename _Graph, typename _Item, typename _Value>

  class VectorMap 

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  private:

    /// The container type of the map.

    typedef std::vector<_Value> Container;	

  public:

    /// The graph type of the map. 

    typedef _Graph Graph;

    /// The item type of the map.

    typedef _Item Item;

    /// The reference map tag.

    typedef True ReferenceMapTag;

    /// The key type of the map.

    typedef _Item Key;

    /// The value type of the map.

    typedef _Value Value;

    /// The notifier type.

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

    /// The map type.

    typedef VectorMap Map;

    /// The base class of the map.

    typedef typename Notifier::ObserverBase Parent;

    /// The reference type of the map;

    typedef typename Container::reference Reference;

    /// The const reference type of the map;

    typedef typename Container::const_reference ConstReference;

    /// \brief Constructor to attach the new map into the notifier.

    ///

    /// It constructs a map and attachs it into the notifier.

    /// It adds all the items of the graph to the map.

    VectorMap(const Graph& graph) {

      Parent::attach(graph.notifier(Item()));

      container.resize(Parent::notifier()->maxId() + 1);

    }

    /// \brief Constructor uses given value to initialize the map. 

    ///

    /// It constructs a map uses a given value to initialize the map. 

    /// It adds all the items of the graph to the map.

    VectorMap(const Graph& graph, const Value& value) {

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_CONCEPT_DIGRAPH_H

#define LEMON_CONCEPT_DIGRAPH_H

///\ingroup graph_concepts

///\file

///\brief The concept of directed graphs.

#include <lemon/bits/invalid.h>

#include <lemon/bits/utility.h>

#include <lemon/concepts/maps.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/graph_components.h>

namespace lemon {

  namespace concepts {

    /// \ingroup graph_concepts

    ///

    /// \brief Class describing the concept of directed graphs.

    ///

    /// This class describes the \ref concept "concept" of the

    /// immutable directed digraphs.

    ///

    /// Note that actual digraph implementation like @ref ListDigraph or

    /// @ref SmartDigraph may have several additional functionality.

    ///

    /// \sa concept

    class Digraph {

    private:

      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.

      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.

      ///

      Digraph(const Digraph &) {};

      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are

      ///\e not allowed. Use DigraphCopy() instead.

      ///Assignment of \ref Digraph "Digraph"s to another ones are

      ///\e not allowed.  Use DigraphCopy() instead.

      void operator=(const Digraph &) {}

    public:

      ///\e

      /// Defalult constructor.

      /// Defalult constructor.

      ///

      Digraph() { }

      /// Class for identifying a node of the digraph

      /// This class identifies a node of the digraph. It also serves

      /// as a base class of the node iterators,

      /// thus they will convert to this type.

      class Node {

      public:

        /// Default constructor

        /// @warning The default constructor sets the iterator

        /// to an undefined value.

        Node() { }

        /// Copy constructor.

        /// Copy constructor.

        ///

        Node(const Node&) { }

        /// Invalid constructor \& conversion.

        /// This constructor initializes the iterator to be invalid.

        /// \sa Invalid for more details.

        Node(Invalid) { }

        /// Equality operator

        /// Two iterators are equal if and only if they point to the

        /// same object or both are invalid.

        bool operator==(Node) const { return true; }

        /// Inequality operator

        /// \sa operator==(Node n)

        ///

        bool operator!=(Node) const { return true; }

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup graph_concepts

///\file

///\brief The concept of Undirected Graphs.

#ifndef LEMON_CONCEPT_GRAPH_H

#define LEMON_CONCEPT_GRAPH_H

#include <lemon/concepts/graph_components.h>

#include <lemon/concepts/graph.h>

#include <lemon/bits/utility.h>

namespace lemon {

  namespace concepts {

    /// \ingroup graph_concepts

    ///

    /// \brief Class describing the concept of Undirected Graphs.

    ///

    /// This class describes the common interface of all Undirected

    /// Graphs.

    ///

    /// As all concept describing classes it provides only interface

    /// without any sensible implementation. So any algorithm for

    /// undirected graph should compile with this class, but it will not

    /// run properly, of course.

    ///

    /// The LEMON undirected graphs also fulfill the concept of

    /// directed graphs (\ref lemon::concepts::Digraph "Digraph

    /// Concept"). Each edges can be seen as two opposite

    /// directed arc and consequently the undirected graph can be

    /// seen as the direceted graph of these directed arcs. The

    /// Graph has the Edge inner class for the edges and

    /// the Arc type for the directed arcs. The Arc type is

    /// convertible to Edge or inherited from it so from a directed

    /// arc we can get the represented edge.

    ///

    /// In the sense of the LEMON each edge has a default

    /// direction (it should be in every computer implementation,

    /// because the order of edge's nodes defines an

    /// orientation). With the default orientation we can define that

    /// the directed arc is forward or backward directed. With the \c

    /// direction() and \c direct() function we can get the direction

    /// of the directed arc and we can direct an edge.

    ///

    /// The EdgeIt is an iterator for the edges. We can use

    /// the EdgeMap to map values for the edges. The InArcIt and

    /// OutArcIt iterates on the same edges but with opposite

    /// direction. The IncEdgeIt iterates also on the same edges

    /// as the OutArcIt and InArcIt but it is not convertible to Arc just

    /// to Edge.  

    class Graph {

    public:

      /// \brief The undirected graph should be tagged by the

      /// UndirectedTag.

      ///

      /// The undirected graph should be tagged by the UndirectedTag. This

      /// tag helps the enable_if technics to make compile time 

      /// specializations for undirected graphs.  

      typedef True UndirectedTag;

      /// \brief The base type of node iterators, 

      /// or in other words, the trivial node iterator.

      ///

      /// This is the base type of each node iterator,

      /// thus each kind of node iterator converts to this.

      /// More precisely each kind of node iterator should be inherited 

      /// from the trivial node iterator.

      class Node {

      public:

        /// Default constructor

        /// @warning The default constructor sets the iterator

        /// to an undefined value.

        Node() { }

        /// Copy constructor.

        /// Copy constructor.

        ///

        Node(const Node&) { }

        /// Invalid constructor \& conversion.

        /// This constructor initializes the iterator to be invalid.

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).