0
6
0
1 | 1 |
/* -*- C++ -*- |
2 | 2 |
* |
3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library |
4 | 4 |
* |
5 | 5 |
* Copyright (C) 2003-2008 |
6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 | 8 |
* |
9 | 9 |
* Permission to use, modify and distribute this software is granted |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef LEMON_BEZIER_H |
20 | 20 |
#define LEMON_BEZIER_H |
21 | 21 |
|
22 | 22 |
///\ingroup misc |
23 | 23 |
///\file |
24 | 24 |
///\brief Classes to compute with Bezier curves. |
25 | 25 |
/// |
26 | 26 |
///Up to now this file is used internally by \ref graph_to_eps.h |
27 | 27 |
|
28 | 28 |
#include<lemon/dim2.h> |
29 | 29 |
|
30 | 30 |
namespace lemon { |
31 | 31 |
namespace dim2 { |
32 | 32 |
|
33 | 33 |
class BezierBase { |
34 | 34 |
public: |
35 |
typedef Point<double> Point; |
|
35 |
typedef lemon::dim2::Point<double> Point; |
|
36 | 36 |
protected: |
37 | 37 |
static Point conv(Point x,Point y,double t) {return (1-t)*x+t*y;} |
38 | 38 |
}; |
39 | 39 |
|
40 | 40 |
class Bezier1 : public BezierBase |
41 | 41 |
{ |
42 | 42 |
public: |
43 | 43 |
Point p1,p2; |
44 | 44 |
|
45 | 45 |
Bezier1() {} |
46 | 46 |
Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {} |
47 | 47 |
|
48 | 48 |
Point operator()(double t) const |
49 | 49 |
{ |
50 | 50 |
// return conv(conv(p1,p2,t),conv(p2,p3,t),t); |
51 | 51 |
return conv(p1,p2,t); |
52 | 52 |
} |
53 | 53 |
Bezier1 before(double t) const |
54 | 54 |
{ |
55 | 55 |
return Bezier1(p1,conv(p1,p2,t)); |
56 | 56 |
} |
57 | 57 |
|
58 | 58 |
Bezier1 after(double t) const |
59 | 59 |
{ |
60 | 60 |
return Bezier1(conv(p1,p2,t),p2); |
61 | 61 |
} |
62 | 62 |
|
63 | 63 |
Bezier1 revert() const { return Bezier1(p2,p1);} |
64 | 64 |
Bezier1 operator()(double a,double b) const { return before(b).after(a/b); } |
65 | 65 |
Point grad() const { return p2-p1; } |
66 | 66 |
Point norm() const { return rot90(p2-p1); } |
67 | 67 |
Point grad(double) const { return grad(); } |
68 | 68 |
Point norm(double t) const { return rot90(grad(t)); } |
69 | 69 |
}; |
70 | 70 |
|
71 | 71 |
class Bezier2 : public BezierBase |
72 | 72 |
{ |
73 | 73 |
public: |
74 | 74 |
Point p1,p2,p3; |
75 | 75 |
|
76 | 76 |
Bezier2() {} |
77 | 77 |
Bezier2(Point _p1, Point _p2, Point _p3) :p1(_p1), p2(_p2), p3(_p3) {} |
78 | 78 |
Bezier2(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,.5)), p3(b.p2) {} |
79 | 79 |
Point operator()(double t) const |
80 | 80 |
{ |
81 | 81 |
// return conv(conv(p1,p2,t),conv(p2,p3,t),t); |
82 | 82 |
return ((1-t)*(1-t))*p1+(2*(1-t)*t)*p2+(t*t)*p3; |
83 | 83 |
} |
84 | 84 |
Bezier2 before(double t) const |
85 | 85 |
{ |
86 | 86 |
Point q(conv(p1,p2,t)); |
87 | 87 |
Point r(conv(p2,p3,t)); |
88 | 88 |
return Bezier2(p1,q,conv(q,r,t)); |
89 | 89 |
} |
90 | 90 |
|
91 | 91 |
Bezier2 after(double t) const |
92 | 92 |
{ |
93 | 93 |
Point q(conv(p1,p2,t)); |
94 | 94 |
Point r(conv(p2,p3,t)); |
95 | 95 |
return Bezier2(conv(q,r,t),r,p3); |
96 | 96 |
} |
97 | 97 |
Bezier2 revert() const { return Bezier2(p3,p2,p1);} |
98 | 98 |
Bezier2 operator()(double a,double b) const { return before(b).after(a/b); } |
99 | 99 |
Bezier1 grad() const { return Bezier1(2.0*(p2-p1),2.0*(p3-p2)); } |
... | ... |
@@ -89,158 +89,158 @@ |
89 | 89 |
|
90 | 90 |
typedef typename Graph::Arc Item; |
91 | 91 |
typedef typename Graph::ArcIt ItemIt; |
92 | 92 |
|
93 | 93 |
typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier; |
94 | 94 |
|
95 | 95 |
template <typename _Value> |
96 | 96 |
class Map : public Graph::template ArcMap<_Value> { |
97 | 97 |
public: |
98 | 98 |
typedef typename Graph::template ArcMap<_Value> Parent; |
99 | 99 |
typedef typename Graph::template ArcMap<_Value> Type; |
100 | 100 |
typedef typename Parent::Value Value; |
101 | 101 |
|
102 | 102 |
Map(const Graph& _digraph) : Parent(_digraph) {} |
103 | 103 |
Map(const Graph& _digraph, const Value& _value) |
104 | 104 |
: Parent(_digraph, _value) {} |
105 | 105 |
}; |
106 | 106 |
|
107 | 107 |
}; |
108 | 108 |
|
109 | 109 |
template <typename Graph, typename Enable = void> |
110 | 110 |
struct EdgeNotifierIndicator { |
111 | 111 |
typedef InvalidType Type; |
112 | 112 |
}; |
113 | 113 |
template <typename Graph> |
114 | 114 |
struct EdgeNotifierIndicator< |
115 | 115 |
Graph, |
116 | 116 |
typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type |
117 | 117 |
> { |
118 | 118 |
typedef typename Graph::EdgeNotifier Type; |
119 | 119 |
}; |
120 | 120 |
|
121 | 121 |
template <typename _Graph> |
122 | 122 |
class ItemSetTraits<_Graph, typename _Graph::Edge> { |
123 | 123 |
public: |
124 | 124 |
|
125 | 125 |
typedef _Graph Graph; |
126 | 126 |
|
127 | 127 |
typedef typename Graph::Edge Item; |
128 | 128 |
typedef typename Graph::EdgeIt ItemIt; |
129 | 129 |
|
130 | 130 |
typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier; |
131 | 131 |
|
132 | 132 |
template <typename _Value> |
133 | 133 |
class Map : public Graph::template EdgeMap<_Value> { |
134 | 134 |
public: |
135 | 135 |
typedef typename Graph::template EdgeMap<_Value> Parent; |
136 | 136 |
typedef typename Graph::template EdgeMap<_Value> Type; |
137 | 137 |
typedef typename Parent::Value Value; |
138 | 138 |
|
139 | 139 |
Map(const Graph& _digraph) : Parent(_digraph) {} |
140 | 140 |
Map(const Graph& _digraph, const Value& _value) |
141 | 141 |
: Parent(_digraph, _value) {} |
142 | 142 |
}; |
143 | 143 |
|
144 | 144 |
}; |
145 | 145 |
|
146 | 146 |
template <typename Map, typename Enable = void> |
147 | 147 |
struct MapTraits { |
148 | 148 |
typedef False ReferenceMapTag; |
149 | 149 |
|
150 | 150 |
typedef typename Map::Key Key; |
151 | 151 |
typedef typename Map::Value Value; |
152 | 152 |
|
153 |
typedef const Value ConstReturnValue; |
|
154 |
typedef const Value ReturnValue; |
|
153 |
typedef Value ConstReturnValue; |
|
154 |
typedef Value ReturnValue; |
|
155 | 155 |
}; |
156 | 156 |
|
157 | 157 |
template <typename Map> |
158 | 158 |
struct MapTraits< |
159 | 159 |
Map, typename enable_if<typename Map::ReferenceMapTag, void>::type > |
160 | 160 |
{ |
161 | 161 |
typedef True ReferenceMapTag; |
162 | 162 |
|
163 | 163 |
typedef typename Map::Key Key; |
164 | 164 |
typedef typename Map::Value Value; |
165 | 165 |
|
166 | 166 |
typedef typename Map::ConstReference ConstReturnValue; |
167 | 167 |
typedef typename Map::Reference ReturnValue; |
168 | 168 |
|
169 | 169 |
typedef typename Map::ConstReference ConstReference; |
170 | 170 |
typedef typename Map::Reference Reference; |
171 | 171 |
}; |
172 | 172 |
|
173 | 173 |
template <typename MatrixMap, typename Enable = void> |
174 | 174 |
struct MatrixMapTraits { |
175 | 175 |
typedef False ReferenceMapTag; |
176 | 176 |
|
177 | 177 |
typedef typename MatrixMap::FirstKey FirstKey; |
178 | 178 |
typedef typename MatrixMap::SecondKey SecondKey; |
179 | 179 |
typedef typename MatrixMap::Value Value; |
180 | 180 |
|
181 |
typedef const Value ConstReturnValue; |
|
182 |
typedef const Value ReturnValue; |
|
181 |
typedef Value ConstReturnValue; |
|
182 |
typedef Value ReturnValue; |
|
183 | 183 |
}; |
184 | 184 |
|
185 | 185 |
template <typename MatrixMap> |
186 | 186 |
struct MatrixMapTraits< |
187 | 187 |
MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag, |
188 | 188 |
void>::type > |
189 | 189 |
{ |
190 | 190 |
typedef True ReferenceMapTag; |
191 | 191 |
|
192 | 192 |
typedef typename MatrixMap::FirstKey FirstKey; |
193 | 193 |
typedef typename MatrixMap::SecondKey SecondKey; |
194 | 194 |
typedef typename MatrixMap::Value Value; |
195 | 195 |
|
196 | 196 |
typedef typename MatrixMap::ConstReference ConstReturnValue; |
197 | 197 |
typedef typename MatrixMap::Reference ReturnValue; |
198 | 198 |
|
199 | 199 |
typedef typename MatrixMap::ConstReference ConstReference; |
200 | 200 |
typedef typename MatrixMap::Reference Reference; |
201 | 201 |
}; |
202 | 202 |
|
203 | 203 |
// Indicators for the tags |
204 | 204 |
|
205 | 205 |
template <typename Graph, typename Enable = void> |
206 | 206 |
struct NodeNumTagIndicator { |
207 | 207 |
static const bool value = false; |
208 | 208 |
}; |
209 | 209 |
|
210 | 210 |
template <typename Graph> |
211 | 211 |
struct NodeNumTagIndicator< |
212 | 212 |
Graph, |
213 | 213 |
typename enable_if<typename Graph::NodeNumTag, void>::type |
214 | 214 |
> { |
215 | 215 |
static const bool value = true; |
216 | 216 |
}; |
217 | 217 |
|
218 | 218 |
template <typename Graph, typename Enable = void> |
219 | 219 |
struct EdgeNumTagIndicator { |
220 | 220 |
static const bool value = false; |
221 | 221 |
}; |
222 | 222 |
|
223 | 223 |
template <typename Graph> |
224 | 224 |
struct EdgeNumTagIndicator< |
225 | 225 |
Graph, |
226 | 226 |
typename enable_if<typename Graph::EdgeNumTag, void>::type |
227 | 227 |
> { |
228 | 228 |
static const bool value = true; |
229 | 229 |
}; |
230 | 230 |
|
231 | 231 |
template <typename Graph, typename Enable = void> |
232 | 232 |
struct FindEdgeTagIndicator { |
233 | 233 |
static const bool value = false; |
234 | 234 |
}; |
235 | 235 |
|
236 | 236 |
template <typename Graph> |
237 | 237 |
struct FindEdgeTagIndicator< |
238 | 238 |
Graph, |
239 | 239 |
typename enable_if<typename Graph::FindEdgeTag, void>::type |
240 | 240 |
> { |
241 | 241 |
static const bool value = true; |
242 | 242 |
}; |
243 | 243 |
|
244 | 244 |
template <typename Graph, typename Enable = void> |
245 | 245 |
struct UndirectedTagIndicator { |
246 | 246 |
static const bool value = false; |
1 | 1 |
/* -*- C++ -*- |
2 | 2 |
* |
3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library |
4 | 4 |
* |
5 | 5 |
* Copyright (C) 2003-2008 |
6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 | 8 |
* |
9 | 9 |
* Permission to use, modify and distribute this software is granted |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef LEMON_DIJKSTRA_H |
20 | 20 |
#define LEMON_DIJKSTRA_H |
21 | 21 |
|
22 | 22 |
///\ingroup shortest_path |
23 | 23 |
///\file |
24 | 24 |
///\brief Dijkstra algorithm. |
25 | 25 |
|
26 |
#include <limits> |
|
26 | 27 |
#include <lemon/list_graph.h> |
27 | 28 |
#include <lemon/bin_heap.h> |
28 | 29 |
#include <lemon/bits/path_dump.h> |
29 | 30 |
#include <lemon/bits/invalid.h> |
30 | 31 |
#include <lemon/error.h> |
31 | 32 |
#include <lemon/maps.h> |
32 | 33 |
|
33 | 34 |
namespace lemon { |
34 | 35 |
|
35 | 36 |
/// \brief Default OperationTraits for the Dijkstra algorithm class. |
36 | 37 |
/// |
37 | 38 |
/// It defines all computational operations and constants which are |
38 | 39 |
/// used in the Dijkstra algorithm. |
39 | 40 |
template <typename Value> |
40 | 41 |
struct DijkstraDefaultOperationTraits { |
41 | 42 |
/// \brief Gives back the zero value of the type. |
42 | 43 |
static Value zero() { |
43 | 44 |
return static_cast<Value>(0); |
44 | 45 |
} |
45 | 46 |
/// \brief Gives back the sum of the given two elements. |
46 | 47 |
static Value plus(const Value& left, const Value& right) { |
47 | 48 |
return left + right; |
48 | 49 |
} |
49 | 50 |
/// \brief Gives back true only if the first value less than the second. |
50 | 51 |
static bool less(const Value& left, const Value& right) { |
51 | 52 |
return left < right; |
52 | 53 |
} |
53 | 54 |
}; |
54 | 55 |
|
55 | 56 |
/// \brief Widest path OperationTraits for the Dijkstra algorithm class. |
56 | 57 |
/// |
57 | 58 |
/// It defines all computational operations and constants which are |
58 | 59 |
/// used in the Dijkstra algorithm for widest path computation. |
59 | 60 |
template <typename Value> |
60 | 61 |
struct DijkstraWidestPathOperationTraits { |
61 | 62 |
/// \brief Gives back the maximum value of the type. |
62 | 63 |
static Value zero() { |
63 | 64 |
return std::numeric_limits<Value>::max(); |
64 | 65 |
} |
65 | 66 |
/// \brief Gives back the minimum of the given two elements. |
66 | 67 |
static Value plus(const Value& left, const Value& right) { |
67 | 68 |
return std::min(left, right); |
68 | 69 |
} |
69 | 70 |
/// \brief Gives back true only if the first value less than the second. |
70 | 71 |
static bool less(const Value& left, const Value& right) { |
71 | 72 |
return left < right; |
72 | 73 |
} |
73 | 74 |
}; |
74 | 75 |
|
75 | 76 |
///Default traits class of Dijkstra class. |
76 | 77 |
|
77 | 78 |
///Default traits class of Dijkstra class. |
78 | 79 |
///\tparam GR Digraph type. |
79 | 80 |
///\tparam LM Type of length map. |
80 | 81 |
template<class GR, class LM> |
81 | 82 |
struct DijkstraDefaultTraits |
82 | 83 |
{ |
83 | 84 |
///The digraph type the algorithm runs on. |
84 | 85 |
typedef GR Digraph; |
85 | 86 |
///The type of the map that stores the arc lengths. |
86 | 87 |
|
87 | 88 |
///The type of the map that stores the arc lengths. |
88 | 89 |
///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
89 | 90 |
typedef LM LengthMap; |
... | ... |
@@ -954,157 +954,158 @@ |
954 | 954 |
d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0; |
955 | 955 |
|
956 | 956 |
for(typename std::vector<Arc>::iterator e=i;e!=j;++e) { |
957 | 957 |
sw+=_arcWidths[*e]*_arcWidthScale/2.0; |
958 | 958 |
dim2::Point<double> mm=m+rot90(d)*sw/.75; |
959 | 959 |
if(_drawArrows) { |
960 | 960 |
int node_shape; |
961 | 961 |
dim2::Point<double> s=mycoords[g.source(*e)]; |
962 | 962 |
dim2::Point<double> t=mycoords[g.target(*e)]; |
963 | 963 |
double rn=_nodeSizes[g.target(*e)]*_nodeScale; |
964 | 964 |
node_shape=_nodeShapes[g.target(*e)]; |
965 | 965 |
dim2::Bezier3 bez(s,mm,mm,t); |
966 | 966 |
double t1=0,t2=1; |
967 | 967 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
968 | 968 |
if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2; |
969 | 969 |
else t1=(t1+t2)/2; |
970 | 970 |
dim2::Point<double> apoint=bez((t1+t2)/2); |
971 | 971 |
rn = _arrowLength+_arcWidths[*e]*_arcWidthScale; |
972 | 972 |
rn*=rn; |
973 | 973 |
t2=(t1+t2)/2;t1=0; |
974 | 974 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
975 | 975 |
if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2; |
976 | 976 |
else t2=(t1+t2)/2; |
977 | 977 |
dim2::Point<double> linend=bez((t1+t2)/2); |
978 | 978 |
bez=bez.before((t1+t2)/2); |
979 | 979 |
// rn=_nodeSizes[g.source(*e)]*_nodeScale; |
980 | 980 |
// node_shape=_nodeShapes[g.source(*e)]; |
981 | 981 |
// t1=0;t2=1; |
982 | 982 |
// for(int i=0;i<INTERPOL_PREC;++i) |
983 | 983 |
// if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t1=(t1+t2)/2; |
984 | 984 |
// else t2=(t1+t2)/2; |
985 | 985 |
// bez=bez.after((t1+t2)/2); |
986 | 986 |
os << _arcWidths[*e]*_arcWidthScale << " setlinewidth " |
987 | 987 |
<< _arcColors[*e].red() << ' ' |
988 | 988 |
<< _arcColors[*e].green() << ' ' |
989 | 989 |
<< _arcColors[*e].blue() << " setrgbcolor newpath\n" |
990 | 990 |
<< bez.p1.x << ' ' << bez.p1.y << " moveto\n" |
991 | 991 |
<< bez.p2.x << ' ' << bez.p2.y << ' ' |
992 | 992 |
<< bez.p3.x << ' ' << bez.p3.y << ' ' |
993 | 993 |
<< bez.p4.x << ' ' << bez.p4.y << " curveto stroke\n"; |
994 | 994 |
dim2::Point<double> dd(rot90(linend-apoint)); |
995 | 995 |
dd*=(.5*_arcWidths[*e]*_arcWidthScale+_arrowWidth)/ |
996 | 996 |
std::sqrt(dd.normSquare()); |
997 | 997 |
os << "newpath " << psOut(apoint) << " moveto " |
998 | 998 |
<< psOut(linend+dd) << " lineto " |
999 | 999 |
<< psOut(linend-dd) << " lineto closepath fill\n"; |
1000 | 1000 |
} |
1001 | 1001 |
else { |
1002 | 1002 |
os << mycoords[g.source(*e)].x << ' ' |
1003 | 1003 |
<< mycoords[g.source(*e)].y << ' ' |
1004 | 1004 |
<< mm.x << ' ' << mm.y << ' ' |
1005 | 1005 |
<< mycoords[g.target(*e)].x << ' ' |
1006 | 1006 |
<< mycoords[g.target(*e)].y << ' ' |
1007 | 1007 |
<< _arcColors[*e].red() << ' ' |
1008 | 1008 |
<< _arcColors[*e].green() << ' ' |
1009 | 1009 |
<< _arcColors[*e].blue() << ' ' |
1010 | 1010 |
<< _arcWidths[*e]*_arcWidthScale << " lb\n"; |
1011 | 1011 |
} |
1012 | 1012 |
sw+=_arcWidths[*e]*_arcWidthScale/2.0+_parArcDist; |
1013 | 1013 |
} |
1014 | 1014 |
} |
1015 | 1015 |
} |
1016 | 1016 |
else for(ArcIt e(g);e!=INVALID;++e) |
1017 | 1017 |
if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0 |
1018 |
&&g.source(e)!=g.target(e)) |
|
1018 |
&&g.source(e)!=g.target(e)) { |
|
1019 | 1019 |
if(_drawArrows) { |
1020 | 1020 |
dim2::Point<double> d(mycoords[g.target(e)]-mycoords[g.source(e)]); |
1021 | 1021 |
double rn=_nodeSizes[g.target(e)]*_nodeScale; |
1022 | 1022 |
int node_shape=_nodeShapes[g.target(e)]; |
1023 | 1023 |
double t1=0,t2=1; |
1024 | 1024 |
for(int i=0;i<INTERPOL_PREC;++i) |
1025 | 1025 |
if(isInsideNode((-(t1+t2)/2)*d,rn,node_shape)) t1=(t1+t2)/2; |
1026 | 1026 |
else t2=(t1+t2)/2; |
1027 | 1027 |
double l=std::sqrt(d.normSquare()); |
1028 | 1028 |
d/=l; |
1029 | 1029 |
|
1030 | 1030 |
os << l*(1-(t1+t2)/2) << ' ' |
1031 | 1031 |
<< _arcWidths[e]*_arcWidthScale << ' ' |
1032 | 1032 |
<< d.x << ' ' << d.y << ' ' |
1033 | 1033 |
<< mycoords[g.source(e)].x << ' ' |
1034 | 1034 |
<< mycoords[g.source(e)].y << ' ' |
1035 | 1035 |
<< _arcColors[e].red() << ' ' |
1036 | 1036 |
<< _arcColors[e].green() << ' ' |
1037 | 1037 |
<< _arcColors[e].blue() << " arr\n"; |
1038 |
} |
|
1038 |
} |
|
1039 | 1039 |
else os << mycoords[g.source(e)].x << ' ' |
1040 | 1040 |
<< mycoords[g.source(e)].y << ' ' |
1041 | 1041 |
<< mycoords[g.target(e)].x << ' ' |
1042 | 1042 |
<< mycoords[g.target(e)].y << ' ' |
1043 | 1043 |
<< _arcColors[e].red() << ' ' |
1044 | 1044 |
<< _arcColors[e].green() << ' ' |
1045 | 1045 |
<< _arcColors[e].blue() << ' ' |
1046 | 1046 |
<< _arcWidths[e]*_arcWidthScale << " l\n"; |
1047 |
} |
|
1047 | 1048 |
os << "grestore\n"; |
1048 | 1049 |
} |
1049 | 1050 |
if(_showNodes) { |
1050 | 1051 |
os << "%Nodes:\ngsave\n"; |
1051 | 1052 |
for(NodeIt n(g);n!=INVALID;++n) { |
1052 | 1053 |
os << mycoords[n].x << ' ' << mycoords[n].y << ' ' |
1053 | 1054 |
<< _nodeSizes[n]*_nodeScale << ' ' |
1054 | 1055 |
<< _nodeColors[n].red() << ' ' |
1055 | 1056 |
<< _nodeColors[n].green() << ' ' |
1056 | 1057 |
<< _nodeColors[n].blue() << ' '; |
1057 | 1058 |
switch(_nodeShapes[n]) { |
1058 | 1059 |
case CIRCLE: |
1059 | 1060 |
os<< "nc";break; |
1060 | 1061 |
case SQUARE: |
1061 | 1062 |
os<< "nsq";break; |
1062 | 1063 |
case DIAMOND: |
1063 | 1064 |
os<< "ndi";break; |
1064 | 1065 |
case MALE: |
1065 | 1066 |
os<< "nmale";break; |
1066 | 1067 |
case FEMALE: |
1067 | 1068 |
os<< "nfemale";break; |
1068 | 1069 |
} |
1069 | 1070 |
os<<'\n'; |
1070 | 1071 |
} |
1071 | 1072 |
os << "grestore\n"; |
1072 | 1073 |
} |
1073 | 1074 |
if(_showNodeText) { |
1074 | 1075 |
os << "%Node texts:\ngsave\n"; |
1075 | 1076 |
os << "/fosi " << _nodeTextSize << " def\n"; |
1076 | 1077 |
os << "(Helvetica) findfont fosi scalefont setfont\n"; |
1077 | 1078 |
for(NodeIt n(g);n!=INVALID;++n) { |
1078 | 1079 |
switch(_nodeTextColorType) { |
1079 | 1080 |
case DIST_COL: |
1080 | 1081 |
os << psOut(distantColor(_nodeColors[n])) << " setrgbcolor\n"; |
1081 | 1082 |
break; |
1082 | 1083 |
case DIST_BW: |
1083 | 1084 |
os << psOut(distantBW(_nodeColors[n])) << " setrgbcolor\n"; |
1084 | 1085 |
break; |
1085 | 1086 |
case CUST_COL: |
1086 | 1087 |
os << psOut(distantColor(_nodeTextColors[n])) << " setrgbcolor\n"; |
1087 | 1088 |
break; |
1088 | 1089 |
default: |
1089 | 1090 |
os << "0 0 0 setrgbcolor\n"; |
1090 | 1091 |
} |
1091 | 1092 |
os << mycoords[n].x << ' ' << mycoords[n].y |
1092 | 1093 |
<< " (" << _nodeTexts[n] << ") cshow\n"; |
1093 | 1094 |
} |
1094 | 1095 |
os << "grestore\n"; |
1095 | 1096 |
} |
1096 | 1097 |
if(_showNodePsText) { |
1097 | 1098 |
os << "%Node PS blocks:\ngsave\n"; |
1098 | 1099 |
for(NodeIt n(g);n!=INVALID;++n) |
1099 | 1100 |
os << mycoords[n].x << ' ' << mycoords[n].y |
1100 | 1101 |
<< " moveto\n" << _nodePsTexts[n] << "\n"; |
1101 | 1102 |
os << "grestore\n"; |
1102 | 1103 |
} |
1103 | 1104 |
|
1104 | 1105 |
os << "grestore\nshowpage\n"; |
1105 | 1106 |
|
1106 | 1107 |
//CleanUp: |
1107 | 1108 |
if(_pleaseRemoveOsStream) {delete &os;} |
1108 | 1109 |
} |
1109 | 1110 |
|
1110 | 1111 |
///\name Aliases |
... | ... |
@@ -54,140 +54,140 @@ |
54 | 54 |
|
55 | 55 |
int first_free_arc; |
56 | 56 |
|
57 | 57 |
public: |
58 | 58 |
|
59 | 59 |
typedef ListDigraphBase Digraph; |
60 | 60 |
|
61 | 61 |
class Node { |
62 | 62 |
friend class ListDigraphBase; |
63 | 63 |
protected: |
64 | 64 |
|
65 | 65 |
int id; |
66 | 66 |
explicit Node(int pid) { id = pid;} |
67 | 67 |
|
68 | 68 |
public: |
69 | 69 |
Node() {} |
70 | 70 |
Node (Invalid) { id = -1; } |
71 | 71 |
bool operator==(const Node& node) const {return id == node.id;} |
72 | 72 |
bool operator!=(const Node& node) const {return id != node.id;} |
73 | 73 |
bool operator<(const Node& node) const {return id < node.id;} |
74 | 74 |
}; |
75 | 75 |
|
76 | 76 |
class Arc { |
77 | 77 |
friend class ListDigraphBase; |
78 | 78 |
protected: |
79 | 79 |
|
80 | 80 |
int id; |
81 | 81 |
explicit Arc(int pid) { id = pid;} |
82 | 82 |
|
83 | 83 |
public: |
84 | 84 |
Arc() {} |
85 | 85 |
Arc (Invalid) { id = -1; } |
86 | 86 |
bool operator==(const Arc& arc) const {return id == arc.id;} |
87 | 87 |
bool operator!=(const Arc& arc) const {return id != arc.id;} |
88 | 88 |
bool operator<(const Arc& arc) const {return id < arc.id;} |
89 | 89 |
}; |
90 | 90 |
|
91 | 91 |
|
92 | 92 |
|
93 | 93 |
ListDigraphBase() |
94 | 94 |
: nodes(), first_node(-1), |
95 | 95 |
first_free_node(-1), arcs(), first_free_arc(-1) {} |
96 | 96 |
|
97 | 97 |
|
98 | 98 |
int maxNodeId() const { return nodes.size()-1; } |
99 | 99 |
int maxArcId() const { return arcs.size()-1; } |
100 | 100 |
|
101 | 101 |
Node source(Arc e) const { return Node(arcs[e.id].source); } |
102 | 102 |
Node target(Arc e) const { return Node(arcs[e.id].target); } |
103 | 103 |
|
104 | 104 |
|
105 | 105 |
void first(Node& node) const { |
106 | 106 |
node.id = first_node; |
107 | 107 |
} |
108 | 108 |
|
109 | 109 |
void next(Node& node) const { |
110 | 110 |
node.id = nodes[node.id].next; |
111 | 111 |
} |
112 | 112 |
|
113 | 113 |
|
114 | 114 |
void first(Arc& arc) const { |
115 | 115 |
int n; |
116 | 116 |
for(n = first_node; |
117 | 117 |
n!=-1 && nodes[n].first_in == -1; |
118 |
n = nodes[n].next) |
|
118 |
n = nodes[n].next) {} |
|
119 | 119 |
arc.id = (n == -1) ? -1 : nodes[n].first_in; |
120 | 120 |
} |
121 | 121 |
|
122 | 122 |
void next(Arc& arc) const { |
123 | 123 |
if (arcs[arc.id].next_in != -1) { |
124 | 124 |
arc.id = arcs[arc.id].next_in; |
125 | 125 |
} else { |
126 | 126 |
int n; |
127 | 127 |
for(n = nodes[arcs[arc.id].target].next; |
128 |
n!=-1 && nodes[n].first_in == -1; |
|
129 |
n = nodes[n].next); |
|
128 |
n!=-1 && nodes[n].first_in == -1; |
|
129 |
n = nodes[n].next) {} |
|
130 | 130 |
arc.id = (n == -1) ? -1 : nodes[n].first_in; |
131 | 131 |
} |
132 | 132 |
} |
133 | 133 |
|
134 | 134 |
void firstOut(Arc &e, const Node& v) const { |
135 | 135 |
e.id = nodes[v.id].first_out; |
136 | 136 |
} |
137 | 137 |
void nextOut(Arc &e) const { |
138 | 138 |
e.id=arcs[e.id].next_out; |
139 | 139 |
} |
140 | 140 |
|
141 | 141 |
void firstIn(Arc &e, const Node& v) const { |
142 | 142 |
e.id = nodes[v.id].first_in; |
143 | 143 |
} |
144 | 144 |
void nextIn(Arc &e) const { |
145 | 145 |
e.id=arcs[e.id].next_in; |
146 | 146 |
} |
147 | 147 |
|
148 | 148 |
|
149 | 149 |
static int id(Node v) { return v.id; } |
150 | 150 |
static int id(Arc e) { return e.id; } |
151 | 151 |
|
152 | 152 |
static Node nodeFromId(int id) { return Node(id);} |
153 | 153 |
static Arc arcFromId(int id) { return Arc(id);} |
154 | 154 |
|
155 | 155 |
bool valid(Node n) const { |
156 | 156 |
return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && |
157 | 157 |
nodes[n.id].prev != -2; |
158 | 158 |
} |
159 | 159 |
|
160 | 160 |
bool valid(Arc a) const { |
161 | 161 |
return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && |
162 | 162 |
arcs[a.id].prev_in != -2; |
163 | 163 |
} |
164 | 164 |
|
165 | 165 |
Node addNode() { |
166 | 166 |
int n; |
167 | 167 |
|
168 | 168 |
if(first_free_node==-1) { |
169 | 169 |
n = nodes.size(); |
170 | 170 |
nodes.push_back(NodeT()); |
171 | 171 |
} else { |
172 | 172 |
n = first_free_node; |
173 | 173 |
first_free_node = nodes[n].next; |
174 | 174 |
} |
175 | 175 |
|
176 | 176 |
nodes[n].next = first_node; |
177 | 177 |
if(first_node != -1) nodes[first_node].prev = n; |
178 | 178 |
first_node = n; |
179 | 179 |
nodes[n].prev = -1; |
180 | 180 |
|
181 | 181 |
nodes[n].first_in = nodes[n].first_out = -1; |
182 | 182 |
|
183 | 183 |
return Node(n); |
184 | 184 |
} |
185 | 185 |
|
186 | 186 |
Arc addArc(Node u, Node v) { |
187 | 187 |
int n; |
188 | 188 |
|
189 | 189 |
if (first_free_arc == -1) { |
190 | 190 |
n = arcs.size(); |
191 | 191 |
arcs.push_back(ArcT()); |
192 | 192 |
} else { |
193 | 193 |
n = first_free_arc; |
1 | 1 |
/* -*- C++ -*- |
2 | 2 |
* |
3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library |
4 | 4 |
* |
5 | 5 |
* Copyright (C) 2003-2008 |
6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 | 8 |
* |
9 | 9 |
* Permission to use, modify and distribute this software is granted |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef LEMON_TEST_TEST_TOOLS_H |
20 | 20 |
#define LEMON_TEST_TEST_TOOLS_H |
21 | 21 |
|
22 | 22 |
///\ingroup misc |
23 | 23 |
///\file |
24 | 24 |
///\brief Some utilities to write test programs. |
25 | 25 |
|
26 | 26 |
#include <iostream> |
27 |
#include <stdlib.h> |
|
27 | 28 |
|
28 | 29 |
///If \c rc is fail, writes an error message and exits. |
29 | 30 |
|
30 | 31 |
///If \c rc is fail, writes an error message and exits. |
31 | 32 |
///The error message contains the file name and the line number of the |
32 | 33 |
///source code in a standard from, which makes it possible to go there |
33 | 34 |
///using good source browsers like e.g. \c emacs. |
34 | 35 |
/// |
35 | 36 |
///For example |
36 | 37 |
///\code check(0==1,"This is obviously false.");\endcode will |
37 | 38 |
///print something like this (and then exits). |
38 | 39 |
///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim |
39 |
/// |
|
40 |
///\todo It should be in \c assert.h |
|
41 | 40 |
#define check(rc, msg) \ |
42 | 41 |
if(!(rc)) { \ |
43 | 42 |
std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \ |
44 | 43 |
abort(); \ |
45 | 44 |
} else { } \ |
46 | 45 |
|
47 | 46 |
#endif |
0 comments (0 inline)