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

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

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

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

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

    }

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

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

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

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

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

/* -*- 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 graph components.

#ifndef LEMON_CONCEPT_GRAPH_COMPONENTS_H

#define LEMON_CONCEPT_GRAPH_COMPONENTS_H

#include <lemon/bits/invalid.h>

#include <lemon/concepts/maps.h>

#include <lemon/bits/alteration_notifier.h>

namespace lemon {

  namespace concepts {

    /// \brief Skeleton class for graph Node and Arc types

    ///

    /// This class describes the interface of Node and Arc (and Edge

    /// in undirected graphs) subtypes of graph types.

    ///

    /// \note This class is a template class so that we can use it to

    /// create graph skeleton classes. The reason for this is than Node

    /// and Arc types should \em not derive from the same base class.

    /// For Node you should instantiate it with character 'n' and for Arc

    /// with 'a'.

#ifndef DOXYGEN

    template <char _selector = '0'>

#endif

    class GraphItem {

    public:

      /// \brief Default constructor.

      ///      

      /// \warning The default constructor is not required to set

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

 *

 */

#include <iostream>

#include <vector>

#include <lemon/concepts/digraph.h>

#include <lemon/list_graph.h>

//#include <lemon/smart_graph.h>

//#include <lemon/full_graph.h>

//#include <lemon/hypercube_graph.h>

#include "test_tools.h"

#include "digraph_test.h"

#include "map_test.h"

using namespace lemon;

using namespace lemon::concepts;

int main() {

  { // checking digraph components

    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

    checkConcept<IDableDigraphComponent<>, 

      IDableDigraphComponent<> >();

    checkConcept<IterableDigraphComponent<>, 

      IterableDigraphComponent<> >();

    checkConcept<MappableDigraphComponent<>, 

      MappableDigraphComponent<> >();

  }

  { // checking skeleton digraphs

    checkConcept<Digraph, 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_TEST_GRAPH_TEST_H

#define LEMON_TEST_GRAPH_TEST_H

//#include <lemon/graph_utils.h>

#include "test_tools.h"

//! \ingroup misc

//! \file

//! \brief Some utility and test cases to test digraph classes.

namespace lemon {

  ///Structure returned by \ref addPetersen().

  ///Structure returned by \ref addPetersen().

  ///

  template<class Digraph> 

  struct PetStruct

  {

    ///Vector containing the outer nodes.

    std::vector<typename Digraph::Node> outer;

    ///Vector containing the inner nodes.

    std::vector<typename Digraph::Node> inner;

    ///Vector containing the edges of the inner circle.

    std::vector<typename Digraph::Arc> incir;

    ///Vector containing the edges of the outer circle.

    std::vector<typename Digraph::Arc> outcir;

    ///Vector containing the chord edges.

    std::vector<typename Digraph::Arc> chords;

  };

  ///Adds a Petersen graph to \c G.

  ///Adds a Petersen graph to \c G.

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

 *

 */

#include <lemon/concepts/graph.h>

#include <lemon/list_graph.h>

// #include <lemon/smart_graph.h>

// #include <lemon/full_graph.h>

// #include <lemon/grid_graph.h>

//#include <lemon/graph_utils.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

void check_concepts() {

  { // checking digraph components

    checkConcept<BaseGraphComponent, BaseGraphComponent >();

    checkConcept<IDableGraphComponent<>, 

      IDableGraphComponent<> >();

    checkConcept<IterableGraphComponent<>, 

      IterableGraphComponent<> >();

    checkConcept<MappableGraphComponent<>, 

      MappableGraphComponent<> >();

  }

  {

    checkConcept<Graph, ListGraph>();    

//     checkConcept<Graph, SmartGraph>();    

//     checkConcept<Graph, FullGraph>();    

//     checkConcept<Graph, Graph>();    

//     checkConcept<Graph, GridGraph>();

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

#define LEMON_TEST_MAP_TEST_H

#include <vector>

#include <lemon/maps.h>

#include "test_tools.h"

//! \ingroup misc

//! \file

//! \brief Some utilities to test map classes.

namespace lemon {

  template <typename Graph>

  void checkGraphNodeMap() {

    Graph graph;

    const int num = 16;

    typedef typename Graph::Node Node;

    std::vector<Node> nodes;

    for (int i = 0; i < num; ++i) {

      nodes.push_back(graph.addNode());      

    }

    typedef typename Graph::template NodeMap<int> IntNodeMap;

    IntNodeMap map(graph, 42);

    for (int i = 0; i < int(nodes.size()); ++i) {

      check(map[nodes[i]] == 42, "Wrong map constructor.");      

    }

    for (int i = 0; i < num; ++i) {