COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [408:69f33ef03334:405:6b9057cdcd8b] in lemon-main


Ignore:
Files:
2 deleted
6 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

    r406 r388  
    1717 */
    1818
    19 namespace lemon {
    20 
    2119/**
    2220@defgroup datas Data Structures
    … …  
    9189
    9290This group describes maps that are specifically designed to assign
    93 values to the nodes and arcs/edges of graphs.
    94 
    95 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
    96 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
     91values to the nodes and arcs of graphs.
    9792*/
    9893
    … …  
    105100maps from other maps.
    106101
    107 Most of them are \ref concepts::ReadMap "read-only maps".
     102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    108103They can make arithmetic and logical operations between one or two maps
    109104(negation, shifting, addition, multiplication, logical 'and', 'or',
    … …  
    207202\brief Common graph search algorithms.
    208203
    209 This group describes the common graph search algorithms, namely
    210 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     204This group describes the common graph search algorithms like
     205Breadth-First Search (BFS) and Depth-First Search (DFS).
    211206*/
    212207
    … …  
    216211\brief Algorithms for finding shortest paths.
    217212
    218 This group describes the algorithms for finding shortest paths in digraphs.
    219 
    220  - \ref Dijkstra algorithm for finding shortest paths from a source node
    221    when all arc lengths are non-negative.
    222  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    223    from a source node when arc lenghts can be either positive or negative,
    224    but the digraph should not contain directed cycles with negative total
    225    length.
    226  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    227    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    228    lenghts can be either positive or negative, but the digraph should
    229    not contain directed cycles with negative total length.
    230  - \ref Suurballe A successive shortest path algorithm for finding
    231    arc-disjoint paths between two nodes having minimum total length.
     213This group describes the algorithms for finding shortest paths in graphs.
    232214*/
    233215
    … …  
    240222feasible circulations.
    241223
    242 The \e maximum \e flow \e problem is to find a flow of maximum value between
    243 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
    244 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
    245 \f$s, t \in V\f$ source and target nodes.
    246 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
    247 following optimization problem.
    248 
    249 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
    250 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
    251     \qquad \forall v\in V\setminus\{s,t\} \f]
    252 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    253234
    254235LEMON contains several algorithms for solving maximum flow problems:
    255 - \ref EdmondsKarp Edmonds-Karp algorithm.
    256 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    257 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    258 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    259 
    260 In most cases the \ref Preflow "Preflow" algorithm provides the
    261 fastest method for computing a maximum flow. All implementations
    262 provides functions to also query the minimum cut, which is the dual
    263 problem of the maximum flow.
     236- \ref lemon::EdmondsKarp "Edmonds-Karp"
     237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     240
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
    264245*/
    265246
    … …  
    272253This group describes the algorithms for finding minimum cost flows and
    273254circulations.
    274 
    275 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    276 minimum total cost from a set of supply nodes to a set of demand nodes
    277 in a network with capacity constraints and arc costs.
    278 Formally, let \f$G=(V,A)\f$ be a digraph,
    279 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
    280 upper bounds for the flow values on the arcs,
    281 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    282 on the arcs, and
    283 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
    284 of the nodes.
    285 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
    286 the following optimization problem.
    287 
    288 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
    289 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
    290     supply(v) \qquad \forall v\in V \f]
    291 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
    292 
    293 LEMON contains several algorithms for solving minimum cost flow problems:
    294  - \ref CycleCanceling Cycle-canceling algorithms.
    295  - \ref CapacityScaling Successive shortest path algorithm with optional
    296    capacity scaling.
    297  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
    298    cost scaling.
    299  - \ref NetworkSimplex Primal network simplex algorithm with various
    300    pivot strategies.
    301255*/
    302256
    … …  
    309263This group describes the algorithms for finding minimum cut in graphs.
    310264
    311 The \e minimum \e cut \e problem is to find a non-empty and non-complete
    312 \f$X\f$ subset of the nodes with minimum overall capacity on
    313 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
    314 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    315269cut is the \f$X\f$ solution of the next optimization problem:
    316270
    317271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    318     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    319273
    320274LEMON contains several algorithms related to minimum cut problems:
    321275
    322 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    323   in directed graphs.
    324 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    325   calculating minimum cut in undirected graphs.
    326 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
    327   all-pairs minimum cut in undirected graphs.
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
     277  in directed graphs
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
     279  calculate minimum cut in undirected graphs
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
     281  pairs minimum cut in undirected graphs
    328282
    329283If you want to find minimum cut just between two distinict nodes,
    330 see the \ref max_flow "maximum flow problem".
     284please see the \ref max_flow "Maximum Flow page".
    331285*/
    332286
    … …  
    367321graphs.  The matching problems in bipartite graphs are generally
    368322easier than in general graphs. The goal of the matching optimization
    369 can be finding maximum cardinality, maximum weight or minimum cost
     323can be the finding maximum cardinality, maximum weight or minimum cost
    370324matching. The search can be constrained to find perfect or
    371325maximum cardinality matching.
    372326
    373 The matching algorithms implemented in LEMON:
    374 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    375   for calculating maximum cardinality matching in bipartite graphs.
    376 - \ref PrBipartiteMatching Push-relabel algorithm
    377   for calculating maximum cardinality matching in bipartite graphs.
    378 - \ref MaxWeightedBipartiteMatching
    379   Successive shortest path algorithm for calculating maximum weighted
    380   matching and maximum weighted bipartite matching in bipartite graphs.
    381 - \ref MinCostMaxBipartiteMatching
    382   Successive shortest path algorithm for calculating minimum cost maximum
    383   matching in bipartite graphs.
    384 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    385   maximum cardinality matching in general graphs.
    386 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
    387   maximum weighted matching in general graphs.
    388 - \ref MaxWeightedPerfectMatching
    389   Edmond's blossom shrinking algorithm for calculating maximum weighted
    390   perfect matching in general graphs.
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
    391347
    392348\image html bipartite_matching.png
    … …  
    400356
    401357This group describes the algorithms for finding a minimum cost spanning
    402 tree in a graph.
     358tree in a graph
    403359*/
    404360
    … …  
    591547\anchor demoprograms
    592548
    593 @defgroup demos Demo Programs
     549@defgroup demos Demo programs
    594550
    595551Some demo programs are listed here. Their full source codes can be found in
    … …  
    601557
    602558/**
    603 @defgroup tools Standalone Utility Applications
     559@defgroup tools Standalone utility applications
    604560
    605561Some utility applications are listed here.
    … …  
    609565*/
    610566
    611 }

  • lemon/Makefile.am

    r404 r395  
    2121        lemon/bfs.h \
    2222        lemon/bin_heap.h \
    23         lemon/circulation.h \
    2423        lemon/color.h \
    2524        lemon/concept_check.h \

  • lemon/dijkstra.h

    r408 r405  
    4848    static Value plus(const Value& left, const Value& right) {
    4949      return left + right;
     50    }
     51    /// \brief Gives back true only if the first value is less than the second.
     52    static bool less(const Value& left, const Value& right) {
     53      return left < right;
     54    }
     55  };
     56
     57  /// \brief Widest path operation traits for the Dijkstra algorithm class.
     58  ///
     59  /// This operation traits class defines all computational operations and
     60  /// constants which are used in the Dijkstra algorithm for widest path
     61  /// computation.
     62  ///
     63  /// \see DijkstraDefaultOperationTraits
     64  template <typename Value>
     65  struct DijkstraWidestPathOperationTraits {
     66    /// \brief Gives back the maximum value of the type.
     67    static Value zero() {
     68      return std::numeric_limits<Value>::max();
     69    }
     70    /// \brief Gives back the minimum of the given two elements.
     71    static Value plus(const Value& left, const Value& right) {
     72      return std::min(left, right);
    5073    }
    5174    /// \brief Gives back true only if the first value is less than the second.

  • scripts/unify-sources.sh

    r396 r341  
    131131    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
    132132
    133     if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ]
     133    if [ $FAILED_FILES -gt 0 ]
     134    then
     135        return 1
     136    elif [ $WARNED_FILES -gt 0 ]
    134137    then
    135138        if [ "$WARNING" == 'INTERACTIVE' ]
    136139        then
    137             echo -n "Are the files with errors/warnings acceptable? (yes/no) "
     140            echo -n "Are the files with warnings acceptable? (yes/no) "
    138141            while read answer
    139142            do
    … …  
    145148                    return 1
    146149                fi
    147                 echo -n "Are the files with errors/warnings acceptable? (yes/no) "
     150                echo -n "Are the files with warnings acceptable? (yes/no) "
    148151            done
    149152        elif [ "$WARNING" == 'WERROR' ]

  • test/Makefile.am

    r404 r389  
    1010check_PROGRAMS += \
    1111        test/bfs_test \
    12         test/circulation_test \
    1312        test/counter_test \
    1413        test/dfs_test \
    … …  
    3736
    3837test_bfs_test_SOURCES = test/bfs_test.cc
    39 test_circulation_test_SOURCES = test/circulation_test.cc
    4038test_counter_test_SOURCES = test/counter_test.cc
    4139test_dfs_test_SOURCES = test/dfs_test.cc

  • test/dijkstra_test.cc

    r397 r293  
    9090      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
    9191      ::SetStandardProcessedMap
    92       ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
     92      ::SetOperationTraits<DijkstraWidestPathOperationTraits<VType> >
    9393      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
    9494      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
Note: See TracChangeset for help on using the changeset viewer.