COIN-OR::LEMON - Graph Library

Changeset 209:765619b7cbb2 in lemon-main for doc/groups.dox


Ignore:
Timestamp:
07/13/08 20:51:02 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r192 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
     
    2727\brief Graph structures implemented in LEMON.
    2828
    29 The implementation of combinatorial algorithms heavily relies on 
    30 efficient graph implementations. LEMON offers data structures which are 
    31 planned to be easily used in an experimental phase of implementation studies, 
    32 and thereafter the program code can be made efficient by small modifications. 
     29The implementation of combinatorial algorithms heavily relies on
     30efficient graph implementations. LEMON offers data structures which are
     31planned to be easily used in an experimental phase of implementation studies,
     32and thereafter the program code can be made efficient by small modifications.
    3333
    3434The most efficient implementation of diverse applications require the
     
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of 
    44 operations, these together satisfy the everyday requirements. 
    45 In the case of graph structures, different operations are needed which do 
    46 not alter the physical graph, but gives another view. If some nodes or 
     43Alteration of standard containers need a very limited number of
     44operations, these together satisfy the everyday requirements.
     45In the case of graph structures, different operations are needed which do
     46not alter the physical graph, but gives another view. If some nodes or
    4747arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation 
    49 the residual graph can be accessed by another algorithm, or a node-set 
    50 is to be shrunk for another algorithm. 
    51 LEMON also provides a variety of graphs for these requirements called 
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
    53 in conjunction with other graph representations. 
     48this is the case. It also may happen that in a flow implementation
     49the residual graph can be accessed by another algorithm, or a node-set
     50is to be shrunk for another algorithm.
     51LEMON also provides a variety of graphs for these requirements called
     52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
     53in conjunction with other graph representations.
    5454
    5555You are free to use the graph structure that fit your requirements
    5656the best, most graph algorithms and auxiliary data structures can be used
    57 with any graph structures. 
     57with any graph structures.
    5858*/
    5959
     
    6464
    6565This group describes some graph types between real graphs and graph adaptors.
    66 These classes wrap graphs to give new functionality as the adaptors do it. 
     66These classes wrap graphs to give new functionality as the adaptors do it.
    6767On the other hand they are not light-weight structures as the adaptors.
    6868*/
    6969
    7070/**
    71 @defgroup maps Maps 
     71@defgroup maps Maps
    7272@ingroup datas
    7373\brief Map structures implemented in LEMON.
     
    8080
    8181/**
    82 @defgroup graph_maps Graph Maps 
     82@defgroup graph_maps Graph Maps
    8383@ingroup maps
    8484\brief Special graph-related maps.
     
    116116    }
    117117  }
    118  
     118
    119119  Digraph::NodeMap<int> degree_map(graph);
    120  
     120
    121121  digraphToEps(graph, "graph.eps")
    122122    .coords(coords).scaleToA4().undirected()
    123123    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    124124    .run();
    125 \endcode 
     125\endcode
    126126The \c functorToMap() function makes an \c int to \c Color map from the
    127127\e nodeColor() function. The \c composeMap() compose the \e degree_map
     
    141141  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
    142142  TimeMap time(length, speed);
    143  
     143
    144144  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
    145145  dijkstra.run(source, target);
     
    153153
    154154/**
    155 @defgroup matrices Matrices 
     155@defgroup matrices Matrices
    156156@ingroup datas
    157157\brief Two dimensional data storages implemented in LEMON.
     
    201201\brief Common graph search algorithms.
    202202
    203 This group describes the common graph search algorithms like 
     203This group describes the common graph search algorithms like
    204204Breadth-first search (Bfs) and Depth-first search (Dfs).
    205205*/
     
    213213*/
    214214
    215 /** 
    216 @defgroup max_flow Maximum Flow algorithms 
    217 @ingroup algs 
     215/**
     216@defgroup max_flow Maximum Flow algorithms
     217@ingroup algs
    218218\brief Algorithms for finding maximum flows.
    219219
     
    232232
    233233LEMON contains several algorithms for solving maximum flow problems:
    234 - \ref lemon::EdmondsKarp "Edmonds-Karp" 
     234- \ref lemon::EdmondsKarp "Edmonds-Karp"
    235235- \ref lemon::Preflow "Goldberg's Preflow algorithm"
    236236- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     
    251251
    252252This group describes the algorithms for finding minimum cost flows and
    253 circulations. 
    254 */
    255 
    256 /**
    257 @defgroup min_cut Minimum Cut algorithms 
    258 @ingroup algs 
     253circulations.
     254*/
     255
     256/**
     257@defgroup min_cut Minimum Cut algorithms
     258@ingroup algs
    259259
    260260\brief Algorithms for finding minimum cut in graphs.
     
    273273
    274274- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    275   in directed graphs 
     275  in directed graphs
    276276- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    277277  calculate minimum cut in undirected graphs
     
    308308
    309309/**
    310 @defgroup matching Matching algorithms 
     310@defgroup matching Matching algorithms
    311311@ingroup algs
    312312\brief Algorithms for finding matchings in graphs and bipartite graphs.
     
    315315matchings in graphs and bipartite graphs. The general matching problem is
    316316finding a subset of the arcs which does not shares common endpoints.
    317  
     317
    318318There are several different algorithms for calculate matchings in
    319319graphs.  The matching problems in bipartite graphs are generally
     
    324324
    325325Lemon contains the next algorithms:
    326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
    327   augmenting path algorithm for calculate maximum cardinality matching in 
     326- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     327  augmenting path algorithm for calculate maximum cardinality matching in
    328328  bipartite graphs
    329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
    330   algorithm for calculate maximum cardinality matching in bipartite graphs 
    331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
    332   Successive shortest path algorithm for calculate maximum weighted matching 
     329- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     330  algorithm for calculate maximum cardinality matching in bipartite graphs
     331- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     332  Successive shortest path algorithm for calculate maximum weighted matching
    333333  and maximum weighted bipartite matching in bipartite graph
    334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
    335   Successive shortest path algorithm for calculate minimum cost maximum 
     334- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     335  Successive shortest path algorithm for calculate minimum cost maximum
    336336  matching in bipartite graph
    337337- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     
    397397*/
    398398
    399 /** 
    400 @defgroup lp_utils Tools for Lp and Mip solvers 
     399/**
     400@defgroup lp_utils Tools for Lp and Mip solvers
    401401@ingroup lp_group
    402402\brief Helper tools to the Lp and Mip solvers.
     
    415415
    416416/**
    417 @defgroup utils Tools and Utilities 
     417@defgroup utils Tools and Utilities
    418418\brief Tools and utilities for programming in LEMON
    419419
     
    468468\brief Graph Input-Output methods
    469469
    470 This group describes the tools for importing and exporting graphs 
     470This group describes the tools for importing and exporting graphs
    471471and graph related data. Now it supports the LEMON format, the
    472472\c DIMACS format and the encapsulated postscript (EPS) format.
     
    487487
    488488This group describes general \c EPS drawing methods and special
    489 graph exporting tools. 
     489graph exporting tools.
    490490*/
    491491
     
    499499
    500500The purpose of the classes in this group is fourfold.
    501  
     501
    502502- These classes contain the documentations of the concepts. In order
    503503  to avoid document multiplications, an implementation of a concept
     
    552552@defgroup tools Standalone utility applications
    553553
    554 Some utility applications are listed here. 
     554Some utility applications are listed here.
    555555
    556556The standard compilation procedure (<tt>./configure;make</tt>) will compile
    557 them, as well. 
    558 */
    559 
     557them, as well.
     558*/
     559
Note: See TracChangeset for help on using the changeset viewer.