LEMON/LEMON-main Changeset - r787:c2230649a493

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r787:c2230649a493

« 784:1a7fe3

788:c92296 »

r787:c2230649a493

Sun, 15 Nov 2009 19:57:02

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Various doc improvements (#331) - Add notes to the graph classes about the time of item counting. - Clarify the doc for run() in BFS and DFS. - Other improvements.

0 11 0

default

11 files changed with 93 insertions and 43 deletions:

lemon/adaptors.h

lemon/bfs.h

lemon/dfs.h

lemon/dijkstra.h

lemon/edge_set.h

lemon/full_graph.h

lemon/grid_graph.h

lemon/hypercube_graph.h

lemon/list_graph.h

lemon/smart_graph.h

lemon/static_graph.h

↑ Collapse diff ↑

0 comments (0 inline)

@@ -361,4 +361,7 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -720,4 +723,6 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -1315,4 +1320,6 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -1472,4 +1479,6 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time item counting.
 		  ///
 		  /// \tparam GR The type of the adapted digraph or graph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept
@@ -1620,4 +1629,6 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -1730,4 +1741,6 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -2233,4 +2246,7 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -2536,4 +2552,7 @@
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// graph structure.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
@@ -2679,4 +2698,6 @@
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// This class provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
@@ -3326,4 +3347,7 @@
 		  /// in the adaptor.
 		  ///
 		  /// This class provides item counting in the same time as the adapted
 		  /// digraph structure.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.

@@ -702,10 +702,6 @@
 		    ///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 <tt>b.run(s)</tt> is just a shortcut of the following code.
@@ -1047,6 +1043,6 @@
 		    ///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()
+		    {
@@ -1696,10 +1692,6 @@
 		    /// \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 <tt>b.run(s)</tt> is just a shortcut of the following code.

@@ -634,10 +634,6 @@
 		    ///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 <tt>d.run()</tt> is just a shortcut of the following code.
@@ -977,6 +973,6 @@
 		    ///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()
+		    {
@@ -1579,10 +1575,6 @@
 		    /// \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 <tt>d.run()</tt> is just a shortcut of the following code.

@@ -207,5 +207,5 @@
 		    ///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;

@@ -256,11 +256,12 @@
 		  /// all arcs incident to the given node is erased from the arc set.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  /// It provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \param GR The type of the graph which shares its node set with
 		  /// this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  /// concept.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  template <typename GR>
 		  class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
@@ -686,11 +687,12 @@
 		  /// incident to the given node is erased from the arc set.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Graph "Graph"
 		  /// concept.
 		  /// It provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \param GR The type of the graph which shares its node set
 		  /// with this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  /// concept.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Graph "Graph"
 		  /// concept.
 		  template <typename GR>
 		  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
@@ -955,11 +957,12 @@
 		  /// arcs. Therefore the arcs cannot be erased from the arc sets.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Digraph "Digraph"
 		  /// concept.
 		  /// It provides only linear time counting for nodes and arcs.
 		  ///
 		  /// \warning If a node is erased from the underlying graph and this
 		  /// node is the source or target of one arc in the arc set, then
 		  /// the arc set is invalidated, and it cannot be used anymore. The
 		  /// validity can be checked with the \c valid() member function.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  template <typename GR>
 		  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
@@ -1305,11 +1308,12 @@
 		  /// edges cannot be erased from the edge sets.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Graph "Graph"
 		  /// concept.
 		  /// It provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \warning If a node is erased from the underlying graph and this
 		  /// node is incident to one edge in the edge set, then the edge set
 		  /// is invalidated, and it cannot be used anymore. The validity can
 		  /// be checked with the \c valid() member function.
 		  ///
 		  /// This class fully conforms to the \ref concepts::Graph
 		  /// "Graph" concept.
 		  template <typename GR>
 		  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {

RhodeCode

Login to your account

@@ -163,4 +163,6 @@
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes and arcs.
 		  ///
 		  /// \note FullDigraph and FullGraph classes are very similar,
 		  /// but there are two differences. While this class conforms only
@@ -205,4 +207,5 @@
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// The index of a node is the same as its ID.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -213,4 +216,5 @@
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// The index of a node is the same as its ID.
 		    /// \sa operator()()
 		    static int index(const Node& node) { return Parent::index(node); }
@@ -536,4 +540,6 @@
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes, edges and arcs.
 		  ///
 		  /// \note FullDigraph and FullGraph classes are very similar,
 		  /// but there are two differences. While FullDigraph
@@ -580,4 +586,5 @@
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// The index of a node is the same as its ID.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
@@ -588,4 +595,5 @@
 		    /// completely static, the nodes can be indexed with integers from
 		    /// the range <tt>[0..nodeNum()-1]</tt>.
 		    /// The index of a node is the same as its ID.
 		    /// \sa operator()()
 		    static int index(const Node& node) { return Parent::index(node); }

@@ -504,4 +504,6 @@
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes, edges and arcs.
 		  class GridGraph : public ExtendedGridGraphBase {
 		    typedef ExtendedGridGraphBase Parent;

@@ -295,4 +295,6 @@
 		  /// 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

@@ -325,4 +325,6 @@
 		  ///only in the concept class.
 		  ///
 		  ///This class provides only linear time counting for nodes and arcs.
 		  ///
 		  ///\sa concepts::Digraph
 		  ///\sa ListGraph
@@ -361,5 +363,9 @@
 		    ///\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); }
@@ -367,4 +373,7 @@
 		    ///
 		    ///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); }
@@ -511,4 +520,5 @@
 		    ///This function erases all nodes and arcs from the digraph.
 		    ///
 		    ///\note All iterators of the digraph are invalidated, of course.
 		    void clear() {
 		      Parent::clear();
@@ -1180,4 +1190,6 @@
 		  ///only in the concept class.
 		  ///
 		  ///This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  ///\sa concepts::Graph
 		  ///\sa ListDigraph
@@ -1218,5 +1230,9 @@
 		    ///\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); }
@@ -1224,4 +1240,7 @@
 		    ///
 		    /// 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
@@ -1313,4 +1332,5 @@
 		    ///This function erases all nodes and arcs from the graph.
 		    ///
 		    ///\note All iterators of the graph are invalidated, of course.
 		    void clear() {
 		      Parent::clear();

@@ -195,4 +195,6 @@
 		  ///only in the concept class.
 		  ///
 		  ///This class provides constant time counting for nodes and arcs.
 		  ///
 		  ///\sa concepts::Digraph
 		  ///\sa SmartGraph
@@ -621,4 +623,6 @@
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes, edges and arcs.
 		  ///
 		  /// \sa concepts::Graph
 		  /// \sa SmartDigraph

@@ -293,4 +293,6 @@
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes and arcs.
 		  ///
 		  /// \sa concepts::Digraph
 		  class StaticDigraph : public ExtendedStaticDigraphBase {