RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

#define LEMON_GRAPH_TO_EPS_H

#include<iostream>

#include<fstream>

#include<sstream>

#include<algorithm>

#include<vector>

#ifndef WIN32

#include<sys/time.h>

#include<ctime>

#else

#define WIN32_LEAN_AND_MEAN

#define NOMINMAX

#include<windows.h>

#endif

#include<lemon/math.h>

#include<lemon/core.h>

#include<lemon/dim2.h>

#include<lemon/maps.h>

#include<lemon/color.h>

#include<lemon/bits/bezier.h>

#include<lemon/error.h>

///\ingroup eps_io

///\file

///\brief A well configurable tool for visualizing graphs

namespace lemon {

  namespace _graph_to_eps_bits {

    template<class MT>

    class _NegY {

    public:

      typedef typename MT::Key Key;

      typedef typename MT::Value Value;

      const MT ↦

      int yscale;

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

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

    };

  }

///Default traits class of GraphToEps

///Default traits class of \ref GraphToEps.

///

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

template<class G>

struct DefaultGraphToEpsTraits

{

  typedef G Graph;

  typedef typename Graph::Node Node;

  typedef typename Graph::NodeIt NodeIt;

  typedef typename Graph::Arc Arc;

  typedef typename Graph::ArcIt ArcIt;

  typedef typename Graph::InArcIt InArcIt;

  typedef typename Graph::OutArcIt OutArcIt;

  const Graph &g;

  std::ostream& os;

  typedef ConstMap<typename Graph::Node,dim2::Point<double> > CoordsMapType;

  CoordsMapType _coords;

  ConstMap<typename Graph::Node,double > _nodeSizes;

  ConstMap<typename Graph::Node,int > _nodeShapes;

  ConstMap<typename Graph::Node,Color > _nodeColors;

  ConstMap<typename Graph::Arc,Color > _arcColors;

  ConstMap<typename Graph::Arc,double > _arcWidths;

  double _arcWidthScale;

  double _nodeScale;

  double _xBorder, _yBorder;

  double _scale;

  double _nodeBorderQuotient;

  bool _drawArrows;

  double _arrowLength, _arrowWidth;

  bool _showNodes, _showArcs;

  bool _enableParallel;

  double _parArcDist;

  bool _showNodeText;

  ConstMap<typename Graph::Node,bool > _nodeTexts;

  double _nodeTextSize;

  bool _showNodePsText;

  ConstMap<typename Graph::Node,bool > _nodePsTexts;

  char *_nodePsTextsPreamble;

  bool _undirected;

  bool _pleaseRemoveOsStream;

  bool _scaleToA4;

  std::string _title;

  std::string _copyright;

  enum NodeTextColorType

    { DIST_COL=0, DIST_BW=1, CUST_COL=2, SAME_COL=3 } _nodeTextColorType;

  ConstMap<typename Graph::Node,Color > _nodeTextColors;

  bool _autoNodeScale;

  bool _autoArcWidthScale;

  bool _absoluteNodeSizes;

  bool _absoluteArcWidths;

  bool _negY;

  bool _preScale;

  ///Constructor

  ///Constructor

  ///\param _g  Reference to the graph to be printed.

  ///\param _os Reference to the output stream.

  ///\param _os Reference to the output stream.

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

  ///\param _pros If it is \c true, then the \c ostream referenced by \c _os

  ///will be explicitly deallocated by the destructor.

  DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,

                          bool _pros=false) :

    g(_g), os(_os),

    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),

    _nodeColors(WHITE), _arcColors(BLACK),

    _arcWidths(1.0), _arcWidthScale(0.003),

    _nodeScale(.01), _xBorder(10), _yBorder(10), _scale(1.0),

    _nodeBorderQuotient(.1),

    _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),

    _showNodes(true), _showArcs(true),

    _enableParallel(false), _parArcDist(1),

    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),

    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),

    _undirected(lemon::UndirectedTagIndicator<G>::value),

    _pleaseRemoveOsStream(_pros), _scaleToA4(false),

    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),

    _autoNodeScale(false),

    _autoArcWidthScale(false),

    _absoluteNodeSizes(false),

    _absoluteArcWidths(false),

    _negY(false),

    _preScale(true)

  {}

};

///Auxiliary class to implement the named parameters of \ref graphToEps()

///Auxiliary class to implement the named parameters of \ref graphToEps().

///

///For detailed examples see the \ref graph_to_eps_demo.cc demo file.

template<class T> class GraphToEps : public T

{

  // Can't believe it is required by the C++ standard

  using T::g;

  using T::os;

  using T::_coords;

  using T::_nodeSizes;

  using T::_nodeShapes;

  using T::_nodeColors;

  using T::_arcColors;

  using T::_arcWidths;

  using T::_arcWidthScale;

  using T::_nodeScale;

  using T::_xBorder;

  using T::_yBorder;

  using T::_scale;

  using T::_nodeBorderQuotient;

  using T::_drawArrows;

  using T::_arrowLength;

  using T::_arrowWidth;

  using T::_showNodes;

  using T::_showArcs;

  using T::_enableParallel;

  using T::_parArcDist;

  using T::_showNodeText;

  using T::_nodeTexts;

  using T::_nodeTextSize;

  using T::_showNodePsText;

  using T::_nodePsTexts;

  using T::_nodePsTextsPreamble;

  using T::_undirected;

  using T::_pleaseRemoveOsStream;

  using T::_scaleToA4;

  using T::_title;

  using T::_copyright;

  using T::NodeTextColorType;

  using T::CUST_COL;

  using T::DIST_COL;

  using T::DIST_BW;

  using T::_nodeTextColorType;

  using T::_nodeTextColors;

  using T::_autoNodeScale;

  using T::_autoArcWidthScale;

  using T::_absoluteNodeSizes;

  using T::_absoluteArcWidths;

  using T::_negY;

  using T::_preScale;

  // dradnats ++C eht yb deriuqer si ti eveileb t'naC

  typedef typename T::Graph Graph;

  typedef typename Graph::Node Node;

  typedef typename Graph::NodeIt NodeIt;

  typedef typename Graph::Arc Arc;

  typedef typename Graph::ArcIt ArcIt;

  typedef typename Graph::InArcIt InArcIt;

  typedef typename Graph::OutArcIt OutArcIt;

  static const int INTERPOL_PREC;

  static const double A4HEIGHT;

  static const double A4WIDTH;

  static const double A4BORDER;

  bool dontPrint;

public:

  ///Node shapes

  ///Node shapes.

  ///

  enum NodeShapes {

    /// = 0

    ///\image html nodeshape_0.png

    ///\image latex nodeshape_0.eps "CIRCLE shape (0)" width=2cm

    CIRCLE=0,

    /// = 1

    ///\image html nodeshape_1.png

    ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm

    ///

    SQUARE=1,

    /// = 2

    ///\image html nodeshape_2.png

    ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm

    ///

    DIAMOND=2,

    /// = 3

    ///\image html nodeshape_3.png

    ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm

    ///

    MALE=3,

    /// = 4

    ///\image html nodeshape_4.png

    ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm

    ///

    FEMALE=4

  };

private:

  class arcLess {

    const Graph &g;

  public:

    arcLess(const Graph &_g) : g(_g) {}

    bool operator()(Arc a,Arc b) const

    {

      Node ai=std::min(g.source(a),g.target(a));

      Node aa=std::max(g.source(a),g.target(a));

      Node bi=std::min(g.source(b),g.target(b));

      Node ba=std::max(g.source(b),g.target(b));

      return ai<bi ||

        (ai==bi && (aa < ba ||

                    (aa==ba && ai==g.source(a) && bi==g.target(b))));

    }

  };

  bool isParallel(Arc e,Arc f) const

  {

    return (g.source(e)==g.source(f)&&

            g.target(e)==g.target(f)) ||

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

       g.target(e)==g.source(f));

  }

  template<class TT>

  static std::string psOut(const dim2::Point<TT> &p)

    {

      std::ostringstream os;

      os << p.x << ' ' << p.y;

      return os.str();

    }

  static std::string psOut(const Color &c)

    {

      std::ostringstream os;

      os << c.red() << ' ' << c.green() << ' ' << c.blue();

      return os.str();

    }

public:

  GraphToEps(const T &t) : T(t), dontPrint(false) {};

  template<class X> struct CoordsTraits : public T {

  typedef X CoordsMapType;

    const X &_coords;

    CoordsTraits(const T &t,const X &x) : T(t), _coords(x) {}

  };

  ///Sets the map of the node coordinates

  ///Sets the map of the node coordinates.

  ///\param x must be a node map with \ref dim2::Point "dim2::Point<double>" or

  ///\ref dim2::Point "dim2::Point<int>" values.

  template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {

    dontPrint=true;

    return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));

  }

  template<class X> struct NodeSizesTraits : public T {

    const X &_nodeSizes;

    NodeSizesTraits(const T &t,const X &x) : T(t), _nodeSizes(x) {}

  };

  ///Sets the map of the node sizes

  ///Sets the map of the node sizes.

  ///\param x must be a node map with \c double (or convertible) values.

  template<class X> GraphToEps<NodeSizesTraits<X> > nodeSizes(const X &x)

  {

    dontPrint=true;

    return GraphToEps<NodeSizesTraits<X> >(NodeSizesTraits<X>(*this,x));

  }

  template<class X> struct NodeShapesTraits : public T {

    const X &_nodeShapes;

    NodeShapesTraits(const T &t,const X &x) : T(t), _nodeShapes(x) {}

  };

  ///Sets the map of the node shapes

  ///Sets the map of the node shapes.

  ///The available shape values

  ///can be found in \ref NodeShapes "enum NodeShapes".

  ///\param x must be a node map with \c int (or convertible) values.

  ///\sa NodeShapes

  template<class X> GraphToEps<NodeShapesTraits<X> > nodeShapes(const X &x)

  {

    dontPrint=true;

    return GraphToEps<NodeShapesTraits<X> >(NodeShapesTraits<X>(*this,x));

  }

  template<class X> struct NodeTextsTraits : public T {

    const X &_nodeTexts;

    NodeTextsTraits(const T &t,const X &x) : T(t), _nodeTexts(x) {}

  };

  ///Sets the text printed on the nodes

  ///Sets the text printed on the nodes.

  ///\param x must be a node map with type that can be pushed to a standard

  ///\c ostream.

  template<class X> GraphToEps<NodeTextsTraits<X> > nodeTexts(const X &x)

  {

    dontPrint=true;

    _showNodeText=true;

    return GraphToEps<NodeTextsTraits<X> >(NodeTextsTraits<X>(*this,x));

  }

  template<class X> struct NodePsTextsTraits : public T {

    const X &_nodePsTexts;

    NodePsTextsTraits(const T &t,const X &x) : T(t), _nodePsTexts(x) {}

  };

  ///Inserts a PostScript block to the nodes

  ///With this command it is possible to insert a verbatim PostScript

  ///block to the nodes.

  ///The PS current point will be moved to the center of the node before

  ///the PostScript block inserted.

  ///

  ///Before and after the block a newline character is inserted so you

  ///don't have to bother with the separators.

  ///

  ///\param x must be a node map with type that can be pushed to a standard

  ///\c ostream.

  ///

  ///\sa nodePsTextsPreamble()

  template<class X> GraphToEps<NodePsTextsTraits<X> > nodePsTexts(const X &x)

  {

    dontPrint=true;

    _showNodePsText=true;

    return GraphToEps<NodePsTextsTraits<X> >(NodePsTextsTraits<X>(*this,x));

  }

  template<class X> struct ArcWidthsTraits : public T {

    const X &_arcWidths;

    ArcWidthsTraits(const T &t,const X &x) : T(t), _arcWidths(x) {}

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

#define LEMON_TIME_MEASURE_H

///\ingroup timecount

///\file

///\brief Tools for measuring cpu usage

#ifdef WIN32

#define WIN32_LEAN_AND_MEAN

#define NOMINMAX

#include <windows.h>

#include <cmath>

#else

#include <unistd.h>

#include <sys/times.h>

#include <sys/time.h>

#endif

#include <string>

#include <fstream>

#include <iostream>

namespace lemon {

  /// \addtogroup timecount

  /// @{

  /// A class to store (cpu)time instances.

  /// This class stores five time values.

  /// - a real time

  /// - a user cpu time

  /// - a system cpu time

  /// - a user cpu time of children

  /// - a system cpu time of children

  ///

  /// TimeStamp's can be added to or substracted from each other and

  /// they can be pushed to a stream.

  ///

  /// In most cases, perhaps the \ref Timer or the \ref TimeReport

  /// class is what you want to use instead.

  class TimeStamp

  {

    double utime;

    double stime;

    double cutime;

    double cstime;

    double rtime;

    void _reset() {

      utime = stime = cutime = cstime = rtime = 0;

    }

  public:

    ///Read the current time values of the process

    void stamp()

    {

#ifndef WIN32

      timeval tv;

      gettimeofday(&tv, 0);

      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;

      tms ts;

      double tck=sysconf(_SC_CLK_TCK);

      times(&ts);

      utime=ts.tms_utime/tck;

      stime=ts.tms_stime/tck;

      cutime=ts.tms_cutime/tck;

      cstime=ts.tms_cstime/tck;

#else

      static const double ch = 4294967296.0e-7;

      static const double cl = 1.0e-7;

      FILETIME system;

      GetSystemTimeAsFileTime(&system);

      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;

      FILETIME create, exit, kernel, user;

      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {

        utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;

        stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;

        cutime = 0;

        cstime = 0;

      } else {

        rtime = 0;

        utime = 0;

        stime = 0;

        cutime = 0;

        cstime = 0;

      }

#endif

    }

    /// Constructor initializing with zero

    TimeStamp()

    { _reset(); }

    ///Constructor initializing with the current time values of the process

    TimeStamp(void *) { stamp();}

    ///Set every time value to zero

    TimeStamp &reset() {_reset();return *this;}

    ///\e

    TimeStamp &operator+=(const TimeStamp &b)

    {

      utime+=b.utime;

      stime+=b.stime;

      cutime+=b.cutime;

      cstime+=b.cstime;

      rtime+=b.rtime;

      return *this;

    }

    ///\e

    TimeStamp operator+(const TimeStamp &b) const

    {

      TimeStamp t(*this);

      return t+=b;

    }

    ///\e

    TimeStamp &operator-=(const TimeStamp &b)

    {

      utime-=b.utime;

      stime-=b.stime;

      cutime-=b.cutime;

      cstime-=b.cstime;

      rtime-=b.rtime;

      return *this;

    }

    ///\e

    TimeStamp operator-(const TimeStamp &b) const

    {

      TimeStamp t(*this);

      return t-=b;

    }

    ///\e

    TimeStamp &operator*=(double b)

    {

      utime*=b;

      stime*=b;

      cutime*=b;

      cstime*=b;

      rtime*=b;

      return *this;

    }

    ///\e

    TimeStamp operator*(double b) const

    {

      TimeStamp t(*this);

      return t*=b;

    }

    friend TimeStamp operator*(double b,const TimeStamp &t);

    ///\e

    TimeStamp &operator/=(double b)

    {

      utime/=b;

      stime/=b;

      cutime/=b;

      cstime/=b;

      rtime/=b;

      return *this;

    }

    ///\e

    TimeStamp operator/(double b) const

    {

      TimeStamp t(*this);

      return t/=b;

    }

    ///The time ellapsed since the last call of stamp()

    TimeStamp ellapsed() const

    {

      TimeStamp t(NULL);

      return t-*this;

    }

    friend std::ostream& operator<<(std::ostream& os,const TimeStamp &t);

    ///Gives back the user time of the process

    double userTime() const

    {

      return utime;

    }

    ///Gives back the system time of the process

    double systemTime() const

    {

      return stime;

    }

    ///Gives back the user time of the process' children

    ///\note On <tt>WIN32</tt> platform this value is not calculated.

    ///

    double cUserTime() const

    {

      return cutime;

    }

    ///Gives back the user time of the process' children

    ///\note On <tt>WIN32</tt> platform this value is not calculated.

    ///

    double cSystemTime() const

    {

      return cstime;

    }

    ///Gives back the real time

    double realTime() const {return rtime;}

  };

  TimeStamp operator*(double b,const TimeStamp &t)

  {

    return t*b;

  }

  ///Prints the time counters

  ///Prints the time counters in the following form:

  ///

  /// <tt>u: XX.XXs s: XX.XXs cu: XX.XXs cs: XX.XXs real: XX.XXs</tt>

  ///

  /// where the values are the

  /// \li \c u: user cpu time,

  /// \li \c s: system cpu time,

  /// \li \c cu: user cpu time of children,

  /// \li \c cs: system cpu time of children,

  /// \li \c real: real time.

  /// \relates TimeStamp

  /// \note On <tt>WIN32</tt> platform the cummulative values are not

  /// calculated.

  inline std::ostream& operator<<(std::ostream& os,const TimeStamp &t)

  {

    os << "u: " << t.userTime() <<

      "s, s: " << t.systemTime() <<

      "s, cu: " << t.cUserTime() <<

      "s, cs: " << t.cSystemTime() <<

      "s, real: " << t.realTime() << "s";

    return os;

  }

  ///Class for measuring the cpu time and real time usage of the process

  ///Class for measuring the cpu time and real time usage of the process.

  ///It is quite easy-to-use, here is a short example.

  ///\code

  /// #include<lemon/time_measure.h>

  /// #include<iostream>

  ///

  /// int main()

  /// {

  ///

  ///   ...

  ///

  ///   Timer t;

  ///   doSomething();

  ///   std::cout << t << '\n';

  ///   t.restart();

  ///   doSomethingElse();

  ///   std::cout << t << '\n';

  ///

  ///   ...

  ///

  /// }

  ///\endcode

  ///

  ///The \ref Timer can also be \ref stop() "stopped" and

  ///\ref start() "started" again, so it is possible to compute collected

  ///running times.

  ///

  ///\warning Depending on the operation system and its actual configuration

  ///the time counters have a certain (10ms on a typical Linux system)

  ///granularity.

  ///Therefore this tool is not appropriate to measure very short times.

  ///Also, if you start and stop the timer very frequently, it could lead to

  ///distorted results.

  ///

  ///\note If you want to measure the running time of the execution of a certain

  ///function, consider the usage of \ref TimeReport instead.

  ///

  ///\sa TimeReport

  class Timer

  {

    int _running; //Timer is running iff _running>0; (_running>=0 always holds)

    TimeStamp start_time; //This is the relativ start-time if the timer

                          //is _running, the collected _running time otherwise.

    void _reset() {if(_running) start_time.stamp(); else start_time.reset();}

  public:

    ///Constructor.

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

    ///

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

    ///\name Control the state of the timer

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

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

    ///The \ref lemon::Timer "Timer" also counts the number of

    ///\ref lemon::Timer::start() "start()" executions, and it stops

    ///only after the same amount (or more) \ref lemon::Timer::stop()

    ///"stop()"s. This can be useful e.g. to compute the running time

    ///of recursive functions.

    ///@{

    ///Reset and stop the time counters

    ///This function resets and stops the time counters

    ///\sa restart()

    void reset()

    {

      _running=0;

      _reset();

    }

    ///Start the time counters

    ///This function starts the time counters.

    ///

    ///If the timer is started more than ones, it will remain running

    ///until the same amount of \ref stop() is called.

    ///\sa stop()

    void start()

    {

      if(_running) _running++;

      else {

        _running=1;

        TimeStamp t;

        t.stamp();

        start_time=t-start_time;

      }

    }

    ///Stop the time counters

    ///This function stops the time counters. If start() was executed more than

    ///once, then the same number of stop() execution is necessary the really

    ///stop the timer.

    ///

    ///\sa halt()

    ///\sa start()

    ///\sa restart()

    ///\sa reset()

    void stop()

    {

      if(_running && !--_running) {

        TimeStamp t;

        t.stamp();

        start_time=t-start_time;

      }

    }

    ///Halt (i.e stop immediately) the time counters

    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>

    ///is a faster

    ///equivalent of the following.

    ///\code

    ///  while(t.running()) t.stop()

    ///\endcode

    ///

    ///

    ///\sa stop()

    ///\sa restart()

    ///\sa reset()

    void halt()

    {

      if(_running) {

        _running=0;

        TimeStamp t;

        t.stamp();

        start_time=t-start_time;

      }

    }

    ///Returns the running state of the timer

    ///This function returns the number of stop() exections that is

    ///necessary to really stop the timer.

    ///For example the timer

    ///is running if and only if the return value is \c true

    ///(i.e. greater than

    ///zero).

    int running()  { return _running; }

    ///Restart the time counters

    ///This function is a shorthand for

    ///a reset() and a start() calls.

    ///

    void restart()