alpar@209

1 
/* * mode: C++; indenttabsmode: nil; *

alpar@40

2 
*

alpar@209

3 
* This file is a part of LEMON, a generic C++ optimization library.

alpar@40

4 
*

alpar@956

5 
* Copyright (C) 20032010

alpar@40

6 
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

alpar@40

7 
* (Egervary Research Group on Combinatorial Optimization, EGRES).

alpar@40

8 
*

alpar@40

9 
* Permission to use, modify and distribute this software is granted

alpar@40

10 
* provided that this copyright notice appears in all copies. For

alpar@40

11 
* precise terms see the accompanying LICENSE file.

alpar@40

12 
*

alpar@40

13 
* This software is provided "AS IS" with no warranty of any kind,

alpar@40

14 
* express or implied, and with no claim as to its suitability for any

alpar@40

15 
* purpose.

alpar@40

16 
*

alpar@40

17 
*/

alpar@40

18 

kpeter@422

19 
namespace lemon {

kpeter@422

20 

alpar@40

21 
/**

alpar@40

22 
@defgroup datas Data Structures

kpeter@606

23 
This group contains the several data structures implemented in LEMON.

alpar@40

24 
*/

alpar@40

25 

alpar@40

26 
/**

alpar@40

27 
@defgroup graphs Graph Structures

alpar@40

28 
@ingroup datas

alpar@40

29 
\brief Graph structures implemented in LEMON.

alpar@40

30 

alpar@209

31 
The implementation of combinatorial algorithms heavily relies on

alpar@209

32 
efficient graph implementations. LEMON offers data structures which are

alpar@209

33 
planned to be easily used in an experimental phase of implementation studies,

alpar@209

34 
and thereafter the program code can be made efficient by small modifications.

alpar@40

35 

alpar@40

36 
The most efficient implementation of diverse applications require the

alpar@40

37 
usage of different physical graph implementations. These differences

alpar@40

38 
appear in the size of graph we require to handle, memory or time usage

alpar@40

39 
limitations or in the set of operations through which the graph can be

alpar@40

40 
accessed. LEMON provides several physical graph structures to meet

alpar@40

41 
the diverging requirements of the possible users. In order to save on

alpar@40

42 
running time or on memory usage, some structures may fail to provide

kpeter@83

43 
some graph features like arc/edge or node deletion.

alpar@40

44 

alpar@209

45 
Alteration of standard containers need a very limited number of

alpar@209

46 
operations, these together satisfy the everyday requirements.

alpar@209

47 
In the case of graph structures, different operations are needed which do

alpar@209

48 
not alter the physical graph, but gives another view. If some nodes or

kpeter@83

49 
arcs have to be hidden or the reverse oriented graph have to be used, then

alpar@209

50 
this is the case. It also may happen that in a flow implementation

alpar@209

51 
the residual graph can be accessed by another algorithm, or a nodeset

alpar@209

52 
is to be shrunk for another algorithm.

alpar@209

53 
LEMON also provides a variety of graphs for these requirements called

alpar@209

54 
\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only

alpar@209

55 
in conjunction with other graph representations.

alpar@40

56 

alpar@40

57 
You are free to use the graph structure that fit your requirements

alpar@40

58 
the best, most graph algorithms and auxiliary data structures can be used

kpeter@314

59 
with any graph structure.

kpeter@314

60 

kpeter@314

61 
<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

alpar@40

62 
*/

alpar@40

63 

alpar@40

64 
/**

kpeter@474

65 
@defgroup graph_adaptors Adaptor Classes for Graphs

deba@432

66 
@ingroup graphs

kpeter@474

67 
\brief Adaptor classes for digraphs and graphs

kpeter@474

68 

kpeter@474

69 
This group contains several useful adaptor classes for digraphs and graphs.

deba@432

70 

deba@432

71 
The main parts of LEMON are the different graph structures, generic

kpeter@474

72 
graph algorithms, graph concepts, which couple them, and graph

deba@432

73 
adaptors. While the previous notions are more or less clear, the

deba@432

74 
latter one needs further explanation. Graph adaptors are graph classes

deba@432

75 
which serve for considering graph structures in different ways.

deba@432

76 

deba@432

77 
A short example makes this much clearer. Suppose that we have an

kpeter@474

78 
instance \c g of a directed graph type, say ListDigraph and an algorithm

deba@432

79 
\code

deba@432

80 
template <typename Digraph>

deba@432

81 
int algorithm(const Digraph&);

deba@432

82 
\endcode

deba@432

83 
is needed to run on the reverse oriented graph. It may be expensive

deba@432

84 
(in time or in memory usage) to copy \c g with the reversed

deba@432

85 
arcs. In this case, an adaptor class is used, which (according

kpeter@474

86 
to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.

kpeter@474

87 
The adaptor uses the original digraph structure and digraph operations when

kpeter@474

88 
methods of the reversed oriented graph are called. This means that the adaptor

kpeter@474

89 
have minor memory usage, and do not perform sophisticated algorithmic

deba@432

90 
actions. The purpose of it is to give a tool for the cases when a

deba@432

91 
graph have to be used in a specific alteration. If this alteration is

kpeter@474

92 
obtained by a usual construction like filtering the node or the arc set or

deba@432

93 
considering a new orientation, then an adaptor is worthwhile to use.

deba@432

94 
To come back to the reverse oriented graph, in this situation

deba@432

95 
\code

deba@432

96 
template<typename Digraph> class ReverseDigraph;

deba@432

97 
\endcode

deba@432

98 
template class can be used. The code looks as follows

deba@432

99 
\code

deba@432

100 
ListDigraph g;

kpeter@474

101 
ReverseDigraph<ListDigraph> rg(g);

deba@432

102 
int result = algorithm(rg);

deba@432

103 
\endcode

kpeter@474

104 
During running the algorithm, the original digraph \c g is untouched.

kpeter@474

105 
This techniques give rise to an elegant code, and based on stable

deba@432

106 
graph adaptors, complex algorithms can be implemented easily.

deba@432

107 

kpeter@474

108 
In flow, circulation and matching problems, the residual

deba@432

109 
graph is of particular importance. Combining an adaptor implementing

kpeter@474

110 
this with shortest path algorithms or minimum mean cycle algorithms,

deba@432

111 
a range of weighted and cardinality optimization algorithms can be

deba@432

112 
obtained. For other examples, the interested user is referred to the

deba@432

113 
detailed documentation of particular adaptors.

deba@432

114 

deba@432

115 
The behavior of graph adaptors can be very different. Some of them keep

deba@432

116 
capabilities of the original graph while in other cases this would be

kpeter@474

117 
meaningless. This means that the concepts that they meet depend

kpeter@474

118 
on the graph adaptor, and the wrapped graph.

kpeter@474

119 
For example, if an arc of a reversed digraph is deleted, this is carried

kpeter@474

120 
out by deleting the corresponding arc of the original digraph, thus the

kpeter@474

121 
adaptor modifies the original digraph.

kpeter@474

122 
However in case of a residual digraph, this operation has no sense.

deba@432

123 

deba@432

124 
Let us stand one more example here to simplify your work.

kpeter@474

125 
ReverseDigraph has constructor

deba@432

126 
\code

deba@432

127 
ReverseDigraph(Digraph& digraph);

deba@432

128 
\endcode

kpeter@474

129 
This means that in a situation, when a <tt>const %ListDigraph&</tt>

deba@432

130 
reference to a graph is given, then it have to be instantiated with

kpeter@474

131 
<tt>Digraph=const %ListDigraph</tt>.

deba@432

132 
\code

deba@432

133 
int algorithm1(const ListDigraph& g) {

kpeter@474

134 
ReverseDigraph<const ListDigraph> rg(g);

deba@432

135 
return algorithm2(rg);

deba@432

136 
}

deba@432

137 
\endcode

deba@432

138 
*/

deba@432

139 

deba@432

140 
/**

alpar@209

141 
@defgroup maps Maps

alpar@40

142 
@ingroup datas

kpeter@50

143 
\brief Map structures implemented in LEMON.

alpar@40

144 

kpeter@606

145 
This group contains the map structures implemented in LEMON.

kpeter@50

146 

kpeter@314

147 
LEMON provides several special purpose maps and map adaptors that e.g. combine

alpar@40

148 
new maps from existing ones.

kpeter@314

149 

kpeter@314

150 
<b>See also:</b> \ref map_concepts "Map Concepts".

alpar@40

151 
*/

alpar@40

152 

alpar@40

153 
/**

alpar@209

154 
@defgroup graph_maps Graph Maps

alpar@40

155 
@ingroup maps

kpeter@83

156 
\brief Special graphrelated maps.

alpar@40

157 

kpeter@606

158 
This group contains maps that are specifically designed to assign

kpeter@422

159 
values to the nodes and arcs/edges of graphs.

kpeter@422

160 

kpeter@422

161 
If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

kpeter@422

162 
\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".

alpar@40

163 
*/

alpar@40

164 

alpar@40

165 
/**

alpar@40

166 
\defgroup map_adaptors Map Adaptors

alpar@40

167 
\ingroup maps

alpar@40

168 
\brief Tools to create new maps from existing ones

alpar@40

169 

kpeter@606

170 
This group contains map adaptors that are used to create "implicit"

kpeter@50

171 
maps from other maps.

alpar@40

172 

kpeter@422

173 
Most of them are \ref concepts::ReadMap "readonly maps".

kpeter@83

174 
They can make arithmetic and logical operations between one or two maps

kpeter@83

175 
(negation, shifting, addition, multiplication, logical 'and', 'or',

kpeter@83

176 
'not' etc.) or e.g. convert a map to another one of different Value type.

alpar@40

177 

kpeter@50

178 
The typical usage of this classes is passing implicit maps to

alpar@40

179 
algorithms. If a function type algorithm is called then the function

alpar@40

180 
type map adaptors can be used comfortable. For example let's see the

kpeter@314

181 
usage of map adaptors with the \c graphToEps() function.

alpar@40

182 
\code

alpar@40

183 
Color nodeColor(int deg) {

alpar@40

184 
if (deg >= 2) {

alpar@40

185 
return Color(0.5, 0.0, 0.5);

alpar@40

186 
} else if (deg == 1) {

alpar@40

187 
return Color(1.0, 0.5, 1.0);

alpar@40

188 
} else {

alpar@40

189 
return Color(0.0, 0.0, 0.0);

alpar@40

190 
}

alpar@40

191 
}

alpar@209

192 

kpeter@83

193 
Digraph::NodeMap<int> degree_map(graph);

alpar@209

194 

kpeter@314

195 
graphToEps(graph, "graph.eps")

alpar@40

196 
.coords(coords).scaleToA4().undirected()

kpeter@83

197 
.nodeColors(composeMap(functorToMap(nodeColor), degree_map))

alpar@40

198 
.run();

alpar@209

199 
\endcode

kpeter@83

200 
The \c functorToMap() function makes an \c int to \c Color map from the

kpeter@314

201 
\c nodeColor() function. The \c composeMap() compose the \c degree_map

kpeter@83

202 
and the previously created map. The composed map is a proper function to

kpeter@83

203 
get the color of each node.

alpar@40

204 

alpar@40

205 
The usage with class type algorithms is little bit harder. In this

alpar@40

206 
case the function type map adaptors can not be used, because the

kpeter@50

207 
function map adaptors give back temporary objects.

alpar@40

208 
\code

kpeter@83

209 
Digraph graph;

kpeter@83

210 

kpeter@83

211 
typedef Digraph::ArcMap<double> DoubleArcMap;

kpeter@83

212 
DoubleArcMap length(graph);

kpeter@83

213 
DoubleArcMap speed(graph);

kpeter@83

214 

kpeter@83

215 
typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

alpar@40

216 
TimeMap time(length, speed);

alpar@209

217 

kpeter@83

218 
Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

alpar@40

219 
dijkstra.run(source, target);

alpar@40

220 
\endcode

kpeter@83

221 
We have a length map and a maximum speed map on the arcs of a digraph.

kpeter@83

222 
The minimum time to pass the arc can be calculated as the division of

kpeter@83

223 
the two maps which can be done implicitly with the \c DivMap template

alpar@40

224 
class. We use the implicit minimum time map as the length map of the

alpar@40

225 
\c Dijkstra algorithm.

alpar@40

226 
*/

alpar@40

227 

alpar@40

228 
/**

alpar@40

229 
@defgroup paths Path Structures

alpar@40

230 
@ingroup datas

kpeter@318

231 
\brief %Path structures implemented in LEMON.

alpar@40

232 

kpeter@606

233 
This group contains the path structures implemented in LEMON.

alpar@40

234 

kpeter@50

235 
LEMON provides flexible data structures to work with paths.

kpeter@50

236 
All of them have similar interfaces and they can be copied easily with

kpeter@50

237 
assignment operators and copy constructors. This makes it easy and

alpar@40

238 
efficient to have e.g. the Dijkstra algorithm to store its result in

alpar@40

239 
any kind of path structure.

alpar@40

240 

kpeter@757

241 
\sa \ref concepts::Path "Path concept"

kpeter@757

242 
*/

kpeter@757

243 

kpeter@757

244 
/**

kpeter@757

245 
@defgroup heaps Heap Structures

kpeter@757

246 
@ingroup datas

kpeter@757

247 
\brief %Heap structures implemented in LEMON.

kpeter@757

248 

kpeter@757

249 
This group contains the heap structures implemented in LEMON.

kpeter@757

250 

kpeter@757

251 
LEMON provides several heap classes. They are efficient implementations

kpeter@757

252 
of the abstract data type \e priority \e queue. They store items with

kpeter@757

253 
specified values called \e priorities in such a way that finding and

kpeter@757

254 
removing the item with minimum priority are efficient.

kpeter@757

255 
The basic operations are adding and erasing items, changing the priority

kpeter@757

256 
of an item, etc.

kpeter@757

257 

kpeter@757

258 
Heaps are crucial in several algorithms, such as Dijkstra and Prim.

kpeter@757

259 
The heap implementations have the same interface, thus any of them can be

kpeter@757

260 
used easily in such algorithms.

kpeter@757

261 

kpeter@757

262 
\sa \ref concepts::Heap "Heap concept"

kpeter@757

263 
*/

kpeter@757

264 

kpeter@757

265 
/**

alpar@40

266 
@defgroup auxdat Auxiliary Data Structures

alpar@40

267 
@ingroup datas

kpeter@50

268 
\brief Auxiliary data structures implemented in LEMON.

alpar@40

269 

kpeter@606

270 
This group contains some data structures implemented in LEMON in

alpar@40

271 
order to make it easier to implement combinatorial algorithms.

alpar@40

272 
*/

alpar@40

273 

alpar@40

274 
/**

kpeter@761

275 
@defgroup geomdat Geometric Data Structures

kpeter@761

276 
@ingroup auxdat

kpeter@761

277 
\brief Geometric data structures implemented in LEMON.

kpeter@761

278 

kpeter@761

279 
This group contains geometric data structures implemented in LEMON.

kpeter@761

280 

kpeter@761

281 
 \ref lemon::dim2::Point "dim2::Point" implements a two dimensional

kpeter@761

282 
vector with the usual operations.

kpeter@761

283 
 \ref lemon::dim2::Box "dim2::Box" can be used to determine the

kpeter@761

284 
rectangular bounding box of a set of \ref lemon::dim2::Point

kpeter@761

285 
"dim2::Point"'s.

kpeter@761

286 
*/

kpeter@761

287 

kpeter@761

288 
/**

kpeter@761

289 
@defgroup matrices Matrices

kpeter@761

290 
@ingroup auxdat

kpeter@761

291 
\brief Two dimensional data storages implemented in LEMON.

kpeter@761

292 

kpeter@761

293 
This group contains two dimensional data storages implemented in LEMON.

kpeter@761

294 
*/

kpeter@761

295 

kpeter@761

296 
/**

alpar@40

297 
@defgroup algs Algorithms

kpeter@606

298 
\brief This group contains the several algorithms

alpar@40

299 
implemented in LEMON.

alpar@40

300 

kpeter@606

301 
This group contains the several algorithms

alpar@40

302 
implemented in LEMON.

alpar@40

303 
*/

alpar@40

304 

alpar@40

305 
/**

alpar@40

306 
@defgroup search Graph Search

alpar@40

307 
@ingroup algs

kpeter@50

308 
\brief Common graph search algorithms.

alpar@40

309 

kpeter@606

310 
This group contains the common graph search algorithms, namely

kpeter@802

311 
\e breadthfirst \e search (BFS) and \e depthfirst \e search (DFS)

kpeter@802

312 
\ref clrs01algorithms.

alpar@40

313 
*/

alpar@40

314 

alpar@40

315 
/**

kpeter@314

316 
@defgroup shortest_path Shortest Path Algorithms

alpar@40

317 
@ingroup algs

kpeter@50

318 
\brief Algorithms for finding shortest paths.

alpar@40

319 

kpeter@802

320 
This group contains the algorithms for finding shortest paths in digraphs

kpeter@802

321 
\ref clrs01algorithms.

kpeter@422

322 

kpeter@422

323 
 \ref Dijkstra algorithm for finding shortest paths from a source node

kpeter@422

324 
when all arc lengths are nonnegative.

kpeter@422

325 
 \ref BellmanFord "BellmanFord" algorithm for finding shortest paths

kpeter@422

326 
from a source node when arc lenghts can be either positive or negative,

kpeter@422

327 
but the digraph should not contain directed cycles with negative total

kpeter@422

328 
length.

kpeter@422

329 
 \ref FloydWarshall "FloydWarshall" and \ref Johnson "Johnson" algorithms

kpeter@422

330 
for solving the \e allpairs \e shortest \e paths \e problem when arc

kpeter@422

331 
lenghts can be either positive or negative, but the digraph should

kpeter@422

332 
not contain directed cycles with negative total length.

kpeter@422

333 
 \ref Suurballe A successive shortest path algorithm for finding

kpeter@422

334 
arcdisjoint paths between two nodes having minimum total length.

alpar@40

335 
*/

alpar@40

336 

alpar@209

337 
/**

kpeter@761

338 
@defgroup spantree Minimum Spanning Tree Algorithms

kpeter@761

339 
@ingroup algs

kpeter@761

340 
\brief Algorithms for finding minimum cost spanning trees and arborescences.

kpeter@761

341 

kpeter@761

342 
This group contains the algorithms for finding minimum cost spanning

kpeter@802

343 
trees and arborescences \ref clrs01algorithms.

kpeter@761

344 
*/

kpeter@761

345 

kpeter@761

346 
/**

kpeter@314

347 
@defgroup max_flow Maximum Flow Algorithms

alpar@209

348 
@ingroup algs

kpeter@50

349 
\brief Algorithms for finding maximum flows.

alpar@40

350 

kpeter@606

351 
This group contains the algorithms for finding maximum flows and

kpeter@802

352 
feasible circulations \ref clrs01algorithms, \ref amo93networkflows.

alpar@40

353 

kpeter@422

354 
The \e maximum \e flow \e problem is to find a flow of maximum value between

kpeter@422

355 
a single source and a single target. Formally, there is a \f$G=(V,A)\f$

kpeter@656

356 
digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

kpeter@422

357 
\f$s, t \in V\f$ source and target nodes.

kpeter@656

358 
A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

kpeter@422

359 
following optimization problem.

alpar@40

360 

kpeter@656

361 
\f[ \max\sum_{sv\in A} f(sv)  \sum_{vs\in A} f(vs) \f]

kpeter@656

362 
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

kpeter@656

363 
\quad \forall u\in V\setminus\{s,t\} \f]

kpeter@656

364 
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

alpar@40

365 

kpeter@50

366 
LEMON contains several algorithms for solving maximum flow problems:

kpeter@802

367 
 \ref EdmondsKarp EdmondsKarp algorithm

kpeter@802

368 
\ref edmondskarp72theoretical.

kpeter@802

369 
 \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm

kpeter@802

370 
\ref goldberg88newapproach.

kpeter@802

371 
 \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees

kpeter@802

372 
\ref dinic70algorithm, \ref sleator83dynamic.

kpeter@802

373 
 \ref GoldbergTarjan !Preflow pushrelabel algorithm with dynamic trees

kpeter@802

374 
\ref goldberg88newapproach, \ref sleator83dynamic.

alpar@40

375 

kpeter@802

376 
In most cases the \ref Preflow algorithm provides the

kpeter@422

377 
fastest method for computing a maximum flow. All implementations

kpeter@698

378 
also provide functions to query the minimum cut, which is the dual

kpeter@698

379 
problem of maximum flow.

kpeter@698

380 

deba@948

381 
\ref Circulation is a preflow pushrelabel algorithm implemented directly

kpeter@698

382 
for finding feasible circulations, which is a somewhat different problem,

kpeter@698

383 
but it is strongly related to maximum flow.

kpeter@698

384 
For more information, see \ref Circulation.

alpar@40

385 
*/

alpar@40

386 

alpar@40

387 
/**

kpeter@710

388 
@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms

alpar@40

389 
@ingroup algs

alpar@40

390 

kpeter@50

391 
\brief Algorithms for finding minimum cost flows and circulations.

alpar@40

392 

kpeter@656

393 
This group contains the algorithms for finding minimum cost flows and

kpeter@802

394 
circulations \ref amo93networkflows. For more information about this

kpeter@802

395 
problem and its dual solution, see \ref min_cost_flow

kpeter@802

396 
"Minimum Cost Flow Problem".

kpeter@422

397 

kpeter@710

398 
LEMON contains several algorithms for this problem.

kpeter@656

399 
 \ref NetworkSimplex Primal Network Simplex algorithm with various

kpeter@802

400 
pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.

kpeter@879

401 
 \ref CostScaling Cost Scaling algorithm based on push/augment and

kpeter@879

402 
relabel operations \ref goldberg90approximation, \ref goldberg97efficient,

kpeter@802

403 
\ref bunnagel98efficient.

kpeter@879

404 
 \ref CapacityScaling Capacity Scaling algorithm based on the successive

kpeter@879

405 
shortest path method \ref edmondskarp72theoretical.

kpeter@879

406 
 \ref CycleCanceling CycleCanceling algorithms, two of which are

kpeter@879

407 
strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.

kpeter@656

408 

kpeter@1023

409 
In general, \ref NetworkSimplex and \ref CostScaling are the most efficient

kpeter@1165

410 
implementations.

kpeter@1165

411 
\ref NetworkSimplex is usually the fastest on relatively small graphs (up to

kpeter@1165

412 
several thousands of nodes) and on dense graphs, while \ref CostScaling is

kpeter@1165

413 
typically more efficient on large graphs (e.g. hundreds of thousands of

kpeter@1165

414 
nodes or above), especially if they are sparse.

kpeter@1165

415 
However, other algorithms could be faster in special cases.

kpeter@656

416 
For example, if the total supply and/or capacities are rather small,

kpeter@1023

417 
\ref CapacityScaling is usually the fastest algorithm (without effective scaling).

kpeter@1164

418 

kpeter@1164

419 
These classes are intended to be used with integervalued input data

kpeter@1164

420 
(capacities, supply values, and costs), except for \ref CapacityScaling,

kpeter@1164

421 
which is capable of handling realvalued arc costs (other numerical

kpeter@1164

422 
data are required to be integer).

alpar@40

423 
*/

alpar@40

424 

alpar@40

425 
/**

kpeter@314

426 
@defgroup min_cut Minimum Cut Algorithms

alpar@209

427 
@ingroup algs

alpar@40

428 

kpeter@50

429 
\brief Algorithms for finding minimum cut in graphs.

alpar@40

430 

kpeter@606

431 
This group contains the algorithms for finding minimum cut in graphs.

alpar@40

432 

kpeter@422

433 
The \e minimum \e cut \e problem is to find a nonempty and noncomplete

kpeter@422

434 
\f$X\f$ subset of the nodes with minimum overall capacity on

kpeter@422

435 
outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

kpeter@422

436 
\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

kpeter@50

437 
cut is the \f$X\f$ solution of the next optimization problem:

alpar@40

438 

alpar@210

439 
\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

kpeter@760

440 
\sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]

alpar@40

441 

kpeter@50

442 
LEMON contains several algorithms related to minimum cut problems:

alpar@40

443 

kpeter@422

444 
 \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut

kpeter@422

445 
in directed graphs.

kpeter@422

446 
 \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for

kpeter@422

447 
calculating minimum cut in undirected graphs.

kpeter@606

448 
 \ref GomoryHu "GomoryHu tree computation" for calculating

kpeter@422

449 
allpairs minimum cut in undirected graphs.

alpar@40

450 

alpar@40

451 
If you want to find minimum cut just between two distinict nodes,

kpeter@422

452 
see the \ref max_flow "maximum flow problem".

alpar@40

453 
*/

alpar@40

454 

alpar@40

455 
/**

kpeter@815

456 
@defgroup min_mean_cycle Minimum Mean Cycle Algorithms

alpar@40

457 
@ingroup algs

kpeter@815

458 
\brief Algorithms for finding minimum mean cycles.

alpar@40

459 

kpeter@818

460 
This group contains the algorithms for finding minimum mean cycles

kpeter@1164

461 
\ref amo93networkflows, \ref karp78characterization.

alpar@40

462 

kpeter@815

463 
The \e minimum \e mean \e cycle \e problem is to find a directed cycle

kpeter@815

464 
of minimum mean length (cost) in a digraph.

kpeter@815

465 
The mean length of a cycle is the average length of its arcs, i.e. the

kpeter@815

466 
ratio between the total length of the cycle and the number of arcs on it.

alpar@40

467 

kpeter@815

468 
This problem has an important connection to \e conservative \e length

kpeter@815

469 
\e functions, too. A length function on the arcs of a digraph is called

kpeter@815

470 
conservative if and only if there is no directed cycle of negative total

kpeter@815

471 
length. For an arbitrary length function, the negative of the minimum

kpeter@815

472 
cycle mean is the smallest \f$\epsilon\f$ value so that increasing the

kpeter@815

473 
arc lengths uniformly by \f$\epsilon\f$ results in a conservative length

kpeter@815

474 
function.

alpar@40

475 

kpeter@815

476 
LEMON contains three algorithms for solving the minimum mean cycle problem:

kpeter@1164

477 
 \ref KarpMmc Karp's original algorithm \ref karp78characterization.

kpeter@959

478 
 \ref HartmannOrlinMmc HartmannOrlin's algorithm, which is an improved

kpeter@1164

479 
version of Karp's algorithm \ref hartmann93finding.

kpeter@959

480 
 \ref HowardMmc Howard's policy iteration algorithm

kpeter@1164

481 
\ref dasdan98minmeancycle, \ref dasdan04experimental.

alpar@40

482 

kpeter@1023

483 
In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the

kpeter@959

484 
most efficient one, though the best known theoretical bound on its running

kpeter@959

485 
time is exponential.

kpeter@959

486 
Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "HartmannOrlin" algorithms

kpeter@959

487 
run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is

kpeter@959

488 
typically faster due to the applied early termination scheme.

alpar@40

489 
*/

alpar@40

490 

alpar@40

491 
/**

kpeter@314

492 
@defgroup matching Matching Algorithms

alpar@40

493 
@ingroup algs

kpeter@50

494 
\brief Algorithms for finding matchings in graphs and bipartite graphs.

alpar@40

495 

kpeter@637

496 
This group contains the algorithms for calculating

alpar@40

497 
matchings in graphs and bipartite graphs. The general matching problem is

kpeter@637

498 
finding a subset of the edges for which each node has at most one incident

kpeter@637

499 
edge.

alpar@209

500 

alpar@40

501 
There are several different algorithms for calculate matchings in

alpar@40

502 
graphs. The matching problems in bipartite graphs are generally

alpar@40

503 
easier than in general graphs. The goal of the matching optimization

kpeter@422

504 
can be finding maximum cardinality, maximum weight or minimum cost

alpar@40

505 
matching. The search can be constrained to find perfect or

alpar@40

506 
maximum cardinality matching.

alpar@40

507 

kpeter@422

508 
The matching algorithms implemented in LEMON:

kpeter@422

509 
 \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm

kpeter@422

510 
for calculating maximum cardinality matching in bipartite graphs.

kpeter@422

511 
 \ref PrBipartiteMatching Pushrelabel algorithm

kpeter@422

512 
for calculating maximum cardinality matching in bipartite graphs.

kpeter@422

513 
 \ref MaxWeightedBipartiteMatching

kpeter@422

514 
Successive shortest path algorithm for calculating maximum weighted

kpeter@422

515 
matching and maximum weighted bipartite matching in bipartite graphs.

kpeter@422

516 
 \ref MinCostMaxBipartiteMatching

kpeter@422

517 
Successive shortest path algorithm for calculating minimum cost maximum

kpeter@422

518 
matching in bipartite graphs.

kpeter@422

519 
 \ref MaxMatching Edmond's blossom shrinking algorithm for calculating

kpeter@422

520 
maximum cardinality matching in general graphs.

kpeter@422

521 
 \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating

kpeter@422

522 
maximum weighted matching in general graphs.

kpeter@422

523 
 \ref MaxWeightedPerfectMatching

kpeter@422

524 
Edmond's blossom shrinking algorithm for calculating maximum weighted

kpeter@422

525 
perfect matching in general graphs.

deba@948

526 
 \ref MaxFractionalMatching Pushrelabel algorithm for calculating

deba@948

527 
maximum cardinality fractional matching in general graphs.

deba@948

528 
 \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating

deba@948

529 
maximum weighted fractional matching in general graphs.

deba@948

530 
 \ref MaxWeightedPerfectFractionalMatching

deba@948

531 
Augmenting path algorithm for calculating maximum weighted

deba@948

532 
perfect fractional matching in general graphs.

alpar@40

533 

alpar@943

534 
\image html matching.png

alpar@952

535 
\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth

alpar@40

536 
*/

alpar@40

537 

alpar@40

538 
/**

kpeter@761

539 
@defgroup graph_properties Connectivity and Other Graph Properties

alpar@40

540 
@ingroup algs

kpeter@761

541 
\brief Algorithms for discovering the graph properties

alpar@40

542 

kpeter@761

543 
This group contains the algorithms for discovering the graph properties

kpeter@761

544 
like connectivity, bipartiteness, euler property, simplicity etc.

kpeter@761

545 

kpeter@761

546 
\image html connected_components.png

kpeter@761

547 
\image latex connected_components.eps "Connected components" width=\textwidth

kpeter@761

548 
*/

kpeter@761

549 

kpeter@761

550 
/**

kpeter@1023

551 
@defgroup planar Planar Embedding and Drawing

kpeter@761

552 
@ingroup algs

kpeter@761

553 
\brief Algorithms for planarity checking, embedding and drawing

kpeter@761

554 

kpeter@761

555 
This group contains the algorithms for planarity checking,

kpeter@761

556 
embedding and drawing.

kpeter@761

557 

kpeter@761

558 
\image html planar.png

kpeter@761

559 
\image latex planar.eps "Plane graph" width=\textwidth

kpeter@761

560 
*/

kpeter@1200

561 

kpeter@1200

562 
/**

kpeter@1200

563 
@defgroup tsp Traveling Salesman Problem

kpeter@1200

564 
@ingroup algs

kpeter@1200

565 
\brief Algorithms for the symmetric traveling salesman problem

kpeter@1200

566 

kpeter@1200

567 
This group contains basic heuristic algorithms for the the symmetric

kpeter@1200

568 
\e traveling \e salesman \e problem (TSP).

kpeter@1200

569 
Given an \ref FullGraph "undirected full graph" with a cost map on its edges,

kpeter@1200

570 
the problem is to find a shortest possible tour that visits each node exactly

kpeter@1200

571 
once (i.e. the minimum cost Hamiltonian cycle).

kpeter@1200

572 

kpeter@1202

573 
These TSP algorithms are intended to be used with a \e metric \e cost

kpeter@1202

574 
\e function, i.e. the edge costs should satisfy the triangle inequality.

kpeter@1202

575 
Otherwise the algorithms could yield worse results.

kpeter@1200

576 

kpeter@1200

577 
LEMON provides five wellknown heuristics for solving symmetric TSP:

kpeter@1200

578 
 \ref NearestNeighborTsp Neareast neighbor algorithm

kpeter@1200

579 
 \ref GreedyTsp Greedy algorithm

kpeter@1200

580 
 \ref InsertionTsp Insertion heuristic (with four selection methods)

kpeter@1200

581 
 \ref ChristofidesTsp Christofides algorithm

kpeter@1200

582 
 \ref Opt2Tsp 2opt algorithm

kpeter@1200

583 

kpeter@1204

584 
\ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest

kpeter@1204

585 
solution methods. Furthermore, \ref InsertionTsp is usually quite effective.

kpeter@1204

586 

kpeter@1204

587 
\ref ChristofidesTsp is somewhat slower, but it has the best guaranteed

kpeter@1204

588 
approximation factor: 3/2.

kpeter@1204

589 

kpeter@1204

590 
\ref Opt2Tsp usually provides the best results in practice, but

kpeter@1204

591 
it is the slowest method. It can also be used to improve given tours,

kpeter@1204

592 
for example, the results of other algorithms.

kpeter@1204

593 

kpeter@1200

594 
\image html tsp.png

kpeter@1200

595 
\image latex tsp.eps "Traveling salesman problem" width=\textwidth

kpeter@1200

596 
*/

kpeter@761

597 

kpeter@761

598 
/**

kpeter@999

599 
@defgroup approx_algs Approximation Algorithms

kpeter@761

600 
@ingroup algs

kpeter@761

601 
\brief Approximation algorithms.

kpeter@761

602 

kpeter@761

603 
This group contains the approximation and heuristic algorithms

kpeter@761

604 
implemented in LEMON.

kpeter@999

605 

kpeter@999

606 
<b>Maximum Clique Problem</b>

kpeter@999

607 
 \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of

kpeter@999

608 
Grosso, Locatelli, and Pullan.

alpar@40

609 
*/

alpar@40

610 

alpar@40

611 
/**

kpeter@314

612 
@defgroup auxalg Auxiliary Algorithms

alpar@40

613 
@ingroup algs

kpeter@50

614 
\brief Auxiliary algorithms implemented in LEMON.

alpar@40

615 

kpeter@606

616 
This group contains some algorithms implemented in LEMON

kpeter@50

617 
in order to make it easier to implement complex algorithms.

alpar@40

618 
*/

alpar@40

619 

alpar@40

620 
/**

alpar@40

621 
@defgroup gen_opt_group General Optimization Tools

kpeter@606

622 
\brief This group contains some general optimization frameworks

alpar@40

623 
implemented in LEMON.

alpar@40

624 

kpeter@606

625 
This group contains some general optimization frameworks

alpar@40

626 
implemented in LEMON.

alpar@40

627 
*/

alpar@40

628 

alpar@40

629 
/**

kpeter@802

630 
@defgroup lp_group LP and MIP Solvers

alpar@40

631 
@ingroup gen_opt_group

kpeter@802

632 
\brief LP and MIP solver interfaces for LEMON.

alpar@40

633 

kpeter@802

634 
This group contains LP and MIP solver interfaces for LEMON.

kpeter@802

635 
Various LP solvers could be used in the same manner with this

kpeter@802

636 
highlevel interface.

kpeter@802

637 

kpeter@802

638 
The currently supported solvers are \ref glpk, \ref clp, \ref cbc,

kpeter@802

639 
\ref cplex, \ref soplex.

alpar@40

640 
*/

alpar@40

641 

alpar@209

642 
/**

kpeter@314

643 
@defgroup lp_utils Tools for Lp and Mip Solvers

alpar@40

644 
@ingroup lp_group

kpeter@50

645 
\brief Helper tools to the Lp and Mip solvers.

alpar@40

646 

alpar@40

647 
This group adds some helper tools to general optimization framework

alpar@40

648 
implemented in LEMON.

alpar@40

649 
*/

alpar@40

650 

alpar@40

651 
/**

alpar@40

652 
@defgroup metah Metaheuristics

alpar@40

653 
@ingroup gen_opt_group

alpar@40

654 
\brief Metaheuristics for LEMON library.

alpar@40

655 

kpeter@606

656 
This group contains some metaheuristic optimization tools.

alpar@40

657 
*/

alpar@40

658 

alpar@40

659 
/**

alpar@209

660 
@defgroup utils Tools and Utilities

kpeter@50

661 
\brief Tools and utilities for programming in LEMON

alpar@40

662 

kpeter@50

663 
Tools and utilities for programming in LEMON.

alpar@40

664 
*/

alpar@40

665 

alpar@40

666 
/**

alpar@40

667 
@defgroup gutils Basic Graph Utilities

alpar@40

668 
@ingroup utils

kpeter@50

669 
\brief Simple basic graph utilities.

alpar@40

670 

kpeter@606

671 
This group contains some simple basic graph utilities.

alpar@40

672 
*/

alpar@40

673 

alpar@40

674 
/**

alpar@40

675 
@defgroup misc Miscellaneous Tools

alpar@40

676 
@ingroup utils

kpeter@50

677 
\brief Tools for development, debugging and testing.

kpeter@50

678 

kpeter@606

679 
This group contains several useful tools for development,

alpar@40

680 
debugging and testing.

alpar@40

681 
*/

alpar@40

682 

alpar@40

683 
/**

kpeter@314

684 
@defgroup timecount Time Measuring and Counting

alpar@40

685 
@ingroup misc

kpeter@50

686 
\brief Simple tools for measuring the performance of algorithms.

kpeter@50

687 

kpeter@606

688 
This group contains simple tools for measuring the performance

alpar@40

689 
of algorithms.

alpar@40

690 
*/

alpar@40

691 

alpar@40

692 
/**

alpar@40

693 
@defgroup exceptions Exceptions

alpar@40

694 
@ingroup utils

kpeter@50

695 
\brief Exceptions defined in LEMON.

kpeter@50

696 

kpeter@606

697 
This group contains the exceptions defined in LEMON.

alpar@40

698 
*/

alpar@40

699 

alpar@40

700 
/**

alpar@40

701 
@defgroup io_group InputOutput

kpeter@50

702 
\brief Graph InputOutput methods

alpar@40

703 

kpeter@606

704 
This group contains the tools for importing and exporting graphs

kpeter@314

705 
and graph related data. Now it supports the \ref lgfformat

kpeter@314

706 
"LEMON Graph Format", the \c DIMACS format and the encapsulated

kpeter@314

707 
postscript (EPS) format.

alpar@40

708 
*/

alpar@40

709 

alpar@40

710 
/**

kpeter@363

711 
@defgroup lemon_io LEMON Graph Format

alpar@40

712 
@ingroup io_group

kpeter@314

713 
\brief Reading and writing LEMON Graph Format.

alpar@40

714 

kpeter@606

715 
This group contains methods for reading and writing

ladanyi@236

716 
\ref lgfformat "LEMON Graph Format".

alpar@40

717 
*/

alpar@40

718 

alpar@40

719 
/**

kpeter@314

720 
@defgroup eps_io Postscript Exporting

alpar@40

721 
@ingroup io_group

alpar@40

722 
\brief General \c EPS drawer and graph exporter

alpar@40

723 

kpeter@606

724 
This group contains general \c EPS drawing methods and special

alpar@209

725 
graph exporting tools.

alpar@40

726 
*/

alpar@40

727 

alpar@40

728 
/**

kpeter@761

729 
@defgroup dimacs_group DIMACS Format

kpeter@403

730 
@ingroup io_group

kpeter@403

731 
\brief Read and write files in DIMACS format

kpeter@403

732 

kpeter@403

733 
Tools to read a digraph from or write it to a file in DIMACS format data.

kpeter@403

734 
*/

kpeter@403

735 

kpeter@403

736 
/**

kpeter@363

737 
@defgroup nauty_group NAUTY Format

kpeter@363

738 
@ingroup io_group

kpeter@363

739 
\brief Read \e Nauty format

kpeter@403

740 

kpeter@363

741 
Tool to read graphs from \e Nauty format data.

kpeter@363

742 
*/

kpeter@363

743 

kpeter@363

744 
/**

alpar@40

745 
@defgroup concept Concepts

alpar@40

746 
\brief Skeleton classes and concept checking classes

alpar@40

747 

kpeter@606

748 
This group contains the data/algorithm skeletons and concept checking

alpar@40

749 
classes implemented in LEMON.

alpar@40

750 

alpar@40

751 
The purpose of the classes in this group is fourfold.

alpar@209

752 

kpeter@318

753 
 These classes contain the documentations of the %concepts. In order

alpar@40

754 
to avoid document multiplications, an implementation of a concept

alpar@40

755 
simply refers to the corresponding concept class.

alpar@40

756 

alpar@40

757 
 These classes declare every functions, <tt>typedef</tt>s etc. an

kpeter@318

758 
implementation of the %concepts should provide, however completely

alpar@40

759 
without implementations and real data structures behind the

alpar@40

760 
interface. On the other hand they should provide nothing else. All

alpar@40

761 
the algorithms working on a data structure meeting a certain concept

alpar@40

762 
should compile with these classes. (Though it will not run properly,

alpar@40

763 
of course.) In this way it is easily to check if an algorithm

alpar@40

764 
doesn't use any extra feature of a certain implementation.

alpar@40

765 

alpar@40

766 
 The concept descriptor classes also provide a <em>checker class</em>

kpeter@50

767 
that makes it possible to check whether a certain implementation of a

alpar@40

768 
concept indeed provides all the required features.

alpar@40

769 

alpar@40

770 
 Finally, They can serve as a skeleton of a new implementation of a concept.

alpar@40

771 
*/

alpar@40

772 

alpar@40

773 
/**

alpar@40

774 
@defgroup graph_concepts Graph Structure Concepts

alpar@40

775 
@ingroup concept

alpar@40

776 
\brief Skeleton and concept checking classes for graph structures

alpar@40

777 

kpeter@782

778 
This group contains the skeletons and concept checking classes of

kpeter@782

779 
graph structures.

alpar@40

780 
*/

alpar@40

781 

kpeter@314

782 
/**

kpeter@314

783 
@defgroup map_concepts Map Concepts

kpeter@314

784 
@ingroup concept

kpeter@314

785 
\brief Skeleton and concept checking classes for maps

kpeter@314

786 

kpeter@606

787 
This group contains the skeletons and concept checking classes of maps.

alpar@40

788 
*/

alpar@40

789 

alpar@40

790 
/**

kpeter@761

791 
@defgroup tools Standalone Utility Applications

kpeter@761

792 

kpeter@761

793 
Some utility applications are listed here.

kpeter@761

794 

kpeter@761

795 
The standard compilation procedure (<tt>./configure;make</tt>) will compile

kpeter@761

796 
them, as well.

kpeter@761

797 
*/

kpeter@761

798 

kpeter@761

799 
/**

alpar@40

800 
\anchor demoprograms

alpar@40

801 

kpeter@422

802 
@defgroup demos Demo Programs

alpar@40

803 

alpar@40

804 
Some demo programs are listed here. Their full source codes can be found in

alpar@40

805 
the \c demo subdirectory of the source tree.

alpar@40

806 

ladanyi@611

807 
In order to compile them, use the <tt>make demo</tt> or the

ladanyi@611

808 
<tt>make check</tt> commands.

alpar@40

809 
*/

alpar@40

810 

kpeter@422

811 
}
