# 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
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.