1.1 --- a/benchmark/swap_bipartite_bench.cc Wed Sep 06 11:39:22 2006 +0000
1.2 +++ b/benchmark/swap_bipartite_bench.cc Thu Sep 07 13:27:16 2006 +0000
1.3 @@ -3,12 +3,13 @@
1.4 #include <sstream>
1.5
1.6 #include <lemon/smart_graph.h>
1.7 +#include <lemon/list_graph.h>
1.8
1.9 #include <lemon/bpugraph_adaptor.h>
1.10 #include <lemon/bipartite_matching.h>
1.11
1.12 #include <lemon/graph_utils.h>
1.13 -#include <lemon/xy.h>
1.14 +#include <lemon/dim2.h>
1.15 #include <lemon/graph_to_eps.h>
1.16
1.17 #include <lemon/time_measure.h>
1.18 @@ -17,6 +18,7 @@
1.19 using namespace lemon;
1.20
1.21 typedef SmartBpUGraph Graph;
1.22 +typedef ListBpUGraph LGraph;
1.23 BPUGRAPH_TYPEDEFS(Graph);
1.24
1.25 int _urandom_init() {
1.26 @@ -41,24 +43,36 @@
1.27 int s = 100;
1.28
1.29 Timer nt(false), st(false);
1.30 + Timer lnt(false), lst(false);
1.31
1.32 for (int i = 0; i < s; ++i) {
1.33 Graph graph;
1.34 + LGraph lgraph;
1.35 vector<Node> aNodes;
1.36 vector<Node> bNodes;
1.37 + vector<LGraph::Node> laNodes;
1.38 + vector<LGraph::Node> lbNodes;
1.39
1.40 for (int i = 0; i < n; ++i) {
1.41 Node node = graph.addANode();
1.42 aNodes.push_back(node);
1.43 + LGraph::Node lnode = lgraph.addANode();
1.44 + laNodes.push_back(lnode);
1.45 }
1.46 for (int i = 0; i < m; ++i) {
1.47 Node node = graph.addBNode();
1.48 bNodes.push_back(node);
1.49 + LGraph::Node lnode = lgraph.addBNode();
1.50 + lbNodes.push_back(lnode);
1.51 }
1.52 for (int i = 0; i < e; ++i) {
1.53 - Node aNode = aNodes[urandom(n)];
1.54 - Node bNode = bNodes[urandom(m)];
1.55 + int a,b;
1.56 + Node aNode = aNodes[a=urandom(n)];
1.57 + Node bNode = bNodes[b=urandom(m)];
1.58 graph.addEdge(aNode, bNode);
1.59 + LGraph::Node laNode = laNodes[a];
1.60 + LGraph::Node lbNode = lbNodes[b];
1.61 + lgraph.addEdge(laNode, lbNode);
1.62 }
1.63
1.64 {
1.65 @@ -81,11 +95,32 @@
1.66 bpmatch.start();
1.67 st.stop();
1.68
1.69 + }
1.70 + {
1.71 + MaxBipartiteMatching<LGraph> bpmatch(lgraph);
1.72 +
1.73 + lnt.start();
1.74 + bpmatch.init();
1.75 + bpmatch.start();
1.76 + lnt.stop();
1.77 +
1.78 }
1.79 -
1.80 - }
1.81
1.82 - cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
1.83 + {
1.84 + typedef SwapBpUGraphAdaptor<LGraph> SGraph;
1.85 + SGraph sgraph(lgraph);
1.86 + MaxBipartiteMatching<SGraph> bpmatch(sgraph);
1.87 +
1.88 + lst.start();
1.89 + bpmatch.init();
1.90 + bpmatch.start();
1.91 + lst.stop();
1.92 +
1.93 + }
1.94 + }
1.95 +
1.96 + cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
1.97 + << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
1.98
1.99 }
1.100
2.1 --- a/demo/coloring.cc Wed Sep 06 11:39:22 2006 +0000
2.2 +++ b/demo/coloring.cc Thu Sep 07 13:27:16 2006 +0000
2.3 @@ -55,7 +55,7 @@
2.4 Graph graph;
2.5
2.6 UGraphReader<Graph> reader("coloring.lgf", graph);
2.7 - Graph::NodeMap<xy<double> > coords(graph);
2.8 + Graph::NodeMap<dim2::Point<double> > coords(graph);
2.9 reader.readNodeMap("coords", coords);
2.10
2.11 reader.run();
3.1 --- a/demo/descriptor_map_demo.cc Wed Sep 06 11:39:22 2006 +0000
3.2 +++ b/demo/descriptor_map_demo.cc Thu Sep 07 13:27:16 2006 +0000
3.3 @@ -29,7 +29,7 @@
3.4 #include <lemon/list_graph.h>
3.5 #include <lemon/graph_utils.h>
3.6 #include <lemon/graph_writer.h>
3.7 -#include <lemon/xy.h>
3.8 +#include <lemon/dim2.h>
3.9 #include <lemon/graph_to_eps.h>
3.10
3.11 #include <iostream>
3.12 @@ -40,7 +40,7 @@
3.13
3.14 using namespace lemon;
3.15
3.16 -// Special xy<double> map type
3.17 +// Special dim2::Point<double> map type
3.18 //
3.19 // It gives back a position for each node. The position of the nodes
3.20 // are on the circle with the given center and radius.
3.21 @@ -51,7 +51,7 @@
3.22 class CircleMap {
3.23 public:
3.24
3.25 - typedef xy<double> Value;
3.26 + typedef dim2::Point<double> Value;
3.27 typedef typename Graph::Node Key;
3.28
3.29 CircleMap(const Graph& _graph,
3.30 @@ -118,7 +118,7 @@
3.31
3.32 // Make postscript from the graph.
3.33
3.34 - CircleMap<Graph> coords(graph, xy<double>(0.0, 0.0), 10.0);
3.35 + CircleMap<Graph> coords(graph, dim2::Point<double>(0.0, 0.0), 10.0);
3.36
3.37 graphToEps(graph,"descriptor_map_demo.eps").scaleToA4().
3.38 title("Generated graph").
4.1 --- a/demo/disjoint_paths_demo.cc Wed Sep 06 11:39:22 2006 +0000
4.2 +++ b/demo/disjoint_paths_demo.cc Thu Sep 07 13:27:16 2006 +0000
4.3 @@ -52,7 +52,7 @@
4.4
4.5 Graph graph;
4.6
4.7 - Graph::NodeMap<xy<double> > coords(graph);
4.8 + Graph::NodeMap<dim2::Point<double> > coords(graph);
4.9 Graph::Node source, target;
4.10 GraphReader<Graph>("disjoint_paths_demo.lgf", graph).
4.11 readNodeMap("coords", coords).
4.12 @@ -98,7 +98,9 @@
4.13 graphToEps(sgraph, "node_disjoint_paths.eps").
4.14 title("node disjoint path").copyright("(C) 2006 LEMON Project").drawArrows().
4.15 edgeColors(composeMap(functorMap(color), sflow)).
4.16 - coords(SGraph::combinedNodeMap(coords, shiftMap(coords, xy<double>(5, 0)))).
4.17 + coords(SGraph::combinedNodeMap(coords,
4.18 + shiftMap(coords,
4.19 + dim2::Point<double>(5, 0)))).
4.20 autoNodeScale().run();
4.21
4.22 cout << "The paths are written into node_disjoint_paths.eps" << endl;
5.1 --- a/demo/graph_orientation.cc Wed Sep 06 11:39:22 2006 +0000
5.2 +++ b/demo/graph_orientation.cc Thu Sep 07 13:27:16 2006 +0000
5.3 @@ -19,7 +19,7 @@
5.4 #include <lemon/list_graph.h>
5.5 #include <lemon/graph_reader.h>
5.6 #include <lemon/iterable_maps.h>
5.7 -#include <lemon/xy.h>
5.8 +#include <lemon/dim2.h>
5.9 #include <lemon/graph_to_eps.h>
5.10
5.11
5.12 @@ -45,7 +45,7 @@
5.13
5.14 ListGraph::NodeMap<int> f(g); //in-deg requirement;
5.15 ListGraph::NodeMap<int> label(g);
5.16 - ListGraph::NodeMap<xy<double> > coords(g);
5.17 + ListGraph::NodeMap<dim2::Point<double> > coords(g);
5.18
5.19 try {
5.20 GraphReader<ListGraph> reader(argv[1],g);
6.1 --- a/demo/graph_to_eps_demo.cc Wed Sep 06 11:39:22 2006 +0000
6.2 +++ b/demo/graph_to_eps_demo.cc Thu Sep 07 13:27:16 2006 +0000
6.3 @@ -48,7 +48,7 @@
6.4 typedef ListGraph::Node Node;
6.5 typedef ListGraph::NodeIt NodeIt;
6.6 typedef ListGraph::Edge Edge;
6.7 - typedef xy<int> Xy;
6.8 + typedef dim2::Point<int> Point;
6.9
6.10 Node n1=g.addNode();
6.11 Node n2=g.addNode();
6.12 @@ -56,18 +56,18 @@
6.13 Node n4=g.addNode();
6.14 Node n5=g.addNode();
6.15
6.16 - ListGraph::NodeMap<Xy> coords(g);
6.17 + ListGraph::NodeMap<Point> coords(g);
6.18 ListGraph::NodeMap<double> sizes(g);
6.19 ListGraph::NodeMap<int> colors(g);
6.20 ListGraph::NodeMap<int> shapes(g);
6.21 ListGraph::EdgeMap<int> ecolors(g);
6.22 ListGraph::EdgeMap<int> widths(g);
6.23
6.24 - coords[n1]=Xy(50,50); sizes[n1]=1; colors[n1]=1; shapes[n1]=0;
6.25 - coords[n2]=Xy(50,70); sizes[n2]=2; colors[n2]=2; shapes[n2]=2;
6.26 - coords[n3]=Xy(70,70); sizes[n3]=1; colors[n3]=3; shapes[n3]=0;
6.27 - coords[n4]=Xy(70,50); sizes[n4]=2; colors[n4]=4; shapes[n4]=1;
6.28 - coords[n5]=Xy(85,60); sizes[n5]=3; colors[n5]=5; shapes[n5]=2;
6.29 + coords[n1]=Point(50,50); sizes[n1]=1; colors[n1]=1; shapes[n1]=0;
6.30 + coords[n2]=Point(50,70); sizes[n2]=2; colors[n2]=2; shapes[n2]=2;
6.31 + coords[n3]=Point(70,70); sizes[n3]=1; colors[n3]=3; shapes[n3]=0;
6.32 + coords[n4]=Point(70,50); sizes[n4]=2; colors[n4]=4; shapes[n4]=1;
6.33 + coords[n5]=Point(85,60); sizes[n5]=3; colors[n5]=5; shapes[n5]=2;
6.34
6.35 Edge e;
6.36
6.37 @@ -183,12 +183,12 @@
6.38
6.39 ListGraph h;
6.40 ListGraph::NodeMap<int> hcolors(h);
6.41 - ListGraph::NodeMap<Xy> hcoords(h);
6.42 + ListGraph::NodeMap<Point> hcoords(h);
6.43
6.44 int cols=int(sqrt(double(palette.size())));
6.45 for(int i=0;i<int(paletteW.size());i++) {
6.46 Node n=h.addNode();
6.47 - hcoords[n]=Xy(i%cols,i/cols);
6.48 + hcoords[n]=Point(i%cols,i/cols);
6.49 hcolors[n]=i;
6.50 }
6.51
7.1 --- a/demo/grid_ugraph_demo.cc Wed Sep 06 11:39:22 2006 +0000
7.2 +++ b/demo/grid_ugraph_demo.cc Thu Sep 07 13:27:16 2006 +0000
7.3 @@ -20,7 +20,7 @@
7.4 #include <lemon/graph_adaptor.h>
7.5 #include <lemon/graph_to_eps.h>
7.6 #include <lemon/bfs.h>
7.7 -#include <lemon/xy.h>
7.8 +#include <lemon/dim2.h>
7.9
7.10 #include <iostream>
7.11 #include <fstream>
8.1 --- a/demo/min_route.cc Wed Sep 06 11:39:22 2006 +0000
8.2 +++ b/demo/min_route.cc Thu Sep 07 13:27:16 2006 +0000
8.3 @@ -22,7 +22,7 @@
8.4 #include <lemon/smart_graph.h>
8.5 #include <lemon/dijkstra.h>
8.6 #include <lemon/maps.h>
8.7 -#include <lemon/xy.h>
8.8 +#include <lemon/dim2.h>
8.9 #include <lemon/graph_reader.h>
8.10
8.11 #include <lemon/time_measure.h>
8.12 @@ -46,7 +46,7 @@
8.13 typedef double Value;
8.14 typedef typename CoordMap::Key Key;
8.15
8.16 - PotentialMap(const CoordMap& _coord, const xy<double>& _target)
8.17 + PotentialMap(const CoordMap& _coord, const dim2::Point<double>& _target)
8.18 : coord(_coord), target(_target) {}
8.19
8.20 double operator[](const Key& node) const {
8.21 @@ -55,7 +55,7 @@
8.22 }
8.23 private:
8.24 const CoordMap& coord;
8.25 - xy<double> target;
8.26 + dim2::Point<double> target;
8.27 };
8.28
8.29 template <typename Graph, typename LengthMap, typename PotentialMap>
8.30 @@ -86,7 +86,7 @@
8.31 typedef Graph::EdgeIt EdgeIt;
8.32 typedef Graph::NodeIt NodeIt;
8.33 typedef Graph::EdgeMap<double> LengthMap;
8.34 - typedef Graph::NodeMap<xy<double> > CoordMap;
8.35 + typedef Graph::NodeMap<dim2::Point<double> > CoordMap;
8.36
8.37 SmartGraph graph;
8.38
8.39 @@ -94,9 +94,9 @@
8.40 GraphReader<Graph> reader(is, graph);
8.41
8.42 CoordMap coord(graph);
8.43 - XMap<CoordMap> xcoord = xMap(coord);
8.44 + dim2::XMap<CoordMap> xcoord = xMap(coord);
8.45 reader.readNodeMap("coordinates_x", xcoord);
8.46 - YMap<CoordMap> ycoord = yMap(coord);
8.47 + dim2::YMap<CoordMap> ycoord = yMap(coord);
8.48 reader.readNodeMap("coordinates_y", ycoord);
8.49
8.50 LengthMap length(graph);
9.1 --- a/demo/strongly_connected_orientation.cc Wed Sep 06 11:39:22 2006 +0000
9.2 +++ b/demo/strongly_connected_orientation.cc Thu Sep 07 13:27:16 2006 +0000
9.3 @@ -78,7 +78,7 @@
9.4 << "to be strongly connected" << endl;
9.5
9.6 UGraph ugraph;
9.7 - UGraph::NodeMap<xy<double> > coords(ugraph);
9.8 + UGraph::NodeMap<dim2::Point<double> > coords(ugraph);
9.9 UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).
9.10 readNodeMap("coords", coords).run();
9.11
10.1 --- a/demo/topology_demo.cc Wed Sep 06 11:39:22 2006 +0000
10.2 +++ b/demo/topology_demo.cc Thu Sep 07 13:27:16 2006 +0000
10.3 @@ -20,7 +20,7 @@
10.4 #include <lemon/topology.h>
10.5 #include <lemon/graph_to_eps.h>
10.6 #include <lemon/graph_reader.h>
10.7 -#include <lemon/xy.h>
10.8 +#include <lemon/dim2.h>
10.9
10.10 #include <iostream>
10.11
10.12 @@ -49,7 +49,7 @@
10.13 typedef Graph::Node Node;
10.14
10.15 Graph graph;
10.16 - Graph::NodeMap<xy<double> > coords(graph);
10.17 + Graph::NodeMap<dim2::Point<double> > coords(graph);
10.18
10.19 UGraphReader<Graph>("u_components.lgf", graph).
10.20 readNodeMap("coordinates_x", xMap(coords)).
10.21 @@ -74,7 +74,7 @@
10.22 typedef Graph::Node Node;
10.23
10.24 Graph graph;
10.25 - Graph::NodeMap<xy<double> > coords(graph);
10.26 + Graph::NodeMap<dim2::Point<double> > coords(graph);
10.27
10.28 GraphReader<Graph>("dir_components.lgf", graph).
10.29 readNodeMap("coordinates_x", xMap(coords)).
10.30 @@ -104,7 +104,7 @@
10.31 typedef Graph::UEdge UEdge;
10.32
10.33 Graph graph;
10.34 - Graph::NodeMap<xy<double> > coords(graph);
10.35 + Graph::NodeMap<dim2::Point<double> > coords(graph);
10.36
10.37 UGraphReader<Graph>("u_components.lgf", graph).
10.38 readNodeMap("coordinates_x", xMap(coords)).
10.39 @@ -134,7 +134,7 @@
10.40 typedef Graph::UEdge UEdge;
10.41
10.42 Graph graph;
10.43 - Graph::NodeMap<xy<double> > coords(graph);
10.44 + Graph::NodeMap<dim2::Point<double> > coords(graph);
10.45
10.46 UGraphReader<Graph>("u_components.lgf", graph).
10.47 readNodeMap("coordinates_x", xMap(coords)).
10.48 @@ -163,7 +163,7 @@
10.49 typedef Graph::UEdge UEdge;
10.50
10.51 Graph graph;
10.52 - Graph::NodeMap<xy<double> > coords(graph);
10.53 + Graph::NodeMap<dim2::Point<double> > coords(graph);
10.54
10.55 UGraphReader<Graph>("partitions.lgf", graph).
10.56 readNodeMap("coordinates_x", xMap(coords)).
11.1 --- a/lemon.spec.in Wed Sep 06 11:39:22 2006 +0000
11.2 +++ b/lemon.spec.in Thu Sep 07 13:27:16 2006 +0000
11.3 @@ -7,7 +7,7 @@
11.4 Source0: %{name}-%{version}.tar.gz
11.5 Group: Development/Libraries
11.6 BuildRoot: %{_tmppath}/%{name}-root
11.7 -# Requires: glpk
11.8 +Requires: glpk
11.9 # BuildRequires: glpk-devel
11.10
11.11 %description
12.1 --- a/lemon/Makefile.am Wed Sep 06 11:39:22 2006 +0000
12.2 +++ b/lemon/Makefile.am Thu Sep 07 13:27:16 2006 +0000
12.3 @@ -41,6 +41,7 @@
12.4 lemon/dag_shortest_path.h \
12.5 lemon/dfs.h \
12.6 lemon/dijkstra.h \
12.7 + lemon/dim2.h \
12.8 lemon/dimacs.h \
12.9 lemon/edge_set.h \
12.10 lemon/edmonds_karp.h \
12.11 @@ -92,8 +93,7 @@
12.12 lemon/tolerance.h \
12.13 lemon/topology.h \
12.14 lemon/ugraph_adaptor.h \
12.15 - lemon/unionfind.h \
12.16 - lemon/xy.h
12.17 + lemon/unionfind.h
12.18
12.19 bits_HEADERS += \
12.20 lemon/bits/alteration_notifier.h \
13.1 --- a/lemon/bits/bezier.h Wed Sep 06 11:39:22 2006 +0000
13.2 +++ b/lemon/bits/bezier.h Thu Sep 07 13:27:16 2006 +0000
13.3 @@ -27,26 +27,27 @@
13.4 ///
13.5 ///\author Alpar Juttner
13.6
13.7 -#include<lemon/xy.h>
13.8 +#include<lemon/dim2.h>
13.9
13.10 namespace lemon {
13.11 + namespace dim2 {
13.12
13.13 class BezierBase {
13.14 public:
13.15 - typedef xy<double> xy;
13.16 + typedef Point<double> Point;
13.17 protected:
13.18 - static xy conv(xy x,xy y,double t) {return (1-t)*x+t*y;}
13.19 + static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;}
13.20 };
13.21
13.22 class Bezier1 : public BezierBase
13.23 {
13.24 public:
13.25 - xy p1,p2;
13.26 + Point p1,p2;
13.27
13.28 Bezier1() {}
13.29 - Bezier1(xy _p1, xy _p2) :p1(_p1), p2(_p2) {}
13.30 + Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
13.31
13.32 - xy operator()(double t) const
13.33 + Point operator()(double t) const
13.34 {
13.35 // return conv(conv(p1,p2,t),conv(p2,p3,t),t);
13.36 return conv(p1,p2,t);
13.37 @@ -63,59 +64,60 @@
13.38
13.39 Bezier1 revert() const { return Bezier1(p2,p1);}
13.40 Bezier1 operator()(double a,double b) const { return before(b).after(a/b); }
13.41 - xy grad() const { return p2-p1; }
13.42 - xy norm() const { return rot90(p2-p1); }
13.43 - xy grad(double) const { return grad(); }
13.44 - xy norm(double t) const { return rot90(grad(t)); }
13.45 + Point grad() const { return p2-p1; }
13.46 + Point norm() const { return rot90(p2-p1); }
13.47 + Point grad(double) const { return grad(); }
13.48 + Point norm(double t) const { return rot90(grad(t)); }
13.49 };
13.50
13.51 class Bezier2 : public BezierBase
13.52 {
13.53 public:
13.54 - xy p1,p2,p3;
13.55 + Point p1,p2,p3;
13.56
13.57 Bezier2() {}
13.58 - Bezier2(xy _p1, xy _p2, xy _p3) :p1(_p1), p2(_p2), p3(_p3) {}
13.59 + Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {}
13.60 Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {}
13.61 - xy operator()(double t) const
13.62 + Point operator()(double t) const
13.63 {
13.64 // return conv(conv(p1,p2,t),conv(p2,p3,t),t);
13.65 return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3;
13.66 }
13.67 Bezier2 before(double t) const
13.68 {
13.69 - xy q(conv(p1,p2,t));
13.70 - xy r(conv(p2,p3,t));
13.71 + Point q(conv(p1,p2,t));
13.72 + Point r(conv(p2,p3,t));
13.73 return Bezier2(p1,q,conv(q,r,t));
13.74 }
13.75
13.76 Bezier2 after(double t) const
13.77 {
13.78 - xy q(conv(p1,p2,t));
13.79 - xy r(conv(p2,p3,t));
13.80 + Point q(conv(p1,p2,t));
13.81 + Point r(conv(p2,p3,t));
13.82 return Bezier2(conv(q,r,t),r,p3);
13.83 }
13.84 Bezier2 revert() const { return Bezier2(p3,p2,p1);}
13.85 Bezier2 operator()(double a,double b) const { return before(b).after(a/b); }
13.86 Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); }
13.87 Bezier1 norm() const { return Bezier1(2.0*rot90(p2-p1),2.0*rot90(p3-p2)); }
13.88 - xy grad(double t) const { return grad()(t); }
13.89 - xy norm(double t) const { return rot90(grad(t)); }
13.90 + Point grad(double t) const { return grad()(t); }
13.91 + Point norm(double t) const { return rot90(grad(t)); }
13.92 };
13.93
13.94 class Bezier3 : public BezierBase
13.95 {
13.96 public:
13.97 - xy p1,p2,p3,p4;
13.98 + Point p1,p2,p3,p4;
13.99
13.100 Bezier3() {}
13.101 - Bezier3(xy _p1, xy _p2, xy _p3, xy _p4) :p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
13.102 + Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
13.103 + : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
13.104 Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)),
13.105 p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
13.106 Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
13.107 p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
13.108
13.109 - xy operator()(double t) const
13.110 + Point operator()(double t) const
13.111 {
13.112 // return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
13.113 return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
13.114 @@ -123,23 +125,23 @@
13.115 }
13.116 Bezier3 before(double t) const
13.117 {
13.118 - xy p(conv(p1,p2,t));
13.119 - xy q(conv(p2,p3,t));
13.120 - xy r(conv(p3,p4,t));
13.121 - xy a(conv(p,q,t));
13.122 - xy b(conv(q,r,t));
13.123 - xy c(conv(a,b,t));
13.124 + Point p(conv(p1,p2,t));
13.125 + Point q(conv(p2,p3,t));
13.126 + Point r(conv(p3,p4,t));
13.127 + Point a(conv(p,q,t));
13.128 + Point b(conv(q,r,t));
13.129 + Point c(conv(a,b,t));
13.130 return Bezier3(p1,p,a,c);
13.131 }
13.132
13.133 Bezier3 after(double t) const
13.134 {
13.135 - xy p(conv(p1,p2,t));
13.136 - xy q(conv(p2,p3,t));
13.137 - xy r(conv(p3,p4,t));
13.138 - xy a(conv(p,q,t));
13.139 - xy b(conv(q,r,t));
13.140 - xy c(conv(a,b,t));
13.141 + Point p(conv(p1,p2,t));
13.142 + Point q(conv(p2,p3,t));
13.143 + Point r(conv(p3,p4,t));
13.144 + Point a(conv(p,q,t));
13.145 + Point b(conv(q,r,t));
13.146 + Point c(conv(a,b,t));
13.147 return Bezier3(c,b,r,p4);
13.148 }
13.149 Bezier3 revert() const { return Bezier3(p4,p3,p2,p1);}
13.150 @@ -148,18 +150,18 @@
13.151 Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
13.152 3.0*rot90(p3-p2),
13.153 3.0*rot90(p4-p3)); }
13.154 - xy grad(double t) const { return grad()(t); }
13.155 - xy norm(double t) const { return rot90(grad(t)); }
13.156 + Point grad(double t) const { return grad()(t); }
13.157 + Point norm(double t) const { return rot90(grad(t)); }
13.158
13.159 template<class R,class F,class S,class D>
13.160 R recSplit(F &_f,const S &_s,D _d) const
13.161 {
13.162 - const xy a=(p1+p2)/2;
13.163 - const xy b=(p2+p3)/2;
13.164 - const xy c=(p3+p4)/2;
13.165 - const xy d=(a+b)/2;
13.166 - const xy e=(b+c)/2;
13.167 - const xy f=(d+e)/2;
13.168 + const Point a=(p1+p2)/2;
13.169 + const Point b=(p2+p3)/2;
13.170 + const Point c=(p3+p4)/2;
13.171 + const Point d=(a+b)/2;
13.172 + const Point e=(b+c)/2;
13.173 + const Point f=(d+e)/2;
13.174 R f1=_f(Bezier3(p1,a,d,e),_d);
13.175 R f2=_f(Bezier3(e,d,c,p4),_d);
13.176 return _s(f1,f2);
13.177 @@ -167,6 +169,8 @@
13.178
13.179 };
13.180
13.181 -} //END OF NAMESPACE LEMON
13.182 +
13.183 +} //END OF NAMESPACE dim2
13.184 +} //END OF NAMESPACE lemon
13.185
13.186 #endif // LEMON_BEZIER_H
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/lemon/dim2.h Thu Sep 07 13:27:16 2006 +0000
14.3 @@ -0,0 +1,655 @@
14.4 +/* -*- C++ -*-
14.5 + *
14.6 + * This file is a part of LEMON, a generic C++ optimization library
14.7 + *
14.8 + * Copyright (C) 2003-2006
14.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
14.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
14.11 + *
14.12 + * Permission to use, modify and distribute this software is granted
14.13 + * provided that this copyright notice appears in all copies. For
14.14 + * precise terms see the accompanying LICENSE file.
14.15 + *
14.16 + * This software is provided "AS IS" with no warranty of any kind,
14.17 + * express or implied, and with no claim as to its suitability for any
14.18 + * purpose.
14.19 + *
14.20 + */
14.21 +
14.22 +#ifndef LEMON_DIM2_H
14.23 +#define LEMON_DIM2_H
14.24 +
14.25 +#include <iostream>
14.26 +#include <lemon/bits/utility.h>
14.27 +
14.28 +///\ingroup misc
14.29 +///\file
14.30 +///\brief A simple two dimensional vector and a bounding box implementation
14.31 +///
14.32 +/// The class \ref lemon::dim2::Point "dim2::Point" implements
14.33 +///a two dimensional vector with the usual
14.34 +/// operations.
14.35 +///
14.36 +/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
14.37 +/// can be used to determine
14.38 +/// the rectangular bounding box of a set of
14.39 +/// \ref lemon::dim2::Point "dim2::Point"'s.
14.40 +///
14.41 +///\author Attila Bernath
14.42 +
14.43 +
14.44 +namespace lemon {
14.45 +
14.46 + ///Tools for handling two dimensional coordinates
14.47 +
14.48 + ///This namespace is a storage of several
14.49 + ///tools for handling two dimensional coordinates
14.50 + namespace dim2 {
14.51 +
14.52 + /// \addtogroup misc
14.53 + /// @{
14.54 +
14.55 + /// A simple two dimensional vector (plainvector) implementation
14.56 +
14.57 + /// A simple two dimensional vector (plainvector) implementation
14.58 + ///with the usual vector
14.59 + /// operators.
14.60 + ///
14.61 + template<typename T>
14.62 + class Point {
14.63 +
14.64 + public:
14.65 +
14.66 + typedef T Value;
14.67 +
14.68 + ///First co-ordinate
14.69 + T x;
14.70 + ///Second co-ordinate
14.71 + T y;
14.72 +
14.73 + ///Default constructor
14.74 + Point() {}
14.75 +
14.76 + ///Construct an instance from coordinates
14.77 + Point(T a, T b) : x(a), y(b) { }
14.78 +
14.79 +
14.80 + ///Conversion constructor
14.81 + template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
14.82 +
14.83 + ///Give back the square of the norm of the vector
14.84 + T normSquare() const {
14.85 + return x*x+y*y;
14.86 + }
14.87 +
14.88 + ///Increment the left hand side by u
14.89 + Point<T>& operator +=(const Point<T>& u) {
14.90 + x += u.x;
14.91 + y += u.y;
14.92 + return *this;
14.93 + }
14.94 +
14.95 + ///Decrement the left hand side by u
14.96 + Point<T>& operator -=(const Point<T>& u) {
14.97 + x -= u.x;
14.98 + y -= u.y;
14.99 + return *this;
14.100 + }
14.101 +
14.102 + ///Multiply the left hand side with a scalar
14.103 + Point<T>& operator *=(const T &u) {
14.104 + x *= u;
14.105 + y *= u;
14.106 + return *this;
14.107 + }
14.108 +
14.109 + ///Divide the left hand side by a scalar
14.110 + Point<T>& operator /=(const T &u) {
14.111 + x /= u;
14.112 + y /= u;
14.113 + return *this;
14.114 + }
14.115 +
14.116 + ///Return the scalar product of two vectors
14.117 + T operator *(const Point<T>& u) const {
14.118 + return x*u.x+y*u.y;
14.119 + }
14.120 +
14.121 + ///Return the sum of two vectors
14.122 + Point<T> operator+(const Point<T> &u) const {
14.123 + Point<T> b=*this;
14.124 + return b+=u;
14.125 + }
14.126 +
14.127 + ///Return the neg of the vectors
14.128 + Point<T> operator-() const {
14.129 + Point<T> b=*this;
14.130 + b.x=-b.x; b.y=-b.y;
14.131 + return b;
14.132 + }
14.133 +
14.134 + ///Return the difference of two vectors
14.135 + Point<T> operator-(const Point<T> &u) const {
14.136 + Point<T> b=*this;
14.137 + return b-=u;
14.138 + }
14.139 +
14.140 + ///Return a vector multiplied by a scalar
14.141 + Point<T> operator*(const T &u) const {
14.142 + Point<T> b=*this;
14.143 + return b*=u;
14.144 + }
14.145 +
14.146 + ///Return a vector divided by a scalar
14.147 + Point<T> operator/(const T &u) const {
14.148 + Point<T> b=*this;
14.149 + return b/=u;
14.150 + }
14.151 +
14.152 + ///Test equality
14.153 + bool operator==(const Point<T> &u) const {
14.154 + return (x==u.x) && (y==u.y);
14.155 + }
14.156 +
14.157 + ///Test inequality
14.158 + bool operator!=(Point u) const {
14.159 + return (x!=u.x) || (y!=u.y);
14.160 + }
14.161 +
14.162 + };
14.163 +
14.164 + ///Return an Point
14.165 +
14.166 + ///Return an Point
14.167 + ///\relates Point
14.168 + template <typename T>
14.169 + inline Point<T> make_Point(const T& x, const T& y) {
14.170 + return Point<T>(x, y);
14.171 + }
14.172 +
14.173 + ///Return a vector multiplied by a scalar
14.174 +
14.175 + ///Return a vector multiplied by a scalar
14.176 + ///\relates Point
14.177 + template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
14.178 + return x*u;
14.179 + }
14.180 +
14.181 + ///Read a plainvector from a stream
14.182 +
14.183 + ///Read a plainvector from a stream
14.184 + ///\relates Point
14.185 + ///
14.186 + template<typename T>
14.187 + inline std::istream& operator>>(std::istream &is, Point<T> &z) {
14.188 + char c;
14.189 + if (is >> c) {
14.190 + if (c != '(') is.putback(c);
14.191 + } else {
14.192 + is.clear();
14.193 + }
14.194 + if (!(is >> z.x)) return is;
14.195 + if (is >> c) {
14.196 + if (c != ',') is.putback(c);
14.197 + } else {
14.198 + is.clear();
14.199 + }
14.200 + if (!(is >> z.y)) return is;
14.201 + if (is >> c) {
14.202 + if (c != ')') is.putback(c);
14.203 + } else {
14.204 + is.clear();
14.205 + }
14.206 + return is;
14.207 + }
14.208 +
14.209 + ///Write a plainvector to a stream
14.210 +
14.211 + ///Write a plainvector to a stream
14.212 + ///\relates Point
14.213 + ///
14.214 + template<typename T>
14.215 + inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
14.216 + {
14.217 + os << "(" << z.x << ", " << z.y << ")";
14.218 + return os;
14.219 + }
14.220 +
14.221 + ///Rotate by 90 degrees
14.222 +
14.223 + ///Returns its parameter rotated by 90 degrees in positive direction.
14.224 + ///\relates Point
14.225 + ///
14.226 + template<typename T>
14.227 + inline Point<T> rot90(const Point<T> &z)
14.228 + {
14.229 + return Point<T>(-z.y,z.x);
14.230 + }
14.231 +
14.232 + ///Rotate by 180 degrees
14.233 +
14.234 + ///Returns its parameter rotated by 180 degrees.
14.235 + ///\relates Point
14.236 + ///
14.237 + template<typename T>
14.238 + inline Point<T> rot180(const Point<T> &z)
14.239 + {
14.240 + return Point<T>(-z.x,-z.y);
14.241 + }
14.242 +
14.243 + ///Rotate by 270 degrees
14.244 +
14.245 + ///Returns its parameter rotated by 90 degrees in negative direction.
14.246 + ///\relates Point
14.247 + ///
14.248 + template<typename T>
14.249 + inline Point<T> rot270(const Point<T> &z)
14.250 + {
14.251 + return Point<T>(z.y,-z.x);
14.252 + }
14.253 +
14.254 +
14.255 +
14.256 + /// A class to calculate or store the bounding box of plainvectors.
14.257 +
14.258 + /// A class to calculate or store the bounding box of plainvectors.
14.259 + ///
14.260 + ///\author Attila Bernath
14.261 + template<typename T>
14.262 + class BoundingBox {
14.263 + Point<T> bottom_left, top_right;
14.264 + bool _empty;
14.265 + public:
14.266 +
14.267 + ///Default constructor: creates an empty bounding box
14.268 + BoundingBox() { _empty = true; }
14.269 +
14.270 + ///Construct an instance from one point
14.271 + BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
14.272 +
14.273 + ///Were any points added?
14.274 + bool empty() const {
14.275 + return _empty;
14.276 + }
14.277 +
14.278 + ///Make the BoundingBox empty
14.279 + void clear() {
14.280 + _empty=1;
14.281 + }
14.282 +
14.283 + ///Give back the bottom left corner
14.284 +
14.285 + ///Give back the bottom left corner.
14.286 + ///If the bounding box is empty, then the return value is not defined.
14.287 + Point<T> bottomLeft() const {
14.288 + return bottom_left;
14.289 + }
14.290 +
14.291 + ///Set the bottom left corner
14.292 +
14.293 + ///Set the bottom left corner.
14.294 + ///It should only bee used for non-empty box.
14.295 + void bottomLeft(Point<T> p) {
14.296 + bottom_left = p;
14.297 + }
14.298 +
14.299 + ///Give back the top right corner
14.300 +
14.301 + ///Give back the top right corner.
14.302 + ///If the bounding box is empty, then the return value is not defined.
14.303 + Point<T> topRight() const {
14.304 + return top_right;
14.305 + }
14.306 +
14.307 + ///Set the top right corner
14.308 +
14.309 + ///Set the top right corner.
14.310 + ///It should only bee used for non-empty box.
14.311 + void topRight(Point<T> p) {
14.312 + top_right = p;
14.313 + }
14.314 +
14.315 + ///Give back the bottom right corner
14.316 +
14.317 + ///Give back the bottom right corner.
14.318 + ///If the bounding box is empty, then the return value is not defined.
14.319 + Point<T> bottomRight() const {
14.320 + return Point<T>(top_right.x,bottom_left.y);
14.321 + }
14.322 +
14.323 + ///Set the bottom right corner
14.324 +
14.325 + ///Set the bottom right corner.
14.326 + ///It should only bee used for non-empty box.
14.327 + void bottomRight(Point<T> p) {
14.328 + top_right.x = p.x;
14.329 + bottom_left.y = p.y;
14.330 + }
14.331 +
14.332 + ///Give back the top left corner
14.333 +
14.334 + ///Give back the top left corner.
14.335 + ///If the bounding box is empty, then the return value is not defined.
14.336 + Point<T> topLeft() const {
14.337 + return Point<T>(bottom_left.x,top_right.y);
14.338 + }
14.339 +
14.340 + ///Set the top left corner
14.341 +
14.342 + ///Set the top left corner.
14.343 + ///It should only bee used for non-empty box.
14.344 + void topLeft(Point<T> p) {
14.345 + top_right.y = p.y;
14.346 + bottom_left.x = p.x;
14.347 + }
14.348 +
14.349 + ///Give back the bottom of the box
14.350 +
14.351 + ///Give back the bottom of the box.
14.352 + ///If the bounding box is empty, then the return value is not defined.
14.353 + T bottom() const {
14.354 + return bottom_left.y;
14.355 + }
14.356 +
14.357 + ///Set the bottom of the box
14.358 +
14.359 + ///Set the bottom of the box.
14.360 + ///It should only bee used for non-empty box.
14.361 + void bottom(T t) {
14.362 + bottom_left.y = t;
14.363 + }
14.364 +
14.365 + ///Give back the top of the box
14.366 +
14.367 + ///Give back the top of the box.
14.368 + ///If the bounding box is empty, then the return value is not defined.
14.369 + T top() const {
14.370 + return top_right.y;
14.371 + }
14.372 +
14.373 + ///Set the top of the box
14.374 +
14.375 + ///Set the top of the box.
14.376 + ///It should only bee used for non-empty box.
14.377 + void top(T t) {
14.378 + top_right.y = t;
14.379 + }
14.380 +
14.381 + ///Give back the left side of the box
14.382 +
14.383 + ///Give back the left side of the box.
14.384 + ///If the bounding box is empty, then the return value is not defined.
14.385 + T left() const {
14.386 + return bottom_left.x;
14.387 + }
14.388 +
14.389 + ///Set the left side of the box
14.390 +
14.391 + ///Set the left side of the box.
14.392 + ///It should only bee used for non-empty box
14.393 + void left(T t) {
14.394 + bottom_left.x = t;
14.395 + }
14.396 +
14.397 + /// Give back the right side of the box
14.398 +
14.399 + /// Give back the right side of the box.
14.400 + ///If the bounding box is empty, then the return value is not defined.
14.401 + T right() const {
14.402 + return top_right.x;
14.403 + }
14.404 +
14.405 + ///Set the right side of the box
14.406 +
14.407 + ///Set the right side of the box.
14.408 + ///It should only bee used for non-empty box
14.409 + void right(T t) {
14.410 + top_right.x = t;
14.411 + }
14.412 +
14.413 + ///Give back the height of the box
14.414 +
14.415 + ///Give back the height of the box.
14.416 + ///If the bounding box is empty, then the return value is not defined.
14.417 + T height() const {
14.418 + return top_right.y-bottom_left.y;
14.419 + }
14.420 +
14.421 + ///Give back the width of the box
14.422 +
14.423 + ///Give back the width of the box.
14.424 + ///If the bounding box is empty, then the return value is not defined.
14.425 + T width() const {
14.426 + return top_right.x-bottom_left.x;
14.427 + }
14.428 +
14.429 + ///Checks whether a point is inside a bounding box
14.430 + bool inside(const Point<T>& u){
14.431 + if (_empty)
14.432 + return false;
14.433 + else{
14.434 + return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
14.435 + (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
14.436 + }
14.437 + }
14.438 +
14.439 + ///Increments a bounding box with a point
14.440 + BoundingBox& add(const Point<T>& u){
14.441 + if (_empty){
14.442 + bottom_left=top_right=u;
14.443 + _empty = false;
14.444 + }
14.445 + else{
14.446 + if (bottom_left.x > u.x) bottom_left.x = u.x;
14.447 + if (bottom_left.y > u.y) bottom_left.y = u.y;
14.448 + if (top_right.x < u.x) top_right.x = u.x;
14.449 + if (top_right.y < u.y) top_right.y = u.y;
14.450 + }
14.451 + return *this;
14.452 + }
14.453 +
14.454 +// ///Sums a bounding box and a point
14.455 +// BoundingBox operator +(const Point<T>& u){
14.456 +// BoundingBox b = *this;
14.457 +// return b += u;
14.458 +// }
14.459 +
14.460 + ///Increments a bounding box with another bounding box
14.461 + BoundingBox& add(const BoundingBox &u){
14.462 + if ( !u.empty() ){
14.463 + this->add(u.bottomLeft());
14.464 + this->add(u.topRight());
14.465 + }
14.466 + return *this;
14.467 + }
14.468 +
14.469 + ///Sums two bounding boxes
14.470 + BoundingBox operator +(const BoundingBox& u){
14.471 + BoundingBox b = *this;
14.472 + return b.add(u);
14.473 + }
14.474 +
14.475 +
14.476 + ///Intersection of two bounding boxes
14.477 + BoundingBox operator &(const BoundingBox& u){
14.478 + BoundingBox b;
14.479 + b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
14.480 + b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
14.481 + b.top_right.x=std::min(this->top_right.x,u.top_right.x);
14.482 + b.top_right.y=std::min(this->top_right.y,u.top_right.y);
14.483 + b._empty = this->_empty || u._empty ||
14.484 + b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
14.485 + return b;
14.486 + }
14.487 +
14.488 + };//class Boundingbox
14.489 +
14.490 +
14.491 + ///Map of x-coordinates of a dim2::Point<>-map
14.492 +
14.493 + ///\ingroup maps
14.494 + ///
14.495 + template<class M>
14.496 + class XMap
14.497 + {
14.498 + M& _map;
14.499 + public:
14.500 +
14.501 + typedef typename M::Value::Value Value;
14.502 + typedef typename M::Key Key;
14.503 + ///\e
14.504 + XMap(M& map) : _map(map) {}
14.505 + Value operator[](Key k) const {return _map[k].x;}
14.506 + void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
14.507 + };
14.508 +
14.509 + ///Returns an \ref XMap class
14.510 +
14.511 + ///This function just returns an \ref XMap class.
14.512 + ///
14.513 + ///\ingroup maps
14.514 + ///\relates XMap
14.515 + template<class M>
14.516 + inline XMap<M> xMap(M &m)
14.517 + {
14.518 + return XMap<M>(m);
14.519 + }
14.520 +
14.521 + template<class M>
14.522 + inline XMap<M> xMap(const M &m)
14.523 + {
14.524 + return XMap<M>(m);
14.525 + }
14.526 +
14.527 + ///Constant (read only) version of \ref XMap
14.528 +
14.529 + ///\ingroup maps
14.530 + ///
14.531 + template<class M>
14.532 + class ConstXMap
14.533 + {
14.534 + const M& _map;
14.535 + public:
14.536 +
14.537 + typedef typename M::Value::Value Value;
14.538 + typedef typename M::Key Key;
14.539 + ///\e
14.540 + ConstXMap(const M &map) : _map(map) {}
14.541 + Value operator[](Key k) const {return _map[k].x;}
14.542 + };
14.543 +
14.544 + ///Returns a \ref ConstXMap class
14.545 +
14.546 + ///This function just returns an \ref ConstXMap class.
14.547 + ///
14.548 + ///\ingroup maps
14.549 + ///\relates ConstXMap
14.550 + template<class M>
14.551 + inline ConstXMap<M> xMap(const M &m)
14.552 + {
14.553 + return ConstXMap<M>(m);
14.554 + }
14.555 +
14.556 + ///Map of y-coordinates of a dim2::Point<>-map
14.557 +
14.558 + ///\ingroup maps
14.559 + ///
14.560 + template<class M>
14.561 + class YMap
14.562 + {
14.563 + M& _map;
14.564 + public:
14.565 +
14.566 + typedef typename M::Value::Value Value;
14.567 + typedef typename M::Key Key;
14.568 + ///\e
14.569 + YMap(M& map) : _map(map) {}
14.570 + Value operator[](Key k) const {return _map[k].y;}
14.571 + void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
14.572 + };
14.573 +
14.574 + ///Returns an \ref YMap class
14.575 +
14.576 + ///This function just returns an \ref YMap class.
14.577 + ///
14.578 + ///\ingroup maps
14.579 + ///\relates YMap
14.580 + template<class M>
14.581 + inline YMap<M> yMap(M &m)
14.582 + {
14.583 + return YMap<M>(m);
14.584 + }
14.585 +
14.586 + template<class M>
14.587 + inline YMap<M> yMap(const M &m)
14.588 + {
14.589 + return YMap<M>(m);
14.590 + }
14.591 +
14.592 + ///Constant (read only) version of \ref YMap
14.593 +
14.594 + ///\ingroup maps
14.595 + ///
14.596 + template<class M>
14.597 + class ConstYMap
14.598 + {
14.599 + const M& _map;
14.600 + public:
14.601 +
14.602 + typedef typename M::Value::Value Value;
14.603 + typedef typename M::Key Key;
14.604 + ///\e
14.605 + ConstYMap(const M &map) : _map(map) {}
14.606 + Value operator[](Key k) const {return _map[k].y;}
14.607 + };
14.608 +
14.609 + ///Returns a \ref ConstYMap class
14.610 +
14.611 + ///This function just returns an \ref ConstYMap class.
14.612 + ///
14.613 + ///\ingroup maps
14.614 + ///\relates ConstYMap
14.615 + template<class M>
14.616 + inline ConstYMap<M> yMap(const M &m)
14.617 + {
14.618 + return ConstYMap<M>(m);
14.619 + }
14.620 +
14.621 +
14.622 + ///Map of the \ref Point::normSquare() "normSquare()" of an \ref Point "Point"-map
14.623 +
14.624 + ///Map of the \ref Point::normSquare() "normSquare()" of an \ref Point "Point"-map
14.625 + ///\ingroup maps
14.626 + ///
14.627 + template<class M>
14.628 + class NormSquareMap
14.629 + {
14.630 + const M& _map;
14.631 + public:
14.632 +
14.633 + typedef typename M::Value::Value Value;
14.634 + typedef typename M::Key Key;
14.635 + ///\e
14.636 + NormSquareMap(const M &map) : _map(map) {}
14.637 + Value operator[](Key k) const {return _map[k].normSquare();}
14.638 + };
14.639 +
14.640 + ///Returns a \ref NormSquareMap class
14.641 +
14.642 + ///This function just returns an \ref NormSquareMap class.
14.643 + ///
14.644 + ///\ingroup maps
14.645 + ///\relates NormSquareMap
14.646 + template<class M>
14.647 + inline NormSquareMap<M> normSquareMap(const M &m)
14.648 + {
14.649 + return NormSquareMap<M>(m);
14.650 + }
14.651 +
14.652 + /// @}
14.653 +
14.654 + } //namespce dim2
14.655 +
14.656 +} //namespace lemon
14.657 +
14.658 +#endif //LEMON_DIM2_H
15.1 --- a/lemon/eps.cc Wed Sep 06 11:39:22 2006 +0000
15.2 +++ b/lemon/eps.cc Thu Sep 07 13:27:16 2006 +0000
15.3 @@ -69,13 +69,13 @@
15.4 init(x1,y1,x2,y2);
15.5 }
15.6
15.7 - EpsDrawer::EpsDrawer(std::ostream &os,xy<double> s) : local_stream(false),
15.8 + EpsDrawer::EpsDrawer(std::ostream &os,dim2::Point<double> s) : local_stream(false),
15.9 out(os)
15.10 {
15.11 init(0.0,0.0,s.x,s.y);
15.12 }
15.13
15.14 - EpsDrawer::EpsDrawer(std::ostream &os,xy<double> a, xy<double> b) :
15.15 + EpsDrawer::EpsDrawer(std::ostream &os,dim2::Point<double> a, dim2::Point<double> b) :
15.16 local_stream(false),
15.17 out(os)
15.18 {
15.19 @@ -97,14 +97,14 @@
15.20 init(x1,y1,x2,y2);
15.21 }
15.22
15.23 - EpsDrawer::EpsDrawer(const std::string &name,xy<double> s) :
15.24 + EpsDrawer::EpsDrawer(const std::string &name,dim2::Point<double> s) :
15.25 local_stream(true),
15.26 out(*new std::ofstream(name.c_str()))
15.27 {
15.28 init(0.0,0.0,s.x,s.y);
15.29 }
15.30
15.31 - EpsDrawer::EpsDrawer(const std::string &name,xy<double> a, xy<double> b) :
15.32 + EpsDrawer::EpsDrawer(const std::string &name,dim2::Point<double> a, dim2::Point<double> b) :
15.33 local_stream(true),
15.34 out(*new std::ofstream(name.c_str()))
15.35 {
16.1 --- a/lemon/eps.h Wed Sep 06 11:39:22 2006 +0000
16.2 +++ b/lemon/eps.h Thu Sep 07 13:27:16 2006 +0000
16.3 @@ -24,7 +24,7 @@
16.4 #include<fstream>
16.5 #include<sstream>
16.6 #include<lemon/color.h>
16.7 -#include<lemon/xy.h>
16.8 +#include<lemon/dim2.h>
16.9
16.10 ///\ingroup eps_io
16.11 ///\file
16.12 @@ -100,7 +100,7 @@
16.13 ///
16.14 ///\c s determines the upper
16.15 ///right corner of the bounding box. The lower left corner is (0,0).
16.16 - EpsDrawer(std::ostream &os,xy<double> s);
16.17 + EpsDrawer(std::ostream &os,dim2::Point<double> s);
16.18 ///\e
16.19
16.20 ///The generated file is put to \c os.
16.21 @@ -108,7 +108,7 @@
16.22 ///\c a and \c b
16.23 /// determine the lower left and the upper right corners of
16.24 ///the bounding box, respectively.
16.25 - EpsDrawer(std::ostream &os,xy<double> a, xy<double> b);
16.26 + EpsDrawer(std::ostream &os,dim2::Point<double> a, dim2::Point<double> b);
16.27 ///\e
16.28
16.29 ///The generated picture is put to the file \c name.
16.30 @@ -130,7 +130,7 @@
16.31 ///
16.32 ///\c s determines the upper
16.33 ///right corner of the bounding box. The lower left corner is (0,0).
16.34 - EpsDrawer(const std::string &name,xy<double> s);
16.35 + EpsDrawer(const std::string &name,dim2::Point<double> s);
16.36 ///\e
16.37
16.38 ///The generated picture is put to the file \c name.
16.39 @@ -138,7 +138,7 @@
16.40 ///\c a and \c b
16.41 /// determine the lower left and the upper right corners of
16.42 ///the bounding box, respectively.
16.43 - EpsDrawer(const std::string &name,xy<double> a, xy<double> b);
16.44 + EpsDrawer(const std::string &name,dim2::Point<double> a, dim2::Point<double> b);
16.45
16.46 // template<class T> EpsDrawer(std::ostream &os,BoundingBox<T> b)
16.47 // template<class T> EpsDrawer(std::ostream &os,BoundingBox<T> b);
16.48 @@ -168,22 +168,22 @@
16.49 EpsDrawer &circle(double x,double y, double r);
16.50
16.51 ///Draw a line
16.52 - template<class T> EpsDrawer &line(xy<T> p1,xy<T> p2)
16.53 + template<class T> EpsDrawer &line(dim2::Point<T> p1,dim2::Point<T> p2)
16.54 {
16.55 return line(p1.x,p1.y,p2.x,p2.y);
16.56 }
16.57 ///Draw a line from the current point
16.58 - template<class T> EpsDrawer &lineTo(xy<T> p)
16.59 + template<class T> EpsDrawer &lineTo(dim2::Point<T> p)
16.60 {
16.61 return lineTo(p.x,p.y);
16.62 }
16.63 ///Move the current point
16.64 - template<class T> EpsDrawer &moveTo(xy<T> p)
16.65 + template<class T> EpsDrawer &moveTo(dim2::Point<T> p)
16.66 {
16.67 return moveTo(p.x,p.y);
16.68 }
16.69 ///Draw a circle
16.70 - template<class T> EpsDrawer &circle(xy<T> p, double r)
16.71 + template<class T> EpsDrawer &circle(dim2::Point<T> p, double r)
16.72 {
16.73 return circle(p.x,p.y,r);
16.74 }
16.75 @@ -296,7 +296,7 @@
16.76 ///\param col Color of the node. The default color is white
16.77 ///\param brd Color of the node border. The default color is black
16.78 template<class T>
16.79 - EpsDrawer &node(NodeShapes t, xy<T> pos, double r,
16.80 + EpsDrawer &node(NodeShapes t, dim2::Point<T> pos, double r,
16.81 Color col=WHITE, Color brd=BLACK)
16.82 {
16.83 return node(t,pos.x,pos.y,r,col,brd);
16.84 @@ -305,7 +305,7 @@
16.85 ///Translate the coordinate system
16.86 EpsDrawer &translate(double x,double y);
16.87 ///Translate the coordinate system
16.88 - template<class T> EpsDrawer &translate(xy<T> p)
16.89 + template<class T> EpsDrawer &translate(dim2::Point<T> p)
16.90 {
16.91 return translate(p.x,p.y);
16.92 }
16.93 @@ -316,7 +316,7 @@
16.94 ///Scale the coordinate system
16.95 EpsDrawer &scale(double s) { return scale(s,s); }
16.96 ///Scale the coordinate system
16.97 - template<class T> EpsDrawer &scale(xy<T> p)
16.98 + template<class T> EpsDrawer &scale(dim2::Point<T> p)
16.99 {
16.100 return scale(p.x,p.y);
16.101 }
16.102 @@ -336,7 +336,7 @@
16.103 EpsDrawer &operator<<(double d);
16.104 ///Print a coordinate at the current point
16.105 template<class T>
16.106 - EpsDrawer &operator<<(xy<T> p)
16.107 + EpsDrawer &operator<<(dim2::Point<T> p)
16.108 {
16.109 out << "((" << p.x << ',' << p.y <<")) show\n";
16.110 return *this;
17.1 --- a/lemon/graph_to_eps.h Wed Sep 06 11:39:22 2006 +0000
17.2 +++ b/lemon/graph_to_eps.h Thu Sep 07 13:27:16 2006 +0000
17.3 @@ -35,7 +35,7 @@
17.4 #include <cmath>
17.5
17.6 #include<lemon/bits/invalid.h>
17.7 -#include<lemon/xy.h>
17.8 +#include<lemon/dim2.h>
17.9 #include<lemon/maps.h>
17.10 #include<lemon/color.h>
17.11 #include<lemon/bits/bezier.h>
17.12 @@ -81,7 +81,7 @@
17.13
17.14 std::ostream& os;
17.15
17.16 - typedef ConstMap<typename Graph::Node,xy<double> > CoordsMapType;
17.17 + typedef ConstMap<typename Graph::Node,dim2::Point<double> > CoordsMapType;
17.18 CoordsMapType _coords;
17.19 ConstMap<typename Graph::Node,double > _nodeSizes;
17.20 ConstMap<typename Graph::Node,int > _nodeShapes;
17.21 @@ -146,7 +146,7 @@
17.22 DefaultGraphToEpsTraits(const G &_g,std::ostream& _os=std::cout,
17.23 bool _pros=false) :
17.24 g(_g), os(_os),
17.25 - _coords(xy<double>(1,1)), _nodeSizes(.01), _nodeShapes(0),
17.26 + _coords(dim2::Point<double>(1,1)), _nodeSizes(.01), _nodeShapes(0),
17.27 _nodeColors(WHITE), _edgeColors(BLACK),
17.28 _edgeWidths(1.0), _edgeWidthScale(0.003),
17.29 _nodeScale(1.0), _xBorder(10), _yBorder(10), _scale(1.0),
17.30 @@ -313,7 +313,7 @@
17.31 g.target(e)==g.source(f));
17.32 }
17.33 template<class TT>
17.34 - static std::string psOut(const xy<TT> &p)
17.35 + static std::string psOut(const dim2::Point<TT> &p)
17.36 {
17.37 std::ostringstream os;
17.38 os << p.x << ' ' << p.y;
17.39 @@ -337,7 +337,8 @@
17.40 ///Sets the map of the node coordinates
17.41
17.42 ///Sets the map of the node coordinates.
17.43 - ///\param x must be a node map with xy<double> or \ref xy "xy<int>" values.
17.44 + ///\param x must be a node map with dim2::Point<double> or
17.45 + ///\ref dim2::Point "dim2::Point<int>" values.
17.46 template<class X> GraphToEps<CoordsTraits<X> > coords(const X &x) {
17.47 dontPrint=true;
17.48 return GraphToEps<CoordsTraits<X> >(CoordsTraits<X>(*this,x));
17.49 @@ -669,7 +670,7 @@
17.50 GraphToEps<T> ©right(const std::string &t) {_copyright=t;return *this;}
17.51
17.52 protected:
17.53 - bool isInsideNode(xy<double> p, double r,int t)
17.54 + bool isInsideNode(dim2::Point<double> p, double r,int t)
17.55 {
17.56 switch(t) {
17.57 case CIRCLE:
17.58 @@ -736,10 +737,10 @@
17.59
17.60 double diag_len = 1;
17.61 if(!(_absoluteNodeSizes&&_absoluteEdgeWidths)) {
17.62 - BoundingBox<double> bb;
17.63 + dim2::BoundingBox<double> bb;
17.64 for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]);
17.65 if (bb.empty()) {
17.66 - bb = BoundingBox<double>(xy<double>(0,0));
17.67 + bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
17.68 }
17.69 diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare());
17.70 if(diag_len<EPSILON) diag_len = 1;
17.71 @@ -747,10 +748,10 @@
17.72 if(!_absoluteEdgeWidths) _edgeWidthScale*=diag_len;
17.73 }
17.74
17.75 - BoundingBox<double> bb;
17.76 + dim2::BoundingBox<double> bb;
17.77 for(NodeIt n(g);n!=INVALID;++n) {
17.78 double ns=_nodeSizes[n]*_nodeScale;
17.79 - xy<double> p(ns,ns);
17.80 + dim2::Point<double> p(ns,ns);
17.81 switch(_nodeShapes[n]) {
17.82 case CIRCLE:
17.83 case SQUARE:
17.84 @@ -760,16 +761,16 @@
17.85 break;
17.86 case MALE:
17.87 bb.add(-p+mycoords[n]);
17.88 - bb.add(xy<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
17.89 + bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]);
17.90 break;
17.91 case FEMALE:
17.92 bb.add(p+mycoords[n]);
17.93 - bb.add(xy<double>(-ns,-3.01*ns)+mycoords[n]);
17.94 + bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]);
17.95 break;
17.96 }
17.97 }
17.98 if (bb.empty()) {
17.99 - bb = BoundingBox<double>(xy<double>(0,0));
17.100 + bb = dim2::BoundingBox<double>(dim2::Point<double>(0,0));
17.101 }
17.102
17.103 if(_scaleToA4)
17.104 @@ -870,7 +871,8 @@
17.105 double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(),
17.106 (A4WIDTH-2*A4BORDER)/bb.width());
17.107 os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' '
17.108 - << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER << " translate\n"
17.109 + << ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER
17.110 + << " translate\n"
17.111 << sc << " dup scale\n"
17.112 << -bb.left() << ' ' << -bb.bottom() << " translate\n";
17.113 }
17.114 @@ -879,7 +881,8 @@
17.115 double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(),
17.116 (A4WIDTH-2*A4BORDER)/bb.height());
17.117 os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' '
17.118 - << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER << " translate\n"
17.119 + << ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER
17.120 + << " translate\n"
17.121 << sc << " dup scale\n90 rotate\n"
17.122 << -bb.left() << ' ' << -bb.top() << " translate\n";
17.123 }
17.124 @@ -904,42 +907,43 @@
17.125 sw+=_edgeWidths[*e]*_edgeWidthScale+_parEdgeDist;
17.126 sw-=_parEdgeDist;
17.127 sw/=-2.0;
17.128 - xy<double> dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
17.129 + dim2::Point<double>
17.130 + dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]);
17.131 double l=std::sqrt(dvec.normSquare());
17.132 ///\todo better 'epsilon' would be nice here.
17.133 - xy<double> d(dvec/std::max(l,EPSILON));
17.134 - xy<double> m;
17.135 -// m=xy<double>(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0;
17.136 + dim2::Point<double> d(dvec/std::max(l,EPSILON));
17.137 + dim2::Point<double> m;
17.138 +// m=dim2::Point<double>(mycoords[g.target(*i)]+mycoords[g.source(*i)])/2.0;
17.139
17.140 -// m=xy<double>(mycoords[g.source(*i)])+
17.141 +// m=dim2::Point<double>(mycoords[g.source(*i)])+
17.142 // dvec*(double(_nodeSizes[g.source(*i)])/
17.143 // (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)]));
17.144
17.145 - m=xy<double>(mycoords[g.source(*i)])+
17.146 + m=dim2::Point<double>(mycoords[g.source(*i)])+
17.147 d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0;
17.148
17.149 for(typename std::vector<Edge>::iterator e=i;e!=j;++e) {
17.150 sw+=_edgeWidths[*e]*_edgeWidthScale/2.0;
17.151 - xy<double> mm=m+rot90(d)*sw/.75;
17.152 + dim2::Point<double> mm=m+rot90(d)*sw/.75;
17.153 if(_drawArrows) {
17.154 int node_shape;
17.155 - xy<double> s=mycoords[g.source(*e)];
17.156 - xy<double> t=mycoords[g.target(*e)];
17.157 + dim2::Point<double> s=mycoords[g.source(*e)];
17.158 + dim2::Point<double> t=mycoords[g.target(*e)];
17.159 double rn=_nodeSizes[g.target(*e)]*_nodeScale;
17.160 node_shape=_nodeShapes[g.target(*e)];
17.161 - Bezier3 bez(s,mm,mm,t);
17.162 + dim2::Bezier3 bez(s,mm,mm,t);
17.163 double t1=0,t2=1;
17.164 for(int i=0;i<INTERPOL_PREC;++i)
17.165 if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2;
17.166 else t1=(t1+t2)/2;
17.167 - xy<double> apoint=bez((t1+t2)/2);
17.168 + dim2::Point<double> apoint=bez((t1+t2)/2);
17.169 rn = _arrowLength+_edgeWidths[*e]*_edgeWidthScale;
17.170 rn*=rn;
17.171 t2=(t1+t2)/2;t1=0;
17.172 for(int i=0;i<INTERPOL_PREC;++i)
17.173 if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2;
17.174 else t2=(t1+t2)/2;
17.175 - xy<double> linend=bez((t1+t2)/2);
17.176 + dim2::Point<double> linend=bez((t1+t2)/2);
17.177 bez=bez.before((t1+t2)/2);
17.178 // rn=_nodeSizes[g.source(*e)]*_nodeScale;
17.179 // node_shape=_nodeShapes[g.source(*e)];
17.180 @@ -956,7 +960,7 @@
17.181 << bez.p2.x << ' ' << bez.p2.y << ' '
17.182 << bez.p3.x << ' ' << bez.p3.y << ' '
17.183 << bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n";
17.184 - xy<double> dd(rot90(linend-apoint));
17.185 + dim2::Point<double> dd(rot90(linend-apoint));
17.186 dd*=(.5*_edgeWidths[*e]*_edgeWidthScale+_arrowWidth)/
17.187 std::sqrt(dd.normSquare());
17.188 os << "newpath " << psOut(apoint) << " moveto "
17.189 @@ -982,7 +986,7 @@
17.190 if((!_undirected||g.source(e)<g.target(e))&&_edgeWidths[e]>0
17.191 &&g.source(e)!=g.target(e))
17.192 if(_drawArrows) {
17.193 - xy<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
17.194 + dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]);
17.195 double rn=_nodeSizes[g.target(e)]*_nodeScale;
17.196 int node_shape=_nodeShapes[g.target(e)];
17.197 double t1=0,t2=1;
18.1 --- a/lemon/grid_ugraph.h Wed Sep 06 11:39:22 2006 +0000
18.2 +++ b/lemon/grid_ugraph.h Thu Sep 07 13:27:16 2006 +0000
18.3 @@ -26,7 +26,7 @@
18.4 #include <lemon/bits/base_extender.h>
18.5 #include <lemon/bits/graph_extender.h>
18.6
18.7 -#include <lemon/xy.h>
18.8 +#include <lemon/dim2.h>
18.9
18.10 ///\ingroup graphs
18.11 ///\file
18.12 @@ -381,15 +381,15 @@
18.13
18.14 typedef ExtendedGridUGraphBase Parent;
18.15
18.16 - /// \brief Map to get the indices of the nodes as xy<int>.
18.17 + /// \brief Map to get the indices of the nodes as dim2::Point<int>.
18.18 ///
18.19 - /// Map to get the indices of the nodes as xy<int>.
18.20 + /// Map to get the indices of the nodes as dim2::Point<int>.
18.21 class IndexMap {
18.22 public:
18.23 /// \brief The key type of the map
18.24 typedef GridUGraph::Node Key;
18.25 /// \brief The value type of the map
18.26 - typedef xy<int> Value;
18.27 + typedef dim2::Point<int> Value;
18.28
18.29 /// \brief Constructor
18.30 ///
18.31 @@ -400,7 +400,7 @@
18.32 ///
18.33 /// The subscript operator.
18.34 Value operator[](Key key) const {
18.35 - return xy<int>(graph.row(key), graph.col(key));
18.36 + return dim2::Point<int>(graph.row(key), graph.col(key));
18.37 }
18.38
18.39 private:
19.1 --- a/lemon/hypercube_graph.h Wed Sep 06 11:39:22 2006 +0000
19.2 +++ b/lemon/hypercube_graph.h Thu Sep 07 13:27:16 2006 +0000
19.3 @@ -275,13 +275,13 @@
19.4 ///\code
19.5 /// const int DIM = 3;
19.6 /// HyperCubeGraph graph(DIM);
19.7 - /// xy<double> base[DIM];
19.8 + /// dim2::Point<double> base[DIM];
19.9 /// for (int k = 0; k < DIM; ++k) {
19.10 /// base[k].x = rand() / (RAND_MAX + 1.0);
19.11 /// base[k].y = rand() / (RAND_MAX + 1.0);
19.12 /// }
19.13 - /// HyperCubeGraph::HyperMap<xy<double> >
19.14 - /// pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
19.15 + /// HyperCubeGraph::HyperMap<dim2::Point<double> >
19.16 + /// pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
19.17 ///\endcode
19.18 ///
19.19 /// \see HyperCubeGraph
20.1 --- a/lemon/lemon_reader.h Wed Sep 06 11:39:22 2006 +0000
20.2 +++ b/lemon/lemon_reader.h Thu Sep 07 13:27:16 2006 +0000
20.3 @@ -38,7 +38,7 @@
20.4 #include <lemon/bits/utility.h>
20.5 #include <lemon/bits/item_reader.h>
20.6
20.7 -#include <lemon/xy.h>
20.8 +#include <lemon/dim2.h>
20.9
20.10 #include <lemon/concept_check.h>
20.11 #include <lemon/concept/maps.h>
20.12 @@ -183,21 +183,21 @@
20.13 };
20.14
20.15 template <typename Map>
20.16 - struct Ref<XMap<Map> > {
20.17 - typedef XMap<Map> Type;
20.18 + struct Ref<dim2::XMap<Map> > {
20.19 + typedef dim2::XMap<Map> Type;
20.20 };
20.21 template <typename Map>
20.22 - struct Arg<XMap<Map> > {
20.23 - typedef const XMap<Map>& Type;
20.24 + struct Arg<dim2::XMap<Map> > {
20.25 + typedef const dim2::XMap<Map>& Type;
20.26 };
20.27
20.28 template <typename Map>
20.29 - struct Ref<YMap<Map> > {
20.30 - typedef YMap<Map> Type;
20.31 + struct Ref<dim2::YMap<Map> > {
20.32 + typedef dim2::YMap<Map> Type;
20.33 };
20.34 template <typename Map>
20.35 - struct Arg<YMap<Map> > {
20.36 - typedef const YMap<Map>& Type;
20.37 + struct Arg<dim2::YMap<Map> > {
20.38 + typedef const dim2::YMap<Map>& Type;
20.39 };
20.40
20.41
21.1 --- a/lemon/lemon_writer.h Wed Sep 06 11:39:22 2006 +0000
21.2 +++ b/lemon/lemon_writer.h Thu Sep 07 13:27:16 2006 +0000
21.3 @@ -37,7 +37,7 @@
21.4 #include <lemon/bits/item_writer.h>
21.5 #include <lemon/bits/utility.h>
21.6 #include <lemon/maps.h>
21.7 -#include <lemon/xy.h>
21.8 +#include <lemon/dim2.h>
21.9
21.10 #include <lemon/concept_check.h>
21.11 #include <lemon/concept/maps.h>
21.12 @@ -173,21 +173,21 @@
21.13 };
21.14
21.15 template <typename Map>
21.16 - struct Ref<XMap<Map> > {
21.17 - typedef XMap<Map> Type;
21.18 + struct Ref<dim2::XMap<Map> > {
21.19 + typedef dim2::XMap<Map> Type;
21.20 };
21.21 template <typename Map>
21.22 - struct Ref<ConstXMap<Map> > {
21.23 - typedef ConstXMap<Map> Type;
21.24 + struct Ref<dim2::ConstXMap<Map> > {
21.25 + typedef dim2::ConstXMap<Map> Type;
21.26 };
21.27
21.28 template <typename Map>
21.29 - struct Ref<YMap<Map> > {
21.30 - typedef YMap<Map> Type;
21.31 + struct Ref<dim2::YMap<Map> > {
21.32 + typedef dim2::YMap<Map> Type;
21.33 };
21.34 template <typename Map>
21.35 - struct Ref<ConstYMap<Map> > {
21.36 - typedef ConstYMap<Map> Type;
21.37 + struct Ref<dim2::ConstYMap<Map> > {
21.38 + typedef dim2::ConstYMap<Map> Type;
21.39 };
21.40
21.41
22.1 --- a/lemon/polynomial.h Wed Sep 06 11:39:22 2006 +0000
22.2 +++ b/lemon/polynomial.h Thu Sep 07 13:27:16 2006 +0000
22.3 @@ -76,11 +76,11 @@
22.4 ///The calculation will be done using type \c R.
22.5 ///The following examples shows the usage of the template parameter \c R.
22.6 ///\code
22.7 - /// Polynomial<xy<double> > line(1);
22.8 - /// line[0]=xy<double>(12,25);
22.9 - /// line[1]=xy<double>(2,7);
22.10 + /// Polynomial<dim2::Point<double> > line(1);
22.11 + /// line[0]=dim2::Point<double>(12,25);
22.12 + /// line[1]=dim2::Point<double>(2,7);
22.13 /// ...
22.14 - /// xy<double> d = line.subst<xy<double> >(23.2);
22.15 + /// dim2::Point<double> d = line.subst<dim2::Point<double> >(23.2);
22.16 ///\endcode
22.17 ///
22.18 ///\code
23.1 --- a/lemon/xy.h Wed Sep 06 11:39:22 2006 +0000
23.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
23.3 @@ -1,654 +0,0 @@
23.4 -/* -*- C++ -*-
23.5 - *
23.6 - * This file is a part of LEMON, a generic C++ optimization library
23.7 - *
23.8 - * Copyright (C) 2003-2006
23.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
23.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
23.11 - *
23.12 - * Permission to use, modify and distribute this software is granted
23.13 - * provided that this copyright notice appears in all copies. For
23.14 - * precise terms see the accompanying LICENSE file.
23.15 - *
23.16 - * This software is provided "AS IS" with no warranty of any kind,
23.17 - * express or implied, and with no claim as to its suitability for any
23.18 - * purpose.
23.19 - *
23.20 - */
23.21 -
23.22 -#ifndef LEMON_XY_H
23.23 -#define LEMON_XY_H
23.24 -
23.25 -#include <iostream>
23.26 -#include <lemon/bits/utility.h>
23.27 -
23.28 -///\ingroup misc
23.29 -///\file
23.30 -///\brief A simple two dimensional vector and a bounding box implementation
23.31 -///
23.32 -/// The class \ref lemon::xy "xy" implements
23.33 -///a two dimensional vector with the usual
23.34 -/// operations.
23.35 -///
23.36 -/// The class \ref lemon::BoundingBox "BoundingBox" can be used to determine
23.37 -/// the rectangular bounding box of a set of \ref lemon::xy "xy"'s.
23.38 -///
23.39 -///\author Attila Bernath
23.40 -
23.41 -
23.42 -namespace lemon {
23.43 -
23.44 - /// \addtogroup misc
23.45 - /// @{
23.46 -
23.47 - /// A simple two dimensional vector (plainvector) implementation
23.48 -
23.49 - /// A simple two dimensional vector (plainvector) implementation
23.50 - ///with the usual vector
23.51 - /// operators.
23.52 - ///
23.53 - ///\note As you might have noticed, this class does not follow the
23.54 - ///\ref naming_conv "LEMON Coding Style" (it should be called \c Xy
23.55 - ///according to it). There is a stupid Hungarian proverb, "A kivétel
23.56 - ///erõsíti a szabályt" ("An exception
23.57 - ///reinforces a rule", which is
23.58 - ///actually a mistranslation of the Latin proverb "Exceptio probat regulam").
23.59 - ///This class is an example for that.
23.60 - ///\author Attila Bernath
23.61 - template<typename T>
23.62 - class xy {
23.63 -
23.64 - public:
23.65 -
23.66 - typedef T Value;
23.67 -
23.68 - ///First co-ordinate
23.69 - T x;
23.70 - ///Second co-ordinate
23.71 - T y;
23.72 -
23.73 - ///Default constructor
23.74 - xy() {}
23.75 -
23.76 - ///Construct an instance from coordinates
23.77 - xy(T a, T b) : x(a), y(b) { }
23.78 -
23.79 -
23.80 - ///Conversion constructor
23.81 - template<class TT> xy(const xy<TT> &p) : x(p.x), y(p.y) {}
23.82 -
23.83 - ///Give back the square of the norm of the vector
23.84 - T normSquare() const {
23.85 - return x*x+y*y;
23.86 - }
23.87 -
23.88 - ///Increment the left hand side by u
23.89 - xy<T>& operator +=(const xy<T>& u) {
23.90 - x += u.x;
23.91 - y += u.y;
23.92 - return *this;
23.93 - }
23.94 -
23.95 - ///Decrement the left hand side by u
23.96 - xy<T>& operator -=(const xy<T>& u) {
23.97 - x -= u.x;
23.98 - y -= u.y;
23.99 - return *this;
23.100 - }
23.101 -
23.102 - ///Multiply the left hand side with a scalar
23.103 - xy<T>& operator *=(const T &u) {
23.104 - x *= u;
23.105 - y *= u;
23.106 - return *this;
23.107 - }
23.108 -
23.109 - ///Divide the left hand side by a scalar
23.110 - xy<T>& operator /=(const T &u) {
23.111 - x /= u;
23.112 - y /= u;
23.113 - return *this;
23.114 - }
23.115 -
23.116 - ///Return the scalar product of two vectors
23.117 - T operator *(const xy<T>& u) const {
23.118 - return x*u.x+y*u.y;
23.119 - }
23.120 -
23.121 - ///Return the sum of two vectors
23.122 - xy<T> operator+(const xy<T> &u) const {
23.123 - xy<T> b=*this;
23.124 - return b+=u;
23.125 - }
23.126 -
23.127 - ///Return the neg of the vectors
23.128 - xy<T> operator-() const {
23.129 - xy<T> b=*this;
23.130 - b.x=-b.x; b.y=-b.y;
23.131 - return b;
23.132 - }
23.133 -
23.134 - ///Return the difference of two vectors
23.135 - xy<T> operator-(const xy<T> &u) const {
23.136 - xy<T> b=*this;
23.137 - return b-=u;
23.138 - }
23.139 -
23.140 - ///Return a vector multiplied by a scalar
23.141 - xy<T> operator*(const T &u) const {
23.142 - xy<T> b=*this;
23.143 - return b*=u;
23.144 - }
23.145 -
23.146 - ///Return a vector divided by a scalar
23.147 - xy<T> operator/(const T &u) const {
23.148 - xy<T> b=*this;
23.149 - return b/=u;
23.150 - }
23.151 -
23.152 - ///Test equality
23.153 - bool operator==(const xy<T> &u) const {
23.154 - return (x==u.x) && (y==u.y);
23.155 - }
23.156 -
23.157 - ///Test inequality
23.158 - bool operator!=(xy u) const {
23.159 - return (x!=u.x) || (y!=u.y);
23.160 - }
23.161 -
23.162 - };
23.163 -
23.164 - ///Return an xy
23.165 -
23.166 - ///Return an xy
23.167 - ///\relates xy
23.168 - template <typename T>
23.169 - inline xy<T> make_xy(const T& x, const T& y) {
23.170 - return xy<T>(x, y);
23.171 - }
23.172 -
23.173 - ///Return a vector multiplied by a scalar
23.174 -
23.175 - ///Return a vector multiplied by a scalar
23.176 - ///\relates xy
23.177 - template<typename T> xy<T> operator*(const T &u,const xy<T> &x) {
23.178 - return x*u;
23.179 - }
23.180 -
23.181 - ///Read a plainvector from a stream
23.182 -
23.183 - ///Read a plainvector from a stream
23.184 - ///\relates xy
23.185 - ///
23.186 - template<typename T>
23.187 - inline std::istream& operator>>(std::istream &is, xy<T> &z) {
23.188 - char c;
23.189 - if (is >> c) {
23.190 - if (c != '(') is.putback(c);
23.191 - } else {
23.192 - is.clear();
23.193 - }
23.194 - if (!(is >> z.x)) return is;
23.195 - if (is >> c) {
23.196 - if (c != ',') is.putback(c);
23.197 - } else {
23.198 - is.clear();
23.199 - }
23.200 - if (!(is >> z.y)) return is;
23.201 - if (is >> c) {
23.202 - if (c != ')') is.putback(c);
23.203 - } else {
23.204 - is.clear();
23.205 - }
23.206 - return is;
23.207 - }
23.208 -
23.209 - ///Write a plainvector to a stream
23.210 -
23.211 - ///Write a plainvector to a stream
23.212 - ///\relates xy
23.213 - ///
23.214 - template<typename T>
23.215 - inline std::ostream& operator<<(std::ostream &os, const xy<T>& z)
23.216 - {
23.217 - os << "(" << z.x << ", " << z.y << ")";
23.218 - return os;
23.219 - }
23.220 -
23.221 - ///Rotate by 90 degrees
23.222 -
23.223 - ///Returns its parameter rotated by 90 degrees in positive direction.
23.224 - ///\relates xy
23.225 - ///
23.226 - template<typename T>
23.227 - inline xy<T> rot90(const xy<T> &z)
23.228 - {
23.229 - return xy<T>(-z.y,z.x);
23.230 - }
23.231 -
23.232 - ///Rotate by 180 degrees
23.233 -
23.234 - ///Returns its parameter rotated by 180 degrees.
23.235 - ///\relates xy
23.236 - ///
23.237 - template<typename T>
23.238 - inline xy<T> rot180(const xy<T> &z)
23.239 - {
23.240 - return xy<T>(-z.x,-z.y);
23.241 - }
23.242 -
23.243 - ///Rotate by 270 degrees
23.244 -
23.245 - ///Returns its parameter rotated by 90 degrees in negative direction.
23.246 - ///\relates xy
23.247 - ///
23.248 - template<typename T>
23.249 - inline xy<T> rot270(const xy<T> &z)
23.250 - {
23.251 - return xy<T>(z.y,-z.x);
23.252 - }
23.253 -
23.254 -
23.255 -
23.256 - /// A class to calculate or store the bounding box of plainvectors.
23.257 -
23.258 - /// A class to calculate or store the bounding box of plainvectors.
23.259 - ///
23.260 - ///\author Attila Bernath
23.261 - template<typename T>
23.262 - class BoundingBox {
23.263 - xy<T> bottom_left, top_right;
23.264 - bool _empty;
23.265 - public:
23.266 -
23.267 - ///Default constructor: creates an empty bounding box
23.268 - BoundingBox() { _empty = true; }
23.269 -
23.270 - ///Construct an instance from one point
23.271 - BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
23.272 -
23.273 - ///Were any points added?
23.274 - bool empty() const {
23.275 - return _empty;
23.276 - }
23.277 -
23.278 - ///Make the BoundingBox empty
23.279 - void clear() {
23.280 - _empty=1;
23.281 - }
23.282 -
23.283 - ///Give back the bottom left corner
23.284 -
23.285 - ///Give back the bottom left corner.
23.286 - ///If the bounding box is empty, then the return value is not defined.
23.287 - xy<T> bottomLeft() const {
23.288 - return bottom_left;
23.289 - }
23.290 -
23.291 - ///Set the bottom left corner
23.292 -
23.293 - ///Set the bottom left corner.
23.294 - ///It should only bee used for non-empty box.
23.295 - void bottomLeft(xy<T> p) {
23.296 - bottom_left = p;
23.297 - }
23.298 -
23.299 - ///Give back the top right corner
23.300 -
23.301 - ///Give back the top right corner.
23.302 - ///If the bounding box is empty, then the return value is not defined.
23.303 - xy<T> topRight() const {
23.304 - return top_right;
23.305 - }
23.306 -
23.307 - ///Set the top right corner
23.308 -
23.309 - ///Set the top right corner.
23.310 - ///It should only bee used for non-empty box.
23.311 - void topRight(xy<T> p) {
23.312 - top_right = p;
23.313 - }
23.314 -
23.315 - ///Give back the bottom right corner
23.316 -
23.317 - ///Give back the bottom right corner.
23.318 - ///If the bounding box is empty, then the return value is not defined.
23.319 - xy<T> bottomRight() const {
23.320 - return xy<T>(top_right.x,bottom_left.y);
23.321 - }
23.322 -
23.323 - ///Set the bottom right corner
23.324 -
23.325 - ///Set the bottom right corner.
23.326 - ///It should only bee used for non-empty box.
23.327 - void bottomRight(xy<T> p) {
23.328 - top_right.x = p.x;
23.329 - bottom_left.y = p.y;
23.330 - }
23.331 -
23.332 - ///Give back the top left corner
23.333 -
23.334 - ///Give back the top left corner.
23.335 - ///If the bounding box is empty, then the return value is not defined.
23.336 - xy<T> topLeft() const {
23.337 - return xy<T>(bottom_left.x,top_right.y);
23.338 - }
23.339 -
23.340 - ///Set the top left corner
23.341 -
23.342 - ///Set the top left corner.
23.343 - ///It should only bee used for non-empty box.
23.344 - void topLeft(xy<T> p) {
23.345 - top_right.y = p.y;
23.346 - bottom_left.x = p.x;
23.347 - }
23.348 -
23.349 - ///Give back the bottom of the box
23.350 -
23.351 - ///Give back the bottom of the box.
23.352 - ///If the bounding box is empty, then the return value is not defined.
23.353 - T bottom() const {
23.354 - return bottom_left.y;
23.355 - }
23.356 -
23.357 - ///Set the bottom of the box
23.358 -
23.359 - ///Set the bottom of the box.
23.360 - ///It should only bee used for non-empty box.
23.361 - void bottom(T t) {
23.362 - bottom_left.y = t;
23.363 - }
23.364 -
23.365 - ///Give back the top of the box
23.366 -
23.367 - ///Give back the top of the box.
23.368 - ///If the bounding box is empty, then the return value is not defined.
23.369 - T top() const {
23.370 - return top_right.y;
23.371 - }
23.372 -
23.373 - ///Set the top of the box
23.374 -
23.375 - ///Set the top of the box.
23.376 - ///It should only bee used for non-empty box.
23.377 - void top(T t) {
23.378 - top_right.y = t;
23.379 - }
23.380 -
23.381 - ///Give back the left side of the box
23.382 -
23.383 - ///Give back the left side of the box.
23.384 - ///If the bounding box is empty, then the return value is not defined.
23.385 - T left() const {
23.386 - return bottom_left.x;
23.387 - }
23.388 -
23.389 - ///Set the left side of the box
23.390 -
23.391 - ///Set the left side of the box.
23.392 - ///It should only bee used for non-empty box
23.393 - void left(T t) {
23.394 - bottom_left.x = t;
23.395 - }
23.396 -
23.397 - /// Give back the right side of the box
23.398 -
23.399 - /// Give back the right side of the box.
23.400 - ///If the bounding box is empty, then the return value is not defined.
23.401 - T right() const {
23.402 - return top_right.x;
23.403 - }
23.404 -
23.405 - ///Set the right side of the box
23.406 -
23.407 - ///Set the right side of the box.
23.408 - ///It should only bee used for non-empty box
23.409 - void right(T t) {
23.410 - top_right.x = t;
23.411 - }
23.412 -
23.413 - ///Give back the height of the box
23.414 -
23.415 - ///Give back the height of the box.
23.416 - ///If the bounding box is empty, then the return value is not defined.
23.417 - T height() const {
23.418 - return top_right.y-bottom_left.y;
23.419 - }
23.420 -
23.421 - ///Give back the width of the box
23.422 -
23.423 - ///Give back the width of the box.
23.424 - ///If the bounding box is empty, then the return value is not defined.
23.425 - T width() const {
23.426 - return top_right.x-bottom_left.x;
23.427 - }
23.428 -
23.429 - ///Checks whether a point is inside a bounding box
23.430 - bool inside(const xy<T>& u){
23.431 - if (_empty)
23.432 - return false;
23.433 - else{
23.434 - return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
23.435 - (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
23.436 - }
23.437 - }
23.438 -
23.439 - ///Increments a bounding box with a point
23.440 - BoundingBox& add(const xy<T>& u){
23.441 - if (_empty){
23.442 - bottom_left=top_right=u;
23.443 - _empty = false;
23.444 - }
23.445 - else{
23.446 - if (bottom_left.x > u.x) bottom_left.x = u.x;
23.447 - if (bottom_left.y > u.y) bottom_left.y = u.y;
23.448 - if (top_right.x < u.x) top_right.x = u.x;
23.449 - if (top_right.y < u.y) top_right.y = u.y;
23.450 - }
23.451 - return *this;
23.452 - }
23.453 -
23.454 -// ///Sums a bounding box and a point
23.455 -// BoundingBox operator +(const xy<T>& u){
23.456 -// BoundingBox b = *this;
23.457 -// return b += u;
23.458 -// }
23.459 -
23.460 - ///Increments a bounding box with another bounding box
23.461 - BoundingBox& add(const BoundingBox &u){
23.462 - if ( !u.empty() ){
23.463 - this->add(u.bottomLeft());
23.464 - this->add(u.topRight());
23.465 - }
23.466 - return *this;
23.467 - }
23.468 -
23.469 - ///Sums two bounding boxes
23.470 - BoundingBox operator +(const BoundingBox& u){
23.471 - BoundingBox b = *this;
23.472 - return b.add(u);
23.473 - }
23.474 -
23.475 -
23.476 - ///Intersection of two bounding boxes
23.477 - BoundingBox operator &(const BoundingBox& u){
23.478 - BoundingBox b;
23.479 - b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
23.480 - b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
23.481 - b.top_right.x=std::min(this->top_right.x,u.top_right.x);
23.482 - b.top_right.y=std::min(this->top_right.y,u.top_right.y);
23.483 - b._empty = this->_empty || u._empty ||
23.484 - b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
23.485 - return b;
23.486 - }
23.487 -
23.488 - };//class Boundingbox
23.489 -
23.490 -
23.491 - ///Map of x-coordinates of an xy<>-map
23.492 -
23.493 - ///\ingroup maps
23.494 - ///
23.495 - template<class M>
23.496 - class XMap
23.497 - {
23.498 - M& _map;
23.499 - public:
23.500 -
23.501 - typedef typename M::Value::Value Value;
23.502 - typedef typename M::Key Key;
23.503 - ///\e
23.504 - XMap(M& map) : _map(map) {}
23.505 - Value operator[](Key k) const {return _map[k].x;}
23.506 - void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
23.507 - };
23.508 -
23.509 - ///Returns an \ref XMap class
23.510 -
23.511 - ///This function just returns an \ref XMap class.
23.512 - ///
23.513 - ///\ingroup maps
23.514 - ///\relates XMap
23.515 - template<class M>
23.516 - inline XMap<M> xMap(M &m)
23.517 - {
23.518 - return XMap<M>(m);
23.519 - }
23.520 -
23.521 - template<class M>
23.522 - inline XMap<M> xMap(const M &m)
23.523 - {
23.524 - return XMap<M>(m);
23.525 - }
23.526 -
23.527 - ///Constant (read only) version of \ref XMap
23.528 -
23.529 - ///\ingroup maps
23.530 - ///
23.531 - template<class M>
23.532 - class ConstXMap
23.533 - {
23.534 - const M& _map;
23.535 - public:
23.536 -
23.537 - typedef typename M::Value::Value Value;
23.538 - typedef typename M::Key Key;
23.539 - ///\e
23.540 - ConstXMap(const M &map) : _map(map) {}
23.541 - Value operator[](Key k) const {return _map[k].x;}
23.542 - };
23.543 -
23.544 - ///Returns a \ref ConstXMap class
23.545 -
23.546 - ///This function just returns an \ref ConstXMap class.
23.547 - ///
23.548 - ///\ingroup maps
23.549 - ///\relates ConstXMap
23.550 - template<class M>
23.551 - inline ConstXMap<M> xMap(const M &m)
23.552 - {
23.553 - return ConstXMap<M>(m);
23.554 - }
23.555 -
23.556 - ///Map of y-coordinates of an xy<>-map
23.557 -
23.558 - ///\ingroup maps
23.559 - ///
23.560 - template<class M>
23.561 - class YMap
23.562 - {
23.563 - M& _map;
23.564 - public:
23.565 -
23.566 - typedef typename M::Value::Value Value;
23.567 - typedef typename M::Key Key;
23.568 - ///\e
23.569 - YMap(M& map) : _map(map) {}
23.570 - Value operator[](Key k) const {return _map[k].y;}
23.571 - void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
23.572 - };
23.573 -
23.574 - ///Returns an \ref YMap class
23.575 -
23.576 - ///This function just returns an \ref YMap class.
23.577 - ///
23.578 - ///\ingroup maps
23.579 - ///\relates YMap
23.580 - template<class M>
23.581 - inline YMap<M> yMap(M &m)
23.582 - {
23.583 - return YMap<M>(m);
23.584 - }
23.585 -
23.586 - template<class M>
23.587 - inline YMap<M> yMap(const M &m)
23.588 - {
23.589 - return YMap<M>(m);
23.590 - }
23.591 -
23.592 - ///Constant (read only) version of \ref YMap
23.593 -
23.594 - ///\ingroup maps
23.595 - ///
23.596 - template<class M>
23.597 - class ConstYMap
23.598 - {
23.599 - const M& _map;
23.600 - public:
23.601 -
23.602 - typedef typename M::Value::Value Value;
23.603 - typedef typename M::Key Key;
23.604 - ///\e
23.605 - ConstYMap(const M &map) : _map(map) {}
23.606 - Value operator[](Key k) const {return _map[k].y;}
23.607 - };
23.608 -
23.609 - ///Returns a \ref ConstYMap class
23.610 -
23.611 - ///This function just returns an \ref ConstYMap class.
23.612 - ///
23.613 - ///\ingroup maps
23.614 - ///\relates ConstYMap
23.615 - template<class M>
23.616 - inline ConstYMap<M> yMap(const M &m)
23.617 - {
23.618 - return ConstYMap<M>(m);
23.619 - }
23.620 -
23.621 -
23.622 - ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map
23.623 -
23.624 - ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map
23.625 - ///\ingroup maps
23.626 - ///
23.627 - template<class M>
23.628 - class NormSquareMap
23.629 - {
23.630 - const M& _map;
23.631 - public:
23.632 -
23.633 - typedef typename M::Value::Value Value;
23.634 - typedef typename M::Key Key;
23.635 - ///\e
23.636 - NormSquareMap(const M &map) : _map(map) {}
23.637 - Value operator[](Key k) const {return _map[k].normSquare();}
23.638 - };
23.639 -
23.640 - ///Returns a \ref NormSquareMap class
23.641 -
23.642 - ///This function just returns an \ref NormSquareMap class.
23.643 - ///
23.644 - ///\ingroup maps
23.645 - ///\relates NormSquareMap
23.646 - template<class M>
23.647 - inline NormSquareMap<M> normSquareMap(const M &m)
23.648 - {
23.649 - return NormSquareMap<M>(m);
23.650 - }
23.651 -
23.652 - /// @}
23.653 -
23.654 -
23.655 -} //namespace lemon
23.656 -
23.657 -#endif //LEMON_XY_H
24.1 --- a/test/Makefile.am Wed Sep 06 11:39:22 2006 +0000
24.2 +++ b/test/Makefile.am Thu Sep 07 13:27:16 2006 +0000
24.3 @@ -18,6 +18,7 @@
24.4 test/counter_test \
24.5 test/dfs_test \
24.6 test/dijkstra_test \
24.7 + test/dim_test \
24.8 test/edge_set_test \
24.9 test/graph_adaptor_test \
24.10 test/graph_test \
24.11 @@ -39,8 +40,7 @@
24.12 test/test_tools_pass \
24.13 test/time_measure_test \
24.14 test/ugraph_test \
24.15 - test/unionfind_test \
24.16 - test/xy_test
24.17 + test/unionfind_test
24.18
24.19 if HAVE_GLPK
24.20 check_PROGRAMS += test/lp_test test/mip_test
24.21 @@ -60,6 +60,7 @@
24.22 test_counter_test_SOURCES = test/counter_test.cc
24.23 test_dfs_test_SOURCES = test/dfs_test.cc
24.24 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
24.25 +test_dim_test_SOURCES = test/dim_test.cc
24.26 test_edge_set_test_SOURCES = test/edge_set_test.cc
24.27 test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
24.28 test_graph_test_SOURCES = test/graph_test.cc
24.29 @@ -82,7 +83,6 @@
24.30 test_time_measure_test_SOURCES = test/time_measure_test.cc
24.31 test_ugraph_test_SOURCES = test/ugraph_test.cc
24.32 test_unionfind_test_SOURCES = test/unionfind_test.cc
24.33 -test_xy_test_SOURCES = test/xy_test.cc
24.34
24.35 test_lp_test_SOURCES = test/lp_test.cc
24.36 test_lp_test_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS)
25.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
25.2 +++ b/test/dim_test.cc Thu Sep 07 13:27:16 2006 +0000
25.3 @@ -0,0 +1,82 @@
25.4 +/* -*- C++ -*-
25.5 + *
25.6 + * This file is a part of LEMON, a generic C++ optimization library
25.7 + *
25.8 + * Copyright (C) 2003-2006
25.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
25.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
25.11 + *
25.12 + * Permission to use, modify and distribute this software is granted
25.13 + * provided that this copyright notice appears in all copies. For
25.14 + * precise terms see the accompanying LICENSE file.
25.15 + *
25.16 + * This software is provided "AS IS" with no warranty of any kind,
25.17 + * express or implied, and with no claim as to its suitability for any
25.18 + * purpose.
25.19 + *
25.20 + */
25.21 +
25.22 +#include <lemon/dim2.h>
25.23 +#include <iostream>
25.24 +#include "test_tools.h"
25.25 +
25.26 +using namespace std;
25.27 +using namespace lemon;
25.28 +int main()
25.29 +{
25.30 +
25.31 + cout << "Testing classes `dim2::Point' and `dim2::BoundingBox'." << endl;
25.32 +
25.33 + typedef dim2::Point<int> Point;
25.34 +
25.35 + Point seged;
25.36 + Point a(1,2);
25.37 + Point b(3,4);
25.38 +
25.39 + seged = a+b;
25.40 + check(seged.x==4 && seged.y==6, "Wrong vector addition");
25.41 +
25.42 + seged = a-b;
25.43 + check(seged.x==-2 && seged.y==-2, "a-b");
25.44 +
25.45 + check(a.normSquare()==5,"Wrong norm calculation");
25.46 + check(a*b==11, "a*b");
25.47 +
25.48 + int l=2;
25.49 + seged = a*l;
25.50 + check(seged.x==2 && seged.y==4, "a*l");
25.51 +
25.52 + seged = b/l;
25.53 + check(seged.x==1 && seged.y==2, "b/l");
25.54 +
25.55 + typedef dim2::BoundingBox<int> BB;
25.56 + BB doboz1;
25.57 + check(doboz1.empty(), "It should be empty.");
25.58 +
25.59 + doboz1.add(a);
25.60 + check(!doboz1.empty(), "It should not be empty.");
25.61 + doboz1.add(b);
25.62 +
25.63 + check(doboz1.bottomLeft().x==1 &&
25.64 + doboz1.bottomLeft().y==2 &&
25.65 + doboz1.topRight().x==3 &&
25.66 + doboz1.topRight().y==4,
25.67 + "added points to box");
25.68 +
25.69 + seged.x=2;seged.y=3;
25.70 + check(doboz1.inside(seged),"It should be inside.");
25.71 +
25.72 + seged.x=1;seged.y=3;
25.73 + check(doboz1.inside(seged),"It should be inside.");
25.74 +
25.75 + seged.x=0;seged.y=3;
25.76 + check(!doboz1.inside(seged),"It should not be inside.");
25.77 +
25.78 + BB doboz2(seged);
25.79 + check(!doboz2.empty(),
25.80 + "It should not be empty. Constructed from 1 point.");
25.81 +
25.82 + doboz2.add(doboz1);
25.83 + check(doboz2.inside(seged),
25.84 + "It should be inside. Incremented a box with another one.");
25.85 +}
26.1 --- a/test/polynomial_test.cc Wed Sep 06 11:39:22 2006 +0000
26.2 +++ b/test/polynomial_test.cc Thu Sep 07 13:27:16 2006 +0000
26.3 @@ -17,7 +17,7 @@
26.4 */
26.5
26.6 #include <lemon/polynomial.h>
26.7 -#include <lemon/xy.h>
26.8 +#include <lemon/dim2.h>
26.9 #include <iostream>
26.10 #include "test_tools.h"
26.11
27.1 --- a/test/xy_test.cc Wed Sep 06 11:39:22 2006 +0000
27.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
27.3 @@ -1,82 +0,0 @@
27.4 -/* -*- C++ -*-
27.5 - *
27.6 - * This file is a part of LEMON, a generic C++ optimization library
27.7 - *
27.8 - * Copyright (C) 2003-2006
27.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
27.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
27.11 - *
27.12 - * Permission to use, modify and distribute this software is granted
27.13 - * provided that this copyright notice appears in all copies. For
27.14 - * precise terms see the accompanying LICENSE file.
27.15 - *
27.16 - * This software is provided "AS IS" with no warranty of any kind,
27.17 - * express or implied, and with no claim as to its suitability for any
27.18 - * purpose.
27.19 - *
27.20 - */
27.21 -
27.22 -#include <lemon/xy.h>
27.23 -#include <iostream>
27.24 -#include "test_tools.h"
27.25 -
27.26 -using namespace std;
27.27 -using namespace lemon;
27.28 -int main()
27.29 -{
27.30 -
27.31 - cout << "Testing classes `xy' and `boundingbox'." << endl;
27.32 -
27.33 - typedef xy<int> XY;
27.34 -
27.35 - XY seged;
27.36 - XY a(1,2);
27.37 - XY b(3,4);
27.38 -
27.39 - seged = a+b;
27.40 - check(seged.x==4 && seged.y==6, "Wrong vector addition");
27.41 -
27.42 - seged = a-b;
27.43 - check(seged.x==-2 && seged.y==-2, "a-b");
27.44 -
27.45 - check(a.normSquare()==5,"Wrong norm calculation");
27.46 - check(a*b==11, "a*b");
27.47 -
27.48 - int l=2;
27.49 - seged = a*l;
27.50 - check(seged.x==2 && seged.y==4, "a*l");
27.51 -
27.52 - seged = b/l;
27.53 - check(seged.x==1 && seged.y==2, "b/l");
27.54 -
27.55 - typedef BoundingBox<int> BB;
27.56 - BB doboz1;
27.57 - check(doboz1.empty(), "It should be empty.");
27.58 -
27.59 - doboz1.add(a);
27.60 - check(!doboz1.empty(), "It should not be empty.");
27.61 - doboz1.add(b);
27.62 -
27.63 - check(doboz1.bottomLeft().x==1 &&
27.64 - doboz1.bottomLeft().y==2 &&
27.65 - doboz1.topRight().x==3 &&
27.66 - doboz1.topRight().y==4,
27.67 - "added points to box");
27.68 -
27.69 - seged.x=2;seged.y=3;
27.70 - check(doboz1.inside(seged),"It should be inside.");
27.71 -
27.72 - seged.x=1;seged.y=3;
27.73 - check(doboz1.inside(seged),"It should be inside.");
27.74 -
27.75 - seged.x=0;seged.y=3;
27.76 - check(!doboz1.inside(seged),"It should not be inside.");
27.77 -
27.78 - BB doboz2(seged);
27.79 - check(!doboz2.empty(),
27.80 - "It should not be empty. Constructed from 1 point.");
27.81 -
27.82 - doboz2.add(doboz1);
27.83 - check(doboz2.inside(seged),
27.84 - "It should be inside. Incremented a box with another one.");
27.85 -}