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)

@@ -360,6 +360,9 @@
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -719,6 +722,8 @@
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -1314,6 +1319,8 @@
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -1471,6 +1478,8 @@
 		  /// by adding or removing nodes or arcs/edges, unless the \c GR template
 		  /// 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
 		  /// or the \ref concepts::Graph "Graph" concept.
@@ -1619,6 +1628,8 @@
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -1729,6 +1740,8 @@
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -2232,6 +2245,9 @@
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -2535,6 +2551,9 @@
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// 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.
 		  /// It can also be specified to be \c const.
@@ -2678,6 +2697,8 @@
 		  /// arcs).
 		  /// 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.
 		  /// It is implicitly \c const.
@@ -3325,6 +3346,9 @@
 		  /// costs/capacities of the original digraph to the \e bind \e arcs
 		  /// 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.
 		  /// It is implicitly \c const.

@@ -701,12 +701,8 @@
 		    ///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.
 		    ///\code
@@ -1046,8 +1042,8 @@
 		    ///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()
+		    {
 		      run(INVALID);
@@ -1695,12 +1691,8 @@
 		    /// \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.
 		    ///\code

@@ -633,12 +633,8 @@
 		    ///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.
 		    ///\code
@@ -976,8 +972,8 @@
 		    ///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()
+		    {
 		      run(INVALID);
@@ -1578,12 +1574,8 @@
 		    /// \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.
 		    ///\code

@@ -206,7 +206,7 @@
 		    typedef typename TR::Digraph Digraph;
 		    ///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;
 		    ///\brief The type of the map that stores the predecessor arcs of the

@@ -255,13 +255,14 @@
 		  /// that node can be removed from the underlying graph, in this case
 		  /// 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> > {
 		    typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
@@ -685,13 +686,14 @@
 		  /// be removed from the underlying graph, in this case all edges
 		  /// 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> > {
 		    typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
@@ -954,13 +956,14 @@
 		  /// single-linked lists for enumerate outgoing and incoming
 		  /// 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> > {
 		    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
@@ -1304,13 +1307,14 @@
 		  /// single-linked lists for enumerate incident edges. Therefore the
 		  /// 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> > {
 		    typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;

RhodeCode

Login to your account

@@ -162,6 +162,8 @@
 		  /// Most of its member functions and nested classes are documented
 		  /// 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
 		  /// to the \ref concepts::Digraph "Digraph" concept, FullGraph
@@ -204,6 +206,7 @@
 		    /// Returns the node with the given index. Since this structure is
 		    /// 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); }
@@ -212,6 +215,7 @@
 		    /// Returns the index of the given node. Since this structure is
 		    /// 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); }
@@ -535,6 +539,8 @@
 		  /// 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.
 		  ///
 		  /// \note FullDigraph and FullGraph classes are very similar,
 		  /// but there are two differences. While FullDigraph
 		  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
@@ -579,6 +585,7 @@
 		    /// Returns the node with the given index. Since this structure is
 		    /// 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); }
@@ -587,6 +594,7 @@
 		    /// Returns the index of the given node. Since this structure is
 		    /// 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); }

@@ -503,6 +503,8 @@
 		  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
 		  /// 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;

@@ -294,6 +294,8 @@
 		  /// 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.
 		  ///
 		  /// \note The type of the indices is chosen to \c int for efficiency
 		  /// reasons. Thus the maximum dimension of this implementation is 26
 		  /// (assuming that the size of \c int is 32 bit).

@@ -324,6 +324,8 @@
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///This class provides only linear time counting for nodes and arcs.
 		  ///
 		  ///\sa concepts::Digraph
 		  ///\sa ListGraph
 		  class ListDigraph : public ExtendedListDigraphBase {
@@ -360,12 +362,19 @@
 		    ///\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); }
 		    ///\brief Erase an arc from the digraph.
 		    ///
 		    ///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); }
 		    /// Node validity check
@@ -510,6 +519,7 @@
 		    ///This function erases all nodes and arcs from the digraph.
 		    ///
 		    ///\note All iterators of the digraph are invalidated, of course.
 		    void clear() {
 		      Parent::clear();
+		    }
@@ -1179,6 +1189,8 @@
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  ///\sa concepts::Graph
 		  ///\sa ListDigraph
 		  class ListGraph : public ExtendedListGraphBase {
@@ -1217,12 +1229,19 @@
 		    ///\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); }
 		    ///\brief Erase an edge from the graph.
 		    ///
 		    /// 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
@@ -1312,6 +1331,7 @@
 		    ///This function erases all nodes and arcs from the graph.
 		    ///
 		    ///\note All iterators of the graph are invalidated, of course.
 		    void clear() {
 		      Parent::clear();
+		    }

@@ -194,6 +194,8 @@
 		  ///Most of its member functions and nested classes are documented
 		  ///only in the concept class.
 		  ///
 		  ///This class provides constant time counting for nodes and arcs.
 		  ///
 		  ///\sa concepts::Digraph
 		  ///\sa SmartGraph
 		  class SmartDigraph : public ExtendedSmartDigraphBase {
@@ -620,6 +622,8 @@
 		  /// 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.
 		  ///
 		  /// \sa concepts::Graph
 		  /// \sa SmartDigraph
 		  class SmartGraph : public ExtendedSmartGraphBase {