... |
... |
@@ -290,98 +290,103 @@
|
290 |
290 |
@defgroup shortest_path Shortest Path Algorithms
|
291 |
291 |
@ingroup algs
|
292 |
292 |
\brief Algorithms for finding shortest paths.
|
293 |
293 |
|
294 |
294 |
This group contains the algorithms for finding shortest paths in digraphs.
|
295 |
295 |
|
296 |
296 |
- \ref Dijkstra algorithm for finding shortest paths from a source node
|
297 |
297 |
when all arc lengths are non-negative.
|
298 |
298 |
- \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
|
299 |
299 |
from a source node when arc lenghts can be either positive or negative,
|
300 |
300 |
but the digraph should not contain directed cycles with negative total
|
301 |
301 |
length.
|
302 |
302 |
- \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
|
303 |
303 |
for solving the \e all-pairs \e shortest \e paths \e problem when arc
|
304 |
304 |
lenghts can be either positive or negative, but the digraph should
|
305 |
305 |
not contain directed cycles with negative total length.
|
306 |
306 |
- \ref Suurballe A successive shortest path algorithm for finding
|
307 |
307 |
arc-disjoint paths between two nodes having minimum total length.
|
308 |
308 |
*/
|
309 |
309 |
|
310 |
310 |
/**
|
311 |
311 |
@defgroup max_flow Maximum Flow Algorithms
|
312 |
312 |
@ingroup algs
|
313 |
313 |
\brief Algorithms for finding maximum flows.
|
314 |
314 |
|
315 |
315 |
This group contains the algorithms for finding maximum flows and
|
316 |
316 |
feasible circulations.
|
317 |
317 |
|
318 |
318 |
The \e maximum \e flow \e problem is to find a flow of maximum value between
|
319 |
319 |
a single source and a single target. Formally, there is a \f$G=(V,A)\f$
|
320 |
320 |
digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
|
321 |
321 |
\f$s, t \in V\f$ source and target nodes.
|
322 |
322 |
A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
|
323 |
323 |
following optimization problem.
|
324 |
324 |
|
325 |
325 |
\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
|
326 |
326 |
\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
|
327 |
327 |
\quad \forall u\in V\setminus\{s,t\} \f]
|
328 |
328 |
\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
|
329 |
329 |
|
330 |
330 |
LEMON contains several algorithms for solving maximum flow problems:
|
331 |
331 |
- \ref EdmondsKarp Edmonds-Karp algorithm.
|
332 |
332 |
- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
|
333 |
333 |
- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
|
334 |
334 |
- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
|
335 |
335 |
|
336 |
336 |
In most cases the \ref Preflow "Preflow" algorithm provides the
|
337 |
337 |
fastest method for computing a maximum flow. All implementations
|
338 |
|
provides functions to also query the minimum cut, which is the dual
|
339 |
|
problem of the maximum flow.
|
|
338 |
also provide functions to query the minimum cut, which is the dual
|
|
339 |
problem of maximum flow.
|
|
340 |
|
|
341 |
\ref Circulation is a preflow push-relabel algorithm implemented directly
|
|
342 |
for finding feasible circulations, which is a somewhat different problem,
|
|
343 |
but it is strongly related to maximum flow.
|
|
344 |
For more information, see \ref Circulation.
|
340 |
345 |
*/
|
341 |
346 |
|
342 |
347 |
/**
|
343 |
348 |
@defgroup min_cost_flow Minimum Cost Flow Algorithms
|
344 |
349 |
@ingroup algs
|
345 |
350 |
|
346 |
351 |
\brief Algorithms for finding minimum cost flows and circulations.
|
347 |
352 |
|
348 |
353 |
This group contains the algorithms for finding minimum cost flows and
|
349 |
354 |
circulations.
|
350 |
355 |
|
351 |
356 |
The \e minimum \e cost \e flow \e problem is to find a feasible flow of
|
352 |
357 |
minimum total cost from a set of supply nodes to a set of demand nodes
|
353 |
358 |
in a network with capacity constraints (lower and upper bounds)
|
354 |
359 |
and arc costs.
|
355 |
360 |
Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
|
356 |
361 |
\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
|
357 |
362 |
upper bounds for the flow values on the arcs, for which
|
358 |
363 |
\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
|
359 |
364 |
\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
|
360 |
365 |
on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
|
361 |
366 |
signed supply values of the nodes.
|
362 |
367 |
If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
|
363 |
368 |
supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
|
364 |
369 |
\f$-sup(u)\f$ demand.
|
365 |
370 |
A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
|
366 |
371 |
of the following optimization problem.
|
367 |
372 |
|
368 |
373 |
\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
|
369 |
374 |
\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
|
370 |
375 |
sup(u) \quad \forall u\in V \f]
|
371 |
376 |
\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
|
372 |
377 |
|
373 |
378 |
The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
|
374 |
379 |
zero or negative in order to have a feasible solution (since the sum
|
375 |
380 |
of the expressions on the left-hand side of the inequalities is zero).
|
376 |
381 |
It means that the total demand must be greater or equal to the total
|
377 |
382 |
supply and all the supplies have to be carried out from the supply nodes,
|
378 |
383 |
but there could be demands that are not satisfied.
|
379 |
384 |
If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
|
380 |
385 |
constraints have to be satisfied with equality, i.e. all demands
|
381 |
386 |
have to be satisfied and all supplies have to be used.
|
382 |
387 |
|
383 |
388 |
If you need the opposite inequalities in the supply/demand constraints
|
384 |
389 |
(i.e. the total demand is less than the total supply and all the demands
|
385 |
390 |
have to be satisfied while there could be supplies that are not used),
|
386 |
391 |
then you could easily transform the problem to the above form by reversing
|
387 |
392 |
the direction of the arcs and taking the negative of the supply values
|
... |
... |
@@ -496,100 +501,100 @@
|
496 |
501 |
|
497 |
502 |
\image html planar.png
|
498 |
503 |
\image latex planar.eps "Plane graph" width=\textwidth
|
499 |
504 |
*/
|
500 |
505 |
|
501 |
506 |
/**
|
502 |
507 |
@defgroup matching Matching Algorithms
|
503 |
508 |
@ingroup algs
|
504 |
509 |
\brief Algorithms for finding matchings in graphs and bipartite graphs.
|
505 |
510 |
|
506 |
511 |
This group contains the algorithms for calculating
|
507 |
512 |
matchings in graphs and bipartite graphs. The general matching problem is
|
508 |
513 |
finding a subset of the edges for which each node has at most one incident
|
509 |
514 |
edge.
|
510 |
515 |
|
511 |
516 |
There are several different algorithms for calculate matchings in
|
512 |
517 |
graphs. The matching problems in bipartite graphs are generally
|
513 |
518 |
easier than in general graphs. The goal of the matching optimization
|
514 |
519 |
can be finding maximum cardinality, maximum weight or minimum cost
|
515 |
520 |
matching. The search can be constrained to find perfect or
|
516 |
521 |
maximum cardinality matching.
|
517 |
522 |
|
518 |
523 |
The matching algorithms implemented in LEMON:
|
519 |
524 |
- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
|
520 |
525 |
for calculating maximum cardinality matching in bipartite graphs.
|
521 |
526 |
- \ref PrBipartiteMatching Push-relabel algorithm
|
522 |
527 |
for calculating maximum cardinality matching in bipartite graphs.
|
523 |
528 |
- \ref MaxWeightedBipartiteMatching
|
524 |
529 |
Successive shortest path algorithm for calculating maximum weighted
|
525 |
530 |
matching and maximum weighted bipartite matching in bipartite graphs.
|
526 |
531 |
- \ref MinCostMaxBipartiteMatching
|
527 |
532 |
Successive shortest path algorithm for calculating minimum cost maximum
|
528 |
533 |
matching in bipartite graphs.
|
529 |
534 |
- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
|
530 |
535 |
maximum cardinality matching in general graphs.
|
531 |
536 |
- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
|
532 |
537 |
maximum weighted matching in general graphs.
|
533 |
538 |
- \ref MaxWeightedPerfectMatching
|
534 |
539 |
Edmond's blossom shrinking algorithm for calculating maximum weighted
|
535 |
540 |
perfect matching in general graphs.
|
536 |
541 |
|
537 |
542 |
\image html bipartite_matching.png
|
538 |
543 |
\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
|
539 |
544 |
*/
|
540 |
545 |
|
541 |
546 |
/**
|
542 |
547 |
@defgroup spantree Minimum Spanning Tree Algorithms
|
543 |
548 |
@ingroup algs
|
544 |
|
\brief Algorithms for finding a minimum cost spanning tree in a graph.
|
|
549 |
\brief Algorithms for finding minimum cost spanning trees and arborescences.
|
545 |
550 |
|
546 |
|
This group contains the algorithms for finding a minimum cost spanning
|
547 |
|
tree in a graph.
|
|
551 |
This group contains the algorithms for finding minimum cost spanning
|
|
552 |
trees and arborescences.
|
548 |
553 |
*/
|
549 |
554 |
|
550 |
555 |
/**
|
551 |
556 |
@defgroup auxalg Auxiliary Algorithms
|
552 |
557 |
@ingroup algs
|
553 |
558 |
\brief Auxiliary algorithms implemented in LEMON.
|
554 |
559 |
|
555 |
560 |
This group contains some algorithms implemented in LEMON
|
556 |
561 |
in order to make it easier to implement complex algorithms.
|
557 |
562 |
*/
|
558 |
563 |
|
559 |
564 |
/**
|
560 |
565 |
@defgroup approx Approximation Algorithms
|
561 |
566 |
@ingroup algs
|
562 |
567 |
\brief Approximation algorithms.
|
563 |
568 |
|
564 |
569 |
This group contains the approximation and heuristic algorithms
|
565 |
570 |
implemented in LEMON.
|
566 |
571 |
*/
|
567 |
572 |
|
568 |
573 |
/**
|
569 |
574 |
@defgroup gen_opt_group General Optimization Tools
|
570 |
575 |
\brief This group contains some general optimization frameworks
|
571 |
576 |
implemented in LEMON.
|
572 |
577 |
|
573 |
578 |
This group contains some general optimization frameworks
|
574 |
579 |
implemented in LEMON.
|
575 |
580 |
*/
|
576 |
581 |
|
577 |
582 |
/**
|
578 |
583 |
@defgroup lp_group Lp and Mip Solvers
|
579 |
584 |
@ingroup gen_opt_group
|
580 |
585 |
\brief Lp and Mip solver interfaces for LEMON.
|
581 |
586 |
|
582 |
587 |
This group contains Lp and Mip solver interfaces for LEMON. The
|
583 |
588 |
various LP solvers could be used in the same manner with this
|
584 |
589 |
interface.
|
585 |
590 |
*/
|
586 |
591 |
|
587 |
592 |
/**
|
588 |
593 |
@defgroup lp_utils Tools for Lp and Mip Solvers
|
589 |
594 |
@ingroup lp_group
|
590 |
595 |
\brief Helper tools to the Lp and Mip solvers.
|
591 |
596 |
|
592 |
597 |
This group adds some helper tools to general optimization framework
|
593 |
598 |
implemented in LEMON.
|
594 |
599 |
*/
|
595 |
600 |
|