# HG changeset patch # User alpar # Date 1157635636 0 # Node ID 75a29ac69c193b682654c319dd1a4f16213c1afc # Parent c3ff11b0025cc2b324b3a8bd2ce3e4ad4e42bfef xy -> dim2::Point diff -r c3ff11b0025c -r 75a29ac69c19 benchmark/swap_bipartite_bench.cc --- a/benchmark/swap_bipartite_bench.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/benchmark/swap_bipartite_bench.cc Thu Sep 07 13:27:16 2006 +0000 @@ -3,12 +3,13 @@ #include #include +#include #include #include #include -#include +#include #include #include @@ -17,6 +18,7 @@ using namespace lemon; typedef SmartBpUGraph Graph; +typedef ListBpUGraph LGraph; BPUGRAPH_TYPEDEFS(Graph); int _urandom_init() { @@ -41,24 +43,36 @@ int s = 100; Timer nt(false), st(false); + Timer lnt(false), lst(false); for (int i = 0; i < s; ++i) { Graph graph; + LGraph lgraph; vector aNodes; vector bNodes; + vector laNodes; + vector lbNodes; for (int i = 0; i < n; ++i) { Node node = graph.addANode(); aNodes.push_back(node); + LGraph::Node lnode = lgraph.addANode(); + laNodes.push_back(lnode); } for (int i = 0; i < m; ++i) { Node node = graph.addBNode(); bNodes.push_back(node); + LGraph::Node lnode = lgraph.addBNode(); + lbNodes.push_back(lnode); } for (int i = 0; i < e; ++i) { - Node aNode = aNodes[urandom(n)]; - Node bNode = bNodes[urandom(m)]; + int a,b; + Node aNode = aNodes[a=urandom(n)]; + Node bNode = bNodes[b=urandom(m)]; graph.addEdge(aNode, bNode); + LGraph::Node laNode = laNodes[a]; + LGraph::Node lbNode = lbNodes[b]; + lgraph.addEdge(laNode, lbNode); } { @@ -81,11 +95,32 @@ bpmatch.start(); st.stop(); + } + { + MaxBipartiteMatching bpmatch(lgraph); + + lnt.start(); + bpmatch.init(); + bpmatch.start(); + lnt.stop(); + } - - } - cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl; + { + typedef SwapBpUGraphAdaptor SGraph; + SGraph sgraph(lgraph); + MaxBipartiteMatching bpmatch(sgraph); + + lst.start(); + bpmatch.init(); + bpmatch.start(); + lst.stop(); + + } + } + + cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() + << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl; } diff -r c3ff11b0025c -r 75a29ac69c19 demo/coloring.cc --- a/demo/coloring.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/coloring.cc Thu Sep 07 13:27:16 2006 +0000 @@ -55,7 +55,7 @@ Graph graph; UGraphReader reader("coloring.lgf", graph); - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); reader.readNodeMap("coords", coords); reader.run(); diff -r c3ff11b0025c -r 75a29ac69c19 demo/descriptor_map_demo.cc --- a/demo/descriptor_map_demo.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/descriptor_map_demo.cc Thu Sep 07 13:27:16 2006 +0000 @@ -29,7 +29,7 @@ #include #include #include -#include +#include #include #include @@ -40,7 +40,7 @@ using namespace lemon; -// Special xy map type +// Special dim2::Point map type // // It gives back a position for each node. The position of the nodes // are on the circle with the given center and radius. @@ -51,7 +51,7 @@ class CircleMap { public: - typedef xy Value; + typedef dim2::Point Value; typedef typename Graph::Node Key; CircleMap(const Graph& _graph, @@ -118,7 +118,7 @@ // Make postscript from the graph. - CircleMap coords(graph, xy(0.0, 0.0), 10.0); + CircleMap coords(graph, dim2::Point(0.0, 0.0), 10.0); graphToEps(graph,"descriptor_map_demo.eps").scaleToA4(). title("Generated graph"). diff -r c3ff11b0025c -r 75a29ac69c19 demo/disjoint_paths_demo.cc --- a/demo/disjoint_paths_demo.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/disjoint_paths_demo.cc Thu Sep 07 13:27:16 2006 +0000 @@ -52,7 +52,7 @@ Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); Graph::Node source, target; GraphReader("disjoint_paths_demo.lgf", graph). readNodeMap("coords", coords). @@ -98,7 +98,9 @@ graphToEps(sgraph, "node_disjoint_paths.eps"). title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows(). edgeColors(composeMap(functorMap(color), sflow)). - coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy(5, 0)))). + coords(SGraph::combinedNodeMap(coords, + shiftMap(coords, + dim2::Point(5, 0)))). autoNodeScale().run(); cout << "The paths are written into node_disjoint_paths.eps" << endl; diff -r c3ff11b0025c -r 75a29ac69c19 demo/graph_orientation.cc --- a/demo/graph_orientation.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/graph_orientation.cc Thu Sep 07 13:27:16 2006 +0000 @@ -19,7 +19,7 @@ #include #include #include -#include +#include #include @@ -45,7 +45,7 @@ ListGraph::NodeMap f(g); //in-deg requirement; ListGraph::NodeMap label(g); - ListGraph::NodeMap > coords(g); + ListGraph::NodeMap > coords(g); try { GraphReader reader(argv[1],g); diff -r c3ff11b0025c -r 75a29ac69c19 demo/graph_to_eps_demo.cc --- a/demo/graph_to_eps_demo.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/graph_to_eps_demo.cc Thu Sep 07 13:27:16 2006 +0000 @@ -48,7 +48,7 @@ typedef ListGraph::Node Node; typedef ListGraph::NodeIt NodeIt; typedef ListGraph::Edge Edge; - typedef xy Xy; + typedef dim2::Point Point; Node n1=g.addNode(); Node n2=g.addNode(); @@ -56,18 +56,18 @@ Node n4=g.addNode(); Node n5=g.addNode(); - ListGraph::NodeMap coords(g); + ListGraph::NodeMap coords(g); ListGraph::NodeMap sizes(g); ListGraph::NodeMap colors(g); ListGraph::NodeMap shapes(g); ListGraph::EdgeMap ecolors(g); ListGraph::EdgeMap widths(g); - coords[n1]=Xy(50,50); sizes[n1]=1; colors[n1]=1; shapes[n1]=0; - coords[n2]=Xy(50,70); sizes[n2]=2; colors[n2]=2; shapes[n2]=2; - coords[n3]=Xy(70,70); sizes[n3]=1; colors[n3]=3; shapes[n3]=0; - coords[n4]=Xy(70,50); sizes[n4]=2; colors[n4]=4; shapes[n4]=1; - coords[n5]=Xy(85,60); sizes[n5]=3; colors[n5]=5; shapes[n5]=2; + coords[n1]=Point(50,50); sizes[n1]=1; colors[n1]=1; shapes[n1]=0; + coords[n2]=Point(50,70); sizes[n2]=2; colors[n2]=2; shapes[n2]=2; + coords[n3]=Point(70,70); sizes[n3]=1; colors[n3]=3; shapes[n3]=0; + coords[n4]=Point(70,50); sizes[n4]=2; colors[n4]=4; shapes[n4]=1; + coords[n5]=Point(85,60); sizes[n5]=3; colors[n5]=5; shapes[n5]=2; Edge e; @@ -183,12 +183,12 @@ ListGraph h; ListGraph::NodeMap hcolors(h); - ListGraph::NodeMap hcoords(h); + ListGraph::NodeMap hcoords(h); int cols=int(sqrt(double(palette.size()))); for(int i=0;i #include #include -#include +#include #include #include diff -r c3ff11b0025c -r 75a29ac69c19 demo/min_route.cc --- a/demo/min_route.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/min_route.cc Thu Sep 07 13:27:16 2006 +0000 @@ -22,7 +22,7 @@ #include #include #include -#include +#include #include #include @@ -46,7 +46,7 @@ typedef double Value; typedef typename CoordMap::Key Key; - PotentialMap(const CoordMap& _coord, const xy& _target) + PotentialMap(const CoordMap& _coord, const dim2::Point& _target) : coord(_coord), target(_target) {} double operator[](const Key& node) const { @@ -55,7 +55,7 @@ } private: const CoordMap& coord; - xy target; + dim2::Point target; }; template @@ -86,7 +86,7 @@ typedef Graph::EdgeIt EdgeIt; typedef Graph::NodeIt NodeIt; typedef Graph::EdgeMap LengthMap; - typedef Graph::NodeMap > CoordMap; + typedef Graph::NodeMap > CoordMap; SmartGraph graph; @@ -94,9 +94,9 @@ GraphReader reader(is, graph); CoordMap coord(graph); - XMap xcoord = xMap(coord); + dim2::XMap xcoord = xMap(coord); reader.readNodeMap("coordinates_x", xcoord); - YMap ycoord = yMap(coord); + dim2::YMap ycoord = yMap(coord); reader.readNodeMap("coordinates_y", ycoord); LengthMap length(graph); diff -r c3ff11b0025c -r 75a29ac69c19 demo/strongly_connected_orientation.cc --- a/demo/strongly_connected_orientation.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/strongly_connected_orientation.cc Thu Sep 07 13:27:16 2006 +0000 @@ -78,7 +78,7 @@ << "to be strongly connected" << endl; UGraph ugraph; - UGraph::NodeMap > coords(ugraph); + UGraph::NodeMap > coords(ugraph); UGraphReader("strongly_connected_orientation.lgf", ugraph). readNodeMap("coords", coords).run(); diff -r c3ff11b0025c -r 75a29ac69c19 demo/topology_demo.cc --- a/demo/topology_demo.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/demo/topology_demo.cc Thu Sep 07 13:27:16 2006 +0000 @@ -20,7 +20,7 @@ #include #include #include -#include +#include #include @@ -49,7 +49,7 @@ typedef Graph::Node Node; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -74,7 +74,7 @@ typedef Graph::Node Node; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); GraphReader("dir_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -104,7 +104,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -134,7 +134,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("u_components.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). @@ -163,7 +163,7 @@ typedef Graph::UEdge UEdge; Graph graph; - Graph::NodeMap > coords(graph); + Graph::NodeMap > coords(graph); UGraphReader("partitions.lgf", graph). readNodeMap("coordinates_x", xMap(coords)). diff -r c3ff11b0025c -r 75a29ac69c19 lemon.spec.in --- a/lemon.spec.in Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon.spec.in Thu Sep 07 13:27:16 2006 +0000 @@ -7,7 +7,7 @@ Source0: %{name}-%{version}.tar.gz Group: Development/Libraries BuildRoot: %{_tmppath}/%{name}-root -# Requires: glpk +Requires: glpk # BuildRequires: glpk-devel %description diff -r c3ff11b0025c -r 75a29ac69c19 lemon/Makefile.am --- a/lemon/Makefile.am Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/Makefile.am Thu Sep 07 13:27:16 2006 +0000 @@ -41,6 +41,7 @@ lemon/dag_shortest_path.h \ lemon/dfs.h \ lemon/dijkstra.h \ + lemon/dim2.h \ lemon/dimacs.h \ lemon/edge_set.h \ lemon/edmonds_karp.h \ @@ -92,8 +93,7 @@ lemon/tolerance.h \ lemon/topology.h \ lemon/ugraph_adaptor.h \ - lemon/unionfind.h \ - lemon/xy.h + lemon/unionfind.h bits_HEADERS += \ lemon/bits/alteration_notifier.h \ diff -r c3ff11b0025c -r 75a29ac69c19 lemon/bits/bezier.h --- a/lemon/bits/bezier.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/bits/bezier.h Thu Sep 07 13:27:16 2006 +0000 @@ -27,26 +27,27 @@ /// ///\author Alpar Juttner -#include +#include namespace lemon { + namespace dim2 { class BezierBase { public: - typedef xy xy; + typedef Point Point; protected: - static xy conv(xy x,xy y,double t) {return (1-t)*x+t*y;} + static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;} }; class Bezier1 : public BezierBase { public: - xy p1,p2; + Point p1,p2; Bezier1() {} - Bezier1(xy _p1, xy _p2) :p1(_p1), p2(_p2) {} + Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {} - xy operator()(double t) const + Point operator()(double t) const { // return conv(conv(p1,p2,t),conv(p2,p3,t),t); return conv(p1,p2,t); @@ -63,59 +64,60 @@ Bezier1 revert() const { return Bezier1(p2,p1);} Bezier1 operator()(double a,double b) const { return before(b).after(a/b); } - xy grad() const { return p2-p1; } - xy norm() const { return rot90(p2-p1); } - xy grad(double) const { return grad(); } - xy norm(double t) const { return rot90(grad(t)); } + 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: - xy p1,p2,p3; + Point p1,p2,p3; Bezier2() {} - Bezier2(xy _p1, xy _p2, xy _p3) :p1(_p1), p2(_p2), p3(_p3) {} + 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) {} - xy operator()(double t) const + 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 { - xy q(conv(p1,p2,t)); - xy r(conv(p2,p3,t)); + 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 { - xy q(conv(p1,p2,t)); - xy r(conv(p2,p3,t)); + Point q(conv(p1,p2,t)); + Point r(conv(p2,p3,t)); return Bezier2(conv(q,r,t),r,p3); } Bezier2 revert() const { return Bezier2(p3,p2,p1);} Bezier2 operator()(double a,double b) const { return before(b).after(a/b); } Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); } Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); } - xy grad(double t) const { return grad()(t); } - xy norm(double t) const { return rot90(grad(t)); } + Point grad(double t) const { return grad()(t); } + Point norm(double t) const { return rot90(grad(t)); } }; class Bezier3 : public BezierBase { public: - xy p1,p2,p3,p4; + Point p1,p2,p3,p4; Bezier3() {} - Bezier3(xy _p1, xy _p2, xy _p3, xy _p4) :p1(_p1), p2(_p2), p3(_p3), p4(_p4) {} + Bezier3(Point _p1, Point _p2, Point _p3, Point _p4) + : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {} Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {} Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)), p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {} - xy operator()(double t) const + Point operator()(double t) const { // return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t); return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+ @@ -123,23 +125,23 @@ } Bezier3 before(double t) const { - xy p(conv(p1,p2,t)); - xy q(conv(p2,p3,t)); - xy r(conv(p3,p4,t)); - xy a(conv(p,q,t)); - xy b(conv(q,r,t)); - xy c(conv(a,b,t)); + Point p(conv(p1,p2,t)); + Point q(conv(p2,p3,t)); + Point r(conv(p3,p4,t)); + Point a(conv(p,q,t)); + Point b(conv(q,r,t)); + Point c(conv(a,b,t)); return Bezier3(p1,p,a,c); } Bezier3 after(double t) const { - xy p(conv(p1,p2,t)); - xy q(conv(p2,p3,t)); - xy r(conv(p3,p4,t)); - xy a(conv(p,q,t)); - xy b(conv(q,r,t)); - xy c(conv(a,b,t)); + Point p(conv(p1,p2,t)); + Point q(conv(p2,p3,t)); + Point r(conv(p3,p4,t)); + Point a(conv(p,q,t)); + Point b(conv(q,r,t)); + Point c(conv(a,b,t)); return Bezier3(c,b,r,p4); } Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);} @@ -148,18 +150,18 @@ Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1), 3.0*rot90(p3-p2), 3.0*rot90(p4-p3)); } - xy grad(double t) const { return grad()(t); } - xy norm(double t) const { return rot90(grad(t)); } + Point grad(double t) const { return grad()(t); } + Point norm(double t) const { return rot90(grad(t)); } template R recSplit(F &_f,const S &_s,D _d) const { - const xy a=(p1+p2)/2; - const xy b=(p2+p3)/2; - const xy c=(p3+p4)/2; - const xy d=(a+b)/2; - const xy e=(b+c)/2; - const xy f=(d+e)/2; + const Point a=(p1+p2)/2; + const Point b=(p2+p3)/2; + const Point c=(p3+p4)/2; + const Point d=(a+b)/2; + const Point e=(b+c)/2; + const Point f=(d+e)/2; R f1=_f(Bezier3(p1,a,d,e),_d); R f2=_f(Bezier3(e,d,c,p4),_d); return _s(f1,f2); @@ -167,6 +169,8 @@ }; -} //END OF NAMESPACE LEMON + +} //END OF NAMESPACE dim2 +} //END OF NAMESPACE lemon #endif // LEMON_BEZIER_H diff -r c3ff11b0025c -r 75a29ac69c19 lemon/dim2.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lemon/dim2.h Thu Sep 07 13:27:16 2006 +0000 @@ -0,0 +1,655 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * 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_DIM2_H +#define LEMON_DIM2_H + +#include +#include + +///\ingroup misc +///\file +///\brief A simple two dimensional vector and a bounding box implementation +/// +/// The class \ref lemon::dim2::Point "dim2::Point" implements +///a two dimensional vector with the usual +/// operations. +/// +/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" +/// can be used to determine +/// the rectangular bounding box of a set of +/// \ref lemon::dim2::Point "dim2::Point"'s. +/// +///\author Attila Bernath + + +namespace lemon { + + ///Tools for handling two dimensional coordinates + + ///This namespace is a storage of several + ///tools for handling two dimensional coordinates + namespace dim2 { + + /// \addtogroup misc + /// @{ + + /// A simple two dimensional vector (plainvector) implementation + + /// A simple two dimensional vector (plainvector) implementation + ///with the usual vector + /// operators. + /// + template + class Point { + + public: + + typedef T Value; + + ///First co-ordinate + T x; + ///Second co-ordinate + T y; + + ///Default constructor + Point() {} + + ///Construct an instance from coordinates + Point(T a, T b) : x(a), y(b) { } + + + ///Conversion constructor + template Point(const Point&p) : x(p.x), y(p.y) {} + + ///Give back the square of the norm of the vector + T normSquare() const { + return x*x+y*y; + } + + ///Increment the left hand side by u + Point& operator +=(const Point& u) { + x += u.x; + y += u.y; + return *this; + } + + ///Decrement the left hand side by u + Point& operator -=(const Point& u) { + x -= u.x; + y -= u.y; + return *this; + } + + ///Multiply the left hand side with a scalar + Point& operator *=(const T &u) { + x *= u; + y *= u; + return *this; + } + + ///Divide the left hand side by a scalar + Point& operator /=(const T &u) { + x /= u; + y /= u; + return *this; + } + + ///Return the scalar product of two vectors + T operator *(const Point& u) const { + return x*u.x+y*u.y; + } + + ///Return the sum of two vectors + Point operator+(const Point &u) const { + Point b=*this; + return b+=u; + } + + ///Return the neg of the vectors + Point operator-() const { + Point b=*this; + b.x=-b.x; b.y=-b.y; + return b; + } + + ///Return the difference of two vectors + Point operator-(const Point &u) const { + Point b=*this; + return b-=u; + } + + ///Return a vector multiplied by a scalar + Point operator*(const T &u) const { + Point b=*this; + return b*=u; + } + + ///Return a vector divided by a scalar + Point operator/(const T &u) const { + Point b=*this; + return b/=u; + } + + ///Test equality + bool operator==(const Point &u) const { + return (x==u.x) && (y==u.y); + } + + ///Test inequality + bool operator!=(Point u) const { + return (x!=u.x) || (y!=u.y); + } + + }; + + ///Return an Point + + ///Return an Point + ///\relates Point + template + inline Point make_Point(const T& x, const T& y) { + return Point(x, y); + } + + ///Return a vector multiplied by a scalar + + ///Return a vector multiplied by a scalar + ///\relates Point + template Point operator*(const T &u,const Point &x) { + return x*u; + } + + ///Read a plainvector from a stream + + ///Read a plainvector from a stream + ///\relates Point + /// + template + inline std::istream& operator>>(std::istream &is, Point &z) { + char c; + if (is >> c) { + if (c != '(') is.putback(c); + } else { + is.clear(); + } + if (!(is >> z.x)) return is; + if (is >> c) { + if (c != ',') is.putback(c); + } else { + is.clear(); + } + if (!(is >> z.y)) return is; + if (is >> c) { + if (c != ')') is.putback(c); + } else { + is.clear(); + } + return is; + } + + ///Write a plainvector to a stream + + ///Write a plainvector to a stream + ///\relates Point + /// + template + inline std::ostream& operator<<(std::ostream &os, const Point& z) + { + os << "(" << z.x << ", " << z.y << ")"; + return os; + } + + ///Rotate by 90 degrees + + ///Returns its parameter rotated by 90 degrees in positive direction. + ///\relates Point + /// + template + inline Point rot90(const Point &z) + { + return Point(-z.y,z.x); + } + + ///Rotate by 180 degrees + + ///Returns its parameter rotated by 180 degrees. + ///\relates Point + /// + template + inline Point rot180(const Point &z) + { + return Point(-z.x,-z.y); + } + + ///Rotate by 270 degrees + + ///Returns its parameter rotated by 90 degrees in negative direction. + ///\relates Point + /// + template + inline Point rot270(const Point &z) + { + return Point(z.y,-z.x); + } + + + + /// A class to calculate or store the bounding box of plainvectors. + + /// A class to calculate or store the bounding box of plainvectors. + /// + ///\author Attila Bernath + template + class BoundingBox { + Point bottom_left, top_right; + bool _empty; + public: + + ///Default constructor: creates an empty bounding box + BoundingBox() { _empty = true; } + + ///Construct an instance from one point + BoundingBox(Point a) { bottom_left=top_right=a; _empty = false; } + + ///Were any points added? + bool empty() const { + return _empty; + } + + ///Make the BoundingBox empty + void clear() { + _empty=1; + } + + ///Give back the bottom left corner + + ///Give back the bottom left corner. + ///If the bounding box is empty, then the return value is not defined. + Point bottomLeft() const { + return bottom_left; + } + + ///Set the bottom left corner + + ///Set the bottom left corner. + ///It should only bee used for non-empty box. + void bottomLeft(Point p) { + bottom_left = p; + } + + ///Give back the top right corner + + ///Give back the top right corner. + ///If the bounding box is empty, then the return value is not defined. + Point topRight() const { + return top_right; + } + + ///Set the top right corner + + ///Set the top right corner. + ///It should only bee used for non-empty box. + void topRight(Point p) { + top_right = p; + } + + ///Give back the bottom right corner + + ///Give back the bottom right corner. + ///If the bounding box is empty, then the return value is not defined. + Point bottomRight() const { + return Point(top_right.x,bottom_left.y); + } + + ///Set the bottom right corner + + ///Set the bottom right corner. + ///It should only bee used for non-empty box. + void bottomRight(Point p) { + top_right.x = p.x; + bottom_left.y = p.y; + } + + ///Give back the top left corner + + ///Give back the top left corner. + ///If the bounding box is empty, then the return value is not defined. + Point topLeft() const { + return Point(bottom_left.x,top_right.y); + } + + ///Set the top left corner + + ///Set the top left corner. + ///It should only bee used for non-empty box. + void topLeft(Point p) { + top_right.y = p.y; + bottom_left.x = p.x; + } + + ///Give back the bottom of the box + + ///Give back the bottom of the box. + ///If the bounding box is empty, then the return value is not defined. + T bottom() const { + return bottom_left.y; + } + + ///Set the bottom of the box + + ///Set the bottom of the box. + ///It should only bee used for non-empty box. + void bottom(T t) { + bottom_left.y = t; + } + + ///Give back the top of the box + + ///Give back the top of the box. + ///If the bounding box is empty, then the return value is not defined. + T top() const { + return top_right.y; + } + + ///Set the top of the box + + ///Set the top of the box. + ///It should only bee used for non-empty box. + void top(T t) { + top_right.y = t; + } + + ///Give back the left side of the box + + ///Give back the left side of the box. + ///If the bounding box is empty, then the return value is not defined. + T left() const { + return bottom_left.x; + } + + ///Set the left side of the box + + ///Set the left side of the box. + ///It should only bee used for non-empty box + void left(T t) { + bottom_left.x = t; + } + + /// Give back the right side of the box + + /// Give back the right side of the box. + ///If the bounding box is empty, then the return value is not defined. + T right() const { + return top_right.x; + } + + ///Set the right side of the box + + ///Set the right side of the box. + ///It should only bee used for non-empty box + void right(T t) { + top_right.x = t; + } + + ///Give back the height of the box + + ///Give back the height of the box. + ///If the bounding box is empty, then the return value is not defined. + T height() const { + return top_right.y-bottom_left.y; + } + + ///Give back the width of the box + + ///Give back the width of the box. + ///If the bounding box is empty, then the return value is not defined. + T width() const { + return top_right.x-bottom_left.x; + } + + ///Checks whether a point is inside a bounding box + bool inside(const Point& u){ + if (_empty) + return false; + else{ + return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && + (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); + } + } + + ///Increments a bounding box with a point + BoundingBox& add(const Point& u){ + if (_empty){ + bottom_left=top_right=u; + _empty = false; + } + else{ + if (bottom_left.x > u.x) bottom_left.x = u.x; + if (bottom_left.y > u.y) bottom_left.y = u.y; + if (top_right.x < u.x) top_right.x = u.x; + if (top_right.y < u.y) top_right.y = u.y; + } + return *this; + } + +// ///Sums a bounding box and a point +// BoundingBox operator +(const Point& u){ +// BoundingBox b = *this; +// return b += u; +// } + + ///Increments a bounding box with another bounding box + BoundingBox& add(const BoundingBox &u){ + if ( !u.empty() ){ + this->add(u.bottomLeft()); + this->add(u.topRight()); + } + return *this; + } + + ///Sums two bounding boxes + BoundingBox operator +(const BoundingBox& u){ + BoundingBox b = *this; + return b.add(u); + } + + + ///Intersection of two bounding boxes + BoundingBox operator &(const BoundingBox& u){ + BoundingBox b; + b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); + b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); + b.top_right.x=std::min(this->top_right.x,u.top_right.x); + b.top_right.y=std::min(this->top_right.y,u.top_right.y); + b._empty = this->_empty || u._empty || + b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y; + return b; + } + + };//class Boundingbox + + + ///Map of x-coordinates of a dim2::Point<>-map + + ///\ingroup maps + /// + template + class XMap + { + M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + XMap(M& map) : _map(map) {} + Value operator[](Key k) const {return _map[k].x;} + void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} + }; + + ///Returns an \ref XMap class + + ///This function just returns an \ref XMap class. + /// + ///\ingroup maps + ///\relates XMap + template + inline XMap xMap(M &m) + { + return XMap(m); + } + + template + inline XMap xMap(const M &m) + { + return XMap(m); + } + + ///Constant (read only) version of \ref XMap + + ///\ingroup maps + /// + template + class ConstXMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + ConstXMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].x;} + }; + + ///Returns a \ref ConstXMap class + + ///This function just returns an \ref ConstXMap class. + /// + ///\ingroup maps + ///\relates ConstXMap + template + inline ConstXMap xMap(const M &m) + { + return ConstXMap(m); + } + + ///Map of y-coordinates of a dim2::Point<>-map + + ///\ingroup maps + /// + template + class YMap + { + M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + YMap(M& map) : _map(map) {} + Value operator[](Key k) const {return _map[k].y;} + void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} + }; + + ///Returns an \ref YMap class + + ///This function just returns an \ref YMap class. + /// + ///\ingroup maps + ///\relates YMap + template + inline YMap yMap(M &m) + { + return YMap(m); + } + + template + inline YMap yMap(const M &m) + { + return YMap(m); + } + + ///Constant (read only) version of \ref YMap + + ///\ingroup maps + /// + template + class ConstYMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + ConstYMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].y;} + }; + + ///Returns a \ref ConstYMap class + + ///This function just returns an \ref ConstYMap class. + /// + ///\ingroup maps + ///\relates ConstYMap + template + inline ConstYMap yMap(const M &m) + { + return ConstYMap(m); + } + + + ///Map of the \ref Point::normSquare() "normSquare()" of an \ref Point "Point"-map + + ///Map of the \ref Point::normSquare() "normSquare()" of an \ref Point "Point"-map + ///\ingroup maps + /// + template + class NormSquareMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + NormSquareMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].normSquare();} + }; + + ///Returns a \ref NormSquareMap class + + ///This function just returns an \ref NormSquareMap class. + /// + ///\ingroup maps + ///\relates NormSquareMap + template + inline NormSquareMap normSquareMap(const M &m) + { + return NormSquareMap(m); + } + + /// @} + + } //namespce dim2 + +} //namespace lemon + +#endif //LEMON_DIM2_H diff -r c3ff11b0025c -r 75a29ac69c19 lemon/eps.cc --- a/lemon/eps.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/eps.cc Thu Sep 07 13:27:16 2006 +0000 @@ -69,13 +69,13 @@ init(x1,y1,x2,y2); } - EpsDrawer::EpsDrawer(std::ostream &os,xy s) : local_stream(false), + EpsDrawer::EpsDrawer(std::ostream &os,dim2::Point s) : local_stream(false), out(os) { init(0.0,0.0,s.x,s.y); } - EpsDrawer::EpsDrawer(std::ostream &os,xy a, xy b) : + EpsDrawer::EpsDrawer(std::ostream &os,dim2::Point a, dim2::Point b) : local_stream(false), out(os) { @@ -97,14 +97,14 @@ init(x1,y1,x2,y2); } - EpsDrawer::EpsDrawer(const std::string &name,xy s) : + EpsDrawer::EpsDrawer(const std::string &name,dim2::Point s) : local_stream(true), out(*new std::ofstream(name.c_str())) { init(0.0,0.0,s.x,s.y); } - EpsDrawer::EpsDrawer(const std::string &name,xy a, xy b) : + EpsDrawer::EpsDrawer(const std::string &name,dim2::Point a, dim2::Point b) : local_stream(true), out(*new std::ofstream(name.c_str())) { diff -r c3ff11b0025c -r 75a29ac69c19 lemon/eps.h --- a/lemon/eps.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/eps.h Thu Sep 07 13:27:16 2006 +0000 @@ -24,7 +24,7 @@ #include #include #include -#include +#include ///\ingroup eps_io ///\file @@ -100,7 +100,7 @@ /// ///\c s determines the upper ///right corner of the bounding box. The lower left corner is (0,0). - EpsDrawer(std::ostream &os,xy s); + EpsDrawer(std::ostream &os,dim2::Point s); ///\e ///The generated file is put to \c os. @@ -108,7 +108,7 @@ ///\c a and \c b /// determine the lower left and the upper right corners of ///the bounding box, respectively. - EpsDrawer(std::ostream &os,xy a, xy b); + EpsDrawer(std::ostream &os,dim2::Point a, dim2::Point b); ///\e ///The generated picture is put to the file \c name. @@ -130,7 +130,7 @@ /// ///\c s determines the upper ///right corner of the bounding box. The lower left corner is (0,0). - EpsDrawer(const std::string &name,xy s); + EpsDrawer(const std::string &name,dim2::Point s); ///\e ///The generated picture is put to the file \c name. @@ -138,7 +138,7 @@ ///\c a and \c b /// determine the lower left and the upper right corners of ///the bounding box, respectively. - EpsDrawer(const std::string &name,xy a, xy b); + EpsDrawer(const std::string &name,dim2::Point a, dim2::Point b); // template EpsDrawer(std::ostream &os,BoundingBox b) // template EpsDrawer(std::ostream &os,BoundingBox b); @@ -168,22 +168,22 @@ EpsDrawer &circle(double x,double y, double r); ///Draw a line - template EpsDrawer &line(xy p1,xy p2) + template EpsDrawer &line(dim2::Point p1,dim2::Point p2) { return line(p1.x,p1.y,p2.x,p2.y); } ///Draw a line from the current point - template EpsDrawer &lineTo(xy p) + template EpsDrawer &lineTo(dim2::Point p) { return lineTo(p.x,p.y); } ///Move the current point - template EpsDrawer &moveTo(xy p) + template EpsDrawer &moveTo(dim2::Point p) { return moveTo(p.x,p.y); } ///Draw a circle - template EpsDrawer &circle(xy p, double r) + template EpsDrawer &circle(dim2::Point p, double r) { return circle(p.x,p.y,r); } @@ -296,7 +296,7 @@ ///\param col Color of the node. The default color is white ///\param brd Color of the node border. The default color is black template - EpsDrawer &node(NodeShapes t, xy pos, double r, + EpsDrawer &node(NodeShapes t, dim2::Point pos, double r, Color col=WHITE, Color brd=BLACK) { return node(t,pos.x,pos.y,r,col,brd); @@ -305,7 +305,7 @@ ///Translate the coordinate system EpsDrawer &translate(double x,double y); ///Translate the coordinate system - template EpsDrawer &translate(xy p) + template EpsDrawer &translate(dim2::Point p) { return translate(p.x,p.y); } @@ -316,7 +316,7 @@ ///Scale the coordinate system EpsDrawer &scale(double s) { return scale(s,s); } ///Scale the coordinate system - template EpsDrawer &scale(xy p) + template EpsDrawer &scale(dim2::Point p) { return scale(p.x,p.y); } @@ -336,7 +336,7 @@ EpsDrawer &operator<<(double d); ///Print a coordinate at the current point template - EpsDrawer &operator<<(xy p) + EpsDrawer &operator<<(dim2::Point p) { out << "((" << p.x << ',' << p.y <<")) show\n"; return *this; diff -r c3ff11b0025c -r 75a29ac69c19 lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/graph_to_eps.h Thu Sep 07 13:27:16 2006 +0000 @@ -35,7 +35,7 @@ #include #include -#include +#include #include #include #include @@ -81,7 +81,7 @@ std::ostream& os; - typedef ConstMap > CoordsMapType; + typedef ConstMap > CoordsMapType; CoordsMapType _coords; ConstMap _nodeSizes; ConstMap _nodeShapes; @@ -146,7 +146,7 @@ DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout, bool _pros=false) : g(_g), os(_os), - _coords(xy(1,1)), _nodeSizes(.01), _nodeShapes(0), + _coords(dim2::Point(1,1)), _nodeSizes(.01), _nodeShapes(0), _nodeColors(WHITE), _edgeColors(BLACK), _edgeWidths(1.0), _edgeWidthScale(0.003), _nodeScale(1.0), _xBorder(10), _yBorder(10), _scale(1.0), @@ -313,7 +313,7 @@ g.target(e)==g.source(f)); } template - static std::string psOut(const xy &p) + static std::string psOut(const dim2::Point &p) { std::ostringstream os; os << p.x << ' ' << p.y; @@ -337,7 +337,8 @@ ///Sets the map of the node coordinates ///Sets the map of the node coordinates. - ///\param x must be a node map with xy or \ref xy "xy" values. + ///\param x must be a node map with dim2::Point or + ///\ref dim2::Point "dim2::Point" values. template GraphToEps > coords(const X &x) { dontPrint=true; return GraphToEps >(CoordsTraits(*this,x)); @@ -669,7 +670,7 @@ GraphToEps ©right(const std::string &t) {_copyright=t;return *this;} protected: - bool isInsideNode(xy p, double r,int t) + bool isInsideNode(dim2::Point p, double r,int t) { switch(t) { case CIRCLE: @@ -736,10 +737,10 @@ double diag_len = 1; if(!(_absoluteNodeSizes&&_absoluteEdgeWidths)) { - BoundingBox bb; + dim2::BoundingBox bb; for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]); if (bb.empty()) { - bb = BoundingBox(xy(0,0)); + bb = dim2::BoundingBox(dim2::Point(0,0)); } diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare()); if(diag_len bb; + dim2::BoundingBox bb; for(NodeIt n(g);n!=INVALID;++n) { double ns=_nodeSizes[n]*_nodeScale; - xy p(ns,ns); + dim2::Point p(ns,ns); switch(_nodeShapes[n]) { case CIRCLE: case SQUARE: @@ -760,16 +761,16 @@ break; case MALE: bb.add(-p+mycoords[n]); - bb.add(xy(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]); + bb.add(dim2::Point(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]); break; case FEMALE: bb.add(p+mycoords[n]); - bb.add(xy(-ns,-3.01*ns)+mycoords[n]); + bb.add(dim2::Point(-ns,-3.01*ns)+mycoords[n]); break; } } if (bb.empty()) { - bb = BoundingBox(xy(0,0)); + bb = dim2::BoundingBox(dim2::Point(0,0)); } if(_scaleToA4) @@ -870,7 +871,8 @@ double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(), (A4WIDTH-2*A4BORDER)/bb.width()); os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' ' - << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER << " translate\n" + << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER + << " translate\n" << sc << " dup scale\n" << -bb.left() << ' ' << -bb.bottom() << " translate\n"; } @@ -879,7 +881,8 @@ double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(), (A4WIDTH-2*A4BORDER)/bb.height()); os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' ' - << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER << " translate\n" + << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER + << " translate\n" << sc << " dup scale\n90 rotate\n" << -bb.left() << ' ' << -bb.top() << " translate\n"; } @@ -904,42 +907,43 @@ sw+=_edgeWidths[*e]*_edgeWidthScale+_parEdgeDist; sw-=_parEdgeDist; sw/=-2.0; - xy dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]); + dim2::Point + dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]); double l=std::sqrt(dvec.normSquare()); ///\todo better 'epsilon' would be nice here. - xy d(dvec/std::max(l,EPSILON)); - xy m; -// m=xy(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0; + dim2::Point d(dvec/std::max(l,EPSILON)); + dim2::Point m; +// m=dim2::Point(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0; -// m=xy(mycoords[g.source(*i)])+ +// m=dim2::Point(mycoords[g.source(*i)])+ // dvec*(double(_nodeSizes[g.source(*i)])/ // (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)])); - m=xy(mycoords[g.source(*i)])+ + m=dim2::Point(mycoords[g.source(*i)])+ d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0; for(typename std::vector::iterator e=i;e!=j;++e) { sw+=_edgeWidths[*e]*_edgeWidthScale/2.0; - xy mm=m+rot90(d)*sw/.75; + dim2::Point mm=m+rot90(d)*sw/.75; if(_drawArrows) { int node_shape; - xy s=mycoords[g.source(*e)]; - xy t=mycoords[g.target(*e)]; + dim2::Point s=mycoords[g.source(*e)]; + dim2::Point t=mycoords[g.target(*e)]; double rn=_nodeSizes[g.target(*e)]*_nodeScale; node_shape=_nodeShapes[g.target(*e)]; - Bezier3 bez(s,mm,mm,t); + dim2::Bezier3 bez(s,mm,mm,t); double t1=0,t2=1; for(int i=0;i apoint=bez((t1+t2)/2); + dim2::Point apoint=bez((t1+t2)/2); rn = _arrowLength+_edgeWidths[*e]*_edgeWidthScale; rn*=rn; t2=(t1+t2)/2;t1=0; for(int i=0;irn) t1=(t1+t2)/2; else t2=(t1+t2)/2; - xy linend=bez((t1+t2)/2); + dim2::Point linend=bez((t1+t2)/2); bez=bez.before((t1+t2)/2); // rn=_nodeSizes[g.source(*e)]*_nodeScale; // node_shape=_nodeShapes[g.source(*e)]; @@ -956,7 +960,7 @@ << bez.p2.x << ' ' << bez.p2.y << ' ' << bez.p3.x << ' ' << bez.p3.y << ' ' << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n"; - xy dd(rot90(linend-apoint)); + dim2::Point dd(rot90(linend-apoint)); dd*=(.5*_edgeWidths[*e]*_edgeWidthScale+_arrowWidth)/ std::sqrt(dd.normSquare()); os << "newpath " << psOut(apoint) << " moveto " @@ -982,7 +986,7 @@ if((!_undirected||g.source(e)0 &&g.source(e)!=g.target(e)) if(_drawArrows) { - xy d(mycoords[g.target(e)]-mycoords[g.source(e)]); + dim2::Point 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; diff -r c3ff11b0025c -r 75a29ac69c19 lemon/grid_ugraph.h --- a/lemon/grid_ugraph.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/grid_ugraph.h Thu Sep 07 13:27:16 2006 +0000 @@ -26,7 +26,7 @@ #include #include -#include +#include ///\ingroup graphs ///\file @@ -381,15 +381,15 @@ typedef ExtendedGridUGraphBase Parent; - /// \brief Map to get the indices of the nodes as xy. + /// \brief Map to get the indices of the nodes as dim2::Point. /// - /// Map to get the indices of the nodes as xy. + /// Map to get the indices of the nodes as dim2::Point. class IndexMap { public: /// \brief The key type of the map typedef GridUGraph::Node Key; /// \brief The value type of the map - typedef xy Value; + typedef dim2::Point Value; /// \brief Constructor /// @@ -400,7 +400,7 @@ /// /// The subscript operator. Value operator[](Key key) const { - return xy(graph.row(key), graph.col(key)); + return dim2::Point(graph.row(key), graph.col(key)); } private: diff -r c3ff11b0025c -r 75a29ac69c19 lemon/hypercube_graph.h --- a/lemon/hypercube_graph.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/hypercube_graph.h Thu Sep 07 13:27:16 2006 +0000 @@ -275,13 +275,13 @@ ///\code /// const int DIM = 3; /// HyperCubeGraph graph(DIM); - /// xy base[DIM]; + /// dim2::Point base[DIM]; /// for (int k = 0; k < DIM; ++k) { /// base[k].x = rand() / (RAND_MAX + 1.0); /// base[k].y = rand() / (RAND_MAX + 1.0); /// } - /// HyperCubeGraph::HyperMap > - /// pos(graph, base, base + DIM, xy(0.0, 0.0)); + /// HyperCubeGraph::HyperMap > + /// pos(graph, base, base + DIM, dim2::Point(0.0, 0.0)); ///\endcode /// /// \see HyperCubeGraph diff -r c3ff11b0025c -r 75a29ac69c19 lemon/lemon_reader.h --- a/lemon/lemon_reader.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/lemon_reader.h Thu Sep 07 13:27:16 2006 +0000 @@ -38,7 +38,7 @@ #include #include -#include +#include #include #include @@ -183,21 +183,21 @@ }; template - struct Ref > { - typedef XMap Type; + struct Ref > { + typedef dim2::XMap Type; }; template - struct Arg > { - typedef const XMap& Type; + struct Arg > { + typedef const dim2::XMap& Type; }; template - struct Ref > { - typedef YMap Type; + struct Ref > { + typedef dim2::YMap Type; }; template - struct Arg > { - typedef const YMap& Type; + struct Arg > { + typedef const dim2::YMap& Type; }; diff -r c3ff11b0025c -r 75a29ac69c19 lemon/lemon_writer.h --- a/lemon/lemon_writer.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/lemon_writer.h Thu Sep 07 13:27:16 2006 +0000 @@ -37,7 +37,7 @@ #include #include #include -#include +#include #include #include @@ -173,21 +173,21 @@ }; template - struct Ref > { - typedef XMap Type; + struct Ref > { + typedef dim2::XMap Type; }; template - struct Ref > { - typedef ConstXMap Type; + struct Ref > { + typedef dim2::ConstXMap Type; }; template - struct Ref > { - typedef YMap Type; + struct Ref > { + typedef dim2::YMap Type; }; template - struct Ref > { - typedef ConstYMap Type; + struct Ref > { + typedef dim2::ConstYMap Type; }; diff -r c3ff11b0025c -r 75a29ac69c19 lemon/polynomial.h --- a/lemon/polynomial.h Wed Sep 06 11:39:22 2006 +0000 +++ b/lemon/polynomial.h Thu Sep 07 13:27:16 2006 +0000 @@ -76,11 +76,11 @@ ///The calculation will be done using type \c R. ///The following examples shows the usage of the template parameter \c R. ///\code - /// Polynomial > line(1); - /// line[0]=xy(12,25); - /// line[1]=xy(2,7); + /// Polynomial > line(1); + /// line[0]=dim2::Point(12,25); + /// line[1]=dim2::Point(2,7); /// ... - /// xy d = line.subst >(23.2); + /// dim2::Point d = line.subst >(23.2); ///\endcode /// ///\code diff -r c3ff11b0025c -r 75a29ac69c19 lemon/xy.h --- a/lemon/xy.h Wed Sep 06 11:39:22 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,654 +0,0 @@ -/* -*- C++ -*- - * - * This file is a part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2003-2006 - * 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_XY_H -#define LEMON_XY_H - -#include -#include - -///\ingroup misc -///\file -///\brief A simple two dimensional vector and a bounding box implementation -/// -/// The class \ref lemon::xy "xy" implements -///a two dimensional vector with the usual -/// operations. -/// -/// The class \ref lemon::BoundingBox "BoundingBox" can be used to determine -/// the rectangular bounding box of a set of \ref lemon::xy "xy"'s. -/// -///\author Attila Bernath - - -namespace lemon { - - /// \addtogroup misc - /// @{ - - /// A simple two dimensional vector (plainvector) implementation - - /// A simple two dimensional vector (plainvector) implementation - ///with the usual vector - /// operators. - /// - ///\note As you might have noticed, this class does not follow the - ///\ref naming_conv "LEMON Coding Style" (it should be called \c Xy - ///according to it). There is a stupid Hungarian proverb, "A kivétel - ///erõsíti a szabályt" ("An exception - ///reinforces a rule", which is - ///actually a mistranslation of the Latin proverb "Exceptio probat regulam"). - ///This class is an example for that. - ///\author Attila Bernath - template - class xy { - - public: - - typedef T Value; - - ///First co-ordinate - T x; - ///Second co-ordinate - T y; - - ///Default constructor - xy() {} - - ///Construct an instance from coordinates - xy(T a, T b) : x(a), y(b) { } - - - ///Conversion constructor - template xy(const xy &p) : x(p.x), y(p.y) {} - - ///Give back the square of the norm of the vector - T normSquare() const { - return x*x+y*y; - } - - ///Increment the left hand side by u - xy& operator +=(const xy& u) { - x += u.x; - y += u.y; - return *this; - } - - ///Decrement the left hand side by u - xy& operator -=(const xy& u) { - x -= u.x; - y -= u.y; - return *this; - } - - ///Multiply the left hand side with a scalar - xy& operator *=(const T &u) { - x *= u; - y *= u; - return *this; - } - - ///Divide the left hand side by a scalar - xy& operator /=(const T &u) { - x /= u; - y /= u; - return *this; - } - - ///Return the scalar product of two vectors - T operator *(const xy& u) const { - return x*u.x+y*u.y; - } - - ///Return the sum of two vectors - xy operator+(const xy &u) const { - xy b=*this; - return b+=u; - } - - ///Return the neg of the vectors - xy operator-() const { - xy b=*this; - b.x=-b.x; b.y=-b.y; - return b; - } - - ///Return the difference of two vectors - xy operator-(const xy &u) const { - xy b=*this; - return b-=u; - } - - ///Return a vector multiplied by a scalar - xy operator*(const T &u) const { - xy b=*this; - return b*=u; - } - - ///Return a vector divided by a scalar - xy operator/(const T &u) const { - xy b=*this; - return b/=u; - } - - ///Test equality - bool operator==(const xy &u) const { - return (x==u.x) && (y==u.y); - } - - ///Test inequality - bool operator!=(xy u) const { - return (x!=u.x) || (y!=u.y); - } - - }; - - ///Return an xy - - ///Return an xy - ///\relates xy - template - inline xy make_xy(const T& x, const T& y) { - return xy(x, y); - } - - ///Return a vector multiplied by a scalar - - ///Return a vector multiplied by a scalar - ///\relates xy - template xy operator*(const T &u,const xy &x) { - return x*u; - } - - ///Read a plainvector from a stream - - ///Read a plainvector from a stream - ///\relates xy - /// - template - inline std::istream& operator>>(std::istream &is, xy &z) { - char c; - if (is >> c) { - if (c != '(') is.putback(c); - } else { - is.clear(); - } - if (!(is >> z.x)) return is; - if (is >> c) { - if (c != ',') is.putback(c); - } else { - is.clear(); - } - if (!(is >> z.y)) return is; - if (is >> c) { - if (c != ')') is.putback(c); - } else { - is.clear(); - } - return is; - } - - ///Write a plainvector to a stream - - ///Write a plainvector to a stream - ///\relates xy - /// - template - inline std::ostream& operator<<(std::ostream &os, const xy& z) - { - os << "(" << z.x << ", " << z.y << ")"; - return os; - } - - ///Rotate by 90 degrees - - ///Returns its parameter rotated by 90 degrees in positive direction. - ///\relates xy - /// - template - inline xy rot90(const xy &z) - { - return xy(-z.y,z.x); - } - - ///Rotate by 180 degrees - - ///Returns its parameter rotated by 180 degrees. - ///\relates xy - /// - template - inline xy rot180(const xy &z) - { - return xy(-z.x,-z.y); - } - - ///Rotate by 270 degrees - - ///Returns its parameter rotated by 90 degrees in negative direction. - ///\relates xy - /// - template - inline xy rot270(const xy &z) - { - return xy(z.y,-z.x); - } - - - - /// A class to calculate or store the bounding box of plainvectors. - - /// A class to calculate or store the bounding box of plainvectors. - /// - ///\author Attila Bernath - template - class BoundingBox { - xy bottom_left, top_right; - bool _empty; - public: - - ///Default constructor: creates an empty bounding box - BoundingBox() { _empty = true; } - - ///Construct an instance from one point - BoundingBox(xy a) { bottom_left=top_right=a; _empty = false; } - - ///Were any points added? - bool empty() const { - return _empty; - } - - ///Make the BoundingBox empty - void clear() { - _empty=1; - } - - ///Give back the bottom left corner - - ///Give back the bottom left corner. - ///If the bounding box is empty, then the return value is not defined. - xy bottomLeft() const { - return bottom_left; - } - - ///Set the bottom left corner - - ///Set the bottom left corner. - ///It should only bee used for non-empty box. - void bottomLeft(xy p) { - bottom_left = p; - } - - ///Give back the top right corner - - ///Give back the top right corner. - ///If the bounding box is empty, then the return value is not defined. - xy topRight() const { - return top_right; - } - - ///Set the top right corner - - ///Set the top right corner. - ///It should only bee used for non-empty box. - void topRight(xy p) { - top_right = p; - } - - ///Give back the bottom right corner - - ///Give back the bottom right corner. - ///If the bounding box is empty, then the return value is not defined. - xy bottomRight() const { - return xy(top_right.x,bottom_left.y); - } - - ///Set the bottom right corner - - ///Set the bottom right corner. - ///It should only bee used for non-empty box. - void bottomRight(xy p) { - top_right.x = p.x; - bottom_left.y = p.y; - } - - ///Give back the top left corner - - ///Give back the top left corner. - ///If the bounding box is empty, then the return value is not defined. - xy topLeft() const { - return xy(bottom_left.x,top_right.y); - } - - ///Set the top left corner - - ///Set the top left corner. - ///It should only bee used for non-empty box. - void topLeft(xy p) { - top_right.y = p.y; - bottom_left.x = p.x; - } - - ///Give back the bottom of the box - - ///Give back the bottom of the box. - ///If the bounding box is empty, then the return value is not defined. - T bottom() const { - return bottom_left.y; - } - - ///Set the bottom of the box - - ///Set the bottom of the box. - ///It should only bee used for non-empty box. - void bottom(T t) { - bottom_left.y = t; - } - - ///Give back the top of the box - - ///Give back the top of the box. - ///If the bounding box is empty, then the return value is not defined. - T top() const { - return top_right.y; - } - - ///Set the top of the box - - ///Set the top of the box. - ///It should only bee used for non-empty box. - void top(T t) { - top_right.y = t; - } - - ///Give back the left side of the box - - ///Give back the left side of the box. - ///If the bounding box is empty, then the return value is not defined. - T left() const { - return bottom_left.x; - } - - ///Set the left side of the box - - ///Set the left side of the box. - ///It should only bee used for non-empty box - void left(T t) { - bottom_left.x = t; - } - - /// Give back the right side of the box - - /// Give back the right side of the box. - ///If the bounding box is empty, then the return value is not defined. - T right() const { - return top_right.x; - } - - ///Set the right side of the box - - ///Set the right side of the box. - ///It should only bee used for non-empty box - void right(T t) { - top_right.x = t; - } - - ///Give back the height of the box - - ///Give back the height of the box. - ///If the bounding box is empty, then the return value is not defined. - T height() const { - return top_right.y-bottom_left.y; - } - - ///Give back the width of the box - - ///Give back the width of the box. - ///If the bounding box is empty, then the return value is not defined. - T width() const { - return top_right.x-bottom_left.x; - } - - ///Checks whether a point is inside a bounding box - bool inside(const xy& u){ - if (_empty) - return false; - else{ - return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && - (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); - } - } - - ///Increments a bounding box with a point - BoundingBox& add(const xy& u){ - if (_empty){ - bottom_left=top_right=u; - _empty = false; - } - else{ - if (bottom_left.x > u.x) bottom_left.x = u.x; - if (bottom_left.y > u.y) bottom_left.y = u.y; - if (top_right.x < u.x) top_right.x = u.x; - if (top_right.y < u.y) top_right.y = u.y; - } - return *this; - } - -// ///Sums a bounding box and a point -// BoundingBox operator +(const xy& u){ -// BoundingBox b = *this; -// return b += u; -// } - - ///Increments a bounding box with another bounding box - BoundingBox& add(const BoundingBox &u){ - if ( !u.empty() ){ - this->add(u.bottomLeft()); - this->add(u.topRight()); - } - return *this; - } - - ///Sums two bounding boxes - BoundingBox operator +(const BoundingBox& u){ - BoundingBox b = *this; - return b.add(u); - } - - - ///Intersection of two bounding boxes - BoundingBox operator &(const BoundingBox& u){ - BoundingBox b; - b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); - b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); - b.top_right.x=std::min(this->top_right.x,u.top_right.x); - b.top_right.y=std::min(this->top_right.y,u.top_right.y); - b._empty = this->_empty || u._empty || - b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y; - return b; - } - - };//class Boundingbox - - - ///Map of x-coordinates of an xy<>-map - - ///\ingroup maps - /// - template - class XMap - { - M& _map; - public: - - typedef typename M::Value::Value Value; - typedef typename M::Key Key; - ///\e - XMap(M& map) : _map(map) {} - Value operator[](Key k) const {return _map[k].x;} - void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} - }; - - ///Returns an \ref XMap class - - ///This function just returns an \ref XMap class. - /// - ///\ingroup maps - ///\relates XMap - template - inline XMap xMap(M &m) - { - return XMap(m); - } - - template - inline XMap xMap(const M &m) - { - return XMap(m); - } - - ///Constant (read only) version of \ref XMap - - ///\ingroup maps - /// - template - class ConstXMap - { - const M& _map; - public: - - typedef typename M::Value::Value Value; - typedef typename M::Key Key; - ///\e - ConstXMap(const M &map) : _map(map) {} - Value operator[](Key k) const {return _map[k].x;} - }; - - ///Returns a \ref ConstXMap class - - ///This function just returns an \ref ConstXMap class. - /// - ///\ingroup maps - ///\relates ConstXMap - template - inline ConstXMap xMap(const M &m) - { - return ConstXMap(m); - } - - ///Map of y-coordinates of an xy<>-map - - ///\ingroup maps - /// - template - class YMap - { - M& _map; - public: - - typedef typename M::Value::Value Value; - typedef typename M::Key Key; - ///\e - YMap(M& map) : _map(map) {} - Value operator[](Key k) const {return _map[k].y;} - void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} - }; - - ///Returns an \ref YMap class - - ///This function just returns an \ref YMap class. - /// - ///\ingroup maps - ///\relates YMap - template - inline YMap yMap(M &m) - { - return YMap(m); - } - - template - inline YMap yMap(const M &m) - { - return YMap(m); - } - - ///Constant (read only) version of \ref YMap - - ///\ingroup maps - /// - template - class ConstYMap - { - const M& _map; - public: - - typedef typename M::Value::Value Value; - typedef typename M::Key Key; - ///\e - ConstYMap(const M &map) : _map(map) {} - Value operator[](Key k) const {return _map[k].y;} - }; - - ///Returns a \ref ConstYMap class - - ///This function just returns an \ref ConstYMap class. - /// - ///\ingroup maps - ///\relates ConstYMap - template - inline ConstYMap yMap(const M &m) - { - return ConstYMap(m); - } - - - ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map - - ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map - ///\ingroup maps - /// - template - class NormSquareMap - { - const M& _map; - public: - - typedef typename M::Value::Value Value; - typedef typename M::Key Key; - ///\e - NormSquareMap(const M &map) : _map(map) {} - Value operator[](Key k) const {return _map[k].normSquare();} - }; - - ///Returns a \ref NormSquareMap class - - ///This function just returns an \ref NormSquareMap class. - /// - ///\ingroup maps - ///\relates NormSquareMap - template - inline NormSquareMap normSquareMap(const M &m) - { - return NormSquareMap(m); - } - - /// @} - - -} //namespace lemon - -#endif //LEMON_XY_H diff -r c3ff11b0025c -r 75a29ac69c19 test/Makefile.am --- a/test/Makefile.am Wed Sep 06 11:39:22 2006 +0000 +++ b/test/Makefile.am Thu Sep 07 13:27:16 2006 +0000 @@ -18,6 +18,7 @@ test/counter_test \ test/dfs_test \ test/dijkstra_test \ + test/dim_test \ test/edge_set_test \ test/graph_adaptor_test \ test/graph_test \ @@ -39,8 +40,7 @@ test/test_tools_pass \ test/time_measure_test \ test/ugraph_test \ - test/unionfind_test \ - test/xy_test + test/unionfind_test if HAVE_GLPK check_PROGRAMS += test/lp_test test/mip_test @@ -60,6 +60,7 @@ test_counter_test_SOURCES = test/counter_test.cc test_dfs_test_SOURCES = test/dfs_test.cc test_dijkstra_test_SOURCES = test/dijkstra_test.cc +test_dim_test_SOURCES = test/dim_test.cc test_edge_set_test_SOURCES = test/edge_set_test.cc test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc test_graph_test_SOURCES = test/graph_test.cc @@ -82,7 +83,6 @@ test_time_measure_test_SOURCES = test/time_measure_test.cc test_ugraph_test_SOURCES = test/ugraph_test.cc test_unionfind_test_SOURCES = test/unionfind_test.cc -test_xy_test_SOURCES = test/xy_test.cc test_lp_test_SOURCES = test/lp_test.cc test_lp_test_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) diff -r c3ff11b0025c -r 75a29ac69c19 test/dim_test.cc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/dim_test.cc Thu Sep 07 13:27:16 2006 +0000 @@ -0,0 +1,82 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2006 + * 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. + * + */ + +#include +#include +#include "test_tools.h" + +using namespace std; +using namespace lemon; +int main() +{ + + cout << "Testing classes `dim2::Point' and `dim2::BoundingBox'." << endl; + + typedef dim2::Point Point; + + Point seged; + Point a(1,2); + Point b(3,4); + + seged = a+b; + check(seged.x==4 && seged.y==6, "Wrong vector addition"); + + seged = a-b; + check(seged.x==-2 && seged.y==-2, "a-b"); + + check(a.normSquare()==5,"Wrong norm calculation"); + check(a*b==11, "a*b"); + + int l=2; + seged = a*l; + check(seged.x==2 && seged.y==4, "a*l"); + + seged = b/l; + check(seged.x==1 && seged.y==2, "b/l"); + + typedef dim2::BoundingBox BB; + BB doboz1; + check(doboz1.empty(), "It should be empty."); + + doboz1.add(a); + check(!doboz1.empty(), "It should not be empty."); + doboz1.add(b); + + check(doboz1.bottomLeft().x==1 && + doboz1.bottomLeft().y==2 && + doboz1.topRight().x==3 && + doboz1.topRight().y==4, + "added points to box"); + + seged.x=2;seged.y=3; + check(doboz1.inside(seged),"It should be inside."); + + seged.x=1;seged.y=3; + check(doboz1.inside(seged),"It should be inside."); + + seged.x=0;seged.y=3; + check(!doboz1.inside(seged),"It should not be inside."); + + BB doboz2(seged); + check(!doboz2.empty(), + "It should not be empty. Constructed from 1 point."); + + doboz2.add(doboz1); + check(doboz2.inside(seged), + "It should be inside. Incremented a box with another one."); +} diff -r c3ff11b0025c -r 75a29ac69c19 test/polynomial_test.cc --- a/test/polynomial_test.cc Wed Sep 06 11:39:22 2006 +0000 +++ b/test/polynomial_test.cc Thu Sep 07 13:27:16 2006 +0000 @@ -17,7 +17,7 @@ */ #include -#include +#include #include #include "test_tools.h" diff -r c3ff11b0025c -r 75a29ac69c19 test/xy_test.cc --- a/test/xy_test.cc Wed Sep 06 11:39:22 2006 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,82 +0,0 @@ -/* -*- C++ -*- - * - * This file is a part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2003-2006 - * 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. - * - */ - -#include -#include -#include "test_tools.h" - -using namespace std; -using namespace lemon; -int main() -{ - - cout << "Testing classes `xy' and `boundingbox'." << endl; - - typedef xy XY; - - XY seged; - XY a(1,2); - XY b(3,4); - - seged = a+b; - check(seged.x==4 && seged.y==6, "Wrong vector addition"); - - seged = a-b; - check(seged.x==-2 && seged.y==-2, "a-b"); - - check(a.normSquare()==5,"Wrong norm calculation"); - check(a*b==11, "a*b"); - - int l=2; - seged = a*l; - check(seged.x==2 && seged.y==4, "a*l"); - - seged = b/l; - check(seged.x==1 && seged.y==2, "b/l"); - - typedef BoundingBox BB; - BB doboz1; - check(doboz1.empty(), "It should be empty."); - - doboz1.add(a); - check(!doboz1.empty(), "It should not be empty."); - doboz1.add(b); - - check(doboz1.bottomLeft().x==1 && - doboz1.bottomLeft().y==2 && - doboz1.topRight().x==3 && - doboz1.topRight().y==4, - "added points to box"); - - seged.x=2;seged.y=3; - check(doboz1.inside(seged),"It should be inside."); - - seged.x=1;seged.y=3; - check(doboz1.inside(seged),"It should be inside."); - - seged.x=0;seged.y=3; - check(!doboz1.inside(seged),"It should not be inside."); - - BB doboz2(seged); - check(!doboz2.empty(), - "It should not be empty. Constructed from 1 point."); - - doboz2.add(doboz1); - check(doboz2.inside(seged), - "It should be inside. Incremented a box with another one."); -}