RhodeCode

/* -*- C++ -*-

 *

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

#define LEMON_BFS_H

///\ingroup search

///\file

///\brief Bfs algorithm.

#include <lemon/list_graph.h>

#include <lemon/graph_utils.h>

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.h>

namespace lemon {

  ///Default traits class of Bfs class.

  ///Default traits class of Bfs class.

  template<class GR>

  struct BfsDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the shortest paths.

    /// 

    ///The type of the map that stores the last

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///

    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

    ///\param G is the digraph, to which we would like to define the PredMap.

    ///\todo The digraph alone may be insufficient to initialize

    static PredMap *createPredMap(const GR &G) 

    {

      return new PredMap(G);

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///\todo named parameter to set this type, function to read and write.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a \ref ProcessedMap. 

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const GR &g)

#else

    static ProcessedMap *createProcessedMap(const GR &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that indicates which nodes are reached.

    ///The type of the map that indicates which nodes are reached.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///\todo named parameter to set this type, function to read and write.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    ///Instantiates a ReachedMap.

    ///This function instantiates a \ref ReachedMap. 

    ///\param G is the digraph, to which

    ///we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const GR &G)

    {

      return new ReachedMap(G);

    }

    ///The type of the map that stores the dists of the nodes.

    ///The type of the map that stores the dists of the nodes.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///

    typedef typename Digraph::template NodeMap<int> DistMap;

    ///Instantiates a DistMap.

    ///This function instantiates a \ref DistMap. 

    ///\param G is the digraph, to which we would like to define the \ref DistMap

    static DistMap *createDistMap(const GR &G)

    {

      return new DistMap(G);

    }

  };

  ///%BFS algorithm class.

  ///\ingroup search

  ///This class provides an efficient implementation of the %BFS algorithm.

  ///

  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it

  ///is only passed to \ref BfsDefaultTraits.

  ///The default traits class is

  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".

  ///See \ref BfsDefaultTraits for the documentation of

  ///a Bfs traits class.

#ifdef DOXYGEN

  template <typename GR,

	    typename TR>

#else

  template <typename GR=ListDigraph,

	    typename TR=BfsDefaultTraits<GR> >

#endif

  class Bfs {

  public:

    /**

     * \brief \ref Exception for uninitialized parameters.

     *

     * This error represents problems in the initialization

     * of the parameters of the algorithms.

     */

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() {

	return "lemon::Bfs::UninitializedParameter";

      }

    };

    typedef TR Traits;

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the shortest paths.

    typedef typename TR::PredMap PredMap;

    ///The type of the map indicating which nodes are reached.

    typedef typename TR::ReachedMap ReachedMap;

    ///The type of the map indicating which nodes are processed.

    typedef typename TR::ProcessedMap ProcessedMap;

    ///The type of the map that stores the dists of the nodes.

    typedef typename TR::DistMap DistMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    /// Pointer to the underlying digraph.

    const Digraph *G;

    ///Pointer to the map of predecessors arcs.

    PredMap *_pred;

    ///Indicates if \ref _pred is locally allocated (\c true) or not.

    bool local_pred;

    ///Pointer to the map of distances.

    DistMap *_dist;

    ///Indicates if \ref _dist is locally allocated (\c true) or not.

    bool local_dist;

    ///Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    ///Indicates if \ref _reached is locally allocated (\c true) or not.

    bool local_reached;

    ///Pointer to the map of processed status of the nodes.

    ProcessedMap *_processed;

    ///Indicates if \ref _processed is locally allocated (\c true) or not.

    bool local_processed;

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

    int _queue_head,_queue_tail,_queue_next_dist;

    ///Returns the distance of a node from the root(s).

    ///\pre \ref run() must be called before using this function.

    ///\warning If node \c v in unreachable from the root(s) the return value

    ///of this function is undefined.

    int dist(Node v) const { return (*_dist)[v]; }

    ///Returns the 'previous arc' of the shortest path tree.

    ///For a node \c v it returns the 'previous arc'

    ///of the shortest path tree,

    ///i.e. it returns the last arc of a shortest path from the root(s) to \c

    ///v. It is \ref INVALID

    ///if \c v is unreachable from the root(s) or \c v is a root. The

    ///shortest path tree used here is equal to the shortest path tree used in

    ///\ref predNode().

    ///\pre Either \ref run() or \ref start() must be called before using

    ///this function.

    Arc predArc(Node v) const { return (*_pred)[v];}

    ///Returns the 'previous node' of the shortest path tree.

    ///For a node \c v it returns the 'previous node'

    ///of the shortest path tree,

    ///i.e. it returns the last but one node from a shortest path from the

    ///root(a) to \c /v.

    ///It is INVALID if \c v is unreachable from the root(s) or

    ///if \c v itself a root.

    ///The shortest path tree used here is equal to the shortest path

    ///tree used in \ref predArc().

    ///\pre Either \ref run() or \ref start() must be called before

    ///using this function.

    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:

				  G->source((*_pred)[v]); }

    ///Returns a reference to the NodeMap of distances.

    ///Returns a reference to the NodeMap of distances.

    ///\pre Either \ref run() or \ref init() must

    ///be called before using this function.

    const DistMap &distMap() const { return *_dist;}

    ///Returns a reference to the shortest path tree map.

    ///Returns a reference to the NodeMap of the arcs of the

    ///shortest path tree.

    ///\pre Either \ref run() or \ref init()

    ///must be called before using this function.

    const PredMap &predMap() const { return *_pred;}

    ///Checks if a node is reachable from the root.

    ///Returns \c true if \c v is reachable from the root.

    ///\warning The source nodes are indicated as unreached.

    ///\pre Either \ref run() or \ref start()

    ///must be called before using this function.

    ///

    bool reached(Node v) { return (*_reached)[v]; }

    ///@}

  };

  ///Default traits class of Bfs function.

  ///Default traits class of Bfs function.

  template<class GR>

  struct BfsWizardDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///\brief The type of the map that stores the last

    ///arcs of the shortest paths.

    /// 

    ///The type of the map that stores the last

    ///arcs of the shortest paths.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///

    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;

    ///Instantiates a PredMap.

    ///This function instantiates a \ref PredMap. 

    ///\param g is the digraph, to which we would like to define the PredMap.

    ///\todo The digraph alone may be insufficient to initialize

#ifdef DOXYGEN

    static PredMap *createPredMap(const GR &g) 

#else

    static PredMap *createPredMap(const GR &) 

#endif

    {

      return new PredMap();

    }

    ///The type of the map that indicates which nodes are processed.

    ///The type of the map that indicates which nodes are processed.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///\todo named parameter to set this type, function to read and write.

    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;

    ///Instantiates a ProcessedMap.

    ///This function instantiates a \ref ProcessedMap. 

    ///\param g is the digraph, to which

    ///we would like to define the \ref ProcessedMap

#ifdef DOXYGEN

    static ProcessedMap *createProcessedMap(const GR &g)

#else

    static ProcessedMap *createProcessedMap(const GR &)

#endif

    {

      return new ProcessedMap();

    }

    ///The type of the map that indicates which nodes are reached.

    ///The type of the map that indicates which nodes are reached.

    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.

    ///\todo named parameter to set this type, function to read and write.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    ///Instantiates a ReachedMap.

    ///This function instantiates a \ref ReachedMap. 

    ///\param G is the digraph, to which

    ///we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const GR &G)

    {

      return new ReachedMap(G);

    }

    ///The type of the map that stores the dists of the nodes.

    ///The type of the map that stores the dists of the nodes.

  /// \brief Visitor class for bfs.

  ///  

  /// This class defines the interface of the BfsVisit events, and

  /// it could be the base of a real Visitor class.

  template <typename _Digraph>

  struct BfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    /// \brief Called when the arc reach a node.

    /// 

    /// It is called when the bfs find an arc which target is not

    /// reached yet.

    void discover(const Arc& arc) {}

    /// \brief Called when the node reached first time.

    /// 

    /// It is Called when the node reached first time.

    void reach(const Node& node) {}

    /// \brief Called when the arc examined but target of the arc 

    /// already discovered.

    /// 

    /// It called when the arc examined but the target of the arc 

    /// already discovered.

    void examine(const Arc& arc) {}

    /// \brief Called for the source node of the bfs.

    /// 

    /// It is called for the source node of the bfs.

    void start(const Node& node) {}

    /// \brief Called when the node processed.

    /// 

    /// It is Called when the node processed.

    void process(const Node& node) {}

  };

#else

  template <typename _Digraph>

  struct BfsVisitor {

    typedef _Digraph Digraph;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::Node Node;

    void discover(const Arc&) {}

    void reach(const Node&) {}

    void examine(const Arc&) {}

    void start(const Node&) {}

    void process(const Node&) {}

    template <typename _Visitor>

    struct Constraints {

      void constraints() {

	Arc arc;

	Node node;

	visitor.discover(arc);

	visitor.reach(node);

	visitor.examine(arc);

	visitor.start(node);

        visitor.process(node);

      }

      _Visitor& visitor;

    };

  };

#endif

  /// \brief Default traits class of BfsVisit class.

  ///

  /// Default traits class of BfsVisit class.

  template<class _Digraph>

  struct BfsVisitDefaultTraits {

    /// \brief The digraph type the algorithm runs on. 

    typedef _Digraph Digraph;

    /// \brief The type of the map that indicates which nodes are reached.

    /// 

    /// The type of the map that indicates which nodes are reached.

    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.

    /// \todo named parameter to set this type, function to read and write.

    typedef typename Digraph::template NodeMap<bool> ReachedMap;

    /// \brief Instantiates a ReachedMap.

    ///

    /// This function instantiates a \ref ReachedMap. 

    /// \param digraph is the digraph, to which

    /// we would like to define the \ref ReachedMap.

    static ReachedMap *createReachedMap(const Digraph &digraph) {

      return new ReachedMap(digraph);

    }

  };

  /// \ingroup search

  ///  

  /// \brief %BFS Visit algorithm class.

  ///  

  /// This class provides an efficient implementation of the %BFS algorithm

  /// with visitor interface.

  ///

  /// The %BfsVisit class provides an alternative interface to the Bfs

  /// class. It works with callback mechanism, the BfsVisit object calls

  /// on every bfs event the \c Visitor class member functions. 

  ///

  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it

  /// is only passed to \ref BfsDefaultTraits.

  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which

  /// does not observe the Bfs events. If you want to observe the bfs

  /// events you should implement your own Visitor class.

  /// algorithm. The default traits class is

  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".

  /// See \ref BfsVisitDefaultTraits for the documentation of

  /// a Bfs visit traits class.

#ifdef DOXYGEN

  template <typename _Digraph, typename _Visitor, typename _Traits>

#else

  template <typename _Digraph = ListDigraph,

	    typename _Visitor = BfsVisitor<_Digraph>,

	    typename _Traits = BfsDefaultTraits<_Digraph> >

#endif

  class BfsVisit {

  public:

    /// \brief \ref Exception for uninitialized parameters.

    ///

    /// This error represents problems in the initialization

    /// of the parameters of the algorithms.

    class UninitializedParameter : public lemon::UninitializedParameter {

    public:

      virtual const char* what() const throw() 

      {

	return "lemon::BfsVisit::UninitializedParameter";

      }

    };

    typedef _Traits Traits;

    typedef typename Traits::Digraph Digraph;

    typedef _Visitor Visitor;

    ///The type of the map indicating which nodes are reached.

    typedef typename Traits::ReachedMap ReachedMap;

  private:

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::OutArcIt OutArcIt;

    /// Pointer to the underlying digraph.

    const Digraph *_digraph;

    /// Pointer to the visitor object.

    Visitor *_visitor;

    ///Pointer to the map of reached status of the nodes.

    ReachedMap *_reached;

    ///Indicates if \ref _reached is locally allocated (\c true) or not.

    bool local_reached;

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

    int _list_front, _list_back;

    /// \brief Creates the maps if necessary.

    ///

    /// Creates the maps if necessary.

    void create_maps() {

      if(!_reached) {

	local_reached = true;

	_reached = Traits::createReachedMap(*_digraph);

      }

    }

  protected:

    BfsVisit() {}

/* -*- C++ -*-

 *

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

#define LEMON_BIN_HEAP_H

///\ingroup auxdat

///\file

///\brief Binary Heap implementation.

#include <vector>

#include <utility>

#include <functional>

namespace lemon {

  ///\ingroup auxdat

  ///

  ///\brief A Binary Heap implementation.

  ///

  ///This class implements the \e binary \e heap data structure. A \e heap

  ///is a data structure for storing items with specified values called \e

  ///priorities in such a way that finding the item with minimum priority is

  ///efficient. \c Compare specifies the ordering of the priorities. In a heap

  ///one can change the priority of an item, add or erase an item, etc.

  ///

  ///to handle the cross references.

  ///default is \c std::less<_Prio>.

  ///

  ///\sa FibHeap

  ///\sa Dijkstra

  template <typename _Prio, typename _ItemIntMap,

	    typename _Compare = std::less<_Prio> >

  class BinHeap {

  public:

    ///\e

    typedef _ItemIntMap ItemIntMap;

    ///\e

    typedef _Prio Prio;

    ///\e

    typedef typename ItemIntMap::Key Item;

    ///\e

    typedef std::pair<Item,Prio> Pair;

    ///\e

    typedef _Compare Compare;

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

    ///

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

    /// "pre heap" or "post heap". The latter two are indifferent from the

    /// heap's point of view, but may be useful to the user.

    ///

    /// The ItemIntMap \e should be initialized in such way that it maps

    /// PRE_HEAP (-1) to any element to be put in the heap...

    enum State {

      IN_HEAP = 0,

      PRE_HEAP = -1,

      POST_HEAP = -2

    };

  private:

    std::vector<Pair> data;

    Compare comp;

    ItemIntMap &iim;

  public:

    /// \brief The constructor.

    ///

    /// The constructor.

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

    /// internally to handle the cross references. The value of the map

    /// should be PRE_HEAP (-1) for each element.

    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}

    /// \brief The constructor.

    ///

    /// The constructor.

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

    /// internally to handle the cross references. The value of the map

    /// should be PRE_HEAP (-1) for each element.

    ///

    /// \param _comp The comparator function object.

    BinHeap(ItemIntMap &_iim, const Compare &_comp) 

      : iim(_iim), comp(_comp) {}

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

    ///

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

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

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

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

/* -*- C++ -*-

 *

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

#define LEMON_BEZIER_H

///\ingroup misc

///\file

///\brief Classes to compute with Bezier curves.

///

///Up to now this file is used internally by \ref graph_to_eps.h

#include<lemon/dim2.h>

namespace lemon {

  namespace dim2 {

class BezierBase {

public:

  typedef Point<double> Point;

protected:

  static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}

};

class Bezier1 : public BezierBase

{

public:

  Point p1,p2;

  Bezier1() {}

  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}

  Point operator()(double t) const

  {

    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);

    return conv(p1,p2,t);

  }

  Bezier1 before(double t) const

  {

    return Bezier1(p1,conv(p1,p2,t));

  }

  Bezier1 after(double t) const

  {

    return Bezier1(conv(p1,p2,t),p2);

  }

  Bezier1 revert() const { return Bezier1(p2,p1);}

  Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }

  Point grad() const { return p2-p1; }

  Point norm() const { return rot90(p2-p1); }

  Point grad(double) const { return grad(); }

  Point norm(double t) const { return rot90(grad(t)); }

};

class Bezier2 : public BezierBase

{

public:

  Point p1,p2,p3;

  Bezier2() {}

  Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}

  Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}

  Point operator()(double t) const

  {

    //    return conv(conv(p1,p2,t),conv(p2,p3,t),t);

    return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;

  }

  Bezier2 before(double t) const

  {

    Point q(conv(p1,p2,t));

    Point r(conv(p2,p3,t));

    return Bezier2(p1,q,conv(q,r,t));

  }

/* -*- C++ -*-

 *

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

  ///

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

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

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

    }

    /// \brief Copy constructor

    ///

    /// Copy constructor.

    VectorMap(const VectorMap& _copy) : Parent() {

      if (_copy.attached()) {

	Parent::attach(*_copy.notifier());

	container = _copy.container;

      }

    }

/* -*- C++ -*-

 *

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