COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r1206 r1221  
    113113detailed documentation of particular adaptors.
    114114
     115Since the adaptor classes conform to the \ref graph_concepts "graph concepts",
     116an adaptor can even be applied to another one.
     117The following image illustrates a situation when a \ref SubDigraph adaptor
     118is applied on a digraph and \ref Undirector is applied on the subgraph.
     119
     120\image html adaptors2.png
     121\image latex adaptors2.eps "Using graph adaptors" width=\textwidth
     122
    115123The behavior of graph adaptors can be very different. Some of them keep
    116124capabilities of the original graph while in other cases this would be
     
    310318This group contains the common graph search algorithms, namely
    311319\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
    312 \ref clrs01algorithms.
     320\cite clrs01algorithms.
    313321*/
    314322
     
    319327
    320328This group contains the algorithms for finding shortest paths in digraphs
    321 \ref clrs01algorithms.
     329\cite clrs01algorithms.
    322330
    323331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    341349
    342350This group contains the algorithms for finding minimum cost spanning
    343 trees and arborescences \ref clrs01algorithms.
     351trees and arborescences \cite clrs01algorithms.
    344352*/
    345353
     
    350358
    351359This group contains the algorithms for finding maximum flows and
    352 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
     360feasible circulations \cite clrs01algorithms, \cite amo93networkflows.
    353361
    354362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    366374LEMON contains several algorithms for solving maximum flow problems:
    367375- \ref EdmondsKarp Edmonds-Karp algorithm
    368   \ref edmondskarp72theoretical.
     376  \cite edmondskarp72theoretical.
    369377- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
    370   \ref goldberg88newapproach.
     378  \cite goldberg88newapproach.
    371379- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
    372   \ref dinic70algorithm, \ref sleator83dynamic.
     380  \cite dinic70algorithm, \cite sleator83dynamic.
    373381- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
    374   \ref goldberg88newapproach, \ref sleator83dynamic.
     382  \cite goldberg88newapproach, \cite sleator83dynamic.
    375383
    376384In most cases the \ref Preflow algorithm provides the
     
    392400
    393401This group contains the algorithms for finding minimum cost flows and
    394 circulations \ref amo93networkflows. For more information about this
    395 problem and its dual solution, see \ref min_cost_flow
     402circulations \cite amo93networkflows. For more information about this
     403problem and its dual solution, see: \ref min_cost_flow
    396404"Minimum Cost Flow Problem".
    397405
    398406LEMON contains several algorithms for this problem.
    399407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    400    pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     408   pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex.
    401409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
    402    relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
    403    \ref bunnagel98efficient.
     410   relabel operations \cite goldberg90approximation, \cite goldberg97efficient,
     411   \cite bunnagel98efficient.
    404412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
    405    shortest path method \ref edmondskarp72theoretical.
     413   shortest path method \cite edmondskarp72theoretical.
    406414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
    407    strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
     415   strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling.
    408416
    409417In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
     
    421429which is capable of handling real-valued arc costs (other numerical
    422430data are required to be integer).
     431
     432For more details about these implementations and for a comprehensive
     433experimental study, see the paper \cite KiralyKovacs12MCF.
     434It also compares these codes to other publicly available
     435minimum cost flow solvers.
    423436*/
    424437
     
    459472
    460473This group contains the algorithms for finding minimum mean cycles
    461 \ref amo93networkflows, \ref karp78characterization.
     474\cite amo93networkflows, \cite karp78characterization.
    462475
    463476The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     
    475488
    476489LEMON contains three algorithms for solving the minimum mean cycle problem:
    477 - \ref KarpMmc Karp's original algorithm \ref karp78characterization.
     490- \ref KarpMmc Karp's original algorithm \cite karp78characterization.
    478491- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
    479   version of Karp's algorithm \ref hartmann93finding.
     492  version of Karp's algorithm \cite hartmann93finding.
    480493- \ref HowardMmc Howard's policy iteration algorithm
    481   \ref dasdan98minmeancycle, \ref dasdan04experimental.
     494  \cite dasdan98minmeancycle, \cite dasdan04experimental.
    482495
    483496In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     
    485498time is exponential.
    486499Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
    487 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
    488 typically faster due to the applied early termination scheme.
     500run in time O(ne) and use space O(n<sup>2</sup>+e).
    489501*/
    490502
     
    636648high-level interface.
    637649
    638 The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
    639 \ref cplex, \ref soplex.
     650The currently supported solvers are \cite glpk, \cite clp, \cite cbc,
     651\cite cplex, \cite soplex.
    640652*/
    641653
     
    724736This group contains general \c EPS drawing methods and special
    725737graph exporting tools.
     738
     739\image html graph_to_eps.png
    726740*/
    727741
Note: See TracChangeset for help on using the changeset viewer.