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.

 *

 */

///\ingroup demos

///\file

///\brief Demonstrating graph input and output

///

/// This simple demo program gives an example of how to read and write

/// a graph and additional maps (on the nodes or the edges) from/to a

/// stream. 

///

/// \include reader_writer_demo.cc

#include <iostream>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/lgf_writer.h>

#include <lemon/random.h>

using namespace lemon;

int main(int argc, const char *argv[]) {

  const int n = argc > 1 ? std::atoi(argv[1]) : 20;

  const int m = argc > 3 ? std::atoi(argv[3]) : 100;

  SmartDigraph digraph;

  std::stringstream ss;

  try {

    typedef SmartDigraph Digraph;

    typedef Digraph::Node Node;

    typedef Digraph::Arc Arc;

    typedef Digraph::ArcIt ArcIt;

    typedef Digraph::NodeMap<int> PotentialMap;

    typedef Digraph::ArcMap<int> CapacityMap;

    typedef Digraph::ArcMap<std::string> NameMap;

    Digraph digraph;

    PotentialMap potential(digraph);

    CapacityMap capacity(digraph);

    NameMap name(digraph);

    std::vector<Node> nodes;

    for (int i = 0; i < n; ++i) {

      Node node = digraph.addNode();

      potential[node] = rnd[m];

      nodes.push_back(node);

    }

    std::vector<Arc> arcs;

    for (int i = 0; i < e; ++i) {

      int s = rnd[n];

      int t = rnd[n];

      int c = rnd[m];

      Arc arc = digraph.addArc(nodes[s], nodes[t]);

      capacity[arc] = c;

      std::ostringstream os;

      os << "arc \t" << i << std::endl;

      name[arc] = os.str();

      arcs.push_back(arc);

    }

    DigraphWriter<Digraph>(ss, digraph).

      nodeMap("potential", potential).

      arcMap("capacity", capacity).

      arcMap("name", name).

      node("source", nodes[0]).

      node("target", nodes[1]).

      arc("bottleneck", arcs[e / 2]).

      attribute("creator", "lemon library").

      run();

  } catch (DataFormatError& error) {

    std::cerr << error.what() << std::endl;

  }

  try {

    typedef SmartDigraph Digraph;

    typedef Digraph::Node Node;

    typedef Digraph::Arc Arc;

    typedef Digraph::ArcIt ArcIt;

    typedef Digraph::NodeMap<int> LabelMap;

    typedef Digraph::NodeMap<int> PotentialMap;

    typedef Digraph::ArcMap<int> CapacityMap;

    typedef Digraph::ArcMap<std::string> NameMap;

    Digraph digraph;

    LabelMap label(digraph);

    PotentialMap potential(digraph);

    CapacityMap capacity(digraph);

    NameMap name(digraph);

    Node s, t;

    Arc a;

    std::string creator;

    for (int i = 0; i < n; ++i) {

      Node node = digraph.addNode();

      label[node] = i;

    }

    DigraphReader<Digraph>(ss, digraph).

      useNodes(label).

      nodeMap("potential", potential).

      arcMap("capacity", capacity).

      arcMap("name", name).

      node("source", s).

      node("target", t).

      arc("bottleneck", a).

      attribute("creator", creator).

      run();

    DigraphWriter<Digraph>(std::cout, digraph).

      nodeMap("potential", potential).

      arcMap("capacity", capacity).

      arcMap("name", name).

      node("source", s).

      node("target", t).

      arc("bottleneck", a).

      attribute("creator", creator).

      run();

  } catch (DataFormatError& error) {

    std::cerr << error.what() << std::endl;

  }

  return 0;

}

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

#include<windows.h>

#endif

#include<lemon/math.h>

#include<lemon/bits/invalid.h>

#include<lemon/dim2.h>

#include<lemon/maps.h>

#include<lemon/color.h>

#include<lemon/bits/bezier.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 \ref 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 is a reference to the graph to be printed

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

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

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

  ///will be explicitly deallocated by the destructor.

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

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

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;

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

#define LEMON_TIME_MEASURE_H

///\ingroup timecount

///\file

///\brief Tools for measuring cpu usage

#ifdef WIN32

#include <windows.h>

#include <cmath>

#else

#include <sys/times.h>

#include <sys/time.h>

#endif

#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.

  ///

  ///\author Alpar Juttner

  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)