Index: lemon/bellman_ford.h
===================================================================
--- lemon/bellman_ford.h (revision 2010)
+++ lemon/bellman_ford.h (revision 2042)
@@ -156,5 +156,5 @@
/// should be used rather.
///
- /// The complexity of the algorithm is O(n * e).
+ /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
///
/// The type of the length is determined by the
Index: lemon/bucket_heap.h
===================================================================
--- lemon/bucket_heap.h (revision 2038)
+++ lemon/bucket_heap.h (revision 2042)
@@ -38,7 +38,7 @@
/// priorities in such a way that finding the item with minimum priority is
/// efficient. The bucket heap is very simple implementation, it can store
- /// only integer priorities and it stores for each priority in the [0..C]
- /// range a list of items. So it should be used only when the priorities
- /// are small. It is not intended to use as dijkstra heap.
+ /// only integer priorities and it stores for each priority in the
+ /// \f$ [0..C) \f$ range a list of items. So it should be used only when
+ /// the priorities are small. It is not intended to use as dijkstra heap.
///
/// \param _Item Type of the items to be stored.
Index: lemon/floyd_warshall.h
===================================================================
--- lemon/floyd_warshall.h (revision 1993)
+++ lemon/floyd_warshall.h (revision 2042)
@@ -160,5 +160,5 @@
/// there are negative circles then the johnson algorithm.
///
- /// The complexity of this algorithm is O(n^3 + e).
+ /// The complexity of this algorithm is \f$ O(n^3+e) \f$.
///
/// The type of the length is determined by the
Index: lemon/fredman_tarjan.h
===================================================================
--- lemon/fredman_tarjan.h (revision 1993)
+++ lemon/fredman_tarjan.h (revision 2042)
@@ -45,6 +45,6 @@
///Default traits class of FredmanTarjan class.
///\param GR Graph type.
- ///\param LM Type of cost map.
- template
+ ///\param CM Type of cost map.
+ template
struct FredmanTarjanDefaultTraits{
///The graph type the algorithm runs on.
@@ -54,7 +54,7 @@
///The type of the map that stores the edge costs.
///It must meet the \ref concept::ReadMap "ReadMap" concept.
- typedef LM CostMap;
+ typedef CM CostMap;
//The type of the cost of the edges.
- typedef typename LM::Value Value;
+ typedef typename CM::Value Value;
///The type of the map that stores whether an edge is in the
///spanning tree or not.
@@ -77,39 +77,40 @@
///%FredmanTarjan algorithm class to find a minimum spanning tree.
- /// \ingroup spantree
- ///This class provides an efficient implementation of %FredmanTarjan algorithm
- ///whitch is sometimes a bit quicker than the Prim algorithm on larger graphs.
- ///Due to the structure of the algorithm, it has less controll functions than
- ///Prim.
- ///
- ///The running time is O(e*B(e,n)) where e is the number of edges, n is the
- ///number of nodes in the graph and B(e,n) is min { i | log^(i) n <= e/n}
- ///( log^(i+1) n = log(log^(i)) n )
- ///
- ///The edge costs are passed to the algorithm using a
- ///\ref concept::ReadMap "ReadMap",
- ///so it is easy to change it to any kind of cost.
- ///
- ///The type of the cost is determined by the
- ///\ref concept::ReadMap::Value "Value" of the cost map.
+ /// \ingroup spantree
+ ///
+ ///This class provides an efficient implementation of %FredmanTarjan
+ ///algorithm whitch is sometimes a bit quicker than the Prim
+ ///algorithm on larger graphs. Due to the structure of the
+ ///algorithm, it has less controll functions than Prim.
+ ///
+ /// The running time is \f$ O(e\beta(e,n)) \f$ where
+ /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and
+ /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$
+ ///
+ ///The edge costs are passed to the algorithm using a \ref
+ ///concept::ReadMap "ReadMap", so it is easy to change it to any
+ ///kind of cost.
+ ///
+ ///The type of the cost is determined by the \ref
+ ///concept::ReadMap::Value "Value" of the cost map.
///
///\param GR The graph type the algorithm runs on. The default value
///is \ref ListUGraph. The value of GR is not used directly by
- ///FredmanTarjan, it is only passed to \ref FredmanTarjanDefaultTraits.
- ///
- ///\param LM This read-only UEdgeMap determines the costs of the
+ ///FredmanTarjan, it is only passed to \ref
+ ///FredmanTarjanDefaultTraits.
+ ///
+ ///\param CM This read-only UEdgeMap determines the costs of the
///edges. It is read once for each edge, so the map may involve in
- ///relatively time consuming process to compute the edge cost if
- ///it is necessary. The default map type is \ref
- ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value
- ///of LM is not used directly by FredmanTarjan, it is only passed to \ref
- ///FredmanTarjanDefaultTraits.
- ///
- ///\param TR Traits class to set
- ///various data types used by the algorithm. The default traits
- ///class is \ref FredmanTarjanDefaultTraits
- ///"FredmanTarjanDefaultTraits". See \ref
- ///FredmanTarjanDefaultTraits for the documentation of a FredmanTarjan traits
- ///class.
+ ///relatively time consuming process to compute the edge cost if it
+ ///is necessary. The default map type is \ref
+ ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap". The value of
+ ///CM is not used directly by FredmanTarjan, it is only passed to
+ ///\ref FredmanTarjanDefaultTraits.
+ ///
+ ///\param TR Traits class to set various data types used by the
+ ///algorithm. The default traits class is \ref
+ ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits".
+ ///See \ref FredmanTarjanDefaultTraits for the documentation of a
+ ///FredmanTarjan traits class.
///
///\author Balazs Attila Mihaly
@@ -117,19 +118,17 @@
#ifdef DOXYGEN
template
#else
template ,
- typename TR=FredmanTarjanDefaultTraits >
+ typename CM=typename GR::template UEdgeMap,
+ typename TR=FredmanTarjanDefaultTraits >
#endif
class FredmanTarjan {
public:
- /**
- * \brief \ref Exception for uninitialized parameters.
- *
- * This error represents problems in the initialization
- * of the parameters of the algorithms.
- */
+ ///\brief \ref Exception for uninitialized parameters.
+ ///
+ ///This error represents problems in the initialization
+ ///of the parameters of the algorithms.
class UninitializedParameter : public lemon::UninitializedParameter {
public:
Index: lemon/graph_adaptor.h
===================================================================
--- lemon/graph_adaptor.h (revision 2037)
+++ lemon/graph_adaptor.h (revision 2042)
@@ -46,8 +46,4 @@
///Base type for the Graph Adaptors
///
- ///\warning Graph adaptors are in even
- ///more experimental state than the other
- ///parts of the lib. Use them at you own risk.
- ///
///This is the base type for most of LEMON graph adaptors.
///This class implements a trivial graph adaptor i.e. it only wraps the
@@ -252,8 +248,4 @@
///\brief A graph adaptor which reverses the orientation of the edges.
///\ingroup graph_adaptors
- ///
- ///\warning Graph adaptors are in even more experimental
- ///state than the other
- ///parts of the lib. Use them at you own risk.
///
/// If \c g is defined as
@@ -648,7 +640,4 @@
/// \brief A graph adaptor for hiding nodes and edges from a graph.
/// \ingroup graph_adaptors
- ///
- /// \warning Graph adaptors are in even more experimental state than the
- /// other parts of the lib. Use them at you own risk.
///
/// SubGraphAdaptor shows the graph with filtered node-set and
@@ -771,8 +760,4 @@
///\ingroup graph_adaptors
///
- ///\warning Graph adaptors are in even more experimental state
- ///than the other
- ///parts of the lib. Use them at you own risk.
- ///
///An adaptor for hiding nodes from a graph.
///This adaptor specializes SubGraphAdaptor in the way that only
@@ -827,7 +812,4 @@
///\brief An adaptor for hiding edges from a graph.
- ///
- ///\warning Graph adaptors are in even more experimental state
- ///than the other parts of the lib. Use them at you own risk.
///
///An adaptor for hiding edges from a graph.
@@ -1480,34 +1462,35 @@
///\ingroup graph_adaptors
///
- ///An adaptor for composing the residual graph for
- ///directed flow and circulation problems.
-// ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a
-// ///number type. Let moreover
-// ///\f$ f,c:A\to F \f$, be functions on the edge-set.
-// ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a
-// ///flow and \f$ c \f$ for a capacity function.
-// ///Suppose that a graph instange \c g of type
-// ///\c ListGraph implements \f$ G \f$.
-// ///\code
-// /// ListGraph g;
-// ///\endcode
-// ///Then RevGraphAdaptor implements the graph structure with node-set
-// ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where
-// ///\f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$,
-// ///i.e. the so called residual graph.
-// ///When we take the union \f$ A_{forward}\cup A_{backward} \f$,
-// ///multilicities are counted, i.e. if an edge is in both
-// ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it
-// ///appears twice. The following code shows how such an instance can be
-// ///constructed.
-// ///\code
-// /// typedef ListGraph Graph;
-// /// Graph::EdgeMap f(g);
-// /// Graph::EdgeMap c(g);
-// /// ResGraphAdaptor, Graph::EdgeMap > ga(g);
-// ///\endcode
-// ///\author Marton Makai
-// ///
+ ///An adaptor for composing the residual graph for directed flow and
+ ///circulation problems. Let \f$ G=(V, A) \f$ be a directed graph
+ ///and let \f$ F \f$ be a number type. Let moreover \f$ f,c:A\to F \f$,
+ ///be functions on the edge-set.
+ ///
+ ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands
+ ///for a flow and \f$ c \f$ for a capacity function. Suppose that a
+ ///graph instange \c g of type \c ListGraph implements \f$ G \f$.
+ ///
+ ///\code
+ /// ListGraph g;
+ ///\endcode
+ ///
+ ///Then RevGraphAdaptor implements the graph structure with node-set
+ /// \f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$,
+ ///where \f$ A_{forward}=\{uv : uv\in A, f(uv)0\} \f$, i.e. the so called
+ ///residual graph. When we take the union
+ /// \f$ A_{forward}\cup A_{backward} \f$, multilicities are counted, i.e.
+ ///if an edge is in both \f$ A_{forward} \f$ and \f$ A_{backward} \f$,
+ ///then in the adaptor it appears twice. The following code shows how
+ ///such an instance can be constructed.
+ ///
+ ///\code
+ /// typedef ListGraph Graph;
+ /// Graph::EdgeMap f(g);
+ /// Graph::EdgeMap c(g);
+ /// ResGraphAdaptor, Graph::EdgeMap > ga(g);
+ ///\endcode
+ ///\author Marton Makai
+ ///
template
-///\ingroup galgs
+///\ingroup matching
///\file
-///\brief Maximum matching algorithm.
+///\brief Maximum matching algorithm in undirected graph.
namespace lemon {
- /// \addtogroup galgs
- /// @{
+ /// \ingroup matching
///Edmonds' alternating forest maximum matching algorithm.
@@ -565,5 +564,4 @@
}
- /// @}
} //END OF NAMESPACE LEMON
Index: lemon/min_cost_arborescence.h
===================================================================
--- lemon/min_cost_arborescence.h (revision 2037)
+++ lemon/min_cost_arborescence.h (revision 2042)
@@ -98,8 +98,8 @@
/// the minimum cost subgraph which are union of arborescences with the
/// given sources and spans all the nodes which are reachable from the
- /// sources. The time complexity of the algorithm is O(n^2 + e).
+ /// sources. The time complexity of the algorithm is \f$ O(n^2+e) \f$.
///
/// The algorithm provides also an optimal dual solution to arborescence
- /// that way the optimality of the algorithm can be proofed easily.
+ /// that way the optimality of the solution can be proofed easily.
///
/// \param _Graph The graph type the algorithm runs on. The default value
Index: lemon/min_cut.h
===================================================================
--- lemon/min_cut.h (revision 2038)
+++ lemon/min_cut.h (revision 2042)
@@ -840,7 +840,8 @@
/// at least two distinict subnetaux.
///
- /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci
- /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity
- /// map is used then it uses BucketHeap which results O(n*e) time complexity.
+ /// The complexity of the algorithm is \f$ O(ne\log(n)) \f$ but with
+ /// Fibonacci heap it can be decreased to \f$ O(ne+n^2\log(n)) \f$. When
+ /// the neutral capacity map is used then it uses BucketHeap which
+ /// results \f$ O(ne) \f$ time complexity.
#ifdef DOXYGEN
template
Index: lemon/prim.h
===================================================================
--- lemon/prim.h (revision 2030)
+++ lemon/prim.h (revision 2042)
@@ -137,5 +137,5 @@
///This class provides an efficient implementation of %Prim algorithm.
///
- ///The running time is O(e*log n) where e is the number of edges and
+ ///The running time is \f$ O(e\log(n)) \f$ where e is the number of edges and
///n is the number of nodes in the graph.
///
Index: lemon/radix_sort.h
===================================================================
--- lemon/radix_sort.h (revision 2033)
+++ lemon/radix_sort.h (revision 2042)
@@ -209,6 +209,7 @@
/// is choosen to partite the items on the next bit. This way, let be
/// \c c the maximal capacity and \c n the number of the items in
- /// the container, the time complexity of the algorithm \c O(log(c)*n)
- /// and the additional space complexity is \c O(log(c)).
+ /// the container, the time complexity of the algorithm
+ /// \f$ O(\log(c)n) \f$ and the additional space complexity is
+ /// \f$ O(\log(c)) \f$.
///
/// \param first The begin of the given range.
@@ -430,6 +431,6 @@
/// whole value. This way, let be \c c the maximal capacity of the integer
/// type and \c n the number of the items in
- /// the container, the time complexity of the algorithm \c O(log(c)*n)
- /// and the additional space complexity is \c O(n).
+ /// the container, the time complexity of the algorithm \f$ O(\log(c)n) \f$
+ /// and the additional space complexity is \f$ O(n) \f$.
///
/// This sorting algorithm is stable so the order of two equal element
Index: lemon/ugraph_adaptor.h
===================================================================
--- lemon/ugraph_adaptor.h (revision 2037)
+++ lemon/ugraph_adaptor.h (revision 2042)
@@ -835,4 +835,6 @@
}
+ /// \ingroup graph_adaptors
+ ///
/// \brief An adaptor for hiding undirected edges from an undirected graph.
///