0
11
0
5
5
26
36
36
36
22
22
... | ... |
@@ -81,49 +81,49 @@ |
81 | 81 |
# configuration options related to the input files |
82 | 82 |
#--------------------------------------------------------------------------- |
83 | 83 |
INPUT = @abs_top_srcdir@/doc \ |
84 | 84 |
@abs_top_srcdir@/lemon \ |
85 | 85 |
@abs_top_srcdir@/lemon/bits \ |
86 | 86 |
@abs_top_srcdir@/lemon/concepts \ |
87 | 87 |
@abs_top_srcdir@/demo \ |
88 | 88 |
@abs_top_srcdir@/tools \ |
89 | 89 |
@abs_top_srcdir@/test/test_tools.h |
90 | 90 |
INPUT_ENCODING = UTF-8 |
91 | 91 |
FILE_PATTERNS = *.h \ |
92 | 92 |
*.cc \ |
93 | 93 |
*.dox |
94 | 94 |
RECURSIVE = NO |
95 | 95 |
EXCLUDE = |
96 | 96 |
EXCLUDE_SYMLINKS = NO |
97 | 97 |
EXCLUDE_PATTERNS = |
98 | 98 |
EXCLUDE_SYMBOLS = |
99 | 99 |
EXAMPLE_PATH = @abs_top_srcdir@/demo \ |
100 | 100 |
@abs_top_srcdir@/LICENSE \ |
101 | 101 |
@abs_top_srcdir@/doc |
102 | 102 |
EXAMPLE_PATTERNS = |
103 | 103 |
EXAMPLE_RECURSIVE = NO |
104 | 104 |
IMAGE_PATH = @abs_top_srcdir@/doc/images \ |
105 |
|
|
105 |
@abs_top_builddir@/doc/gen-images |
|
106 | 106 |
INPUT_FILTER = |
107 | 107 |
FILTER_PATTERNS = |
108 | 108 |
FILTER_SOURCE_FILES = NO |
109 | 109 |
#--------------------------------------------------------------------------- |
110 | 110 |
# configuration options related to source browsing |
111 | 111 |
#--------------------------------------------------------------------------- |
112 | 112 |
SOURCE_BROWSER = NO |
113 | 113 |
INLINE_SOURCES = NO |
114 | 114 |
STRIP_CODE_COMMENTS = YES |
115 | 115 |
REFERENCED_BY_RELATION = NO |
116 | 116 |
REFERENCES_RELATION = NO |
117 | 117 |
REFERENCES_LINK_SOURCE = YES |
118 | 118 |
USE_HTAGS = NO |
119 | 119 |
VERBATIM_HEADERS = NO |
120 | 120 |
#--------------------------------------------------------------------------- |
121 | 121 |
# configuration options related to the alphabetical class index |
122 | 122 |
#--------------------------------------------------------------------------- |
123 | 123 |
ALPHABETICAL_INDEX = YES |
124 | 124 |
COLS_IN_ALPHA_INDEX = 2 |
125 | 125 |
IGNORE_PREFIX = |
126 | 126 |
#--------------------------------------------------------------------------- |
127 | 127 |
# configuration options related to the HTML output |
128 | 128 |
#--------------------------------------------------------------------------- |
129 | 129 |
GENERATE_HTML = YES |
... | ... |
@@ -36,64 +36,64 @@ |
36 | 36 |
\@arcs and \c \@edges |
37 | 37 |
and \@attributes. Each header line may also have an optional |
38 | 38 |
\e name, which can be use to distinguish the sections of the same |
39 | 39 |
type. |
40 | 40 |
|
41 | 41 |
The standard sections are column oriented, each line consists of |
42 | 42 |
<em>token</em>s separated by whitespaces. A token can be \e plain or |
43 | 43 |
\e quoted. A plain token is just a sequence of non-whitespace characters, |
44 | 44 |
while a quoted token is a |
45 | 45 |
character sequence surrounded by double quotes, and it can also |
46 | 46 |
contain whitespaces and escape sequences. |
47 | 47 |
|
48 | 48 |
The \c \@nodes section describes a set of nodes and associated |
49 | 49 |
maps. The first is a header line, its columns are the names of the |
50 | 50 |
maps appearing in the following lines. |
51 | 51 |
One of the maps must be called \c |
52 | 52 |
"label", which plays special role in the file. |
53 | 53 |
The following |
54 | 54 |
non-empty lines until the next section describes nodes of the |
55 | 55 |
graph. Each line contains the values of the node maps |
56 | 56 |
associated to the current node. |
57 | 57 |
|
58 | 58 |
\code |
59 | 59 |
@nodes |
60 |
label coordinates size title |
|
61 |
1 (10,20) 10 "First node" |
|
62 |
2 (80,80) 8 "Second node" |
|
63 |
3 (40,10) 10 "Third node" |
|
60 |
label coordinates size title |
|
61 |
1 (10,20) 10 "First node" |
|
62 |
2 (80,80) 8 "Second node" |
|
63 |
3 (40,10) 10 "Third node" |
|
64 | 64 |
\endcode |
65 | 65 |
|
66 | 66 |
The \c \@arcs section is very similar to the \c \@nodes section, |
67 | 67 |
it again starts with a header line describing the names of the maps, |
68 | 68 |
but the \c "label" map is not obligatory here. The following lines |
69 | 69 |
describe the arcs. The first two tokens of each line are |
70 | 70 |
the source and the target node of the arc, respectively, then come the map |
71 | 71 |
values. The source and target tokens must be node labels. |
72 | 72 |
|
73 | 73 |
\code |
74 | 74 |
@arcs |
75 |
|
|
75 |
capacity |
|
76 | 76 |
1 2 16 |
77 | 77 |
1 3 12 |
78 | 78 |
2 3 18 |
79 | 79 |
\endcode |
80 | 80 |
|
81 | 81 |
The \c \@edges is just a synonym of \c \@arcs. The @arcs section can |
82 | 82 |
also store the edge set of an undirected graph. In such case there is |
83 | 83 |
a conventional method for store arc maps in the file, if two columns |
84 | 84 |
has the same caption with \c '+' and \c '-' prefix, then these columns |
85 | 85 |
can be regarded as the values of an arc map. |
86 | 86 |
|
87 | 87 |
The \c \@attributes section contains key-value pairs, each line |
88 | 88 |
consists of two tokens, an attribute name, and then an attribute |
89 | 89 |
value. The value of the attribute could be also a label value of a |
90 | 90 |
node or an edge, or even an edge label prefixed with \c '+' or \c '-', |
91 | 91 |
which regards to the forward or backward directed arc of the |
92 | 92 |
corresponding edge. |
93 | 93 |
|
94 | 94 |
\code |
95 | 95 |
@attributes |
96 | 96 |
source 1 |
97 | 97 |
target 3 |
98 | 98 |
caption "LEMON test digraph" |
99 | 99 |
\endcode |
... | ... |
@@ -45,59 +45,59 @@ |
45 | 45 |
{ |
46 | 46 |
assert_fail_log(file, line, function, message, assertion); |
47 | 47 |
std::abort(); |
48 | 48 |
} |
49 | 49 |
|
50 | 50 |
namespace _assert_bits { |
51 | 51 |
|
52 | 52 |
|
53 | 53 |
inline const char* cstringify(const std::string& str) { |
54 | 54 |
return str.c_str(); |
55 | 55 |
} |
56 | 56 |
|
57 | 57 |
inline const char* cstringify(const char* str) { |
58 | 58 |
return str; |
59 | 59 |
} |
60 | 60 |
} |
61 | 61 |
} |
62 | 62 |
|
63 | 63 |
#endif // LEMON_ASSERT_H |
64 | 64 |
|
65 | 65 |
#undef LEMON_ASSERT |
66 | 66 |
#undef LEMON_FIXME |
67 | 67 |
#undef LEMON_DEBUG |
68 | 68 |
|
69 |
#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
70 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
69 |
#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
70 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
71 | 71 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1 |
72 | 72 |
#error "LEMON assertion system is not set properly" |
73 | 73 |
#endif |
74 | 74 |
|
75 |
#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
76 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
77 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \ |
|
78 |
defined(LEMON_ENABLE_ASSERTS)) && \ |
|
79 |
|
|
75 |
#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) + \ |
|
76 |
(defined(LEMON_ASSERT_ABORT) ? 1 : 0) + \ |
|
77 |
(defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 || \ |
|
78 |
defined(LEMON_ENABLE_ASSERTS)) && \ |
|
79 |
(defined(LEMON_DISABLE_ASSERTS) || \ |
|
80 | 80 |
defined(NDEBUG)) |
81 | 81 |
#error "LEMON assertion system is not set properly" |
82 | 82 |
#endif |
83 | 83 |
|
84 | 84 |
|
85 | 85 |
#if defined LEMON_ASSERT_LOG |
86 | 86 |
# undef LEMON_ASSERT_HANDLER |
87 | 87 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_log |
88 | 88 |
#elif defined LEMON_ASSERT_ABORT |
89 | 89 |
# undef LEMON_ASSERT_HANDLER |
90 | 90 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort |
91 | 91 |
#elif defined LEMON_ASSERT_CUSTOM |
92 | 92 |
# undef LEMON_ASSERT_HANDLER |
93 | 93 |
# ifndef LEMON_CUSTOM_ASSERT_HANDLER |
94 | 94 |
# error "LEMON_CUSTOM_ASSERT_HANDLER is not set" |
95 | 95 |
# endif |
96 | 96 |
# define LEMON_ASSERT_HANDLER LEMON_CUSTOM_ASSERT_HANDLER |
97 | 97 |
#elif defined LEMON_DISABLE_ASSERTS |
98 | 98 |
# undef LEMON_ASSERT_HANDLER |
99 | 99 |
#elif defined NDEBUG |
100 | 100 |
# undef LEMON_ASSERT_HANDLER |
101 | 101 |
#else |
102 | 102 |
# define LEMON_ASSERT_HANDLER ::lemon::assert_fail_abort |
103 | 103 |
#endif |
... | ... |
@@ -147,115 +147,105 @@ |
147 | 147 |
/// message to the standard error and continues the execution. |
148 | 148 |
/// - \c LEMON_ASSERT_ABORT This mode is similar to the \c |
149 | 149 |
/// LEMON_ASSERT_LOG, but it aborts the program. It is the default |
150 | 150 |
/// behaviour. |
151 | 151 |
/// - \c LEMON_ASSERT_CUSTOM The user can define own assertion handler |
152 | 152 |
/// function. |
153 | 153 |
/// \code |
154 | 154 |
/// void custom_assert_handler(const char* file, int line, |
155 | 155 |
/// const char* function, const char* message, |
156 | 156 |
/// const char* assertion); |
157 | 157 |
/// \endcode |
158 | 158 |
/// The name of the function should be defined as the \c |
159 | 159 |
/// LEMON_CUSTOM_ASSERT_HANDLER macro name. |
160 | 160 |
/// \code |
161 | 161 |
/// #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler |
162 | 162 |
/// \endcode |
163 | 163 |
/// Whenever an assertion is occured, the custom assertion |
164 | 164 |
/// handler is called with appropiate parameters. |
165 | 165 |
/// |
166 | 166 |
/// The assertion mode can also be changed within one compilation unit. |
167 | 167 |
/// If the macros are redefined with other settings and the |
168 | 168 |
/// \ref lemon/assert.h "assert.h" file is reincluded, then the |
169 | 169 |
/// behaviour is changed appropiately to the new settings. |
170 | 170 |
# define LEMON_ASSERT(exp, msg) \ |
171 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
172 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
173 |
|
|
171 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
172 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
173 |
LEMON_FUNCTION_NAME, \ |
|
174 | 174 |
::lemon::_assert_bits::cstringify(msg), #exp), 0))) |
175 | 175 |
|
176 | 176 |
/// \ingroup exceptions |
177 | 177 |
/// |
178 | 178 |
/// \brief Macro for mark not yet implemented features. |
179 | 179 |
/// |
180 | 180 |
/// Macro for mark not yet implemented features and outstanding bugs. |
181 | 181 |
/// It is close to be the shortcut of the following code: |
182 | 182 |
/// \code |
183 | 183 |
/// LEMON_ASSERT(false, msg); |
184 | 184 |
/// \endcode |
185 | 185 |
/// |
186 | 186 |
/// \see LEMON_ASSERT |
187 |
# define LEMON_FIXME(msg) |
|
187 |
# define LEMON_FIXME(msg) \ |
|
188 | 188 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \ |
189 |
::lemon::_assert_bits::cstringify(msg), |
|
189 |
::lemon::_assert_bits::cstringify(msg), \ |
|
190 | 190 |
static_cast<const char*>(0))) |
191 | 191 |
|
192 | 192 |
/// \ingroup exceptions |
193 | 193 |
/// |
194 | 194 |
/// \brief Macro for internal assertions |
195 | 195 |
/// |
196 | 196 |
/// Macro for internal assertions, it is used in the library to check |
197 | 197 |
/// the consistency of results of algorithms, several pre- and |
198 | 198 |
/// postconditions and invariants. The checking is disabled by |
199 | 199 |
/// default, but it can be turned on with the macro \c |
200 | 200 |
/// LEMON_ENABLE_DEBUG. |
201 | 201 |
/// \code |
202 | 202 |
/// #define LEMON_ENABLE_DEBUG |
203 | 203 |
/// \endcode |
204 | 204 |
/// or with compilation parameters: |
205 | 205 |
/// \code |
206 | 206 |
/// g++ -DLEMON_ENABLE_DEBUG |
207 | 207 |
/// make CXXFLAGS='-DLEMON_ENABLE_DEBUG' |
208 | 208 |
/// \endcode |
209 | 209 |
/// |
210 | 210 |
/// This macro works like the \c LEMON_ASSERT macro, therefore the |
211 | 211 |
/// current behaviour depends on the settings of \c LEMON_ASSERT |
212 | 212 |
/// macro. |
213 | 213 |
/// |
214 | 214 |
/// \see LEMON_ASSERT |
215 |
# define LEMON_DEBUG(exp, msg) \ |
|
216 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
215 |
# define LEMON_DEBUG(exp, msg) \ |
|
216 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
217 | 217 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
218 |
LEMON_FUNCTION_NAME, |
|
218 |
LEMON_FUNCTION_NAME, \ |
|
219 | 219 |
::lemon::_assert_bits::cstringify(msg), #exp), 0))) |
220 | 220 |
|
221 | 221 |
#else |
222 | 222 |
|
223 | 223 |
# ifndef LEMON_ASSERT_HANDLER |
224 | 224 |
# define LEMON_ASSERT(exp, msg) (static_cast<void>(0)) |
225 | 225 |
# define LEMON_FIXME(msg) (static_cast<void>(0)) |
226 | 226 |
# define LEMON_DEBUG(exp, msg) (static_cast<void>(0)) |
227 | 227 |
# else |
228 |
# define LEMON_ASSERT(exp, msg) \ |
|
229 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
228 |
# define LEMON_ASSERT(exp, msg) \ |
|
229 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
230 | 230 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
231 |
LEMON_FUNCTION_NAME, \ |
|
232 |
::lemon::_assert_bits::cstringify(msg), \ |
|
231 |
LEMON_FUNCTION_NAME, \ |
|
232 |
::lemon::_assert_bits::cstringify(msg), \ |
|
233 | 233 |
#exp), 0))) |
234 |
# define LEMON_FIXME(msg) \ |
|
235 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \ |
|
236 |
|
|
234 |
# define LEMON_FIXME(msg) \ |
|
235 |
(LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME, \ |
|
236 |
::lemon::_assert_bits::cstringify(msg), \ |
|
237 | 237 |
static_cast<const char*>(0))) |
238 | 238 |
|
239 | 239 |
# if LEMON_ENABLE_DEBUG |
240 | 240 |
# define LEMON_DEBUG(exp, msg) |
241 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
242 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
243 |
LEMON_FUNCTION_NAME, \ |
|
244 |
::lemon::_assert_bits::cstringify(msg), \ |
|
241 |
(static_cast<void> (!!(exp) ? 0 : ( \ |
|
242 |
LEMON_ASSERT_HANDLER(__FILE__, __LINE__, \ |
|
243 |
LEMON_FUNCTION_NAME, \ |
|
244 |
::lemon::_assert_bits::cstringify(msg), \ |
|
245 | 245 |
#exp), 0))) |
246 | 246 |
# else |
247 | 247 |
# define LEMON_DEBUG(exp, msg) (static_cast<void>(0)) |
248 | 248 |
# endif |
249 | 249 |
# endif |
250 | 250 |
|
251 | 251 |
#endif |
252 |
|
|
253 |
#ifdef DOXYGEN |
|
254 |
|
|
255 |
|
|
256 |
#else |
|
257 |
|
|
258 |
|
|
259 |
#endif |
|
260 |
|
|
261 |
... | ... |
@@ -79,50 +79,50 @@ |
79 | 79 |
void clear() {} |
80 | 80 |
|
81 | 81 |
/// \brief Lemon style iterator for path arcs |
82 | 82 |
/// |
83 | 83 |
/// This class is used to iterate on the arcs of the paths. |
84 | 84 |
class ArcIt { |
85 | 85 |
public: |
86 | 86 |
/// Default constructor |
87 | 87 |
ArcIt() {} |
88 | 88 |
/// Invalid constructor |
89 | 89 |
ArcIt(Invalid) {} |
90 | 90 |
/// Constructor for first arc |
91 | 91 |
ArcIt(const Path &) {} |
92 | 92 |
|
93 | 93 |
/// Conversion to Arc |
94 | 94 |
operator Arc() const { return INVALID; } |
95 | 95 |
|
96 | 96 |
/// Next arc |
97 | 97 |
ArcIt& operator++() {return *this;} |
98 | 98 |
|
99 | 99 |
/// Comparison operator |
100 | 100 |
bool operator==(const ArcIt&) const {return true;} |
101 | 101 |
/// Comparison operator |
102 | 102 |
bool operator!=(const ArcIt&) const {return true;} |
103 |
/// Comparison operator |
|
104 |
bool operator<(const ArcIt&) const {return false;} |
|
103 |
/// Comparison operator |
|
104 |
bool operator<(const ArcIt&) const {return false;} |
|
105 | 105 |
|
106 | 106 |
}; |
107 | 107 |
|
108 | 108 |
template <typename _Path> |
109 | 109 |
struct Constraints { |
110 | 110 |
void constraints() { |
111 | 111 |
Path<Digraph> pc; |
112 | 112 |
_Path p, pp(pc); |
113 | 113 |
int l = p.length(); |
114 | 114 |
int e = p.empty(); |
115 | 115 |
p.clear(); |
116 | 116 |
|
117 | 117 |
p = pc; |
118 | 118 |
|
119 | 119 |
typename _Path::ArcIt id, ii(INVALID), i(p); |
120 | 120 |
|
121 | 121 |
++i; |
122 | 122 |
typename Digraph::Arc ed = i; |
123 | 123 |
|
124 | 124 |
e = (i == ii); |
125 | 125 |
e = (i != ii); |
126 | 126 |
e = (i < ii); |
127 | 127 |
|
128 | 128 |
ignore_unused_variable_warning(l); |
... | ... |
@@ -234,74 +234,74 @@ |
234 | 234 |
typedef False RevPathTag; |
235 | 235 |
|
236 | 236 |
/// \brief Lemon style iterator for path arcs |
237 | 237 |
/// |
238 | 238 |
/// This class is used to iterate on the arcs of the paths. |
239 | 239 |
class ArcIt { |
240 | 240 |
public: |
241 | 241 |
/// Default constructor |
242 | 242 |
ArcIt() {} |
243 | 243 |
/// Invalid constructor |
244 | 244 |
ArcIt(Invalid) {} |
245 | 245 |
/// Constructor for first arc |
246 | 246 |
ArcIt(const PathDumper&) {} |
247 | 247 |
|
248 | 248 |
/// Conversion to Arc |
249 | 249 |
operator Arc() const { return INVALID; } |
250 | 250 |
|
251 | 251 |
/// Next arc |
252 | 252 |
ArcIt& operator++() {return *this;} |
253 | 253 |
|
254 | 254 |
/// Comparison operator |
255 | 255 |
bool operator==(const ArcIt&) const {return true;} |
256 | 256 |
/// Comparison operator |
257 | 257 |
bool operator!=(const ArcIt&) const {return true;} |
258 |
/// Comparison operator |
|
259 |
bool operator<(const ArcIt&) const {return false;} |
|
258 |
/// Comparison operator |
|
259 |
bool operator<(const ArcIt&) const {return false;} |
|
260 | 260 |
|
261 | 261 |
}; |
262 | 262 |
|
263 | 263 |
/// \brief Lemon style iterator for path arcs |
264 | 264 |
/// |
265 | 265 |
/// This class is used to iterate on the arcs of the paths in |
266 | 266 |
/// reverse direction. |
267 | 267 |
class RevArcIt { |
268 | 268 |
public: |
269 | 269 |
/// Default constructor |
270 | 270 |
RevArcIt() {} |
271 | 271 |
/// Invalid constructor |
272 | 272 |
RevArcIt(Invalid) {} |
273 | 273 |
/// Constructor for first arc |
274 | 274 |
RevArcIt(const PathDumper &) {} |
275 | 275 |
|
276 | 276 |
/// Conversion to Arc |
277 | 277 |
operator Arc() const { return INVALID; } |
278 | 278 |
|
279 | 279 |
/// Next arc |
280 | 280 |
RevArcIt& operator++() {return *this;} |
281 | 281 |
|
282 | 282 |
/// Comparison operator |
283 | 283 |
bool operator==(const RevArcIt&) const {return true;} |
284 | 284 |
/// Comparison operator |
285 | 285 |
bool operator!=(const RevArcIt&) const {return true;} |
286 |
/// Comparison operator |
|
287 |
bool operator<(const RevArcIt&) const {return false;} |
|
286 |
/// Comparison operator |
|
287 |
bool operator<(const RevArcIt&) const {return false;} |
|
288 | 288 |
|
289 | 289 |
}; |
290 | 290 |
|
291 | 291 |
template <typename _Path> |
292 | 292 |
struct Constraints { |
293 | 293 |
void constraints() { |
294 | 294 |
function_requires<_path_bits:: |
295 | 295 |
PathDumperConstraints<Digraph, _Path> >(); |
296 | 296 |
} |
297 | 297 |
}; |
298 | 298 |
|
299 | 299 |
}; |
300 | 300 |
|
301 | 301 |
|
302 | 302 |
///@} |
303 | 303 |
} |
304 | 304 |
|
305 | 305 |
} // namespace lemon |
306 | 306 |
|
307 | 307 |
#endif // LEMON_CONCEPT_PATH_H |
... | ... |
@@ -49,49 +49,49 @@ |
49 | 49 |
} catch (...) {} |
50 | 50 |
} |
51 | 51 |
|
52 | 52 |
ExceptionMember(const Type& type) throw() { |
53 | 53 |
try { |
54 | 54 |
ptr.reset(new Type()); |
55 | 55 |
if (ptr.get() == 0) return; |
56 | 56 |
*ptr = type; |
57 | 57 |
} catch (...) {} |
58 | 58 |
} |
59 | 59 |
|
60 | 60 |
ExceptionMember(const ExceptionMember& copy) throw() { |
61 | 61 |
try { |
62 | 62 |
if (!copy.valid()) return; |
63 | 63 |
ptr.reset(new Type()); |
64 | 64 |
if (ptr.get() == 0) return; |
65 | 65 |
*ptr = copy.get(); |
66 | 66 |
} catch (...) {} |
67 | 67 |
} |
68 | 68 |
|
69 | 69 |
ExceptionMember& operator=(const ExceptionMember& copy) throw() { |
70 | 70 |
if (ptr.get() == 0) return; |
71 | 71 |
try { |
72 | 72 |
if (!copy.valid()) return; |
73 |
|
|
73 |
*ptr = copy.get(); |
|
74 | 74 |
} catch (...) {} |
75 | 75 |
} |
76 | 76 |
|
77 | 77 |
void set(const Type& type) throw() { |
78 | 78 |
if (ptr.get() == 0) return; |
79 | 79 |
try { |
80 | 80 |
*ptr = type; |
81 | 81 |
} catch (...) {} |
82 | 82 |
} |
83 | 83 |
|
84 | 84 |
const Type& get() const { |
85 | 85 |
return *ptr; |
86 | 86 |
} |
87 | 87 |
|
88 | 88 |
bool valid() const throw() { |
89 | 89 |
return ptr.get() != 0; |
90 | 90 |
} |
91 | 91 |
|
92 | 92 |
private: |
93 | 93 |
std::auto_ptr<_Type> ptr; |
94 | 94 |
}; |
95 | 95 |
|
96 | 96 |
/// Exception-safe convenient error message builder class. |
97 | 97 |
... | ... |
@@ -887,57 +887,57 @@ |
887 | 887 |
if(_showArcs) { |
888 | 888 |
os << "%Arcs:\ngsave\n"; |
889 | 889 |
if(_enableParallel) { |
890 | 890 |
std::vector<Arc> el; |
891 | 891 |
for(ArcIt e(g);e!=INVALID;++e) |
892 | 892 |
if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0 |
893 | 893 |
&&g.source(e)!=g.target(e)) |
894 | 894 |
el.push_back(e); |
895 | 895 |
std::sort(el.begin(),el.end(),arcLess(g)); |
896 | 896 |
|
897 | 897 |
typename std::vector<Arc>::iterator j; |
898 | 898 |
for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) { |
899 | 899 |
for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ; |
900 | 900 |
|
901 | 901 |
double sw=0; |
902 | 902 |
for(typename std::vector<Arc>::iterator e=i;e!=j;++e) |
903 | 903 |
sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist; |
904 | 904 |
sw-=_parArcDist; |
905 | 905 |
sw/=-2.0; |
906 | 906 |
dim2::Point<double> |
907 | 907 |
dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]); |
908 | 908 |
double l=std::sqrt(dvec.normSquare()); |
909 | 909 |
//\todo better 'epsilon' would be nice here. |
910 | 910 |
dim2::Point<double> d(dvec/std::max(l,EPSILON)); |
911 |
|
|
911 |
dim2::Point<double> m; |
|
912 | 912 |
// m=dim2::Point<double>(mycoords[g.target(*i)]+ |
913 | 913 |
// mycoords[g.source(*i)])/2.0; |
914 | 914 |
|
915 | 915 |
// m=dim2::Point<double>(mycoords[g.source(*i)])+ |
916 | 916 |
// dvec*(double(_nodeSizes[g.source(*i)])/ |
917 | 917 |
// (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)])); |
918 | 918 |
|
919 |
|
|
919 |
m=dim2::Point<double>(mycoords[g.source(*i)])+ |
|
920 | 920 |
d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0; |
921 | 921 |
|
922 | 922 |
for(typename std::vector<Arc>::iterator e=i;e!=j;++e) { |
923 | 923 |
sw+=_arcWidths[*e]*_arcWidthScale/2.0; |
924 | 924 |
dim2::Point<double> mm=m+rot90(d)*sw/.75; |
925 | 925 |
if(_drawArrows) { |
926 | 926 |
int node_shape; |
927 | 927 |
dim2::Point<double> s=mycoords[g.source(*e)]; |
928 | 928 |
dim2::Point<double> t=mycoords[g.target(*e)]; |
929 | 929 |
double rn=_nodeSizes[g.target(*e)]*_nodeScale; |
930 | 930 |
node_shape=_nodeShapes[g.target(*e)]; |
931 | 931 |
dim2::Bezier3 bez(s,mm,mm,t); |
932 | 932 |
double t1=0,t2=1; |
933 | 933 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
934 | 934 |
if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2; |
935 | 935 |
else t1=(t1+t2)/2; |
936 | 936 |
dim2::Point<double> apoint=bez((t1+t2)/2); |
937 | 937 |
rn = _arrowLength+_arcWidths[*e]*_arcWidthScale; |
938 | 938 |
rn*=rn; |
939 | 939 |
t2=(t1+t2)/2;t1=0; |
940 | 940 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
941 | 941 |
if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2; |
942 | 942 |
else t2=(t1+t2)/2; |
943 | 943 |
dim2::Point<double> linend=bez((t1+t2)/2); |
... | ... |
@@ -31,114 +31,114 @@ |
31 | 31 |
#include <lemon/bits/traits.h> |
32 | 32 |
|
33 | 33 |
#include <lemon/bits/alteration_notifier.h> |
34 | 34 |
#include <lemon/bits/default_map.h> |
35 | 35 |
|
36 | 36 |
///\ingroup gutils |
37 | 37 |
///\file |
38 | 38 |
///\brief Graph utilities. |
39 | 39 |
|
40 | 40 |
namespace lemon { |
41 | 41 |
|
42 | 42 |
/// \addtogroup gutils |
43 | 43 |
/// @{ |
44 | 44 |
|
45 | 45 |
///Creates convenience typedefs for the digraph types and iterators |
46 | 46 |
|
47 | 47 |
///This \c \#define creates convenience typedefs for the following types |
48 | 48 |
///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, |
49 | 49 |
///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
50 | 50 |
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
51 | 51 |
/// |
52 | 52 |
///\note If the graph type is a dependent type, ie. the graph type depend |
53 | 53 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
54 | 54 |
///macro. |
55 |
#define DIGRAPH_TYPEDEFS(Digraph) \ |
|
56 |
typedef Digraph::Node Node; \ |
|
57 |
typedef Digraph::NodeIt NodeIt; \ |
|
58 |
typedef Digraph::Arc Arc; \ |
|
59 |
typedef Digraph::ArcIt ArcIt; \ |
|
60 |
typedef Digraph::InArcIt InArcIt; \ |
|
61 |
typedef Digraph::OutArcIt OutArcIt; \ |
|
62 |
typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
|
63 |
typedef Digraph::NodeMap<int> IntNodeMap; \ |
|
64 |
typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
|
65 |
typedef Digraph::ArcMap<bool> BoolArcMap; \ |
|
66 |
typedef Digraph::ArcMap<int> IntArcMap; \ |
|
55 |
#define DIGRAPH_TYPEDEFS(Digraph) \ |
|
56 |
typedef Digraph::Node Node; \ |
|
57 |
typedef Digraph::NodeIt NodeIt; \ |
|
58 |
typedef Digraph::Arc Arc; \ |
|
59 |
typedef Digraph::ArcIt ArcIt; \ |
|
60 |
typedef Digraph::InArcIt InArcIt; \ |
|
61 |
typedef Digraph::OutArcIt OutArcIt; \ |
|
62 |
typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
|
63 |
typedef Digraph::NodeMap<int> IntNodeMap; \ |
|
64 |
typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
|
65 |
typedef Digraph::ArcMap<bool> BoolArcMap; \ |
|
66 |
typedef Digraph::ArcMap<int> IntArcMap; \ |
|
67 | 67 |
typedef Digraph::ArcMap<double> DoubleArcMap |
68 | 68 |
|
69 | 69 |
///Creates convenience typedefs for the digraph types and iterators |
70 | 70 |
|
71 | 71 |
///\see DIGRAPH_TYPEDEFS |
72 | 72 |
/// |
73 | 73 |
///\note Use this macro, if the graph type is a dependent type, |
74 | 74 |
///ie. the graph type depend on a template parameter. |
75 |
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ |
|
76 |
typedef typename Digraph::Node Node; \ |
|
77 |
typedef typename Digraph::NodeIt NodeIt; \ |
|
78 |
typedef typename Digraph::Arc Arc; \ |
|
75 |
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \ |
|
76 |
typedef typename Digraph::Node Node; \ |
|
77 |
typedef typename Digraph::NodeIt NodeIt; \ |
|
78 |
typedef typename Digraph::Arc Arc; \ |
|
79 | 79 |
typedef typename Digraph::ArcIt ArcIt; \ |
80 |
typedef typename Digraph::InArcIt InArcIt; \ |
|
81 |
typedef typename Digraph::OutArcIt OutArcIt; \ |
|
82 |
typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
|
83 |
typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
|
84 |
typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
|
85 |
typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
|
86 |
typedef typename Digraph:: |
|
80 |
typedef typename Digraph::InArcIt InArcIt; \ |
|
81 |
typedef typename Digraph::OutArcIt OutArcIt; \ |
|
82 |
typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
|
83 |
typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
|
84 |
typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
|
85 |
typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
|
86 |
typedef typename Digraph::template ArcMap<int> IntArcMap; \ |
|
87 | 87 |
typedef typename Digraph::template ArcMap<double> DoubleArcMap |
88 | 88 |
|
89 | 89 |
///Creates convenience typedefs for the graph types and iterators |
90 | 90 |
|
91 | 91 |
///This \c \#define creates the same convenience typedefs as defined |
92 | 92 |
///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates |
93 | 93 |
///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, |
94 | 94 |
///\c DoubleEdgeMap. |
95 | 95 |
/// |
96 | 96 |
///\note If the graph type is a dependent type, ie. the graph type depend |
97 | 97 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
98 | 98 |
///macro. |
99 |
#define GRAPH_TYPEDEFS(Graph) \ |
|
100 |
DIGRAPH_TYPEDEFS(Graph); \ |
|
101 |
typedef Graph::Edge Edge; \ |
|
102 |
typedef Graph::EdgeIt EdgeIt; \ |
|
103 |
typedef Graph::IncEdgeIt IncEdgeIt; \ |
|
104 |
typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
|
105 |
|
|
99 |
#define GRAPH_TYPEDEFS(Graph) \ |
|
100 |
DIGRAPH_TYPEDEFS(Graph); \ |
|
101 |
typedef Graph::Edge Edge; \ |
|
102 |
typedef Graph::EdgeIt EdgeIt; \ |
|
103 |
typedef Graph::IncEdgeIt IncEdgeIt; \ |
|
104 |
typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
|
105 |
typedef Graph::EdgeMap<int> IntEdgeMap; \ |
|
106 | 106 |
typedef Graph::EdgeMap<double> DoubleEdgeMap |
107 | 107 |
|
108 | 108 |
///Creates convenience typedefs for the graph types and iterators |
109 | 109 |
|
110 | 110 |
///\see GRAPH_TYPEDEFS |
111 | 111 |
/// |
112 | 112 |
///\note Use this macro, if the graph type is a dependent type, |
113 | 113 |
///ie. the graph type depend on a template parameter. |
114 |
#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ |
|
115 |
TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ |
|
116 |
|
|
114 |
#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \ |
|
115 |
TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \ |
|
116 |
typedef typename Graph::Edge Edge; \ |
|
117 | 117 |
typedef typename Graph::EdgeIt EdgeIt; \ |
118 |
typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
|
119 |
typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
|
120 |
typedef typename Graph:: |
|
118 |
typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
|
119 |
typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
|
120 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ |
|
121 | 121 |
typedef typename Graph::template EdgeMap<double> DoubleEdgeMap |
122 | 122 |
|
123 | 123 |
/// \brief Function to count the items in the graph. |
124 | 124 |
/// |
125 | 125 |
/// This function counts the items (nodes, arcs etc) in the graph. |
126 | 126 |
/// The complexity of the function is O(n) because |
127 | 127 |
/// it iterates on all of the items. |
128 | 128 |
template <typename Graph, typename Item> |
129 | 129 |
inline int countItems(const Graph& g) { |
130 | 130 |
typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
131 | 131 |
int num = 0; |
132 | 132 |
for (ItemIt it(g); it != INVALID; ++it) { |
133 | 133 |
++num; |
134 | 134 |
} |
135 | 135 |
return num; |
136 | 136 |
} |
137 | 137 |
|
138 | 138 |
// Node counting: |
139 | 139 |
|
140 | 140 |
namespace _graph_utils_bits { |
141 | 141 |
|
142 | 142 |
template <typename Graph, typename Enable = void> |
143 | 143 |
struct CountNodesSelector { |
144 | 144 |
static int count(const Graph &g) { |
... | ... |
@@ -125,49 +125,49 @@ |
125 | 125 |
_map.set(_graph.direct(item, dir), _converter(value)); |
126 | 126 |
} |
127 | 127 |
}; |
128 | 128 |
|
129 | 129 |
class ValueStorageBase { |
130 | 130 |
public: |
131 | 131 |
ValueStorageBase() {} |
132 | 132 |
virtual ~ValueStorageBase() {} |
133 | 133 |
|
134 | 134 |
virtual void set(const std::string&) = 0; |
135 | 135 |
}; |
136 | 136 |
|
137 | 137 |
template <typename _Value, typename _Converter = DefaultConverter<_Value> > |
138 | 138 |
class ValueStorage : public ValueStorageBase { |
139 | 139 |
public: |
140 | 140 |
typedef _Value Value; |
141 | 141 |
typedef _Converter Converter; |
142 | 142 |
|
143 | 143 |
private: |
144 | 144 |
Value& _value; |
145 | 145 |
Converter _converter; |
146 | 146 |
|
147 | 147 |
public: |
148 | 148 |
ValueStorage(Value& value, const Converter& converter = Converter()) |
149 |
|
|
149 |
: _value(value), _converter(converter) {} |
|
150 | 150 |
|
151 | 151 |
virtual void set(const std::string& value) { |
152 | 152 |
_value = _converter(value); |
153 | 153 |
} |
154 | 154 |
}; |
155 | 155 |
|
156 | 156 |
template <typename Value> |
157 | 157 |
struct MapLookUpConverter { |
158 | 158 |
const std::map<std::string, Value>& _map; |
159 | 159 |
|
160 | 160 |
MapLookUpConverter(const std::map<std::string, Value>& map) |
161 | 161 |
: _map(map) {} |
162 | 162 |
|
163 | 163 |
Value operator()(const std::string& str) { |
164 | 164 |
typename std::map<std::string, Value>::const_iterator it = |
165 | 165 |
_map.find(str); |
166 | 166 |
if (it == _map.end()) { |
167 | 167 |
std::ostringstream msg; |
168 | 168 |
msg << "Item not found: " << str; |
169 | 169 |
throw DataFormatError(msg.str().c_str()); |
170 | 170 |
} |
171 | 171 |
return it->second; |
172 | 172 |
} |
173 | 173 |
}; |
... | ... |
@@ -489,58 +489,58 @@ |
489 | 489 |
|
490 | 490 |
bool _skip_nodes; |
491 | 491 |
bool _skip_arcs; |
492 | 492 |
|
493 | 493 |
int line_num; |
494 | 494 |
std::istringstream line; |
495 | 495 |
|
496 | 496 |
public: |
497 | 497 |
|
498 | 498 |
/// \brief Constructor |
499 | 499 |
/// |
500 | 500 |
/// Construct a directed graph reader, which reads from the given |
501 | 501 |
/// input stream. |
502 | 502 |
DigraphReader(std::istream& is, Digraph& digraph) |
503 | 503 |
: _is(&is), local_is(false), _digraph(digraph), |
504 | 504 |
_use_nodes(false), _use_arcs(false), |
505 | 505 |
_skip_nodes(false), _skip_arcs(false) {} |
506 | 506 |
|
507 | 507 |
/// \brief Constructor |
508 | 508 |
/// |
509 | 509 |
/// Construct a directed graph reader, which reads from the given |
510 | 510 |
/// file. |
511 | 511 |
DigraphReader(const std::string& fn, Digraph& digraph) |
512 | 512 |
: _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph), |
513 |
|
|
513 |
_use_nodes(false), _use_arcs(false), |
|
514 | 514 |
_skip_nodes(false), _skip_arcs(false) {} |
515 | 515 |
|
516 | 516 |
/// \brief Constructor |
517 | 517 |
/// |
518 | 518 |
/// Construct a directed graph reader, which reads from the given |
519 | 519 |
/// file. |
520 | 520 |
DigraphReader(const char* fn, Digraph& digraph) |
521 | 521 |
: _is(new std::ifstream(fn)), local_is(true), _digraph(digraph), |
522 |
|
|
522 |
_use_nodes(false), _use_arcs(false), |
|
523 | 523 |
_skip_nodes(false), _skip_arcs(false) {} |
524 | 524 |
|
525 | 525 |
/// \brief Destructor |
526 | 526 |
~DigraphReader() { |
527 | 527 |
for (typename NodeMaps::iterator it = _node_maps.begin(); |
528 | 528 |
it != _node_maps.end(); ++it) { |
529 | 529 |
delete it->second; |
530 | 530 |
} |
531 | 531 |
|
532 | 532 |
for (typename ArcMaps::iterator it = _arc_maps.begin(); |
533 | 533 |
it != _arc_maps.end(); ++it) { |
534 | 534 |
delete it->second; |
535 | 535 |
} |
536 | 536 |
|
537 | 537 |
for (typename Attributes::iterator it = _attributes.begin(); |
538 | 538 |
it != _attributes.end(); ++it) { |
539 | 539 |
delete it->second; |
540 | 540 |
} |
541 | 541 |
|
542 | 542 |
if (local_is) { |
543 | 543 |
delete _is; |
544 | 544 |
} |
545 | 545 |
|
546 | 546 |
} |
... | ... |
@@ -1273,58 +1273,58 @@ |
1273 | 1273 |
|
1274 | 1274 |
bool _skip_nodes; |
1275 | 1275 |
bool _skip_edges; |
1276 | 1276 |
|
1277 | 1277 |
int line_num; |
1278 | 1278 |
std::istringstream line; |
1279 | 1279 |
|
1280 | 1280 |
public: |
1281 | 1281 |
|
1282 | 1282 |
/// \brief Constructor |
1283 | 1283 |
/// |
1284 | 1284 |
/// Construct an undirected graph reader, which reads from the given |
1285 | 1285 |
/// input stream. |
1286 | 1286 |
GraphReader(std::istream& is, Graph& graph) |
1287 | 1287 |
: _is(&is), local_is(false), _graph(graph), |
1288 | 1288 |
_use_nodes(false), _use_edges(false), |
1289 | 1289 |
_skip_nodes(false), _skip_edges(false) {} |
1290 | 1290 |
|
1291 | 1291 |
/// \brief Constructor |
1292 | 1292 |
/// |
1293 | 1293 |
/// Construct an undirected graph reader, which reads from the given |
1294 | 1294 |
/// file. |
1295 | 1295 |
GraphReader(const std::string& fn, Graph& graph) |
1296 | 1296 |
: _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph), |
1297 |
|
|
1297 |
_use_nodes(false), _use_edges(false), |
|
1298 | 1298 |
_skip_nodes(false), _skip_edges(false) {} |
1299 | 1299 |
|
1300 | 1300 |
/// \brief Constructor |
1301 | 1301 |
/// |
1302 | 1302 |
/// Construct an undirected graph reader, which reads from the given |
1303 | 1303 |
/// file. |
1304 | 1304 |
GraphReader(const char* fn, Graph& graph) |
1305 | 1305 |
: _is(new std::ifstream(fn)), local_is(true), _graph(graph), |
1306 |
|
|
1306 |
_use_nodes(false), _use_edges(false), |
|
1307 | 1307 |
_skip_nodes(false), _skip_edges(false) {} |
1308 | 1308 |
|
1309 | 1309 |
/// \brief Destructor |
1310 | 1310 |
~GraphReader() { |
1311 | 1311 |
for (typename NodeMaps::iterator it = _node_maps.begin(); |
1312 | 1312 |
it != _node_maps.end(); ++it) { |
1313 | 1313 |
delete it->second; |
1314 | 1314 |
} |
1315 | 1315 |
|
1316 | 1316 |
for (typename EdgeMaps::iterator it = _edge_maps.begin(); |
1317 | 1317 |
it != _edge_maps.end(); ++it) { |
1318 | 1318 |
delete it->second; |
1319 | 1319 |
} |
1320 | 1320 |
|
1321 | 1321 |
for (typename Attributes::iterator it = _attributes.begin(); |
1322 | 1322 |
it != _attributes.end(); ++it) { |
1323 | 1323 |
delete it->second; |
1324 | 1324 |
} |
1325 | 1325 |
|
1326 | 1326 |
if (local_is) { |
1327 | 1327 |
delete _is; |
1328 | 1328 |
} |
1329 | 1329 |
|
1330 | 1330 |
} |
... | ... |
@@ -160,49 +160,49 @@ |
160 | 160 |
std::sort(items.begin(), items.end(), less); |
161 | 161 |
} |
162 | 162 |
}; |
163 | 163 |
|
164 | 164 |
class ValueStorageBase { |
165 | 165 |
public: |
166 | 166 |
ValueStorageBase() {} |
167 | 167 |
virtual ~ValueStorageBase() {} |
168 | 168 |
|
169 | 169 |
virtual std::string get() = 0; |
170 | 170 |
}; |
171 | 171 |
|
172 | 172 |
template <typename _Value, typename _Converter = DefaultConverter<_Value> > |
173 | 173 |
class ValueStorage : public ValueStorageBase { |
174 | 174 |
public: |
175 | 175 |
typedef _Value Value; |
176 | 176 |
typedef _Converter Converter; |
177 | 177 |
|
178 | 178 |
private: |
179 | 179 |
const Value& _value; |
180 | 180 |
Converter _converter; |
181 | 181 |
|
182 | 182 |
public: |
183 | 183 |
ValueStorage(const Value& value, const Converter& converter = Converter()) |
184 |
|
|
184 |
: _value(value), _converter(converter) {} |
|
185 | 185 |
|
186 | 186 |
virtual std::string get() { |
187 | 187 |
return _converter(_value); |
188 | 188 |
} |
189 | 189 |
}; |
190 | 190 |
|
191 | 191 |
template <typename Value> |
192 | 192 |
struct MapLookUpConverter { |
193 | 193 |
const std::map<Value, std::string>& _map; |
194 | 194 |
|
195 | 195 |
MapLookUpConverter(const std::map<Value, std::string>& map) |
196 | 196 |
: _map(map) {} |
197 | 197 |
|
198 | 198 |
std::string operator()(const Value& str) { |
199 | 199 |
typename std::map<Value, std::string>::const_iterator it = |
200 | 200 |
_map.find(str); |
201 | 201 |
if (it == _map.end()) { |
202 | 202 |
throw DataFormatError("Item not found"); |
203 | 203 |
} |
204 | 204 |
return it->second; |
205 | 205 |
} |
206 | 206 |
}; |
207 | 207 |
|
208 | 208 |
template <typename Graph> |
... | ... |
@@ -473,49 +473,49 @@ |
473 | 473 |
e=f; |
474 | 474 |
} |
475 | 475 |
erase(b); |
476 | 476 |
} |
477 | 477 |
|
478 | 478 |
///Split a node. |
479 | 479 |
|
480 | 480 |
///This function splits a node. First a new node is added to the digraph, |
481 | 481 |
///then the source of each outgoing arc of \c n is moved to this new node. |
482 | 482 |
///If \c connect is \c true (this is the default value), then a new arc |
483 | 483 |
///from \c n to the newly created node is also added. |
484 | 484 |
///\return The newly created node. |
485 | 485 |
/// |
486 | 486 |
///\note The <tt>ArcIt</tt>s referencing a moved arc remain |
487 | 487 |
///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may |
488 | 488 |
///be invalidated. |
489 | 489 |
/// |
490 | 490 |
///\warning This functionality cannot be used together with the |
491 | 491 |
///Snapshot feature. |
492 | 492 |
/// |
493 | 493 |
///\todo It could be implemented in a bit faster way. |
494 | 494 |
Node split(Node n, bool connect = true) { |
495 | 495 |
Node b = addNode(); |
496 | 496 |
for(OutArcIt e(*this,n);e!=INVALID;) { |
497 |
|
|
497 |
OutArcIt f=e; |
|
498 | 498 |
++f; |
499 | 499 |
changeSource(e,b); |
500 | 500 |
e=f; |
501 | 501 |
} |
502 | 502 |
if (connect) addArc(n,b); |
503 | 503 |
return b; |
504 | 504 |
} |
505 | 505 |
|
506 | 506 |
///Split an arc. |
507 | 507 |
|
508 | 508 |
///This function splits an arc. First a new node \c b is added to |
509 | 509 |
///the digraph, then the original arc is re-targeted to \c |
510 | 510 |
///b. Finally an arc from \c b to the original target is added. |
511 | 511 |
/// |
512 | 512 |
///\return The newly created node. |
513 | 513 |
/// |
514 | 514 |
///\warning This functionality cannot be used together with the |
515 | 515 |
///Snapshot feature. |
516 | 516 |
Node split(Arc e) { |
517 | 517 |
Node b = addNode(); |
518 | 518 |
addArc(b,target(e)); |
519 | 519 |
changeTarget(e,b); |
520 | 520 |
return b; |
521 | 521 |
} |
... | ... |
@@ -33,69 +33,69 @@ |
33 | 33 |
#include <lemon/bin_heap.h> |
34 | 34 |
|
35 | 35 |
#include "test_tools.h" |
36 | 36 |
|
37 | 37 |
using namespace lemon; |
38 | 38 |
using namespace lemon::concepts; |
39 | 39 |
|
40 | 40 |
typedef ListDigraph Digraph; |
41 | 41 |
DIGRAPH_TYPEDEFS(Digraph); |
42 | 42 |
|
43 | 43 |
char test_lgf[] = |
44 | 44 |
"@nodes\n" |
45 | 45 |
"label\n" |
46 | 46 |
"0\n" |
47 | 47 |
"1\n" |
48 | 48 |
"2\n" |
49 | 49 |
"3\n" |
50 | 50 |
"4\n" |
51 | 51 |
"5\n" |
52 | 52 |
"6\n" |
53 | 53 |
"7\n" |
54 | 54 |
"8\n" |
55 | 55 |
"9\n" |
56 | 56 |
"@arcs\n" |
57 |
" label capacity\n" |
|
58 |
"0 5 0 94\n" |
|
59 |
"3 9 1 11\n" |
|
60 |
"8 7 2 83\n" |
|
61 |
"1 2 3 94\n" |
|
62 |
"5 7 4 35\n" |
|
63 |
"7 4 5 84\n" |
|
64 |
"9 5 6 38\n" |
|
65 |
"0 4 7 96\n" |
|
66 |
"6 7 8 6\n" |
|
67 |
"3 1 9 27\n" |
|
68 |
"5 2 10 77\n" |
|
69 |
"5 6 11 69\n" |
|
70 |
"6 5 12 41\n" |
|
71 |
"4 6 13 70\n" |
|
72 |
"3 2 14 45\n" |
|
73 |
"7 9 15 93\n" |
|
74 |
"5 9 16 50\n" |
|
75 |
"9 0 17 94\n" |
|
76 |
"9 6 18 67\n" |
|
77 |
" |
|
57 |
" label capacity\n" |
|
58 |
"0 5 0 94\n" |
|
59 |
"3 9 1 11\n" |
|
60 |
"8 7 2 83\n" |
|
61 |
"1 2 3 94\n" |
|
62 |
"5 7 4 35\n" |
|
63 |
"7 4 5 84\n" |
|
64 |
"9 5 6 38\n" |
|
65 |
"0 4 7 96\n" |
|
66 |
"6 7 8 6\n" |
|
67 |
"3 1 9 27\n" |
|
68 |
"5 2 10 77\n" |
|
69 |
"5 6 11 69\n" |
|
70 |
"6 5 12 41\n" |
|
71 |
"4 6 13 70\n" |
|
72 |
"3 2 14 45\n" |
|
73 |
"7 9 15 93\n" |
|
74 |
"5 9 16 50\n" |
|
75 |
"9 0 17 94\n" |
|
76 |
"9 6 18 67\n" |
|
77 |
"0 9 19 86\n" |
|
78 | 78 |
"@attributes\n" |
79 | 79 |
"source 3\n"; |
80 | 80 |
|
81 | 81 |
int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26, 1, 9, 4, 34}; |
82 | 82 |
int test_inc[] = {20, 28, 34, 16, 0, 46, 44, 0, 42, 32, 14, 8, 6, 37}; |
83 | 83 |
|
84 | 84 |
int test_len = sizeof(test_seq) / sizeof(test_seq[0]); |
85 | 85 |
|
86 | 86 |
template <typename Heap> |
87 | 87 |
void heapSortTest() { |
88 | 88 |
RangeMap<int> map(test_len, -1); |
89 | 89 |
|
90 | 90 |
Heap heap(map); |
91 | 91 |
|
92 | 92 |
std::vector<int> v(test_len); |
93 | 93 |
|
94 | 94 |
for (int i = 0; i < test_len; ++i) { |
95 | 95 |
v[i] = test_seq[i]; |
96 | 96 |
heap.push(i, v[i]); |
97 | 97 |
} |
98 | 98 |
std::sort(v.begin(), v.end()); |
99 | 99 |
for (int i = 0; i < test_len; ++i) { |
100 | 100 |
check(v[i] == heap.prio() ,"Wrong order in heap sort."); |
101 | 101 |
heap.pop(); |
... | ... |
@@ -120,49 +120,49 @@ |
120 | 120 |
} |
121 | 121 |
std::sort(v.begin(), v.end()); |
122 | 122 |
for (int i = 0; i < test_len; ++i) { |
123 | 123 |
check(v[i] == heap.prio() ,"Wrong order in heap increase test."); |
124 | 124 |
heap.pop(); |
125 | 125 |
} |
126 | 126 |
} |
127 | 127 |
|
128 | 128 |
|
129 | 129 |
|
130 | 130 |
template <typename Heap> |
131 | 131 |
void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, |
132 | 132 |
Node source) { |
133 | 133 |
|
134 | 134 |
typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>:: |
135 | 135 |
Create dijkstra(digraph, length); |
136 | 136 |
|
137 | 137 |
dijkstra.run(source); |
138 | 138 |
|
139 | 139 |
for(ArcIt a(digraph); a != INVALID; ++a) { |
140 | 140 |
Node s = digraph.source(a); |
141 | 141 |
Node t = digraph.target(a); |
142 | 142 |
if (dijkstra.reached(s)) { |
143 | 143 |
check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a], |
144 |
|
|
144 |
"Error in a shortest path tree!"); |
|
145 | 145 |
} |
146 | 146 |
} |
147 | 147 |
|
148 | 148 |
for(NodeIt n(digraph); n != INVALID; ++n) { |
149 | 149 |
if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) { |
150 | 150 |
Arc a = dijkstra.predArc(n); |
151 | 151 |
Node s = digraph.source(a); |
152 | 152 |
check( dijkstra.dist(n) - dijkstra.dist(s) == length[a], |
153 | 153 |
"Error in a shortest path tree!"); |
154 | 154 |
} |
155 | 155 |
} |
156 | 156 |
|
157 | 157 |
} |
158 | 158 |
|
159 | 159 |
int main() { |
160 | 160 |
|
161 | 161 |
typedef int Item; |
162 | 162 |
typedef int Prio; |
163 | 163 |
typedef RangeMap<int> ItemIntMap; |
164 | 164 |
|
165 | 165 |
Digraph digraph; |
166 | 166 |
IntArcMap length(digraph); |
167 | 167 |
Node source; |
168 | 168 |
|
0 comments (0 inline)