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

    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;

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

	    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

    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;

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

#define LEMON_TEST_TEST_TOOLS_H

///\ingroup misc

///\file

///\brief Some utilities to write test programs.

#include <iostream>

///If \c rc is fail, writes an error message and exits.

///If \c rc is fail, writes an error message and exits.

///The error message contains the file name and the line number of the

///source code in a standard from, which makes it possible to go there

///using good source browsers like e.g. \c emacs.

///

///For example

///\code check(0==1,"This is obviously false.");\endcode will

///print something like this (and then exits).

///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim

#define check(rc, msg) \

  if(!(rc)) { \

    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \

    abort(); \

  } else { } \

#endif