# Changeset 788:c92296660262 in lemon-1.2

Ignore:
Timestamp:
11/18/09 14:38:02 (10 years ago)
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

Unmodified
Added
Removed
• ## doc/min_cost_flow.dox

 r786 minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs. and arc costs \ref amo93networkflows. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
• ## doc/min_cost_flow.dox

 r755 - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)<=0\f$; - \f$\pi(u)\leq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)>=0\f$; - \f$\pi(u)\geq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$.
• ## lemon/bellman_ford.h

 r786 /// \brief Bellman-Ford algorithm. #include #include #include /// length if the algorithm has already found one. /// Otherwise it gives back an empty path. lemon::Path negativeCycle() { lemon::Path negativeCycle() const { typename Digraph::template NodeMap state(*_gr, -1); lemon::Path cycle;
• ## lemon/bellman_ford.h

 r781 /// \ref named-templ-param "Named parameter" for setting /// \c OperationTraits type. /// For more information see \ref BellmanFordDefaultOperationTraits. /// For more information, see \ref BellmanFordDefaultOperationTraits. template struct SetOperationTraits /// /// The shortest path tree used here is equal to the shortest path /// tree used in \ref predNode() and \predMap(). /// tree used in \ref predNode() and \ref predMap(). /// /// \pre Either \ref run() or \ref init() must be called before /// /// The shortest path tree used here is equal to the shortest path /// tree used in \ref predArc() and \predMap(). /// tree used in \ref predArc() and \ref predMap(). /// /// \pre Either \ref run() or \ref init() must be called before
• ## lemon/bfs.h

 r786 ///Runs the algorithm to visit all nodes in the digraph. ///This method runs the %BFS algorithm in order to ///compute the shortest path to each node. /// ///The algorithm computes ///- the shortest path tree (forest), ///- the distance of each node from the root(s). ///This method runs the %BFS algorithm in order to visit all nodes ///in the digraph. /// ///\note b.run(s) is just a shortcut of the following code. ///Runs BFS algorithm to visit all nodes in the digraph. ///This method runs BFS algorithm in order to compute ///the shortest path to each node. ///This method runs BFS algorithm in order to visit all nodes ///in the digraph. void run() { /// \brief Runs the algorithm to visit all nodes in the digraph. /// /// This method runs the %BFS algorithm in order to /// compute the shortest path to each node. /// /// The algorithm computes /// - the shortest path tree (forest), /// - the distance of each node from the root(s). /// This method runs the %BFS algorithm in order to visit all nodes /// in the digraph. /// /// \note b.run(s) is just a shortcut of the following code.
• ## lemon/bfs.h

 r787 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap.
• ## lemon/dfs.h

 r786 ///Runs the algorithm to visit all nodes in the digraph. ///This method runs the %DFS algorithm in order to compute the ///%DFS path to each node. /// ///The algorithm computes ///- the %DFS tree (forest), ///- the distance of each node from the root(s) in the %DFS tree. ///This method runs the %DFS algorithm in order to visit all nodes ///in the digraph. /// ///\note d.run() is just a shortcut of the following code. ///Runs DFS algorithm to visit all nodes in the digraph. ///This method runs DFS algorithm in order to compute ///the DFS path to each node. ///This method runs DFS algorithm in order to visit all nodes ///in the digraph. void run() { /// \brief Runs the algorithm to visit all nodes in the digraph. /// This method runs the %DFS algorithm in order to /// compute the %DFS path to each node. /// /// The algorithm computes /// - the %DFS tree (forest), /// - the distance of each node from the root(s) in the %DFS tree. /// This method runs the %DFS algorithm in order to visit all nodes /// in the digraph. /// /// \note d.run() is just a shortcut of the following code.
• ## lemon/dfs.h

 r787 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap.
• ## lemon/dijkstra.h

 r786 ///The type of the arc lengths. typedef typename TR::LengthMap::Value Value; typedef typename TR::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap;
• ## lemon/dijkstra.h

 r787 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///passed to the constructor of the cross reference and the cross ///reference should be passed to the constructor of the heap). ///However external heap and cross reference objects could also be ///However, external heap and cross reference objects could also be ///passed to the algorithm using the \ref heap() function before ///calling \ref run(Node) "run()" or \ref init(). ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. /// For more information see \ref DijkstraDefaultOperationTraits. /// For more information, see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap.
• ## lemon/hypercube_graph.h

 r786 } int index(Node node) const { static int index(Node node) { return node._id; } /// only in the concept class. /// /// This class provides constant time counting for nodes, edges and arcs. /// /// \note The type of the indices is chosen to \c int for efficiency /// reasons. Thus the maximum dimension of this implementation is 26 /// Gives back the index of the given node. /// The lower bits of the integer describes the node. int index(Node node) const { static int index(Node node) { return Parent::index(node); }
• ## lemon/hypercube_graph.h

 r787 /// differ only on one position in the binary form. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however /// Thus you can neither add nor delete nodes or edges, however, /// the structure can be resized using resize(). ///
• ## lemon/list_graph.h

 r786 ///only in the concept class. /// ///This class provides only linear time counting for nodes and arcs. /// ///\sa concepts::Digraph ///\sa ListGraph ///\brief Erase a node from the digraph. /// ///This function erases the given node from the digraph. ///This function erases the given node along with its outgoing and ///incoming arcs from the digraph. /// ///\note All iterators referencing the removed node or the connected ///arcs are invalidated, of course. void erase(Node n) { Parent::erase(n); } /// ///This function erases the given arc from the digraph. /// ///\note All iterators referencing the removed arc are invalidated, ///of course. void erase(Arc a) { Parent::erase(a); } ///This function erases all nodes and arcs from the digraph. /// ///\note All iterators of the digraph are invalidated, of course. void clear() { Parent::clear(); ///only in the concept class. /// ///This class provides only linear time counting for nodes, edges and arcs. /// ///\sa concepts::Graph ///\sa ListDigraph ///\brief Erase a node from the graph. /// /// This function erases the given node from the graph. /// This function erases the given node along with its incident arcs /// from the graph. /// /// \note All iterators referencing the removed node or the incident /// edges are invalidated, of course. void erase(Node n) { Parent::erase(n); } /// /// This function erases the given edge from the graph. /// /// \note All iterators referencing the removed edge are invalidated, /// of course. void erase(Edge e) { Parent::erase(e); } /// Node validity check ///This function erases all nodes and arcs from the graph. /// ///\note All iterators of the graph are invalidated, of course. void clear() { Parent::clear();
• ## lemon/list_graph.h

 r787 /// ///\note \c ArcIt and \c OutArcIt iterators referencing the changed ///arc remain valid, however \c InArcIt iterators are invalidated. ///arc remain valid, but \c InArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot /// ///\note \c InArcIt iterators referencing the changed arc remain ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated. ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated. /// ///\warning This functionality cannot be used together with the Snapshot /// reversing, contracting, splitting arcs or nodes) cannot be /// restored. These events invalidate the snapshot. /// However the arcs and nodes that were added to the digraph after /// However, the arcs and nodes that were added to the digraph after /// making the current snapshot can be removed without invalidating it. class Snapshot { /// ///\note \c EdgeIt iterators referencing the changed edge remain ///valid, however \c ArcIt iterators referencing the changed edge and ///valid, but \c ArcIt iterators referencing the changed edge and ///all other iterators whose base node is the changed node are also ///invalidated. /// (e.g. changing the end-nodes of edges or contracting nodes) /// cannot be restored. These events invalidate the snapshot. /// However the edges and nodes that were added to the graph after /// However, the edges and nodes that were added to the graph after /// making the current snapshot can be removed without invalidating it. class Snapshot {
• ## lemon/network_simplex.h

 r786 /// /// \ref NetworkSimplex implements the primal Network Simplex algorithm /// for finding a \ref min_cost_flow "minimum cost flow". /// for finding a \ref min_cost_flow "minimum cost flow" /// \ref amo93networkflows, \ref dantzig63linearprog, /// \ref kellyoneill91netsimplex. /// This algorithm is a specialized version of the linear programming /// simplex method directly for the minimum cost flow problem.
• ## lemon/network_simplex.h

 r755 /// in LEMON for the minimum cost flow problem. /// Moreover it supports both directions of the supply/demand inequality /// constraints. For more information see \ref SupplyType. /// constraints. For more information, see \ref SupplyType. /// /// Most of the parameters of the problem (except for the digraph) /// \tparam GR The digraph type the algorithm runs on. /// \tparam V The value type used for flow amounts, capacity bounds /// and supply values in the algorithm. By default it is \c int. /// and supply values in the algorithm. By default, it is \c int. /// \tparam C The value type used for costs and potentials in the /// algorithm. By default it is the same as \c V. /// algorithm. By default, it is the same as \c V. /// /// \warning Both value types must be signed and all input data must /// \note %NetworkSimplex provides five different pivot rule /// implementations, from which the most efficient one is used /// by default. For more information see \ref PivotRule. /// by default. For more information, see \ref PivotRule. template class NetworkSimplex /// implementations that significantly affect the running time /// of the algorithm. /// By default \ref BLOCK_SEARCH "Block Search" is used, which /// By default, \ref BLOCK_SEARCH "Block Search" is used, which /// proved to be the most efficient and the most robust on various /// test inputs according to our benchmark tests. /// However another pivot rule can be selected using the \ref run() /// However, another pivot rule can be selected using the \ref run() /// function with the proper parameter. enum PivotRule { /// The First Eligible pivot rule. /// The \e First \e Eligible pivot rule. /// The next eligible arc is selected in a wraparound fashion /// in every iteration. FIRST_ELIGIBLE, /// The Best Eligible pivot rule. /// The \e Best \e Eligible pivot rule. /// The best eligible arc is selected in every iteration. BEST_ELIGIBLE, /// The Block Search pivot rule. /// The \e Block \e Search pivot rule. /// A specified number of arcs are examined in every iteration /// in a wraparound fashion and the best eligible arc is selected BLOCK_SEARCH, /// The Candidate List pivot rule. /// The \e Candidate \e List pivot rule. /// In a major iteration a candidate list is built from eligible arcs /// in a wraparound fashion and in the following minor iterations CANDIDATE_LIST, /// The Altering Candidate List pivot rule. /// The \e Altering \e Candidate \e List pivot rule. /// It is a modified version of the Candidate List method. /// It keeps only the several best eligible arcs from the former /// type will be used. /// /// For more information see \ref SupplyType. /// For more information, see \ref SupplyType. /// /// \return (*this) /// \ref reset() is called, thus only the modified parameters /// have to be set again. See \ref reset() for examples. /// However the underlying digraph must not be modified after this /// However, the underlying digraph must not be modified after this /// class have been constructed, since it copies and extends the graph. /// /// \param pivot_rule The pivot rule that will be used during the /// algorithm. For more information see \ref PivotRule. /// algorithm. For more information, see \ref PivotRule. /// /// \return \c INFEASIBLE if no feasible flow exists, /// used, all the parameters given before are kept for the next /// \ref run() call. /// However the underlying digraph must not be modified after this /// However, the underlying digraph must not be modified after this /// class have been constructed, since it copies and extends the graph. ///
• ## lemon/preflow.h

 r786 /// This class provides an implementation of Goldberg-Tarjan's \e preflow /// \e push-relabel algorithm producing a \ref max_flow /// "flow of maximum value" in a digraph. /// "flow of maximum value" in a digraph \ref clrs01algorithms, /// \ref amo93networkflows, \ref goldberg88newapproach. /// The preflow algorithms are the fastest known maximum /// flow algorithms. The current implementation uses a mixture of the
• ## lemon/preflow.h

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