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_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:

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

  }

  Bezier2 after(double t) const

  {

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

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

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

  }

  Bezier2 revert() const { return Bezier2(p3,p2,p1);}

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

  Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }

  Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }

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

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

};

class Bezier3 : public BezierBase

{

public:

  Point p1,p2,p3,p4;

  Bezier3() {}

  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)

    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}

  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), 

			      p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}

  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),

			      p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}

  Point operator()(double t) const 

    {

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

      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+

	(3*t*t*(1-t))*p3+(t*t*t)*p4;

    }

  Bezier3 before(double t) const

    {

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

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

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

      Point a(conv(p,q,t));

      Point b(conv(q,r,t));

      Point c(conv(a,b,t));

      return Bezier3(p1,p,a,c);

    }

  Bezier3 after(double t) const

    {

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

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

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

      Point a(conv(p,q,t));

      Point b(conv(q,r,t));

      Point c(conv(a,b,t));

      return Bezier3(c,b,r,p4);

    }

  Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}

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

  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }

  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),

				  3.0*rot90(p3-p2),

				  3.0*rot90(p4-p3)); }

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

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

  template<class R,class F,class S,class D>

  R recSplit(F &_f,const S &_s,D _d) const 

  {

    const Point a=(p1+p2)/2;

    const Point b=(p2+p3)/2;

    const Point c=(p3+p4)/2;

    const Point d=(a+b)/2;

    const Point e=(b+c)/2;

    const Point f=(d+e)/2;

    R f1=_f(Bezier3(p1,a,d,e),_d);

    R f2=_f(Bezier3(e,d,c,p4),_d);

    return _s(f1,f2);

  }

};

} //END OF NAMESPACE dim2

} //END OF NAMESPACE lemon

#endif // LEMON_BEZIER_H

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

#define LEMON_BITS_TRAITS_H

#include <lemon/bits/utility.h>

///\file

///\brief Traits for graphs and maps

///

namespace lemon {

  template <typename _Graph, typename _Item>

  class ItemSetTraits {};

  template <typename Graph, typename Enable = void>

  struct NodeNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct NodeNotifierIndicator<

    Graph, 

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

  > { 

    typedef typename Graph::NodeNotifier Type;

  };

  template <typename _Graph>

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

  public:

    typedef _Graph Graph;

    typedef typename Graph::Node Item;

    typedef typename Graph::NodeIt ItemIt;

    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

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

    public:

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

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

      typedef typename Parent::Value Value;

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

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

	: Parent(_digraph, _value) {}

     };

  };

  template <typename Graph, typename Enable = void>

  struct ArcNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct ArcNotifierIndicator<

    Graph, 

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

  > { 

    typedef typename Graph::ArcNotifier Type;

  };

  template <typename _Graph>

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

  public:

    typedef _Graph Graph;

    typedef typename Graph::Arc Item;

    typedef typename Graph::ArcIt ItemIt;

    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

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

    public:

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

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

      typedef typename Parent::Value Value;

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

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

	: Parent(_digraph, _value) {}

    };

  };

  template <typename Graph, typename Enable = void>

  struct EdgeNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct EdgeNotifierIndicator<

    Graph, 

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

  > { 

    typedef typename Graph::EdgeNotifier Type;

  };

  template <typename _Graph>

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

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Item;

    typedef typename Graph::EdgeIt ItemIt;

    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

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

    public:

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

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

      typedef typename Parent::Value Value;

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

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

	: Parent(_digraph, _value) {}

    };

  };

  template <typename Map, typename Enable = void>

  struct MapTraits {

    typedef False ReferenceMapTag;

    typedef typename Map::Key Key;

    typedef typename Map::Value Value;

  };

  template <typename Map>

  struct MapTraits<

    Map, typename enable_if<typename Map::ReferenceMapTag, void>::type > 

  {

    typedef True ReferenceMapTag;

    typedef typename Map::Key Key;

    typedef typename Map::Value Value;

    typedef typename Map::ConstReference ConstReturnValue;

    typedef typename Map::Reference ReturnValue;

    typedef typename Map::ConstReference ConstReference; 

    typedef typename Map::Reference Reference;

 };

  template <typename MatrixMap, typename Enable = void>

  struct MatrixMapTraits {

    typedef False ReferenceMapTag;

    typedef typename MatrixMap::FirstKey FirstKey;

    typedef typename MatrixMap::SecondKey SecondKey;

    typedef typename MatrixMap::Value Value;

  };

  template <typename MatrixMap>

  struct MatrixMapTraits<

    MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, 

                                  void>::type > 

  {

    typedef True ReferenceMapTag;

    typedef typename MatrixMap::FirstKey FirstKey;

    typedef typename MatrixMap::SecondKey SecondKey;

    typedef typename MatrixMap::Value Value;

    typedef typename MatrixMap::ConstReference ConstReturnValue;

    typedef typename MatrixMap::Reference ReturnValue;

    typedef typename MatrixMap::ConstReference ConstReference; 

    typedef typename MatrixMap::Reference Reference;

 };

  // Indicators for the tags

  template <typename Graph, typename Enable = void>

  struct NodeNumTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct NodeNumTagIndicator<

    Graph, 

    typename enable_if<typename Graph::NodeNumTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct EdgeNumTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct EdgeNumTagIndicator<

    Graph, 

    typename enable_if<typename Graph::EdgeNumTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct FindEdgeTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct FindEdgeTagIndicator<

    Graph, 

    typename enable_if<typename Graph::FindEdgeTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct UndirectedTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct UndirectedTagIndicator<

    Graph, 

    typename enable_if<typename Graph::UndirectedTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct BuildTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct BuildTagIndicator<

    Graph, 

    typename enable_if<typename Graph::BuildTag, void>::type

  > {

    static const bool value = true;

  };

}

#endif

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

#define LEMON_DIJKSTRA_H

///\ingroup shortest_path

///\file

///\brief Dijkstra algorithm.

#include <lemon/list_graph.h>

#include <lemon/bin_heap.h>

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.h>

namespace lemon {

  /// \brief Default OperationTraits for the Dijkstra algorithm class.

  ///  

  /// It defines all computational operations and constants which are

  /// used in the Dijkstra algorithm.

  template <typename Value>

  struct DijkstraDefaultOperationTraits {

    /// \brief Gives back the zero value of the type.

    static Value zero() {

      return static_cast<Value>(0);

    }

    /// \brief Gives back the sum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return left + right;

    }

    /// \brief Gives back true only if the first value less than the second.

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.

  ///  

  /// It defines all computational operations and constants which are

  /// used in the Dijkstra algorithm for widest path computation.

  template <typename Value>

  struct DijkstraWidestPathOperationTraits {

    /// \brief Gives back the maximum value of the type.

    static Value zero() {

      return std::numeric_limits<Value>::max();

    }

    /// \brief Gives back the minimum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return std::min(left, right);

    }

    /// \brief Gives back true only if the first value less than the second.

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  ///Default traits class of Dijkstra class.

  ///Default traits class of Dijkstra class.

  ///\tparam GR Digraph type.

  ///\tparam LM Type of length map.

  template<class GR, class LM>

  struct DijkstraDefaultTraits

  {

    ///The digraph type the algorithm runs on. 

    typedef GR Digraph;

    ///The type of the map that stores the arc lengths.

    ///The type of the map that stores the arc lengths.

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

    typedef LM LengthMap;

    //The type of the length of the arcs.

    typedef typename LM::Value Value;

    /// Operation traits for Dijkstra algorithm.

    /// It defines the used operation by the algorithm.

    /// \see DijkstraDefaultOperationTraits

    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;

    /// The cross reference type used by heap.

    /// The cross reference type used by heap.

    /// Usually it is \c Digraph::NodeMap<int>.

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

    ///Instantiates a HeapCrossRef.

    ///This function instantiates a \c HeapCrossRef. 

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

    /// HeapCrossRef.

    static HeapCrossRef *createHeapCrossRef(const GR &G) 

    {

      return new HeapCrossRef(G);

    }

    ///The heap type used by Dijkstra algorithm.

    ///The heap type used by Dijkstra algorithm.

    ///

    ///\sa BinHeap

    ///\sa Dijkstra

    typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;

    static Heap *createHeap(HeapCrossRef& R) 

    {

      return new Heap(R);

    }

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

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

    ///\todo The digraph alone may be insufficient for the initialization

    static PredMap *createPredMap(const GR &G) 

    {

      return new PredMap(G);

    }

    ///The type of the map that stores whether a nodes is processed.

    ///The type of the map that stores whether a nodes is processed.

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

    ///By default it is a NullMap.

    ///\todo If it is set to a real map,

    ///Dijkstra::processed() should read this.

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

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

    ///we would like to define the \c 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 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<typename LM::Value> 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);

    }

  };

  ///%Dijkstra algorithm class.

  /// \ingroup shortest_path

  ///This class provides an efficient implementation of %Dijkstra algorithm.

  ///The arc lengths are passed to the algorithm using a

  ///\ref concepts::ReadMap "ReadMap",

  ///so it is easy to change it to any kind of length.

  ///

  ///The type of the length is determined by the

  ///\ref concepts::ReadMap::Value "Value" of the length map.

  ///

  ///It is also possible to change the underlying priority heap.

  ///

  ///\tparam GR The digraph type the algorithm runs on. The default value

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

  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.

  ///\tparam LM This read-only ArcMap determines the lengths of the

  ///arcs. It is read once for each arc, so the map may involve in

  ///relatively time consuming process to compute the arc length if

  ///it is necessary. The default map type is \ref

  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value

  ///of LM is not used directly by Dijkstra, it is only passed to \ref

  ///DijkstraDefaultTraits.  

  ///\tparam TR Traits class to set

  ///various data types used by the algorithm.  The default traits

  ///class is \ref DijkstraDefaultTraits

  ///"DijkstraDefaultTraits<GR,LM>".  See \ref

  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits

  ///class.

#ifdef DOXYGEN

  template <typename GR, typename LM, typename TR>

#else

  template <typename GR=ListDigraph,

	    typename LM=typename GR::template ArcMap<int>,

	    typename TR=DijkstraDefaultTraits<GR,LM> >

    os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def\n";

    //x y r

    os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def\n";

    //x y r

    os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"

       << "      2 index 1 index sub 2 index 2 index add lineto\n"

       << "      2 index 1 index sub 2 index 2 index sub lineto\n"

       << "      2 index 1 index add 2 index 2 index sub lineto\n"

       << "      closepath pop pop pop} bind def\n";

    //x y r

    os << "/di { newpath 2 index 1 index add 2 index moveto\n"

       << "      2 index             2 index 2 index add lineto\n"

       << "      2 index 1 index sub 2 index             lineto\n"

       << "      2 index             2 index 2 index sub lineto\n"

       << "      closepath pop pop pop} bind def\n";

    // x y r cr cg cb

    os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"

       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"

       << "   } bind def\n";

    os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"

       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"

       << "   } bind def\n";

    os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"

       << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"

       << "   } bind def\n";

    os << "/nfemale { 0 0 0 setrgbcolor 3 index "

       << _nodeBorderQuotient/(1+_nodeBorderQuotient)

       << " 1.5 mul mul setlinewidth\n"

       << "  newpath 5 index 5 index moveto "

       << "5 index 5 index 5 index 3.01 mul sub\n"

       << "  lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub moveto\n"

       << "  5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto stroke\n"

       << "  5 index 5 index 5 index c fill\n"

       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"

       << "  } bind def\n";

    os << "/nmale {\n"

       << "  0 0 0 setrgbcolor 3 index "

       << _nodeBorderQuotient/(1+_nodeBorderQuotient)

       <<" 1.5 mul mul setlinewidth\n"

       << "  newpath 5 index 5 index moveto\n"

       << "  5 index 4 index 1 mul 1.5 mul add\n"

       << "  5 index 5 index 3 sqrt 1.5 mul mul add\n"

       << "  1 index 1 index lineto\n"

       << "  1 index 1 index 7 index sub moveto\n"

       << "  1 index 1 index lineto\n"

       << "  exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub lineto\n"

       << "  stroke\n"

       << "  5 index 5 index 5 index c fill\n"

       << "  setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"

       << "  } bind def\n";

    os << "/arrl " << _arrowLength << " def\n";

    os << "/arrw " << _arrowWidth << " def\n";

    // l dx_norm dy_norm

    os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";

    //len w dx_norm dy_norm x1 y1 cr cg cb

    os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def\n"

       << "       /w exch def /len exch def\n"

      //	 << "       0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"

       << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"

       << "       len w sub arrl sub dx dy lrl\n"

       << "       arrw dy dx neg lrl\n"

       << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"

       << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"

       << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"

       << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"

       << "       arrw dy dx neg lrl\n"

       << "       len w sub arrl sub neg dx dy lrl\n"

       << "       closepath fill } bind def\n";

    os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"

       << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";

    os << "\ngsave\n";

    if(_scaleToA4)

      if(bb.height()>bb.width()) {

	double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),

		  (A4WIDTH-2*A4BORDER)/bb.width());

	os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '

	   << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER

	   << " translate\n"

	   << sc << " dup scale\n"

	   << -bb.left() << ' ' << -bb.bottom() << " translate\n";

      }

      else {

	//\todo Verify centering

	double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),

		  (A4WIDTH-2*A4BORDER)/bb.height());

	os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '

	   << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER 

	   << " translate\n"

	   << sc << " dup scale\n90 rotate\n"

	   << -bb.left() << ' ' << -bb.top() << " translate\n";	

	}

    else if(_scale!=1.0) os << _scale << " dup scale\n";

    if(_showArcs) {

      os << "%Arcs:\ngsave\n";      

      if(_enableParallel) {

	std::vector<Arc> el;

	for(ArcIt e(g);e!=INVALID;++e)

	  if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0

	     &&g.source(e)!=g.target(e))

	    el.push_back(e);

	std::sort(el.begin(),el.end(),arcLess(g));

	typename std::vector<Arc>::iterator j;

	for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {

	  for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;

	  double sw=0;

	  for(typename std::vector<Arc>::iterator e=i;e!=j;++e)

	    sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist;

	  sw-=_parArcDist;

	  sw/=-2.0;

	  dim2::Point<double>

	    dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);

	  double l=std::sqrt(dvec.normSquare()); 

	  //\todo better 'epsilon' would be nice here.

	  dim2::Point<double> d(dvec/std::max(l,EPSILON));

 	  dim2::Point<double> m;

// 	  m=dim2::Point<double>(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0;

//  	  m=dim2::Point<double>(mycoords[g.source(*i)])+

// 	    dvec*(double(_nodeSizes[g.source(*i)])/

// 	       (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));

 	  m=dim2::Point<double>(mycoords[g.source(*i)])+

	    d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;

	  for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {

	    sw+=_arcWidths[*e]*_arcWidthScale/2.0;

	    dim2::Point<double> mm=m+rot90(d)*sw/.75;

	    if(_drawArrows) {

	      int node_shape;

	      dim2::Point<double> s=mycoords[g.source(*e)];

	      dim2::Point<double> t=mycoords[g.target(*e)];

	      double rn=_nodeSizes[g.target(*e)]*_nodeScale;

	      node_shape=_nodeShapes[g.target(*e)];

	      dim2::Bezier3 bez(s,mm,mm,t);

	      double t1=0,t2=1;

	      for(int ii=0;ii<INTERPOL_PREC;++ii)

		if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;

		else t1=(t1+t2)/2;

	      dim2::Point<double> apoint=bez((t1+t2)/2);

	      rn = _arrowLength+_arcWidths[*e]*_arcWidthScale;

	      rn*=rn;

	      t2=(t1+t2)/2;t1=0;

	      for(int ii=0;ii<INTERPOL_PREC;++ii)

		if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;

		else t2=(t1+t2)/2;

	      dim2::Point<double> linend=bez((t1+t2)/2);	      

	      bez=bez.before((t1+t2)/2);

// 	      rn=_nodeSizes[g.source(*e)]*_nodeScale;

// 	      node_shape=_nodeShapes[g.source(*e)];

// 	      t1=0;t2=1;

// 	      for(int i=0;i<INTERPOL_PREC;++i)

// 		if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t1=(t1+t2)/2;

// 		else t2=(t1+t2)/2;

// 	      bez=bez.after((t1+t2)/2);

	      os << _arcWidths[*e]*_arcWidthScale << " setlinewidth "

		 << _arcColors[*e].red() << ' '

		 << _arcColors[*e].green() << ' '

		 << _arcColors[*e].blue() << " setrgbcolor newpath\n"

		 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"

		 << bez.p2.x << ' ' << bez.p2.y << ' '

		 << bez.p3.x << ' ' << bez.p3.y << ' '

		 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";

	      dim2::Point<double> dd(rot90(linend-apoint));

	      dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/

		std::sqrt(dd.normSquare());

	      os << "newpath " << psOut(apoint) << " moveto "

		 << psOut(linend+dd) << " lineto "

		 << psOut(linend-dd) << " lineto closepath fill\n";

	    }

	    else {

	      os << mycoords[g.source(*e)].x << ' '

		 << mycoords[g.source(*e)].y << ' '

		 << mm.x << ' ' << mm.y << ' '

		 << mycoords[g.target(*e)].x << ' '

		 << mycoords[g.target(*e)].y << ' '

		 << _arcColors[*e].red() << ' '

		 << _arcColors[*e].green() << ' '

		 << _arcColors[*e].blue() << ' '

		 << _arcWidths[*e]*_arcWidthScale << " lb\n";

	    }

	    sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist;

	  }

	}

      }

      else for(ArcIt e(g);e!=INVALID;++e)

	if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0

	  if(_drawArrows) {

	    dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);

	    double rn=_nodeSizes[g.target(e)]*_nodeScale;

	    int node_shape=_nodeShapes[g.target(e)];

	    double t1=0,t2=1;

	    for(int i=0;i<INTERPOL_PREC;++i)

	      if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;

	      else t2=(t1+t2)/2;

	    double l=std::sqrt(d.normSquare());

	    d/=l;

	    os << l*(1-(t1+t2)/2) << ' '

	       << _arcWidths[e]*_arcWidthScale << ' '

	       << d.x << ' ' << d.y << ' '

	       << mycoords[g.source(e)].x << ' '

	       << mycoords[g.source(e)].y << ' '

	       << _arcColors[e].red() << ' '

	       << _arcColors[e].green() << ' '

	       << _arcColors[e].blue() << " arr\n";

	  else os << mycoords[g.source(e)].x << ' '

		  << mycoords[g.source(e)].y << ' '

		  << mycoords[g.target(e)].x << ' '

		  << mycoords[g.target(e)].y << ' '

		  << _arcColors[e].red() << ' '

		  << _arcColors[e].green() << ' '

		  << _arcColors[e].blue() << ' '

		  << _arcWidths[e]*_arcWidthScale << " l\n";

      os << "grestore\n";

    }

    if(_showNodes) {

      os << "%Nodes:\ngsave\n";

      for(NodeIt n(g);n!=INVALID;++n) {

	os << mycoords[n].x << ' ' << mycoords[n].y << ' '

	   << _nodeSizes[n]*_nodeScale << ' '

	   << _nodeColors[n].red() << ' '

	   << _nodeColors[n].green() << ' '

	   << _nodeColors[n].blue() << ' ';

	switch(_nodeShapes[n]) {

	case CIRCLE:

	  os<< "nc";break;

	case SQUARE:

	  os<< "nsq";break;

	case DIAMOND:

	  os<< "ndi";break;

	case MALE:

	  os<< "nmale";break;

	case FEMALE:

	  os<< "nfemale";break;

	}

	os<<'\n';

      }

      os << "grestore\n";

    }

    if(_showNodeText) {

      os << "%Node texts:\ngsave\n";

      os << "/fosi " << _nodeTextSize << " def\n";

      os << "(Helvetica) findfont fosi scalefont setfont\n";

      for(NodeIt n(g);n!=INVALID;++n) {

	switch(_nodeTextColorType) {

	case DIST_COL:

	  os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n";

	  break;

	case DIST_BW:

	  os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n";

	  break;

	case CUST_COL:

	  os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n";

	  break;

	default:

	  os << "0 0 0 setrgbcolor\n";

	}

	os << mycoords[n].x << ' ' << mycoords[n].y

	   << " (" << _nodeTexts[n] << ") cshow\n";

      }

      os << "grestore\n";

    }

    if(_showNodePsText) {

      os << "%Node PS blocks:\ngsave\n";

      for(NodeIt n(g);n!=INVALID;++n)

	os << mycoords[n].x << ' ' << mycoords[n].y

	   << " moveto\n" << _nodePsTexts[n] << "\n";

      os << "grestore\n";

    }

    os << "grestore\nshowpage\n";

    //CleanUp:

    if(_pleaseRemoveOsStream) {delete &os;}

  }

  ///\name Aliases

  ///These are just some aliases to other parameter setting functions.

  ///@{

  ///An alias for arcWidths()

  ///An alias for arcWidths()

  ///

  template<class X> GraphToEps<ArcWidthsTraits<X> > edgeWidths(const X &x)

  {

    return arcWidths(x);

  }

  ///An alias for arcColors()

  ///An alias for arcColors()

  ///

  template<class X> GraphToEps<ArcColorsTraits<X> >

  edgeColors(const X &x)

  {

    return arcColors(x);

  }

  ///An alias for arcWidthScale()

  ///An alias for arcWidthScale()

  ///

  GraphToEps<T> &edgeWidthScale(double d) {return arcWidthScale(d);}

  ///An alias for autoArcWidthScale()

  ///An alias for autoArcWidthScale()

  ///

  GraphToEps<T> &autoEdgeWidthScale(bool b=true)

  {

    return autoArcWidthScale(b);

  }

  ///An alias for absoluteArcWidths()

  ///An alias for absoluteArcWidths()

  ///

  GraphToEps<T> &absoluteEdgeWidths(bool b=true)

  {

    return absoluteArcWidths(b);

  }

  ///An alias for parArcDist()

  ///An alias for parArcDist()

  ///

  GraphToEps<T> &parEdgeDist(double d) {return parArcDist(d);}

  ///An alias for hideArcs()

  ///An alias for hideArcs()

  ///

  GraphToEps<T> &hideEdges(bool b=true) {return hideArcs(b);}

  ///@}

};

template<class T>

const int GraphToEps<T>::INTERPOL_PREC = 20;

template<class T>

const double GraphToEps<T>::A4HEIGHT = 841.8897637795276;

template<class T>

const double GraphToEps<T>::A4WIDTH  = 595.275590551181;

template<class T>

const double GraphToEps<T>::A4BORDER = 15;

///Generates an EPS file from a graph

///\ingroup eps_io

///Generates an EPS file from a graph.

///\param g is a reference to the graph to be printed

///\param os is a reference to the output stream.

///By default it is <tt>std::cout</tt>

///

///This function also has a lot of

///\ref named-templ-func-param "named parameters",

///they are declared as the members of class \ref GraphToEps. The following

///example shows how to use these parameters.

///\code

/// graphToEps(g,os).scale(10).coords(coords)

///              .nodeScale(2).nodeSizes(sizes)

///              .arcWidthScale(.4).run();

///\endcode

///\warning Don't forget to put the \ref GraphToEps::run() "run()"

///to the end of the parameter list.

///\sa GraphToEps

///\sa graphToEps(G &g, const char *file_name)

template<class G>

GraphToEps<DefaultGraphToEpsTraits<G> > 

graphToEps(G &g, std::ostream& os=std::cout)

{

  return 

    GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));

}

///Generates an EPS file from a graph

///\ingroup eps_io

///This function does the same as

///\ref graphToEps(G &g,std::ostream& os)

///but it writes its output into the file \c file_name

///instead of a stream.

///\sa graphToEps(G &g, std::ostream& os)

template<class G>

GraphToEps<DefaultGraphToEpsTraits<G> > 

graphToEps(G &g,const char *file_name)

{

  return GraphToEps<DefaultGraphToEpsTraits<G> >

    (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name),true));

}

///Generates an EPS file from a graph

///\ingroup eps_io

///This function does the same as

///\ref graphToEps(G &g,std::ostream& os)

///but it writes its output into the file \c file_name

///instead of a stream.

///\sa graphToEps(G &g, std::ostream& os)

template<class G>

GraphToEps<DefaultGraphToEpsTraits<G> > 

graphToEps(G &g,const std::string& file_name)

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