# HG changeset patch
# User alpar
# Date 1099927359 0
# Node ID 6563019430ba8a2478951bf9a26c2c338dab1082
# Parent 5e865c5c8a873c19a0e4d3d4056e62b0e78ea8f3
Several changes in doc.
diff -r 5e865c5c8a87 -r 6563019430ba src/lemon/bin_heap.h
--- a/src/lemon/bin_heap.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/lemon/bin_heap.h Mon Nov 08 15:22:39 2004 +0000
@@ -32,6 +32,11 @@
/// @{
/// A Binary Heap implementation.
+
+ ///\todo Please document...
+ ///
+ ///\sa FibHeap
+ ///\sa Dijkstra
template <typename Item, typename Prio, typename ItemIntMap,
typename Compare = std::less<Prio> >
class BinHeap {
@@ -67,11 +72,15 @@
ItemIntMap &iim;
public:
+ ///\e
BinHeap(ItemIntMap &_iim) : iim(_iim) {}
+ ///\e
BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
+ ///\e
int size() const { return data.size(); }
+ ///\e
bool empty() const { return data.empty(); }
private:
@@ -101,13 +110,16 @@
}
public:
+ ///\e
void push(const PairType &p) {
int n = data.size();
data.resize(n+1);
bubble_up(n, p);
}
+ ///\e
void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
+ ///\e
Item top() const {
return data[0].first;
}
@@ -116,19 +128,23 @@
return data[0].second;
}
+ ///\e
void pop() {
rmidx(0);
}
+ ///\e
void erase(const Item &i) {
rmidx(iim[i]);
}
+ ///\e
Prio operator[](const Item &i) const {
int idx = iim[i];
return data[idx].second;
}
+ ///\e
void set(const Item &i, const Prio &p) {
int idx = iim[i];
if( idx < 0 ) {
@@ -142,15 +158,18 @@
}
}
+ ///\e
void decrease(const Item &i, const Prio &p) {
int idx = iim[i];
bubble_up(idx, PairType(i,p));
}
+ ///\e
void increase(const Item &i, const Prio &p) {
int idx = iim[i];
bubble_down(idx, PairType(i,p), data.size());
}
+ ///\e
state_enum state(const Item &i) const {
int s = iim[i];
if( s>=0 )
diff -r 5e865c5c8a87 -r 6563019430ba src/lemon/concept/path.h
--- a/src/lemon/concept/path.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/lemon/concept/path.h Mon Nov 08 15:22:39 2004 +0000
@@ -29,7 +29,7 @@
/// @{
- //! \brief A skeletom structure for representing directed paths in a graph.
+ //! \brief A skeleton structure for representing directed paths in a graph.
//!
//! A skeleton structure for representing directed paths in a graph.
//! \param GR The graph type in which the path is.
diff -r 5e865c5c8a87 -r 6563019430ba src/lemon/fib_heap.h
--- a/src/lemon/fib_heap.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/lemon/fib_heap.h Mon Nov 08 15:22:39 2004 +0000
@@ -49,6 +49,8 @@
///\param Compare A class for the ordering of the priorities. The
///default is \c std::less<Prio>.
///
+ ///\sa BinHeap
+ ///\sa Dijkstra
///\author Jacint Szabo
#ifdef DOXYGEN
diff -r 5e865c5c8a87 -r 6563019430ba src/lemon/graph_utils.h
--- a/src/lemon/graph_utils.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/lemon/graph_utils.h Mon Nov 08 15:22:39 2004 +0000
@@ -90,6 +90,36 @@
}
return num;
}
+
+ /// Finds an edge between two nodes of a graph.
+
+ /// Finds an edge from node \c u to node \c v in graph \c g.
+ ///
+ /// If \c prev is \ref INVALID (this is the default value), then
+ /// it finds the first edge from \c u to \c v. Otherwise it looks for
+ /// the next edge from \c u to \c v after \c prev.
+ /// \return The found edge or \ref INVALID if there is no such an edge.
+ ///
+ /// Thus you can iterate through each edge from \c u to \c v as it follows.
+ /// \code
+ /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) {
+ /// ...
+ /// }
+ /// \endcode
+ /// \todo We may want to use the \ref concept::GraphBase "GraphBase"
+ /// interface here...
+ /// \bug Untested ...
+ template <typename Graph>
+ typename Graph::Edge findEdge(const Graph &g,
+ typename Graph::Node u, typename Graph::Node v,
+ typename Graph::Edge prev = INVALID)
+ {
+ typename Graph::OutEdgeIt e(g,prev);
+ if(prev==INVALID) g.first(e,u);
+ else ++e;
+ while(e!=INVALID && g.tail(e)!=v) ++e;
+ return e;
+ }
///\e
diff -r 5e865c5c8a87 -r 6563019430ba src/lemon/xy.h
--- a/src/lemon/xy.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/lemon/xy.h Mon Nov 08 15:22:39 2004 +0000
@@ -137,6 +137,7 @@
///Read a plainvector from a stream
+ ///Read a plainvector from a stream
///\relates xy
///
template<typename T>
@@ -150,6 +151,7 @@
///Write a plainvector to a stream
+ ///Write a plainvector to a stream
///\relates xy
///
template<typename T>
diff -r 5e865c5c8a87 -r 6563019430ba src/work/alpar/dijkstra.h
--- a/src/work/alpar/dijkstra.h Mon Nov 08 08:40:37 2004 +0000
+++ b/src/work/alpar/dijkstra.h Mon Nov 08 15:22:39 2004 +0000
@@ -42,12 +42,17 @@
typedef GR Graph;
///The type of the map that stores the edge lengths.
- ///It must meet the \ref ReadMap concept.
+ ///It must meet the \ref concept::ReadMap "ReadMap" concept.
///
typedef LM LengthMap;
//The type of the length of the edges.
typedef typename LM::ValueType ValueType;
///The heap type used by Dijkstra algorithm.
+
+ ///The heap type used by Dijkstra algorithm.
+ ///
+ ///\sa BinHeap
+ ///\sa Dijkstra
typedef BinHeap<typename Graph::Node,
typename LM::ValueType,
typename GR::template NodeMap<int>,
@@ -56,7 +61,7 @@
///\brief The type of the map that stores the last
///edges of the shortest paths.
///
- ///It must meet the \ref WriteMap concept.
+ ///It must meet the \ref concept::WriteMap "WriteMap" concept.
///
typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
///Instantiates a PredMap.
@@ -70,20 +75,20 @@
///\brief The type of the map that stores the last but one
///nodes of the shortest paths.
///
- ///It must meet the \ref WriteMap concept.
+ ///It must meet the \ref concept::WriteMap "WriteMap" concept.
///
typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
///Instantiates a PredNodeMap.
///\todo Please document...
- ///
+ ///
static PredNodeMap *createPredNodeMap(const GR &G)
{
return new PredNodeMap(G);
}
///The type of the map that stores the dists of the nodes.
- ///It must meet the \ref WriteMap concept.
+ ///It must meet the \ref concept::WriteMap "WriteMap" concept.
///
typedef typename Graph::template NodeMap<typename LM::ValueType> DistMap;
///Instantiates a DistMap.
@@ -166,7 +171,6 @@
typedef typename TR::DistMap DistMap;
///The heap type used by the dijkstra algorithm.
typedef typename TR::Heap Heap;
-
private:
/// Pointer to the underlying graph.
const Graph *G;
@@ -224,6 +228,7 @@
};
///\ref named-templ-param "Named parameter" for setting PredMap type
+ ///\relates Dijkstra
///\ingroup flowalgs
///\ref named-templ-param "Named parameter" for setting PredMap type
template <class T>