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

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

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

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

#define LEMON_LIST_GRAPH_H

///\ingroup graphs

///\file

///\brief ListDigraph, ListGraph classes.

#include <lemon/bits/graph_extender.h>

#include <vector>

#include <list>

namespace lemon {

  class ListDigraphBase {

  protected:

    struct NodeT {

      int first_in, first_out;

      int prev, next;

    };

    struct ArcT {

      int target, source;

      int prev_in, prev_out;

      int next_in, next_out;

    };

    std::vector<NodeT> nodes;

    int first_node;

    int first_free_node;

    std::vector<ArcT> arcs;

    int first_free_arc;

  public:

    typedef ListDigraphBase Digraph;

    class Node {

      friend class ListDigraphBase;

    protected:

      int id;

      explicit Node(int pid) { id = pid;}

    public:

      Node() {}

      Node (Invalid) { id = -1; }

      bool operator==(const Node& node) const {return id == node.id;}

      bool operator!=(const Node& node) const {return id != node.id;}

      bool operator<(const Node& node) const {return id < node.id;}

    };

    class Arc {

      friend class ListDigraphBase;

    protected:

      int id;

      explicit Arc(int pid) { id = pid;}

    public:

      Arc() {}

      Arc (Invalid) { id = -1; }

      bool operator==(const Arc& arc) const {return id == arc.id;}

      bool operator!=(const Arc& arc) const {return id != arc.id;}

      bool operator<(const Arc& arc) const {return id < arc.id;}

    };

    ListDigraphBase()

      : nodes(), first_node(-1),

	first_free_node(-1), arcs(), first_free_arc(-1) {}

    int maxNodeId() const { return nodes.size()-1; } 

    int maxArcId() const { return arcs.size()-1; }

    Node source(Arc e) const { return Node(arcs[e.id].source); }

    Node target(Arc e) const { return Node(arcs[e.id].target); }

    void first(Node& node) const { 

      node.id = first_node;

    }

    void next(Node& node) const {

      node.id = nodes[node.id].next;

    }

    void first(Arc& arc) const { 

      int n;

      for(n = first_node; 

	  n!=-1 && nodes[n].first_in == -1; 

      arc.id = (n == -1) ? -1 : nodes[n].first_in;

    }

    void next(Arc& arc) const {

      if (arcs[arc.id].next_in != -1) {

	arc.id = arcs[arc.id].next_in;

      } else {

	int n;

	for(n = nodes[arcs[arc.id].target].next;

	arc.id = (n == -1) ? -1 : nodes[n].first_in;

      }      

    }

    void firstOut(Arc &e, const Node& v) const {

      e.id = nodes[v.id].first_out;

    }

    void nextOut(Arc &e) const {

      e.id=arcs[e.id].next_out;

    }

    void firstIn(Arc &e, const Node& v) const {

      e.id = nodes[v.id].first_in;

    }

    void nextIn(Arc &e) const {

      e.id=arcs[e.id].next_in;

    }

    static int id(Node v) { return v.id; }

    static int id(Arc e) { return e.id; }

    static Node nodeFromId(int id) { return Node(id);}

    static Arc arcFromId(int id) { return Arc(id);}

    bool valid(Node n) const { 

      return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 

	nodes[n.id].prev != -2;

    }

    bool valid(Arc a) const { 

      return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 

	arcs[a.id].prev_in != -2;

    }

    Node addNode() {     

      int n;

      if(first_free_node==-1) {

	n = nodes.size();

	nodes.push_back(NodeT());

      } else {

	n = first_free_node;

	first_free_node = nodes[n].next;

      }

      nodes[n].next = first_node;

      if(first_node != -1) nodes[first_node].prev = n;

      first_node = n;

      nodes[n].prev = -1;

      nodes[n].first_in = nodes[n].first_out = -1;

      return Node(n);

    }

    Arc addArc(Node u, Node v) {

      int n;      

      if (first_free_arc == -1) {

	n = arcs.size();

	arcs.push_back(ArcT());

      } else {

	n = first_free_arc;

	first_free_arc = arcs[n].next_in;

      }

      arcs[n].source = u.id; 

      arcs[n].target = v.id;

      arcs[n].next_out = nodes[u.id].first_out;

      if(nodes[u.id].first_out != -1) {

	arcs[nodes[u.id].first_out].prev_out = n;

      }

      arcs[n].next_in = nodes[v.id].first_in;

      if(nodes[v.id].first_in != -1) {

	arcs[nodes[v.id].first_in].prev_in = n;

      }

      arcs[n].prev_in = arcs[n].prev_out = -1;

      nodes[u.id].first_out = nodes[v.id].first_in = n;

      return Arc(n);

    }

    void erase(const Node& node) {

      int n = node.id;

      if(nodes[n].next != -1) {

	nodes[nodes[n].next].prev = nodes[n].prev;

      }

      if(nodes[n].prev != -1) {

	nodes[nodes[n].prev].next = nodes[n].next;

      } else {

	first_node = nodes[n].next;

      }

      nodes[n].next = first_free_node;

      first_free_node = n;

      nodes[n].prev = -2;

    }

    void erase(const Arc& arc) {

      int n = arc.id;