COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 788:c92296660262 in lemon-main


Ignore:
Timestamp:
11/18/09 14:38:02 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
787:c2230649a493 (diff), 786:e20173729589 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
18 edited

Legend:

Unmodified
Added
Removed

  • doc/min_cost_flow.dox

    r786 r788  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs.
     29and arc costs \ref amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,

  • doc/min_cost_flow.dox

    r755 r788  
    7979   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    8080 - For all \f$u\in V\f$ nodes:
    81    - \f$\pi(u)<=0\f$;
     81   - \f$\pi(u)\leq 0\f$;
    8282   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    8383     then \f$\pi(u)=0\f$.
    … …  
    146146   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    147147 - For all \f$u\in V\f$ nodes:
    148    - \f$\pi(u)>=0\f$;
     148   - \f$\pi(u)\geq 0\f$;
    149149   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    150150     then \f$\pi(u)=0\f$.

  • lemon/bellman_ford.h

    r786 r788  
    2424/// \brief Bellman-Ford algorithm.
    2525
     26#include <lemon/list_graph.h>
    2627#include <lemon/bits/path_dump.h>
    2728#include <lemon/core.h>
    … …  
    776777    /// length if the algorithm has already found one.
    777778    /// Otherwise it gives back an empty path.
    778     lemon::Path<Digraph> negativeCycle() {
     779    lemon::Path<Digraph> negativeCycle() const {
    779780      typename Digraph::template NodeMap<int> state(*_gr, -1);
    780781      lemon::Path<Digraph> cycle;

  • lemon/bellman_ford.h

    r781 r788  
    301301    /// \ref named-templ-param "Named parameter" for setting
    302302    /// \c OperationTraits type.
    303     /// For more information see \ref BellmanFordDefaultOperationTraits.
     303    /// For more information, see \ref BellmanFordDefaultOperationTraits.
    304304    template <class T>
    305305    struct SetOperationTraits
    … …  
    719719    ///
    720720    /// The shortest path tree used here is equal to the shortest path
    721     /// tree used in \ref predNode() and \predMap().
     721    /// tree used in \ref predNode() and \ref predMap().
    722722    ///
    723723    /// \pre Either \ref run() or \ref init() must be called before
    … …  
    734734    ///
    735735    /// The shortest path tree used here is equal to the shortest path
    736     /// tree used in \ref predArc() and \predMap().
     736    /// tree used in \ref predArc() and \ref predMap().
    737737    ///
    738738    /// \pre Either \ref run() or \ref init() must be called before

  • lemon/bfs.h

    r786 r788  
    702702    ///Runs the algorithm to visit all nodes in the digraph.
    703703
    704     ///This method runs the %BFS algorithm in order to
    705     ///compute the shortest path to each node.
    706     ///
    707     ///The algorithm computes
    708     ///- the shortest path tree (forest),
    709     ///- the distance of each node from the root(s).
     704    ///This method runs the %BFS algorithm in order to visit all nodes
     705    ///in the digraph.
    710706    ///
    711707    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    10471043    ///Runs BFS algorithm to visit all nodes in the digraph.
    10481044
    1049     ///This method runs BFS algorithm in order to compute
    1050     ///the shortest path to each node.
     1045    ///This method runs BFS algorithm in order to visit all nodes
     1046    ///in the digraph.
    10511047    void run()
    10521048    {
    … …  
    16961692    /// \brief Runs the algorithm to visit all nodes in the digraph.
    16971693    ///
    1698     /// This method runs the %BFS algorithm in order to
    1699     /// compute the shortest path to each node.
    1700     ///
    1701     /// The algorithm computes
    1702     /// - the shortest path tree (forest),
    1703     /// - the distance of each node from the root(s).
     1694    /// This method runs the %BFS algorithm in order to visit all nodes
     1695    /// in the digraph.
    17041696    ///
    17051697    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.

  • lemon/bfs.h

    r787 r788  
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     66    ///By default, it is a NullMap.
    6767    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6868    ///Instantiates a \c ProcessedMap.
    … …  
    849849    ///The type of the map that indicates which nodes are processed.
    850850    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    851     ///By default it is a NullMap.
     851    ///By default, it is a NullMap.
    852852    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    853853    ///Instantiates a ProcessedMap.

  • lemon/dfs.h

    r786 r788  
    634634    ///Runs the algorithm to visit all nodes in the digraph.
    635635
    636     ///This method runs the %DFS algorithm in order to compute the
    637     ///%DFS path to each node.
    638     ///
    639     ///The algorithm computes
    640     ///- the %DFS tree (forest),
    641     ///- the distance of each node from the root(s) in the %DFS tree.
     636    ///This method runs the %DFS algorithm in order to visit all nodes
     637    ///in the digraph.
    642638    ///
    643639    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
    … …  
    977973    ///Runs DFS algorithm to visit all nodes in the digraph.
    978974
    979     ///This method runs DFS algorithm in order to compute
    980     ///the DFS path to each node.
     975    ///This method runs DFS algorithm in order to visit all nodes
     976    ///in the digraph.
    981977    void run()
    982978    {
    … …  
    15791575    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15801576
    1581     /// This method runs the %DFS algorithm in order to
    1582     /// compute the %DFS path to each node.
    1583     ///
    1584     /// The algorithm computes
    1585     /// - the %DFS tree (forest),
    1586     /// - the distance of each node from the root(s) in the %DFS tree.
     1577    /// This method runs the %DFS algorithm in order to visit all nodes
     1578    /// in the digraph.
    15871579    ///
    15881580    /// \note <tt>d.run()</tt> is just a shortcut of the following code.

  • lemon/dfs.h

    r787 r788  
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
     66    ///By default, it is a NullMap.
    6767    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6868    ///Instantiates a \c ProcessedMap.
    … …  
    779779    ///The type of the map that indicates which nodes are processed.
    780780    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    781     ///By default it is a NullMap.
     781    ///By default, it is a NullMap.
    782782    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    783783    ///Instantiates a ProcessedMap.

  • lemon/dijkstra.h

    r786 r788  
    207207
    208208    ///The type of the arc lengths.
    209     typedef typename TR::LengthMap::Value Value;
     209    typedef typename TR::Value Value;
    210210    ///The type of the map that stores the arc lengths.
    211211    typedef typename TR::LengthMap LengthMap;

  • lemon/dijkstra.h

    r787 r788  
    133133    ///The type of the map that indicates which nodes are processed.
    134134    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    135     ///By default it is a NullMap.
     135    ///By default, it is a NullMap.
    136136    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    137137    ///Instantiates a \c ProcessedMap.
    … …  
    427427    ///passed to the constructor of the cross reference and the cross
    428428    ///reference should be passed to the constructor of the heap).
    429     ///However external heap and cross reference objects could also be
     429    ///However, external heap and cross reference objects could also be
    430430    ///passed to the algorithm using the \ref heap() function before
    431431    ///calling \ref run(Node) "run()" or \ref init().
    … …  
    448448    ///\ref named-templ-param "Named parameter" for setting
    449449    ///\c OperationTraits type.
    450     /// For more information see \ref DijkstraDefaultOperationTraits.
     450    /// For more information, see \ref DijkstraDefaultOperationTraits.
    451451    template <class T>
    452452    struct SetOperationTraits
    … …  
    997997    ///The type of the map that indicates which nodes are processed.
    998998    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    999     ///By default it is a NullMap.
     999    ///By default, it is a NullMap.
    10001000    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    10011001    ///Instantiates a ProcessedMap.

  • lemon/hypercube_graph.h

    r786 r788  
    263263    }
    264264
    265     int index(Node node) const {
     265    static int index(Node node) {
    266266      return node._id;
    267267    }
    … …  
    295295  /// only in the concept class.
    296296  ///
     297  /// This class provides constant time counting for nodes, edges and arcs.
     298  ///
    297299  /// \note The type of the indices is chosen to \c int for efficiency
    298300  /// reasons. Thus the maximum dimension of this implementation is 26
    … …  
    357359    /// Gives back the index of the given node.
    358360    /// The lower bits of the integer describes the node.
    359     int index(Node node) const {
     361    static int index(Node node) {
    360362      return Parent::index(node);
    361363    }

  • lemon/hypercube_graph.h

    r787 r788  
    288288  /// differ only on one position in the binary form.
    289289  /// This class is completely static and it needs constant memory space.
    290   /// Thus you can neither add nor delete nodes or edges, however 
     290  /// Thus you can neither add nor delete nodes or edges, however,
    291291  /// the structure can be resized using resize().
    292292  ///

  • lemon/list_graph.h

    r786 r788  
    325325  ///only in the concept class.
    326326  ///
     327  ///This class provides only linear time counting for nodes and arcs.
     328  ///
    327329  ///\sa concepts::Digraph
    328330  ///\sa ListGraph
    … …  
    361363    ///\brief Erase a node from the digraph.
    362364    ///
    363     ///This function erases the given node from the digraph.
     365    ///This function erases the given node along with its outgoing and
     366    ///incoming arcs from the digraph.
     367    ///
     368    ///\note All iterators referencing the removed node or the connected
     369    ///arcs are invalidated, of course.
    364370    void erase(Node n) { Parent::erase(n); }
    365371
    … …  
    367373    ///
    368374    ///This function erases the given arc from the digraph.
     375    ///
     376    ///\note All iterators referencing the removed arc are invalidated,
     377    ///of course.
    369378    void erase(Arc a) { Parent::erase(a); }
    370379
    … …  
    511520    ///This function erases all nodes and arcs from the digraph.
    512521    ///
     522    ///\note All iterators of the digraph are invalidated, of course.
    513523    void clear() {
    514524      Parent::clear();
    … …  
    11801190  ///only in the concept class.
    11811191  ///
     1192  ///This class provides only linear time counting for nodes, edges and arcs.
     1193  ///
    11821194  ///\sa concepts::Graph
    11831195  ///\sa ListDigraph
    … …  
    12181230    ///\brief Erase a node from the graph.
    12191231    ///
    1220     /// This function erases the given node from the graph.
     1232    /// This function erases the given node along with its incident arcs
     1233    /// from the graph.
     1234    ///
     1235    /// \note All iterators referencing the removed node or the incident
     1236    /// edges are invalidated, of course.
    12211237    void erase(Node n) { Parent::erase(n); }
    12221238
    … …  
    12241240    ///
    12251241    /// This function erases the given edge from the graph.
     1242    ///
     1243    /// \note All iterators referencing the removed edge are invalidated,
     1244    /// of course.
    12261245    void erase(Edge e) { Parent::erase(e); }
    12271246    /// Node validity check
    … …  
    13131332    ///This function erases all nodes and arcs from the graph.
    13141333    ///
     1334    ///\note All iterators of the graph are invalidated, of course.
    13151335    void clear() {
    13161336      Parent::clear();

  • lemon/list_graph.h

    r787 r788  
    401401    ///
    402402    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
    403     ///arc remain valid, however \c InArcIt iterators are invalidated.
     403    ///arc remain valid, but \c InArcIt iterators are invalidated.
    404404    ///
    405405    ///\warning This functionality cannot be used together with the Snapshot
    … …  
    413413    ///
    414414    ///\note \c InArcIt iterators referencing the changed arc remain
    415     ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
     415    ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
    416416    ///
    417417    ///\warning This functionality cannot be used together with the Snapshot
    … …  
    560560    /// reversing, contracting, splitting arcs or nodes) cannot be
    561561    /// restored. These events invalidate the snapshot.
    562     /// However the arcs and nodes that were added to the digraph after
     562    /// However, the arcs and nodes that were added to the digraph after
    563563    /// making the current snapshot can be removed without invalidating it.
    564564    class Snapshot {
    … …  
    12871287    ///
    12881288    ///\note \c EdgeIt iterators referencing the changed edge remain
    1289     ///valid, however \c ArcIt iterators referencing the changed edge and
     1289    ///valid, but \c ArcIt iterators referencing the changed edge and
    12901290    ///all other iterators whose base node is the changed node are also
    12911291    ///invalidated.
    … …  
    13721372    /// (e.g. changing the end-nodes of edges or contracting nodes)
    13731373    /// cannot be restored. These events invalidate the snapshot.
    1374     /// However the edges and nodes that were added to the graph after
     1374    /// However, the edges and nodes that were added to the graph after
    13751375    /// making the current snapshot can be removed without invalidating it.
    13761376    class Snapshot {

  • lemon/network_simplex.h

    r786 r788  
    4141  ///
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    43   /// for finding a \ref min_cost_flow "minimum cost flow".
     43  /// for finding a \ref min_cost_flow "minimum cost flow"
     44  /// \ref amo93networkflows, \ref dantzig63linearprog,
     45  /// \ref kellyoneill91netsimplex.
    4446  /// This algorithm is a specialized version of the linear programming
    4547  /// simplex method directly for the minimum cost flow problem.

  • lemon/network_simplex.h

    r755 r788  
    5151  /// in LEMON for the minimum cost flow problem.
    5252  /// Moreover it supports both directions of the supply/demand inequality
    53   /// constraints. For more information see \ref SupplyType.
     53  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    5555  /// Most of the parameters of the problem (except for the digraph)
    … …  
    6060  /// \tparam GR The digraph type the algorithm runs on.
    6161  /// \tparam V The value type used for flow amounts, capacity bounds
    62   /// and supply values in the algorithm. By default it is \c int.
     62  /// and supply values in the algorithm. By default, it is \c int.
    6363  /// \tparam C The value type used for costs and potentials in the
    64   /// algorithm. By default it is the same as \c V.
     64  /// algorithm. By default, it is the same as \c V.
    6565  ///
    6666  /// \warning Both value types must be signed and all input data must
    … …  
    6969  /// \note %NetworkSimplex provides five different pivot rule
    7070  /// implementations, from which the most efficient one is used
    71   /// by default. For more information see \ref PivotRule.
     71  /// by default. For more information, see \ref PivotRule.
    7272  template <typename GR, typename V = int, typename C = V>
    7373  class NetworkSimplex
    … …  
    125125    /// implementations that significantly affect the running time
    126126    /// of the algorithm.
    127     /// By default \ref BLOCK_SEARCH "Block Search" is used, which
     127    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    128128    /// proved to be the most efficient and the most robust on various
    129129    /// test inputs according to our benchmark tests.
    130     /// However another pivot rule can be selected using the \ref run()
     130    /// However, another pivot rule can be selected using the \ref run()
    131131    /// function with the proper parameter.
    132132    enum PivotRule {
    133133
    134       /// The First Eligible pivot rule.
     134      /// The \e First \e Eligible pivot rule.
    135135      /// The next eligible arc is selected in a wraparound fashion
    136136      /// in every iteration.
    137137      FIRST_ELIGIBLE,
    138138
    139       /// The Best Eligible pivot rule.
     139      /// The \e Best \e Eligible pivot rule.
    140140      /// The best eligible arc is selected in every iteration.
    141141      BEST_ELIGIBLE,
    142142
    143       /// The Block Search pivot rule.
     143      /// The \e Block \e Search pivot rule.
    144144      /// A specified number of arcs are examined in every iteration
    145145      /// in a wraparound fashion and the best eligible arc is selected
    … …  
    147147      BLOCK_SEARCH,
    148148
    149       /// The Candidate List pivot rule.
     149      /// The \e Candidate \e List pivot rule.
    150150      /// In a major iteration a candidate list is built from eligible arcs
    151151      /// in a wraparound fashion and in the following minor iterations
    … …  
    153153      CANDIDATE_LIST,
    154154
    155       /// The Altering Candidate List pivot rule.
     155      /// The \e Altering \e Candidate \e List pivot rule.
    156156      /// It is a modified version of the Candidate List method.
    157157      /// It keeps only the several best eligible arcs from the former
    … …  
    813813    /// type will be used.
    814814    ///
    815     /// For more information see \ref SupplyType.
     815    /// For more information, see \ref SupplyType.
    816816    ///
    817817    /// \return <tt>(*this)</tt>
    … …  
    845845    /// \ref reset() is called, thus only the modified parameters
    846846    /// have to be set again. See \ref reset() for examples.
    847     /// However the underlying digraph must not be modified after this
     847    /// However, the underlying digraph must not be modified after this
    848848    /// class have been constructed, since it copies and extends the graph.
    849849    ///
    850850    /// \param pivot_rule The pivot rule that will be used during the
    851     /// algorithm. For more information see \ref PivotRule.
     851    /// algorithm. For more information, see \ref PivotRule.
    852852    ///
    853853    /// \return \c INFEASIBLE if no feasible flow exists,
    … …  
    874874    /// used, all the parameters given before are kept for the next
    875875    /// \ref run() call.
    876     /// However the underlying digraph must not be modified after this
     876    /// However, the underlying digraph must not be modified after this
    877877    /// class have been constructed, since it copies and extends the graph.
    878878    ///

  • lemon/preflow.h

    r786 r788  
    103103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    104104  /// \e push-relabel algorithm producing a \ref max_flow
    105   /// "flow of maximum value" in a digraph.
     105  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
     106  /// \ref amo93networkflows, \ref goldberg88newapproach.
    106107  /// The preflow algorithms are the fastest known maximum
    107108  /// flow algorithms. The current implementation uses a mixture of the

  • lemon/preflow.h

    r755 r788  
    266266    /// able to automatically created by the algorithm (i.e. the
    267267    /// digraph and the maximum level should be passed to it).
    268     /// However an external elevator object could also be passed to the
     268    /// However, an external elevator object could also be passed to the
    269269    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    270270    /// before calling \ref run() or \ref init().
Note: See TracChangeset for help on using the changeset viewer.