RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

/// \file

/// \brief Demo of the graph drawing function \ref graphToEps()

///

/// This demo program shows examples how to use the function \ref

/// graphToEps(). It takes no input but simply creates seven

/// <tt>.eps</tt> files demonstrating the capability of \ref

/// graphToEps(), and showing how to draw directed graphs,

/// how to handle parallel egdes, how to change the properties (like

/// color, shape, size, title etc.) of nodes and arcs individually

///

/// \include graph_to_eps_demo.cc

#include<lemon/list_graph.h>

#include<lemon/graph_to_eps.h>

#include<lemon/math.h>

using namespace std;

using namespace lemon;

int main()

{

  Palette palette;

  Palette paletteW(true);

  // Create a small digraph

  ListDigraph g;

  typedef ListDigraph::Node Node;

  typedef ListDigraph::NodeIt NodeIt;

  typedef ListDigraph::Arc Arc;

  typedef dim2::Point<int> Point;

  Node n1=g.addNode();

  Node n2=g.addNode();

  Node n3=g.addNode();

  Node n4=g.addNode();

  Node n5=g.addNode();

  ListDigraph::NodeMap<Point> coords(g);

  ListDigraph::NodeMap<double> sizes(g);

  ListDigraph::NodeMap<int> colors(g);

  ListDigraph::NodeMap<int> shapes(g);

  ListDigraph::ArcMap<int> acolors(g);

  ListDigraph::ArcMap<int> widths(g);

  coords[n1]=Point(50,50);  sizes[n1]=1; colors[n1]=1; shapes[n1]=0;

  coords[n2]=Point(50,70);  sizes[n2]=2; colors[n2]=2; shapes[n2]=2;

  coords[n3]=Point(70,70);  sizes[n3]=1; colors[n3]=3; shapes[n3]=0;

  coords[n4]=Point(70,50);  sizes[n4]=2; colors[n4]=4; shapes[n4]=1;

  coords[n5]=Point(85,60);  sizes[n5]=3; colors[n5]=5; shapes[n5]=2;

  Arc a;

  a=g.addArc(n1,n2); acolors[a]=0; widths[a]=1;

  a=g.addArc(n2,n3); acolors[a]=0; widths[a]=1;

  a=g.addArc(n3,n5); acolors[a]=0; widths[a]=3;

  a=g.addArc(n5,n4); acolors[a]=0; widths[a]=1;

  a=g.addArc(n4,n1); acolors[a]=0; widths[a]=1;

  a=g.addArc(n2,n4); acolors[a]=1; widths[a]=2;

  a=g.addArc(n3,n4); acolors[a]=2; widths[a]=1;

  IdMap<ListDigraph,Node> id(g);

  // Create .eps files showing the digraph with different options

  cout << "Create 'graph_to_eps_demo_out_1_pure.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_1_pure.eps").

    coords(coords).

    title("Sample .eps figure").

    copyright("(C) 2003-2008 LEMON Project").

    run();

  cout << "Create 'graph_to_eps_demo_out_2.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_2.eps").

    coords(coords).

    title("Sample .eps figure").

    copyright("(C) 2003-2008 LEMON Project").

    absoluteNodeSizes().absoluteArcWidths().

    nodeScale(2).nodeSizes(sizes).

    nodeShapes(shapes).

    nodeColors(composeMap(palette,colors)).

    arcColors(composeMap(palette,acolors)).

    arcWidthScale(.4).arcWidths(widths).

    nodeTexts(id).nodeTextSize(3).

    run();

  cout << "Create 'graph_to_eps_demo_out_3_arr.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_3_arr.eps").

    title("Sample .eps figure (with arrowheads)").

    copyright("(C) 2003-2008 LEMON Project").

    absoluteNodeSizes().absoluteArcWidths().

    nodeColors(composeMap(palette,colors)).

    coords(coords).

    nodeScale(2).nodeSizes(sizes).

    nodeShapes(shapes).

    arcColors(composeMap(palette,acolors)).

    arcWidthScale(.4).arcWidths(widths).

    nodeTexts(id).nodeTextSize(3).

    drawArrows().arrowWidth(2).arrowLength(2).

    run();

  // Add more arcs to the digraph

  a=g.addArc(n1,n4); acolors[a]=2; widths[a]=1;

  a=g.addArc(n4,n1); acolors[a]=1; widths[a]=2;

  a=g.addArc(n1,n2); acolors[a]=1; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=2; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=3; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=4; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=5; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=6; widths[a]=1;

  a=g.addArc(n1,n2); acolors[a]=7; widths[a]=1;

  cout << "Create 'graph_to_eps_demo_out_4_par.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_4_par.eps").

    title("Sample .eps figure (parallel arcs)").

    copyright("(C) 2003-2008 LEMON Project").

    absoluteNodeSizes().absoluteArcWidths().

    nodeShapes(shapes).

    coords(coords).

    nodeScale(2).nodeSizes(sizes).

    nodeColors(composeMap(palette,colors)).

    arcColors(composeMap(palette,acolors)).

    arcWidthScale(.4).arcWidths(widths).

    nodeTexts(id).nodeTextSize(3).

    enableParallel().parArcDist(1.5).

    run();

  cout << "Create 'graph_to_eps_demo_out_5_par_arr.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_5_par_arr.eps").

    title("Sample .eps figure (parallel arcs and arrowheads)").

    copyright("(C) 2003-2008 LEMON Project").

    absoluteNodeSizes().absoluteArcWidths().

    nodeScale(2).nodeSizes(sizes).

    coords(coords).

    nodeShapes(shapes).

    nodeColors(composeMap(palette,colors)).

    arcColors(composeMap(palette,acolors)).

    arcWidthScale(.3).arcWidths(widths).

    nodeTexts(id).nodeTextSize(3).

    enableParallel().parArcDist(1).

    drawArrows().arrowWidth(1).arrowLength(1).

    run();

  cout << "Create 'graph_to_eps_demo_out_6_par_arr_a4.eps'" << endl;

  graphToEps(g,"graph_to_eps_demo_out_6_par_arr_a4.eps").

    title("Sample .eps figure (fits to A4)").

    copyright("(C) 2003-2008 LEMON Project").

    scaleToA4().

    absoluteNodeSizes().absoluteArcWidths().

    nodeScale(2).nodeSizes(sizes).

    coords(coords).

    nodeShapes(shapes).

    nodeColors(composeMap(palette,colors)).

    arcColors(composeMap(palette,acolors)).

    arcWidthScale(.3).arcWidths(widths).

    nodeTexts(id).nodeTextSize(3).

    enableParallel().parArcDist(1).

    drawArrows().arrowWidth(1).arrowLength(1).

    run();

  // Create an .eps file showing the colors of a default Palette

  ListDigraph h;

  ListDigraph::NodeMap<int> hcolors(h);

  ListDigraph::NodeMap<Point> hcoords(h);

  int cols=int(sqrt(double(palette.size())));

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

    Node n=h.addNode();

    hcoords[n]=Point(1+i%cols,1+i/cols);

    hcolors[n]=i;

  }

  cout << "Create 'graph_to_eps_demo_out_7_colors.eps'" << endl;

  graphToEps(h,"graph_to_eps_demo_out_7_colors.eps").

    scale(60).

    title("Sample .eps figure (Palette demo)").

    copyright("(C) 2003-2008 LEMON Project").

    coords(hcoords).

    absoluteNodeSizes().absoluteArcWidths().

    nodeScale(.45).

    distantColorNodeTexts().

    nodeTexts(hcolors).nodeTextSize(.6).

    nodeColors(composeMap(paletteW,hcolors)).

    run();

  return 0;

}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

 *

 */

namespace lemon {

/*!

\page lgf-format LEMON Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences.

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label  coordinates  size    title

 1      (10,20)      10      "First node"

 2      (80,80)      8       "Second node"

 3      (40,10)      10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

         capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

also store the edge set of an undirected graph. In such case there is

a conventional method for store arc maps in the file, if two columns

has the same caption with \c '+' and \c '-' prefix, then these columns

can be regarded as the values of an arc map.

The \c \@attributes section contains key-value pairs, each line

consists of two tokens, an attribute name, and then an attribute

value. The value of the attribute could be also a label value of a

node or an edge, or even an edge label prefixed with \c '+' or \c '-',

which regards to the forward or backward directed arc of the

corresponding edge.

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

  template <typename _Container, typename _Item>

  class AlterationNotifier {

  public:

    typedef True Notifier;

    typedef _Container Container;

    typedef _Item Item;

    /// \brief Exception which can be called from \e clear() and

    /// \e erase().

    ///

    /// From the \e clear() and \e erase() function only this

    /// exception is allowed to throw. The exception immediatly

    /// detaches the current observer from the notifier. Because the

    /// \e clear() and \e erase() should not throw other exceptions

    /// it can be used to invalidate the observer.

    struct ImmediateDetach {};

    /// \brief ObserverBase is the base class for the observers.

    ///

    /// ObserverBase is the abstract base class for the observers.

    /// It will be notified about an item was inserted into or

    /// erased from the graph.

    ///

    /// The observer interface contains some pure virtual functions

    /// to override. The add() and erase() functions are

    /// to notify the oberver when one item is added or

    /// erased.

    ///

    /// The build() and clear() members are to notify the observer

    /// about the container is built from an empty container or

    /// is cleared to an empty container.

    class ObserverBase {

    protected:

      typedef AlterationNotifier Notifier;

      friend class AlterationNotifier;

      /// \brief Default constructor.

      ///

      /// Default constructor for ObserverBase.

      ///

      ObserverBase() : _notifier(0) {}

      /// \brief Constructor which attach the observer into notifier.

      ///

      /// Constructor which attach the observer into notifier.

      ObserverBase(AlterationNotifier& nf) {

        attach(nf);

      }

      /// \brief Constructor which attach the obserever to the same notifier.

      ///

      /// Constructor which attach the obserever to the same notifier as

      /// the other observer is attached to.

      ObserverBase(const ObserverBase& copy) {

        if (copy.attached()) {

          attach(*copy.notifier());

        }

      }

      /// \brief Destructor

      virtual ~ObserverBase() {

        if (attached()) {

          detach();

        }

      }

      /// \brief Attaches the observer into an AlterationNotifier.

      ///

      /// This member attaches the observer into an AlterationNotifier.

      ///

      void attach(AlterationNotifier& nf) {

        nf.attach(*this);

      }

      /// \brief Detaches the observer into an AlterationNotifier.

      ///

      /// This member detaches the observer from an AlterationNotifier.

      ///

      void detach() {

        _notifier->detach(*this);

      }

      /// \brief Gives back a pointer to the notifier which the map

      /// attached into.

      ///

      /// This function gives back a pointer to the notifier which the map

      /// attached into.

      ///

      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }

      /// Gives back true when the observer is attached into a notifier.

      bool attached() const { return _notifier != 0; }

    private:

      ObserverBase& operator=(const ObserverBase& copy);

    protected:

      Notifier* _notifier;

      typename std::list<ObserverBase*>::iterator _index;

      /// \brief The member function to notificate the observer about an

      /// item is added to the container.

      ///

      /// The add() member function notificates the observer about an item

      /// is added to the container. It have to be overrided in the

      /// subclasses.

      virtual void add(const Item&) = 0;

      /// \brief The member function to notificate the observer about

      /// more item is added to the container.

      ///

      /// The add() member function notificates the observer about more item

      /// is added to the container. It have to be overrided in the

      /// subclasses.

      virtual void add(const std::vector<Item>& items) = 0;

      /// \brief The member function to notificate the observer about an

      /// item is erased from the container.

      ///

      /// The erase() member function notificates the observer about an

      /// item is erased from the container. It have to be overrided in

      /// the subclasses.

      virtual void erase(const Item&) = 0;

      /// \brief The member function to notificate the observer about

      /// more item is erased from the container.

      ///

      /// The erase() member function notificates the observer about more item

      /// is erased from the container. It have to be overrided in the

      /// subclasses.

      virtual void erase(const std::vector<Item>& items) = 0;

      /// \brief The member function to notificate the observer about the

      /// container is built.

      ///

      /// The build() member function notificates the observer about the

      /// container is built from an empty container. It have to be

      /// overrided in the subclasses.

      virtual void build() = 0;

      /// \brief The member function to notificate the observer about all

      /// items are erased from the container.

      ///

      /// The clear() member function notificates the observer about all

      /// items are erased from the container. It have to be overrided in

      /// the subclasses.

      virtual void clear() = 0;

    };

  protected:

    const Container* container;

    typedef std::list<ObserverBase*> Observers;

    Observers _observers;

  public:

    /// \brief Default constructor.

    ///

    /// The default constructor of the AlterationNotifier.

    /// It creates an empty notifier.

    AlterationNotifier()

      : container(0) {}

    /// \brief Constructor.

    ///

    /// Constructor with the observed container parameter.

    AlterationNotifier(const Container& _container)

      : container(&_container) {}

    /// \brief Copy Constructor of the AlterationNotifier.

    ///

    /// Copy constructor of the AlterationNotifier.

    /// It creates only an empty notifier because the copiable

    /// notifier's observers have to be registered still into that notifier.

    AlterationNotifier(const AlterationNotifier& _notifier)

      : container(_notifier.container) {}

    /// \brief Destructor.

    ///

    /// Destructor of the AlterationNotifier.

    ///

    ~AlterationNotifier() {

      typename Observers::iterator it;

      for (it = _observers.begin(); it != _observers.end(); ++it) {

        (*it)->_notifier = 0;

      }

    }

    /// \brief Sets the container.

    ///

    /// Sets the container.

    void setContainer(const Container& _container) {

      container = &_container;

    }

  protected:

    AlterationNotifier& operator=(const AlterationNotifier&);

  public:

    /// \brief First item in the container.

    ///

    /// Returns the first item in the container. It is

    /// for start the iteration on the container.

    void first(Item& item) const {

      container->first(item);

    }

    /// \brief Next item in the container.

    ///

    /// Returns the next item in the container. It is

    /// for iterate on the container.

    void next(Item& item) const {

      container->next(item);

    }

    /// \brief Returns the id of the item.

    ///

    /// Returns the id of the item provided by the container.

    int id(const Item& item) const {

      return container->id(item);

    }

    /// \brief Returns the maximum id of the container.

    ///

    /// Returns the maximum id of the container.

    int maxId() const {

      return container->maxId(Item());

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

  // long long

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, signed long long> {

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

  };

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, unsigned long long> {

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

  };

#endif

  // float

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, float> {

    typedef VectorMap<_Graph, _Item, float> Map;

  };

  // double

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, double> {

    typedef VectorMap<_Graph, _Item,  double> Map;

  };

  // long double

  template <typename _Graph, typename _Item>

  struct DefaultMapSelector<_Graph, _Item, long double> {

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

  };

  // pointer

  template <typename _Graph, typename _Item, typename _Ptr>

  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {

    typedef VectorMap<_Graph, _Item, _Ptr*> Map;

  };

// #else

//   template <typename _Graph, typename _Item, typename _Value>

//   struct DefaultMapSelector {

//     typedef DebugMap<_Graph, _Item, _Value> Map;

//   };

// #endif

  template <typename _Graph, typename _Item, typename _Value>

  class DefaultMap

    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {

  public:

    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;

    typedef DefaultMap<_Graph, _Item, _Value> Map;

    typedef typename Parent::Graph Graph;

    typedef typename Parent::Value Value;

    explicit DefaultMap(const Graph& graph) : Parent(graph) {}

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

      : Parent(graph, value) {}

    DefaultMap& operator=(const DefaultMap& cmap) {

      return operator=<DefaultMap>(cmap);

    }

    template <typename CMap>

    DefaultMap& operator=(const CMap& cmap) {

      Parent::operator=(cmap);

      return *this;

    }

  };

}

#endif

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

#define LEMON_COLOR_H

#include<vector>

#include<lemon/math.h>

#include<lemon/maps.h>

///\ingroup misc

///\file

///\brief Tools to manage RGB colors.

namespace lemon {

  /// \addtogroup misc

  /// @{

  ///Data structure representing RGB colors.

  ///Data structure representing RGB colors.

  class Color

  {

    double _r,_g,_b;

  public:

    ///Default constructor

    Color() {}

    ///Constructor

    Color(double r,double g,double b) :_r(r),_g(g),_b(b) {};

    ///Set the red component

    double & red() {return _r;}

    ///Return the red component

    const double & red() const {return _r;}

    ///Set the green component

    double & green() {return _g;}

    ///Return the green component

    const double & green() const {return _g;}

    ///Set the blue component

    double & blue() {return _b;}

    ///Return the blue component

    const double & blue() const {return _b;}

    ///Set the color components

    void set(double r,double g,double b) { _r=r;_g=g;_b=b; };

  };

  /// White color constant

  extern const Color WHITE;

  /// Black color constant

  extern const Color BLACK;

  /// Red color constant

  extern const Color RED;

  /// Green color constant

  extern const Color GREEN;

  /// Blue color constant

  extern const Color BLUE;

  /// Yellow color constant

  extern const Color YELLOW;

  /// Magenta color constant

  extern const Color MAGENTA;

  /// Cyan color constant

  extern const Color CYAN;

  /// Grey color constant

  extern const Color GREY;

  /// Dark red color constant

  extern const Color DARK_RED;

  /// Dark green color constant

  extern const Color DARK_GREEN;

  /// Drak blue color constant

  extern const Color DARK_BLUE;

  /// Dark yellow color constant

  extern const Color DARK_YELLOW;

  /// Dark magenta color constant

  extern const Color DARK_MAGENTA;

  /// Dark cyan color constant

  extern const Color DARK_CYAN;

  ///This map assigns one of the predefined \ref Color "Color"s to

  ///each <tt>int</tt>. It is possible to change the colors as well as

  ///their number. The integer range is cyclically mapped to the

  ///provided set of colors.

  ///

  ///This is a true \ref concepts::ReferenceMap "reference map", so

  ///you can also change the actual colors.

  class Palette : public MapBase<int,Color>

  {

    std::vector<Color> colors;

  public:

    ///Constructor

    ///Constructor.

    ///\param have_white Indicates whether white is among the

    ///provided initial colors (\c true) or not (\c false). If it is true,

    ///white will be assigned to \c 0.

    ///\param num The number of the allocated colors. If it is \c -1,

    ///the default color configuration is set up (26 color plus optionaly the

    ///white).  If \c num is less then 26/27 then the default color

    ///list is cut. Otherwise the color list is filled repeatedly with

    ///the default color list.  (The colors can be changed later on.)

    Palette(bool have_white=false,int num=-1)

    {

      if (num==0) return;

      do {

        if(have_white) colors.push_back(Color(1,1,1));

        colors.push_back(Color(0,0,0));

        colors.push_back(Color(1,0,0));

        colors.push_back(Color(0,1,0));

        colors.push_back(Color(0,0,1));

        colors.push_back(Color(1,1,0));

        colors.push_back(Color(1,0,1));

        colors.push_back(Color(0,1,1));

        colors.push_back(Color(.5,0,0));

        colors.push_back(Color(0,.5,0));

        colors.push_back(Color(0,0,.5));

        colors.push_back(Color(.5,.5,0));

        colors.push_back(Color(.5,0,.5));

        colors.push_back(Color(0,.5,.5));

        colors.push_back(Color(.5,.5,.5));

        colors.push_back(Color(1,.5,.5));

        colors.push_back(Color(.5,1,.5));

        colors.push_back(Color(.5,.5,1));

        colors.push_back(Color(1,1,.5));

        colors.push_back(Color(1,.5,1));

        colors.push_back(Color(.5,1,1));

        colors.push_back(Color(1,.5,0));

        colors.push_back(Color(.5,1,0));

        colors.push_back(Color(1,0,.5));

        colors.push_back(Color(0,1,.5));

        colors.push_back(Color(0,.5,1));

        colors.push_back(Color(.5,0,1));

      } while(int(colors.size())<num);

      if(num>=0) colors.resize(num);

    }

    ///\e

    Color &operator[](int i)

    {

      return colors[i%colors.size()];

    }

    ///\e

    const Color &operator[](int i) const

    {

      return colors[i%colors.size()];

    }

    ///\e

    void set(int i,const Color &c)

    {

      colors[i%colors.size()]=c;

    }

    ///Adds a new color to the end of the color list.

    void add(const Color &c)

    {

      colors.push_back(c);

    }

    ///Sets the number of the existing colors.

    void resize(int s) { colors.resize(s);}

    ///Returns the number of the existing colors.

    int size() const { return int(colors.size());}

  };

  ///Returns a visibly distinct \ref Color

  ///Returns a \ref Color which is as different from the given parameter

  ///as it is possible.

  inline Color distantColor(const Color &c)

  {

    return Color(c.red()<.5?1:0,c.green()<.5?1:0,c.blue()<.5?1:0);

  }

  ///Returns black for light colors and white for the dark ones.

  ///Returns black for light colors and white for the dark ones.

  inline Color distantBW(const Color &c){

    return (.2125*c.red()+.7154*c.green()+.0721*c.blue())<.5 ? WHITE : BLACK;

  }

  /// @}

} //END OF NAMESPACE LEMON

#endif // LEMON_COLOR_H

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,

              typename _Digraph::ArcIt >();

            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,

              typename _Digraph::NodeIt >();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();

            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,

              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();

            typename _Digraph::Node n;

            typename _Digraph::InArcIt ieit(INVALID);

            typename _Digraph::OutArcIt oeit(INVALID);

            n = digraph.baseNode(ieit);

            n = digraph.runningNode(ieit);

            n = digraph.baseNode(oeit);

            n = digraph.runningNode(oeit);

            ignore_unused_variable_warning(n);

          }

        }

        const _Digraph& digraph;

      };

    };

    /// \brief An empty iterable undirected graph class.

    ///

    /// This class provides beside the core graph features iterator

    /// based iterable interface for the undirected graph structure.

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

    template <typename _Base = BaseGraphComponent>

    class IterableGraphComponent : public IterableDigraphComponent<_Base> {

    public:

      typedef _Base Base;

      typedef typename Base::Node Node;

      typedef typename Base::Arc Arc;

      typedef typename Base::Edge Edge;

      typedef IterableGraphComponent Graph;