src/lemon/graph_to_eps.h
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 1202 da44ee225dad
child 1287 984723507b86
permissions -rw-r--r--
Completions.
     1 /* -*- C++ -*-
     2  * src/lemon/graph_to_eps.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_GRAPH_TO_EPS_H
    18 #define LEMON_GRAPH_TO_EPS_H
    19 
    20 #include <sys/time.h>
    21 #include <time.h>
    22 
    23 #include<iostream>
    24 #include<fstream>
    25 #include<sstream>
    26 #include<algorithm>
    27 #include<vector>
    28 
    29 #include<lemon/invalid.h>
    30 #include<lemon/xy.h>
    31 #include<lemon/maps.h>
    32 #include<lemon/bezier.h>
    33 
    34 ///\ingroup misc
    35 ///\file
    36 ///\brief Simple graph drawer
    37 ///
    38 ///\author Alpar Juttner
    39 
    40 namespace lemon {
    41 
    42 ///Data structure representing RGB colors.
    43 
    44 ///Data structure representing RGB colors.
    45 ///\ingroup misc
    46 class Color
    47 {
    48   double _r,_g,_b;
    49 public:
    50   ///Default constructor
    51   Color() {}
    52   ///Constructor
    53   Color(double r,double g,double b) :_r(r),_g(g),_b(b) {};
    54   ///Returns the red component
    55 
    56   ///\todo \c red() could be a better name...
    57   double getR() const {return _r;}
    58   ///Returns the green component
    59   double getG() const {return _g;}
    60   ///Returns the blue component
    61   double getB() const {return _b;}
    62   ///Set the color components
    63   void set(double r,double g,double b) { _r=r;_g=g;_b=b; };
    64 };
    65 
    66 ///Maps <tt>int</tt>s to different \ref Color "Color"s
    67 
    68 ///This map assing one of the predefined \ref Color "Color"s
    69 ///to each <tt>int</tt>. It is possible to change the colors as well as their
    70 ///number. The integer range is cyclically mapped to the provided set of colors.
    71 ///
    72 ///This is a true \ref concept::ReferenceMap "reference map", so you can also
    73 ///change the actual colors.
    74 
    75 class ColorSet : public MapBase<int,Color>
    76 {
    77   std::vector<Color> colors;
    78 public:
    79   ///Constructor
    80 
    81   ///Constructor
    82   ///\param have_white indicates wheter white is
    83   ///amongst the provided color (\c true) or not (\c false). If it is true,
    84   ///white will be assigned to \c 0.
    85   ///\param num the number of the allocated colors. If it is \c 0
    86   ///the default color configuration is set up (26 color plus the while).
    87   ///If \c num is less then 26/27 then the default color list is cut. Otherwise
    88   ///the color list is filled repeatedly with the default color list.
    89   ColorSet(bool have_white=false,int num=0)
    90   {
    91     do {
    92       if(have_white) colors.push_back(Color(1,1,1));
    93 
    94       colors.push_back(Color(0,0,0));
    95       colors.push_back(Color(1,0,0));
    96       colors.push_back(Color(0,1,0));
    97       colors.push_back(Color(0,0,1));
    98       colors.push_back(Color(1,1,0));
    99       colors.push_back(Color(1,0,1));
   100       colors.push_back(Color(0,1,1));
   101       
   102       colors.push_back(Color(.5,0,0));
   103       colors.push_back(Color(0,.5,0));
   104       colors.push_back(Color(0,0,.5));
   105       colors.push_back(Color(.5,.5,0));
   106       colors.push_back(Color(.5,0,.5));
   107       colors.push_back(Color(0,.5,.5));
   108       
   109       colors.push_back(Color(.5,.5,.5));
   110       colors.push_back(Color(1,.5,.5));
   111       colors.push_back(Color(.5,1,.5));
   112       colors.push_back(Color(.5,.5,1));
   113       colors.push_back(Color(1,1,.5));
   114       colors.push_back(Color(1,.5,1));
   115       colors.push_back(Color(.5,1,1));
   116       
   117       colors.push_back(Color(1,.5,0));
   118       colors.push_back(Color(.5,1,0));
   119       colors.push_back(Color(1,0,.5));
   120       colors.push_back(Color(0,1,.5));
   121       colors.push_back(Color(0,.5,1));
   122       colors.push_back(Color(.5,0,1));
   123     } while(int(colors.size())<num);
   124     //    colors.push_back(Color(1,1,1));
   125     if(num>0) colors.resize(num);
   126   }
   127   ///\e
   128   Color &operator[](int i)
   129   {
   130     return colors[i%colors.size()];
   131   }
   132   ///\e
   133   const Color &operator[](int i) const
   134   {
   135     return colors[i%colors.size()];
   136   }
   137   ///\e
   138   void set(int i,const Color &c)
   139   {
   140     colors[i%colors.size()]=c;
   141   }
   142   ///Sets the number of the exiting colors.
   143   void resize(int s) { colors.resize(s);}
   144   ///Returns the munber of the existing colors.
   145   std::size_t size() { return colors.size();}
   146 };
   147 
   148 ///Returns a visible distinct \ref Color
   149 
   150 ///Returns a \ref Color which is as different from the given parameter
   151 ///as it is possible.
   152 inline Color distantColor(const Color &c) 
   153 {
   154   return Color(c.getR()<.5?1:0,c.getG()<.5?1:0,c.getB()<.5?1:0);
   155 }
   156 ///Returns black for light colors and white for the dark ones.
   157 
   158 ///Returns black for light colors and white for the dark ones.
   159 ///\todo weighted average would be better
   160 inline Color distantBW(const Color &c){
   161   double v=(.2125*c.getR()+.7154*c.getG()+.0721*c.getB())<.5?1:0;
   162   return Color(v,v,v);
   163 }
   164 
   165 ///Default traits class of \ref GraphToEps
   166 
   167 ///Default traits class of \ref GraphToEps
   168 ///
   169 ///\c G is the type of the underlying graph.
   170 template<class G>
   171 struct DefaultGraphToEpsTraits
   172 {
   173   typedef G Graph;
   174   typedef typename Graph::Node Node;
   175   typedef typename Graph::NodeIt NodeIt;
   176   typedef typename Graph::Edge Edge;
   177   typedef typename Graph::EdgeIt EdgeIt;
   178   typedef typename Graph::InEdgeIt InEdgeIt;
   179   typedef typename Graph::OutEdgeIt OutEdgeIt;
   180   
   181 
   182   const Graph &g;
   183 
   184   std::ostream& os;
   185   
   186   ConstMap<typename Graph::Node,xy<double> > _coords;
   187   ConstMap<typename Graph::Node,double > _nodeSizes;
   188   ConstMap<typename Graph::Node,int > _nodeShapes;
   189 
   190   ConstMap<typename Graph::Node,Color > _nodeColors;
   191   ConstMap<typename Graph::Edge,Color > _edgeColors;
   192 
   193   ConstMap<typename Graph::Edge,double > _edgeWidths;
   194 
   195   double _edgeWidthScale;
   196   
   197   double _nodeScale;
   198   double _xBorder, _yBorder;
   199   double _scale;
   200   double _nodeBorderQuotient;
   201   
   202   bool _drawArrows;
   203   double _arrowLength, _arrowWidth;
   204   
   205   bool _showNodes, _showEdges;
   206 
   207   bool _enableParallel;
   208   double _parEdgeDist;
   209 
   210   bool _showNodeText;
   211   ConstMap<typename Graph::Node,bool > _nodeTexts;  
   212   double _nodeTextSize;
   213 
   214   bool _showNodePsText;
   215   ConstMap<typename Graph::Node,bool > _nodePsTexts;  
   216   char *_nodePsTextsPreamble;
   217   
   218   bool _undir;
   219   bool _pleaseRemoveOsStream;
   220 
   221   bool _scaleToA4;
   222 
   223   std::string _title;
   224   std::string _copyright;
   225 
   226   enum NodeTextColorType 
   227     { DIST_COL=0, DIST_BW=1, CUST_COL=2, SAME_COL=3 } _nodeTextColorType;
   228   ConstMap<typename Graph::Node,Color > _nodeTextColors;
   229 
   230   ///Constructor
   231 
   232   ///Constructor
   233   ///\param _g is a reference to the graph to be printed
   234   ///\param _os is a reference to the output stream.
   235   ///\param _os is a reference to the output stream.
   236   ///\param _pros If it is \c true, then the \c ostream referenced by \c _os
   237   ///will be explicitly deallocated by the destructor.
   238   ///By default it is <tt>std::cout</tt>
   239   DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
   240 			  bool _pros=false) :
   241     g(_g), os(_os),
   242     _coords(xy<double>(1,1)), _nodeSizes(1.0), _nodeShapes(0),
   243     _nodeColors(Color(1,1,1)), _edgeColors(Color(0,0,0)),
   244     _edgeWidths(1), _edgeWidthScale(0.3),
   245     _nodeScale(1.0), _xBorder(10), _yBorder(10), _scale(1.0),
   246     _nodeBorderQuotient(.1),
   247     _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),
   248     _showNodes(true), _showEdges(true),
   249     _enableParallel(false), _parEdgeDist(1),
   250     _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
   251     _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
   252     _undir(false),
   253     _pleaseRemoveOsStream(_pros), _scaleToA4(false),
   254     _nodeTextColorType(SAME_COL), _nodeTextColors(Color(0,0,0))
   255   {}
   256 };
   257 
   258 ///Helper class to implement the named parameters of \ref graphToEps()
   259 
   260 ///Helper class to implement the named parameters of \ref graphToEps()
   261 ///\todo Is 'helper class' a good name for this?
   262 ///
   263 ///\todo Follow PostScript's DSC.
   264 /// Use own dictionary.
   265 ///\todo Useful new features.
   266 /// - Linestyles: dotted, dashed etc.
   267 /// - A second color and percent value for the lines.
   268 template<class T> class GraphToEps : public T 
   269 {
   270   // Can't believe it is required by the C++ standard
   271   using T::g;
   272   using T::os;
   273 
   274   using T::_coords;
   275   using T::_nodeSizes;
   276   using T::_nodeShapes;
   277   using T::_nodeColors;
   278   using T::_edgeColors;
   279   using T::_edgeWidths;
   280 
   281   using T::_edgeWidthScale;
   282   using T::_nodeScale;
   283   using T::_xBorder;
   284   using T::_yBorder;
   285   using T::_scale;
   286   using T::_nodeBorderQuotient;
   287   
   288   using T::_drawArrows;
   289   using T::_arrowLength;
   290   using T::_arrowWidth;
   291   
   292   using T::_showNodes;
   293   using T::_showEdges;
   294 
   295   using T::_enableParallel;
   296   using T::_parEdgeDist;
   297 
   298   using T::_showNodeText;
   299   using T::_nodeTexts;  
   300   using T::_nodeTextSize;
   301 
   302   using T::_showNodePsText;
   303   using T::_nodePsTexts;  
   304   using T::_nodePsTextsPreamble;
   305   
   306   using T::_undir;
   307   using T::_pleaseRemoveOsStream;
   308 
   309   using T::_scaleToA4;
   310 
   311   using T::_title;
   312   using T::_copyright;
   313 
   314   using T::NodeTextColorType;
   315   using T::CUST_COL;
   316   using T::DIST_COL;
   317   using T::DIST_BW;
   318   using T::_nodeTextColorType;
   319   using T::_nodeTextColors;
   320   // dradnats ++C eht yb deriuqer si ti eveileb t'naC
   321 
   322   typedef typename T::Graph Graph;
   323   typedef typename Graph::Node Node;
   324   typedef typename Graph::NodeIt NodeIt;
   325   typedef typename Graph::Edge Edge;
   326   typedef typename Graph::EdgeIt EdgeIt;
   327   typedef typename Graph::InEdgeIt InEdgeIt;
   328   typedef typename Graph::OutEdgeIt OutEdgeIt;
   329 
   330   static const int INTERPOL_PREC=20;
   331   static const double A4HEIGHT = 841.8897637795276;
   332   static const double A4WIDTH  = 595.275590551181;
   333   static const double A4BORDER = 15;
   334 
   335   bool dontPrint;
   336 
   337 public:
   338   ///Node shapes
   339 
   340   ///Node shapes
   341   ///
   342   enum NodeShapes { 
   343     /// = 0
   344     ///\image html nodeshape_0.png
   345     ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm
   346     CIRCLE=0, 
   347     /// = 1
   348     ///\image html nodeshape_1.png
   349     ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm
   350     ///
   351     SQUARE=1, 
   352     /// = 2
   353     ///\image html nodeshape_2.png
   354     ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm
   355     ///
   356     DIAMOND=2
   357   };
   358 
   359 private:
   360   class edgeLess {
   361     const Graph &g;
   362   public:
   363     edgeLess(const Graph &_g) : g(_g) {}
   364     bool operator()(Edge a,Edge b) const 
   365     {
   366       Node ai=min(g.source(a),g.target(a));
   367       Node aa=max(g.source(a),g.target(a));
   368       Node bi=min(g.source(b),g.target(b));
   369       Node ba=max(g.source(b),g.target(b));
   370       return ai<bi ||
   371 	(ai==bi && (aa < ba || 
   372 		    (aa==ba && ai==g.source(a) && bi==g.target(b))));
   373     }
   374   };
   375   bool isParallel(Edge e,Edge f) const
   376   {
   377     return (g.source(e)==g.source(f)&&
   378 	    g.target(e)==g.target(f)) ||
   379       (g.source(e)==g.target(f)&&
   380        g.target(e)==g.source(f));
   381   }
   382   template<class TT>
   383   static std::string psOut(const xy<TT> &p) 
   384     {
   385       std::ostringstream os;	
   386       os << p.x << ' ' << p.y;
   387       return os.str();
   388     }
   389   static std::string psOut(const Color &c) 
   390     {
   391       std::ostringstream os;	
   392       os << c.getR() << ' ' << c.getG() << ' ' << c.getB();
   393       return os.str();
   394     }
   395   
   396 public:
   397   GraphToEps(const T &t) : T(t), dontPrint(false) {};
   398   
   399   template<class X> struct CoordsTraits : public T {
   400     const X &_coords;
   401     CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}
   402   };
   403   ///Sets the map of the node coordinates
   404 
   405   ///Sets the map of the node coordinates.
   406   ///\param x must be a node map with xy<double> or \ref xy "xy<int>" values. 
   407   template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
   408     dontPrint=true;
   409     return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
   410   }
   411   template<class X> struct NodeSizesTraits : public T {
   412     const X &_nodeSizes;
   413     NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}
   414   };
   415   ///Sets the map of the node sizes
   416 
   417   ///Sets the map of the node sizes
   418   ///\param x must be a node map with \c double (or convertible) values. 
   419   template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)
   420   {
   421     dontPrint=true;
   422     return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));
   423   }
   424   template<class X> struct NodeShapesTraits : public T {
   425     const X &_nodeShapes;
   426     NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}
   427   };
   428   ///Sets the map of the node shapes
   429 
   430   ///Sets the map of the node shapes.
   431   ///The availabe shape values
   432   ///can be found in \ref NodeShapes "enum NodeShapes".
   433   ///\param x must be a node map with \c int (or convertible) values. 
   434   ///\sa NodeShapes
   435   template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)
   436   {
   437     dontPrint=true;
   438     return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));
   439   }
   440   template<class X> struct NodeTextsTraits : public T {
   441     const X &_nodeTexts;
   442     NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}
   443   };
   444   ///Sets the text printed on the nodes
   445 
   446   ///Sets the text printed on the nodes
   447   ///\param x must be a node map with type that can be pushed to a standard
   448   ///ostream. 
   449   template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)
   450   {
   451     dontPrint=true;
   452     _showNodeText=true;
   453     return GraphToEps<NodeTextsTraits<X> >(NodeTextsTraits<X>(*this,x));
   454   }
   455   template<class X> struct NodePsTextsTraits : public T {
   456     const X &_nodePsTexts;
   457     NodePsTextsTraits(const T &t,const X &x) : T(t), _nodePsTexts(x) {}
   458   };
   459   ///Inserts a PostScript block to the nodes
   460 
   461   ///With this command it is possible to insert a verbatim PostScript
   462   ///block to the nodes.
   463   ///The PS current point will be moved to the centre of the node before
   464   ///the PostScript block inserted.
   465   ///
   466   ///Before and after the block a newline character is inserted to you
   467   ///don't have to bother with the separators.
   468   ///
   469   ///\param x must be a node map with type that can be pushed to a standard
   470   ///ostream.
   471   ///
   472   ///\sa nodePsTextsPreamble()
   473   ///\todo Offer the choise not to move to the centre but pass the coordinates
   474   ///to the Postscript block inserted.
   475   template<class X> GraphToEps<NodePsTextsTraits<X> > nodePsTexts(const X &x)
   476   {
   477     dontPrint=true;
   478     _showNodePsText=true;
   479     return GraphToEps<NodePsTextsTraits<X> >(NodePsTextsTraits<X>(*this,x));
   480   }
   481   template<class X> struct EdgeWidthsTraits : public T {
   482     const X &_edgeWidths;
   483     EdgeWidthsTraits(const T &t,const X &x) : T(t), _edgeWidths(x) {}
   484   };
   485   ///Sets the map of the edge widths
   486 
   487   ///Sets the map of the edge widths
   488   ///\param x must be a edge map with \c double (or convertible) values. 
   489   template<class X> GraphToEps<EdgeWidthsTraits<X> > edgeWidths(const X &x)
   490   {
   491     dontPrint=true;
   492     return GraphToEps<EdgeWidthsTraits<X> >(EdgeWidthsTraits<X>(*this,x));
   493   }
   494 
   495   template<class X> struct NodeColorsTraits : public T {
   496     const X &_nodeColors;
   497     NodeColorsTraits(const T &t,const X &x) : T(t), _nodeColors(x) {}
   498   };
   499   ///Sets the map of the node colors
   500 
   501   ///Sets the map of the node colors
   502   ///\param x must be a node map with \ref Color values. 
   503   template<class X> GraphToEps<NodeColorsTraits<X> >
   504   nodeColors(const X &x)
   505   {
   506     dontPrint=true;
   507     return GraphToEps<NodeColorsTraits<X> >(NodeColorsTraits<X>(*this,x));
   508   }
   509   template<class X> struct NodeTextColorsTraits : public T {
   510     const X &_nodeTextColors;
   511     NodeTextColorsTraits(const T &t,const X &x) : T(t), _nodeTextColors(x) {}
   512   };
   513   ///Sets the map of the node text colors
   514 
   515   ///Sets the map of the node text colors
   516   ///\param x must be a node map with \ref Color values. 
   517   template<class X> GraphToEps<NodeTextColorsTraits<X> >
   518   nodeTextColors(const X &x)
   519   {
   520     dontPrint=true;
   521     _nodeTextColorType=CUST_COL;
   522     return GraphToEps<NodeTextColorsTraits<X> >
   523       (NodeTextColorsTraits<X>(*this,x));
   524   }
   525   template<class X> struct EdgeColorsTraits : public T {
   526     const X &_edgeColors;
   527     EdgeColorsTraits(const T &t,const X &x) : T(t), _edgeColors(x) {}
   528   };
   529   ///Sets the map of the edge colors
   530 
   531   ///Sets the map of the edge colors
   532   ///\param x must be a edge map with \ref Color values. 
   533   template<class X> GraphToEps<EdgeColorsTraits<X> >
   534   edgeColors(const X &x)
   535   {
   536     dontPrint=true;
   537     return GraphToEps<EdgeColorsTraits<X> >(EdgeColorsTraits<X>(*this,x));
   538   }
   539   ///Sets a global scale factor for node sizes
   540 
   541   ///Sets a global scale factor for node sizes
   542   ///
   543   GraphToEps<T> &nodeScale(double d) {_nodeScale=d;return *this;}
   544   ///Sets a global scale factor for edge widths
   545 
   546   ///Sets a global scale factor for edge widths
   547   ///
   548   GraphToEps<T> &edgeWidthScale(double d) {_edgeWidthScale=d;return *this;}
   549   ///Sets a global scale factor for the whole picture
   550 
   551   ///Sets a global scale factor for the whole picture
   552   ///
   553   GraphToEps<T> &scale(double d) {_scale=d;return *this;}
   554   ///Sets the width of the border around the picture
   555 
   556   ///Sets the width of the border around the picture
   557   ///
   558   GraphToEps<T> &border(double b) {_xBorder=_yBorder=b;return *this;}
   559   ///Sets the width of the border around the picture
   560 
   561   ///Sets the width of the border around the picture
   562   ///
   563   GraphToEps<T> &border(double x, double y) {
   564     _xBorder=x;_yBorder=y;return *this;
   565   }
   566   ///Sets whether to draw arrows
   567 
   568   ///Sets whether to draw arrows
   569   ///
   570   GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
   571   ///Sets the length of the arrowheads
   572 
   573   ///Sets the length of the arrowheads
   574   ///
   575   GraphToEps<T> &arrowLength(double d) {_arrowLength*=d;return *this;}
   576   ///Sets the width of the arrowheads
   577 
   578   ///Sets the width of the arrowheads
   579   ///
   580   GraphToEps<T> &arrowWidth(double d) {_arrowWidth*=d;return *this;}
   581   
   582   ///Scales the drawing to fit to A4 page
   583 
   584   ///Scales the drawing to fit to A4 page
   585   ///
   586   GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
   587   
   588   ///Enables parallel edges
   589 
   590   ///Enables parallel edges
   591   ///\todo Partially implemented
   592   GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
   593   
   594   ///Sets the distance 
   595   
   596   ///Sets the distance 
   597   ///
   598   GraphToEps<T> &parEdgeDist(double d) {_parEdgeDist*=d;return *this;}
   599   
   600   ///Hides the edges
   601   
   602   ///Hides the edges
   603   ///
   604   GraphToEps<T> &hideEdges(bool b=true) {_showEdges=!b;return *this;}
   605   ///Hides the nodes
   606   
   607   ///Hides the nodes
   608   ///
   609   GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
   610   
   611   ///Sets the size of the node texts
   612   
   613   ///Sets the size of the node texts
   614   ///
   615   GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
   616 
   617   ///Sets the color of the node texts to be different from the node color
   618 
   619   ///Sets the color of the node texts to be as different from the node color
   620   ///as it is possible
   621     ///
   622   GraphToEps<T> &distantColorNodeTexts()
   623   {_nodeTextColorType=DIST_COL;return *this;}
   624   ///Sets the color of the node texts to be black or white and always visible.
   625 
   626   ///Sets the color of the node texts to be black or white according to
   627   ///which is more 
   628   ///different from the node color
   629   ///
   630   GraphToEps<T> &distantBWNodeTexts()
   631   {_nodeTextColorType=DIST_BW;return *this;}
   632 
   633   ///Gives a preamble block for node Postscript block.
   634   
   635   ///Gives a preamble block for node Postscript block.
   636   ///
   637   ///\sa nodePsTexts()
   638   GraphToEps<T> & nodePsTextsPreamble(const char *str) {
   639     _nodePsTextsPreamble=str ;return *this;
   640   }
   641   ///Sets whether the the graph is undirected
   642 
   643   ///Sets whether the the graph is undirected
   644   ///
   645   GraphToEps<T> &undir(bool b=true) {_undir=b;return *this;}
   646   ///Sets whether the the graph is directed
   647 
   648   ///Sets whether the the graph is directed.
   649   ///Use it to show the undirected edges as a pair of directed ones.
   650   GraphToEps<T> &bidir(bool b=true) {_undir=!b;return *this;}
   651 
   652   ///Sets the title.
   653 
   654   ///Sets the title of the generated image,
   655   ///namely it inserts a <tt>%%Title:</tt> DSC field to the header of
   656   ///the EPS file.
   657   GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
   658   ///Sets the copyright statement.
   659 
   660   ///Sets the copyright statement of the generated image,
   661   ///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of
   662   ///the EPS file.
   663   ///\todo Multiline copyright notice could be supported.
   664   GraphToEps<T> &copyright(const std::string &t) {_copyright=t;return *this;}
   665 
   666 protected:
   667   bool isInsideNode(xy<double> p, double r,int t) 
   668   {
   669     switch(t) {
   670     case CIRCLE:
   671       return p.normSquare()<=r*r;
   672     case SQUARE:
   673       return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r;
   674     case DIAMOND:
   675       return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r;
   676     }
   677     return false;
   678   }
   679 
   680 public:
   681   ~GraphToEps() { }
   682   
   683   ///Draws the graph.
   684 
   685   ///Like other functions using
   686   ///\ref named-templ-func-param "named template parameters",
   687   ///this function calles the algorithm itself, i.e. in this case
   688   ///it draws the graph.
   689   void run() {
   690     if(dontPrint) return;
   691     
   692     os << "%!PS-Adobe-2.0 EPSF-2.0\n";
   693     if(_title.size()>0) os << "%%Title: " << _title << '\n';
   694      if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n';
   695 //        << "%%Copyright: XXXX\n"
   696     os << "%%Creator: LEMON GraphToEps function\n";
   697     
   698     {
   699       char cbuf[50];
   700       timeval tv;
   701       gettimeofday(&tv, 0);
   702       ctime_r(&tv.tv_sec,cbuf);
   703       os << "%%CreationDate: " << cbuf;
   704     }
   705     ///\todo: Chech whether the graph is empty.
   706     BoundingBox<double> bb;
   707     for(NodeIt n(g);n!=INVALID;++n) {
   708       double ns=_nodeSizes[n]*_nodeScale;
   709       xy<double> p(ns,ns);
   710       bb+=p+_coords[n];
   711       bb+=-p+_coords[n];
   712       }
   713     if(_scaleToA4)
   714       os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n";
   715     else os << "%%BoundingBox: "
   716 	    << bb.left()*  _scale-_xBorder << ' '
   717 	    << bb.bottom()*_scale-_yBorder << ' '
   718 	    << bb.right()* _scale+_xBorder << ' '
   719 	    << bb.top()*   _scale+_yBorder << '\n';
   720     
   721     os << "%%EndComments\n";
   722     
   723     //x1 y1 x2 y2 x3 y3 cr cg cb w
   724     os << "/lb { setlinewidth setrgbcolor newpath moveto\n"
   725        << "      4 2 roll 1 index 1 index curveto stroke } bind def\n";
   726     os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def\n";
   727     //x y r
   728     os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def\n";
   729     //x y r
   730     os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"
   731        << "      2 index 1 index sub 2 index 2 index add lineto\n"
   732        << "      2 index 1 index sub 2 index 2 index sub lineto\n"
   733        << "      2 index 1 index add 2 index 2 index sub lineto\n"
   734        << "      closepath pop pop pop} bind def\n";
   735     //x y r
   736     os << "/di { newpath 2 index 1 index add 2 index moveto\n"
   737        << "      2 index             2 index 2 index add lineto\n"
   738        << "      2 index 1 index sub 2 index             lineto\n"
   739        << "      2 index             2 index 2 index sub lineto\n"
   740        << "      closepath pop pop pop} bind def\n";
   741     // x y r cr cg cb
   742     os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
   743        << "     setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n"
   744        << "   } bind def\n";
   745     os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
   746        << "     setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n"
   747        << "   } bind def\n";
   748     os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
   749        << "     setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n"
   750        << "   } bind def\n";
   751     os << "/arrl " << _arrowLength << " def\n";
   752     os << "/arrw " << _arrowWidth << " def\n";
   753     // l dx_norm dy_norm
   754     os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
   755     //len w dx_norm dy_norm x1 y1 cr cg cb
   756     os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def\n"
   757        << "       /w exch def /len exch def\n"
   758       //	 << "       0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke"
   759        << "       newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n"
   760        << "       len w sub arrl sub dx dy lrl\n"
   761        << "       arrw dy dx neg lrl\n"
   762        << "       dx arrl w add mul dy w 2 div arrw add mul sub\n"
   763        << "       dy arrl w add mul dx w 2 div arrw add mul add rlineto\n"
   764        << "       dx arrl w add mul neg dy w 2 div arrw add mul sub\n"
   765        << "       dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n"
   766        << "       arrw dy dx neg lrl\n"
   767        << "       len w sub arrl sub neg dx dy lrl\n"
   768        << "       closepath fill } bind def\n";
   769     os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
   770        << "         neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n";
   771 
   772     os << "\ngsave\n";
   773     if(_scaleToA4)
   774       if(bb.height()>bb.width()) {
   775 	double sc= min((A4HEIGHT-2*A4BORDER)/bb.height(),
   776 		  (A4WIDTH-2*A4BORDER)/bb.width());
   777 	os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '
   778 	   << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER << " translate\n"
   779 	   << sc << " dup scale\n"
   780 	   << -bb.left() << ' ' << -bb.bottom() << " translate\n";
   781       }
   782       else {
   783 	//\todo Verify centering
   784 	double sc= min((A4HEIGHT-2*A4BORDER)/bb.width(),
   785 		  (A4WIDTH-2*A4BORDER)/bb.height());
   786 	os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '
   787 	   << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER  << " translate\n"
   788 	   << sc << " dup scale\n90 rotate\n"
   789 	   << -bb.left() << ' ' << -bb.top() << " translate\n";	
   790 	}
   791     else if(_scale!=1.0) os << _scale << " dup scale\n";
   792     
   793     if(_showEdges) {
   794       os << "%Edges:\ngsave\n";      
   795       if(_enableParallel) {
   796 	std::vector<Edge> el;
   797 	for(EdgeIt e(g);e!=INVALID;++e)
   798 	  if((!_undir||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
   799 	    el.push_back(e);
   800 	sort(el.begin(),el.end(),edgeLess(g));
   801 	
   802 	typename std::vector<Edge>::iterator j;
   803 	for(typename std::vector<Edge>::iterator i=el.begin();i!=el.end();i=j) {
   804 	  for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ;
   805 
   806 	  double sw=0;
   807 	  for(typename std::vector<Edge>::iterator e=i;e!=j;++e)
   808 	    sw+=_edgeWidths[*e]*_edgeWidthScale+_parEdgeDist;
   809 	  sw-=_parEdgeDist;
   810 	  sw/=-2.0;
   811 	  xy<double> dvec(_coords[g.target(*i)]-_coords[g.source(*i)]);
   812 	  double l=sqrt(dvec.normSquare());
   813 	  xy<double> d(dvec/l);
   814  	  xy<double> m;
   815 // 	  m=xy<double>(_coords[g.target(*i)]+_coords[g.source(*i)])/2.0;
   816 
   817 //  	  m=xy<double>(_coords[g.source(*i)])+
   818 // 	    dvec*(double(_nodeSizes[g.source(*i)])/
   819 // 	       (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));
   820 
   821  	  m=xy<double>(_coords[g.source(*i)])+
   822 	    d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;
   823 
   824 	  for(typename std::vector<Edge>::iterator e=i;e!=j;++e) {
   825 	    sw+=_edgeWidths[*e]*_edgeWidthScale/2.0;
   826 	    xy<double> mm=m+rot90(d)*sw/.75;
   827 	    if(_drawArrows) {
   828 	      int node_shape;
   829 	      xy<double> s=_coords[g.source(*e)];
   830 	      xy<double> t=_coords[g.target(*e)];
   831 	      double rn=_nodeSizes[g.target(*e)]*_nodeScale;
   832 	      node_shape=_nodeShapes[g.target(*e)];
   833 	      Bezier3 bez(s,mm,mm,t);
   834 	      double t1=0,t2=1;
   835 	      for(int i=0;i<INTERPOL_PREC;++i)
   836 		if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;
   837 		else t1=(t1+t2)/2;
   838 	      xy<double> apoint=bez((t1+t2)/2);
   839 	      rn = _arrowLength+_edgeWidths[*e]*_edgeWidthScale;
   840 	      rn*=rn;
   841 	      t2=(t1+t2)/2;t1=0;
   842 	      for(int i=0;i<INTERPOL_PREC;++i)
   843 		if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;
   844 		else t2=(t1+t2)/2;
   845 	      xy<double> linend=bez((t1+t2)/2);	      
   846 	      bez=bez.before((t1+t2)/2);
   847 // 	      rn=_nodeSizes[g.source(*e)]*_nodeScale;
   848 // 	      node_shape=_nodeShapes[g.source(*e)];
   849 // 	      t1=0;t2=1;
   850 // 	      for(int i=0;i<INTERPOL_PREC;++i)
   851 // 		if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t1=(t1+t2)/2;
   852 // 		else t2=(t1+t2)/2;
   853 // 	      bez=bez.after((t1+t2)/2);
   854 	      os << _edgeWidths[*e]*_edgeWidthScale << " setlinewidth "
   855 		 << _edgeColors[*e].getR() << ' '
   856 		 << _edgeColors[*e].getG() << ' '
   857 		 << _edgeColors[*e].getB() << " setrgbcolor newpath\n"
   858 		 << bez.p1.x << ' ' <<  bez.p1.y << " moveto\n"
   859 		 << bez.p2.x << ' ' << bez.p2.y << ' '
   860 		 << bez.p3.x << ' ' << bez.p3.y << ' '
   861 		 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";
   862 	      xy<double> dd(rot90(linend-apoint));
   863 	      dd*=(.5*_edgeWidths[*e]*_edgeWidthScale+_arrowWidth)/
   864 		sqrt(dd.normSquare());
   865 	      os << "newpath " << psOut(apoint) << " moveto "
   866 		 << psOut(linend+dd) << " lineto "
   867 		 << psOut(linend-dd) << " lineto closepath fill\n";
   868 	    }
   869 	    else {
   870 	      os << _coords[g.source(*e)].x << ' '
   871 		 << _coords[g.source(*e)].y << ' '
   872 		 << mm.x << ' ' << mm.y << ' '
   873 		 << _coords[g.target(*e)].x << ' '
   874 		 << _coords[g.target(*e)].y << ' '
   875 		 << _edgeColors[*e].getR() << ' '
   876 		 << _edgeColors[*e].getG() << ' '
   877 		 << _edgeColors[*e].getB() << ' '
   878 		 << _edgeWidths[*e]*_edgeWidthScale << " lb\n";
   879 	    }
   880 	    sw+=_edgeWidths[*e]*_edgeWidthScale/2.0+_parEdgeDist;
   881 	  }
   882 	}
   883       }
   884       else for(EdgeIt e(g);e!=INVALID;++e)
   885 	if((!_undir||g.source(e)<g.target(e))&&_edgeWidths[e]>0)
   886 	  if(_drawArrows) {
   887 	    xy<double> d(_coords[g.target(e)]-_coords[g.source(e)]);
   888 	    double rn=_nodeSizes[g.target(e)]*_nodeScale;
   889 	    int node_shape=_nodeShapes[g.target(e)];
   890 	    double t1=0,t2=1;
   891 	    for(int i=0;i<INTERPOL_PREC;++i)
   892 	      if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2;
   893 	      else t2=(t1+t2)/2;
   894 	    double l=sqrt(d.normSquare());
   895 	    d/=l;
   896 	    
   897 	    os << l*(1-(t1+t2)/2) << ' '
   898 	       << _edgeWidths[e]*_edgeWidthScale << ' '
   899 	       << d.x << ' ' << d.y << ' '
   900 	       << _coords[g.source(e)].x << ' '
   901 	       << _coords[g.source(e)].y << ' '
   902 	       << _edgeColors[e].getR() << ' '
   903 	       << _edgeColors[e].getG() << ' '
   904 	       << _edgeColors[e].getB() << " arr\n";
   905 	  }
   906 	  else os << _coords[g.source(e)].x << ' '
   907 		  << _coords[g.source(e)].y << ' '
   908 		  << _coords[g.target(e)].x << ' '
   909 		  << _coords[g.target(e)].y << ' '
   910 		  << _edgeColors[e].getR() << ' '
   911 		  << _edgeColors[e].getG() << ' '
   912 		  << _edgeColors[e].getB() << ' '
   913 		  << _edgeWidths[e]*_edgeWidthScale << " l\n";
   914       os << "grestore\n";
   915     }
   916     if(_showNodes) {
   917       os << "%Nodes:\ngsave\n";
   918       for(NodeIt n(g);n!=INVALID;++n) {
   919 	os << _coords[n].x << ' ' << _coords[n].y << ' '
   920 	   << _nodeSizes[n]*_nodeScale << ' '
   921 	   << _nodeColors[n].getR() << ' '
   922 	   << _nodeColors[n].getG() << ' '
   923 	   << _nodeColors[n].getB() << ' ';
   924 	switch(_nodeShapes[n]) {
   925 	case CIRCLE:
   926 	  os<< "nc";break;
   927 	case SQUARE:
   928 	  os<< "nsq";break;
   929 	case DIAMOND:
   930 	  os<< "ndi";break;
   931 	}
   932 	os<<'\n';
   933       }
   934       os << "grestore\n";
   935     }
   936     if(_showNodeText) {
   937       os << "%Node texts:\ngsave\n";
   938       os << "/fosi " << _nodeTextSize << " def\n";
   939       os << "(Helvetica) findfont fosi scalefont setfont\n";
   940       for(NodeIt n(g);n!=INVALID;++n) {
   941 	switch(_nodeTextColorType) {
   942 	case DIST_COL:
   943 	  os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n";
   944 	  break;
   945 	case DIST_BW:
   946 	  os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n";
   947 	  break;
   948 	case CUST_COL:
   949 	  os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n";
   950 	  break;
   951 	default:
   952 	  os << "0 0 0 setrgbcolor\n";
   953 	}
   954 	os << _coords[n].x << ' ' << _coords[n].y
   955 	   << " (" << _nodeTexts[n] << ") cshow\n";
   956       }
   957       os << "grestore\n";
   958     }
   959     if(_showNodePsText) {
   960       os << "%Node PS blocks:\ngsave\n";
   961       for(NodeIt n(g);n!=INVALID;++n)
   962 	os << _coords[n].x << ' ' << _coords[n].y
   963 	   << " moveto\n" << _nodePsTexts[n] << "\n";
   964       os << "grestore\n";
   965     }
   966     
   967     os << "grestore\nshowpage\n";
   968 
   969     //CleanUp:
   970     if(_pleaseRemoveOsStream) {delete &os;}
   971   } 
   972 };
   973 
   974 
   975 ///Generates an EPS file from a graph
   976 
   977 ///\ingroup misc
   978 ///Generates an EPS file from a graph.
   979 ///\param g is a reference to the graph to be printed
   980 ///\param os is a reference to the output stream.
   981 ///By default it is <tt>std::cout</tt>
   982 ///
   983 ///This function also has a lot of
   984 ///\ref named-templ-func-param "named parameters",
   985 ///they are declared as the members of class \ref GraphToEps. The following
   986 ///example shows how to use these parameters.
   987 ///\code
   988 /// graphToEps(g,os).scale(10).coords(coords)
   989 ///              .nodeScale(2).nodeSizes(sizes)
   990 ///              .edgeWidthScale(.4).run();
   991 ///\endcode
   992 ///\warning Don't forget to put the \ref GraphToEps::run() "run()"
   993 ///to the end of the parameter list.
   994 ///\sa GraphToEps
   995 ///\sa graphToEps(G &g, char *file_name)
   996 template<class G>
   997 GraphToEps<DefaultGraphToEpsTraits<G> > 
   998 graphToEps(G &g, std::ostream& os=std::cout)
   999 {
  1000   return 
  1001     GraphToEps<DefaultGraphToEpsTraits<G> >(DefaultGraphToEpsTraits<G>(g,os));
  1002 }
  1003  
  1004 ///Generates an EPS file from a graph
  1005 
  1006 ///\ingroup misc
  1007 ///This function does the same as
  1008 ///\ref graphToEps(G &g,std::ostream& os)
  1009 ///but it writes its output into the file \c file_name
  1010 ///instead of a stream.
  1011 ///\sa graphToEps(G &g, std::ostream& os)
  1012 template<class G>
  1013 GraphToEps<DefaultGraphToEpsTraits<G> > 
  1014 graphToEps(G &g,const char *file_name)
  1015 {
  1016   return GraphToEps<DefaultGraphToEpsTraits<G> >
  1017     (DefaultGraphToEpsTraits<G>(g,*new std::ofstream(file_name),true));
  1018 }
  1019 
  1020 } //END OF NAMESPACE LEMON
  1021 
  1022 #endif // LEMON_GRAPH_TO_EPS_H