RhodeCode

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

\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

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

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

  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.

      };

    };

    /// \brief Class describing the concept of graph maps

    ///

    /// This class describes the common interface of the graph maps

    /// associate data to graph descriptors (nodes or arcs).

    template <typename _Graph, typename _Item, typename _Value>

    class GraphMap : public ReadWriteMap<_Item, _Value> {

    public:

      typedef ReadWriteMap<_Item, _Value> Parent;

      /// The graph type of the map.

    ///Finding the arcs take at most <em>O</em>(log<em>d</em>)

    ///amortized time, specifically, the time complexity of the lookups

    ///is equal to the optimal search tree implementation for the

    ///current query distribution in a constant factor.

    ///

    ///\note This is a dynamic data structure, therefore the data

    ///structure is updated after each graph alteration. Thus although

    ///this data structure is theoretically faster than \ref ArcLookUp

    ///them.

    Arc operator()(Node s, Node t, Arc p = INVALID) const  {

      if (p == INVALID) {

        Arc a = _head[s];

        if (a == INVALID) return INVALID;

        Arc r = INVALID;

        while (true) {

          if (_g.target(a) < t) {

    ///out-degree of the digraph.

    void refresh()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an arc between two nodes.

    ///\param s The source node.

    ///\param t The target node.

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.

    ///following way.

    ///\code

    ///AllArcLookUp<ListDigraph> ae(g);

    ///...

    ///int n = 0;

    ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;

    ///\endcode

    ///

    ///consecutive arcs are found in constant time.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.

    ///

#ifdef DOXYGEN

    Arc operator()(Node s, Node t, Arc prev=INVALID) const {}

    ///The type of the DFS paths.

    ///The type of the DFS paths.

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

    typedef lemon::Path<Digraph> Path;

  };

  /// To make it easier to use Dfs algorithm

  /// we have created a wizard class.

  /// This \ref DfsWizard class needs default traits,

  /// as well as the \ref Dfs class.

  /// The \ref DfsWizardBase is a class to be the default traits of the

  /// \ref DfsWizard class.

  template<class GR>

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \brief \ref named-templ-param "Named parameter" for setting

    ///

    ///\ref named-templ-param "Named parameter" for setting

    ///\ref OperationTraits type.

    template <class T>

    struct SetOperationTraits

      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    ///The type of the shortest paths.

    ///The type of the shortest paths.

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

    typedef lemon::Path<Digraph> Path;

  };

  /// To make it easier to use Dijkstra algorithm

  /// we have created a wizard class.

  /// This \ref DijkstraWizard class needs default traits,

  /// as well as the \ref Dijkstra class.

  /// The \ref DijkstraWizardBase is a class to be the default traits of the

  /// \ref DijkstraWizard class.

  template<class GR,class LM>

  template<typename T>

  inline Point<T> rot270(const Point<T> &z)

  {

    return Point<T>(z.y,-z.x);

  }

  /// A class to calculate or store the bounding box of plain vectors

  template<typename T>

  class Box {

      Point<T> _bottom_left, _top_right;

      bool _empty;

    public:

      ///Default constructor: creates an empty box

      Box() { _empty = true; }

  ///\relates Box

  template<typename T>

  inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)

  {

    os << "(" << b.bottomLeft() << "," << b.topRight() << ")";

    return os;

  }

  ///\ingroup maps

  template<class M>

  class XMap

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    XMap(M& map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].x;}

    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}

  };

  ///

  ///\ingroup maps

  ///\relates XMap

  template<class M>

  inline XMap<M> xMap(M &m)

  {

    return XMap<M>(m);

  }

  template<class M>

  inline XMap<M> xMap(const M &m)

  {

    return XMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class ConstXMap

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    ConstXMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].x;}

  };

  ///

  ///\ingroup maps

  ///\relates ConstXMap

  template<class M>

  inline ConstXMap<M> xMap(const M &m)

  {

    return ConstXMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class YMap

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    YMap(M& map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].y;}

    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}

  };

  ///

  ///\ingroup maps

  ///\relates YMap

  template<class M>

  inline YMap<M> yMap(M &m)

  {

    return YMap<M>(m);

  }

  template<class M>

  inline YMap<M> yMap(const M &m)

  {

    return YMap<M>(m);

  }

  ///\ingroup maps

  template<class M>

  class ConstYMap

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    ConstYMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].y;}

  };

  ///

  ///\ingroup maps

  ///\relates ConstYMap

  template<class M>

  inline ConstYMap<M> yMap(const M &m)

  {

    return ConstYMap<M>(m);

  }

  ///

  ///Map of the \ref Point::normSquare() "normSquare()"

  ///of a \ref Point "Point"-map.

  ///\ingroup maps

  template<class M>

  class NormSquareMap

  {

    const M& _map;

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    NormSquareMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].normSquare();}

  };

  ///

  ///\ingroup maps

  ///\relates NormSquareMap

  template<class M>

  inline NormSquareMap<M> normSquareMap(const M &m)

  {

    return NormSquareMap<M>(m);

  }

      typedef typename MT::Value Value;

      const MT ↦

      int yscale;

      _NegY(const MT &m,bool b) : map(m), yscale(1-b*2) {}

      Value operator[](Key n) { return Value(map[n].x,map[n].y*yscale);}

    };

  }

///Default traits class of \ref GraphToEps.

///

///\c G is the type of the underlying graph.

template<class G>

struct DefaultGraphToEpsTraits

{

  typedef G Graph;

    void changeTarget(Arc a, Node n) {

      Parent::changeTarget(a,n);

    }

    /// Change the source of \c a to \c n

    /// Change the source of \c a to \c n

    ///

    ///\note The <tt>InArcIt</tt>s referencing the changed arc remain

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeSource(Arc a, Node n) {

      Parent::changeSource(a,n);

    }

  /// Base class of maps.

  /// Base class of maps. It provides the necessary type definitions

  /// required by the map %concepts.

  template<typename K, typename V>

  class MapBase {

  public:

    typedef K Key;

    /// \brief The value type of the map.

    /// (The type of objects associated with the keys).

    typedef V Value;

  };

  /// Null map. (a.k.a. DoNothingMap)

  public:

    typedef typename Digraph::Node Value;

    typedef typename Digraph::Arc Key;

    /// \brief Constructor

    ///

    /// Constructor

    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}

    /// \brief The subscript operator.

    ///

    /// The subscript operator.

    /// \param arc The arc

    /// \return The source of the arc

    Value operator[](const Key& arc) const {

  public:

    typedef typename Digraph::Node Value;

    typedef typename Digraph::Arc Key;

    /// \brief Constructor

    ///

    /// Constructor

    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}

    /// \brief The subscript operator.

    ///

    /// The subscript operator.

    /// \param e The arc

    /// \return The target of the arc

    Value operator[](const Key& e) const {

  public:

    typedef typename Graph::Arc Value;

    typedef typename Graph::Edge Key;

    /// \brief Constructor

    ///

    /// Constructor

    explicit ForwardMap(const Graph& graph) : _graph(graph) {}

    /// \brief The subscript operator.

    ///

    /// The subscript operator.

    /// \param key An edge

    /// \return The "forward" directed arc view of edge

    Value operator[](const Key& key) const {

  public:

    typedef typename Graph::Arc Value;

    typedef typename Graph::Edge Key;

    /// \brief Constructor

    ///

    /// Constructor

    explicit BackwardMap(const Graph& graph) : _graph(graph) {}

    /// \brief The subscript operator.

    ///

    /// The subscript operator.

    /// \param key An edge

    /// \return The "backward" directed arc view of edge

    Value operator[](const Key& key) const {

    }

    /// \brief The length of the path.

    int length() const { return len; }

    /// \brief Return true when the path is empty.

    int empty() const { return len == 0; }

    void clear() {

      len = 0;

      if (arcs) delete[] arcs;

      arcs = 0;

    }

    /// \brief The first arc of the path.

    const Arc& front() const {

      ///Default constructor.

      ///To actually make a snapshot you must call save().

      ///

      Snapshot() : _graph(0) {}

      ///Constructor that immediately makes a snapshot

      ///This constructor immediately makes a snapshot of the digraph.

      Snapshot(SmartDigraph &graph) : _graph(&graph) {

        node_num=_graph->nodes.size();

        arc_num=_graph->arcs.size();

      }

      ///Make a snapshot.

      ///Make a snapshot of the digraph.

      ///

      ///This function can be called more than once. In case of a repeated

      ///call, the previous snapshot gets lost.

      void save(SmartDigraph &graph)

      {

        _graph=&graph;

        node_num=_graph->nodes.size();

        arc_num=_graph->arcs.size();

      }

      ///Undo the changes until a snapshot.

      ///Default constructor.

      ///To actually make a snapshot you must call save().

      ///

      Snapshot() : _graph(0) {}

      ///Constructor that immediately makes a snapshot

      ///This constructor immediately makes a snapshot of the digraph.

      Snapshot(SmartGraph &graph) {

        graph.saveSnapshot(*this);

      }

      ///Make a snapshot.

      ///Make a snapshot of the graph.

      ///

      ///This function can be called more than once. In case of a repeated

      ///call, the previous snapshot gets lost.

      void save(SmartGraph &graph)

      {

        graph.saveSnapshot(*this);

      }

      ///Undo the changes until a snapshot.

      ///Undo the changes until a snapshot created by save().

    ///\param run indicates whether or not the timer starts immediately.

    ///

    Timer(bool run=true) :_running(run) {_reset();}

    ///\name Control the state of the timer

    ///Basically a Timer can be either running or stopped,

    ///but it provides a bit finer control on the execution.

    ///of recursive functions.

    ///@{

    ///Reset and stop the time counters

    ///This function resets and stops the time counters

    ///\sa restart()

    void reset()

      t.stamp();

      return _running?t-start_time:start_time;

    }

    ///@}

  };

  ///Same as \ref Timer but prints a report on destruction.

  ///This example shows its usage.

  ///\code

  ///  void myAlg(ListGraph &g,int n)

  ///  {

  ///    TimeReport tr("Running time of myAlg: ");

  ///    ... //Here comes the algorithm

  ///

  ///\sa Timer

  ///\sa NoTimeReport

  class TimeReport : public Timer

  {

    std::string _title;

    std::ostream &_os;

  public:

    ///\param title This text will be printed before the ellapsed time.

    ///\param os The stream to print the report to.

    ///\param run Sets whether the timer should start immediately.

    TimeReport(std::string title,std::ostream &os=std::cerr,bool run=true)

      : Timer(run), _title(title), _os(os){}

    ~TimeReport()

    {

      _os << _title << *this << std::endl;

    }

  };

  ///\sa TimeReport

  ///

  class NoTimeReport

  {

  public:

    ///\e

    NoTimeReport(std::string,std::ostream &,bool) {}