Changeset 606:c5fd2d996909 in lemon for lemon/concepts

Timestamp:

03/29/09 23:08:20 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Various doc improvements (#248)

• Rename all the ugly template parameters (too long and/or starting with an underscore).
• Rename function parameters starting with an underscore.
• Extend the doc for many classes.
• Use LaTeX-style O(...) expressions only for the complicated ones.
• A lot of small unification changes.
• Small fixes.
• Some other improvements.

Location:

lemon/concepts

Files:

• graph.h (modified) (1 diff)
• graph_components.h (modified) (38 diffs)
• heap.h (modified) (4 diffs)
• path.h (modified) (3 diffs)

lemon/concepts/graph.h

@@ -602 +602 @@
       /// \brief Opposite node on an arc
       ///
-      /// \return the opposite of the given Node on the given Edge
+      /// \return The opposite of the given node on the given edge.
       Node oppositeNode(Node, Edge) const { return INVALID; }
 
       /// \brief First node of the edge.
       ///
-      /// \return the first node of the given Edge.
+      /// \return The first node of the given edge.
       ///
       /// Naturally edges don't have direction and thus
-      /// don't have source and target node. But we use these two methods
-      /// to query the two nodes of the arc. The direction of the arc
-      /// which arises this way is called the inherent direction of the
+      /// don't have source and target node. However we use \c u() and \c v()
+      /// methods to query the two nodes of the arc. The direction of the
+      /// arc which arises this way is called the inherent direction of the
       /// edge, and is used to define the "default" direction
       /// of the directed versions of the arcs.
-      /// \sa direction
+      /// \sa v()
+      /// \sa direction()
       Node u(Edge) const { return INVALID; }
 
       /// \brief Second node of the edge.
+      ///
+      /// \return The second node of the given edge.
+      ///
+      /// Naturally edges don't have direction and thus
+      /// don't have source and target node. However we use \c u() and \c v()
+      /// methods to query the two nodes of the arc. The direction of the
+      /// arc which arises this way is called the inherent direction of the
+      /// edge, and is used to define the "default" direction
+      /// of the directed versions of the arcs.
+      /// \sa u()
+      /// \sa direction()
       Node v(Edge) const { return INVALID; }
 

lemon/concepts/graph_components.h

@@ -21 +21 @@
 ///\brief The concept of graph components.
 
-
 #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 #define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
@@ -45 +44 @@
 
 #ifndef DOXYGEN
-    template <char _selector = '0'>
+    template <char sel = '0'>
 #endif
     class GraphItem {
@@ -297 +296 @@
     /// The most of the base digraphs should conform to this concept.
     /// The id's are unique and immutable.
-    template <typename _Base = BaseDigraphComponent>
-    class IDableDigraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class IDableDigraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -375 +374 @@
     /// most of the base undirected graphs should conform to this
     /// concept.  The id's are unique and immutable.
-    template <typename _Base = BaseGraphComponent>
-    class IDableGraphComponent : public IDableDigraphComponent<_Base> {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Edge Edge;
 
-      using IDableDigraphComponent<_Base>::id;
+      using IDableDigraphComponent<Base>::id;
 
       /// \brief Gives back an unique integer id for the Edge.
@@ -426 +425 @@
     /// Skeleton class for graph NodeIt and ArcIt.
     ///
-    template <typename _Graph, typename _Item>
-    class GraphItemIt : public _Item {
+    template <typename GR, typename Item>
+    class GraphItemIt : public Item {
     public:
       /// \brief Default constructor.
@@ -443 +442 @@
       /// Sets the iterator to the first item of \c the graph.
       ///
-      explicit GraphItemIt(const _Graph&) {}
+      explicit GraphItemIt(const GR&) {}
       /// \brief Invalid constructor \& conversion.
       ///
@@ -480 +479 @@
           ++(++it1);
 
-          _Item bi = it1;
+          Item bi = it1;
           bi = it2;
         }
-        _Graph& g;
+        GR& g;
       };
     };
@@ -490 +489 @@
     ///
     /// \note Because InArcIt and OutArcIt may not inherit from the same
-    /// base class, the _selector is a additional template parameter. For
-    /// InArcIt you should instantiate it with character 'i' and for
+    /// base class, the \c sel is a additional template parameter (selector).
+    /// For InArcIt you should instantiate it with character 'i' and for
     /// OutArcIt with 'o'.
-    template <typename _Graph,
-              typename _Item = typename _Graph::Arc,
-              typename _Base = typename _Graph::Node,
-              char _selector = '0'>
-    class GraphIncIt : public _Item {
+    template <typename GR,
+              typename Item = typename GR::Arc,
+              typename Base = typename GR::Node,
+              char sel = '0'>
+    class GraphIncIt : public Item {
     public:
       /// \brief Default constructor.
@@ -508 +507 @@
       /// Copy constructor.
       ///
-      GraphIncIt(GraphIncIt const& gi) : _Item(gi) {}
+      GraphIncIt(GraphIncIt const& gi) : Item(gi) {}
       /// \brief Sets the iterator to the first arc incoming into or outgoing
       /// from the node.
@@ -515 +514 @@
       /// from the node.
       ///
-      explicit GraphIncIt(const _Graph&, const _Base&) {}
+      explicit GraphIncIt(const GR&, const Base&) {}
       /// \brief Invalid constructor \& conversion.
       ///
@@ -547 +546 @@
       struct Constraints {
         void constraints() {
-          checkConcept<GraphItem<_selector>, _GraphIncIt>();
+          checkConcept<GraphItem<sel>, _GraphIncIt>();
           _GraphIncIt it1(graph, node);
           _GraphIncIt it2;
@@ -554 +553 @@
           ++it2 = it1;
           ++(++it1);
-          _Item e = it1;
+          Item e = it1;
           e = it2;
 
         }
 
-        _Item arc;
-        _Base node;
-        _Graph graph;
+        Item arc;
+        Base node;
+        GR graph;
         _GraphIncIt it;
       };
@@ -572 +571 @@
     /// iterator based iterable interface for the digraph structure.
     /// This concept is part of the Digraph concept.
-    template <typename _Base = BaseDigraphComponent>
-    class IterableDigraphComponent : public _Base {
-
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class IterableDigraphComponent : public BAS {
+
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -757 +756 @@
     /// based iterable interface for the undirected graph structure.
     /// This concept is part of the Graph concept.
-    template <typename _Base = BaseGraphComponent>
-    class IterableGraphComponent : public IterableDigraphComponent<_Base> {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -774 +773 @@
       /// @{
 
-      using IterableDigraphComponent<_Base>::first;
-      using IterableDigraphComponent<_Base>::next;
+      using IterableDigraphComponent<Base>::first;
+      using IterableDigraphComponent<Base>::next;
 
       /// \brief Gives back the first edge in the iterating
@@ -809 +808 @@
       void nextInc(Edge&, bool&) const {}
 
-      using IterableDigraphComponent<_Base>::baseNode;
-      using IterableDigraphComponent<_Base>::runningNode;
+      using IterableDigraphComponent<Base>::baseNode;
+      using IterableDigraphComponent<Base>::runningNode;
 
       /// @}
@@ -876 +875 @@
 
         const _Graph& graph;
-
       };
     };
@@ -888 +886 @@
     /// alteration occured in the digraph all the observers will
     /// notified about it.
-    template <typename _Base = BaseDigraphComponent>
-    class AlterableDigraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class AlterableDigraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -946 +944 @@
     /// alteration occured in the graph all the observers will
     /// notified about it.
-    template <typename _Base = BaseGraphComponent>
-    class AlterableGraphComponent : public AlterableDigraphComponent<_Base> {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Edge Edge;
 
@@ -975 +973 @@
 
         const _Graph& graph;
-
-      };
-
+      };
     };
 
@@ -985 +981 @@
     /// (NodeMap, ArcMap), that is maps that can be used to
     /// associate data to graph descriptors (nodes or arcs).
-    template <typename _Graph, typename _Item, typename _Value>
-    class GraphMap : public ReadWriteMap<_Item, _Value> {
-    public:
-
-      typedef ReadWriteMap<_Item, _Value> Parent;
+    template <typename GR, typename K, typename V>
+    class GraphMap : public ReadWriteMap<K, V> {
+    public:
+
+      typedef ReadWriteMap<K, V> Parent;
 
       /// The graph type of the map.
-      typedef _Graph Graph;
+      typedef GR Graph;
       /// The key type of the map.
-      typedef _Item Key;
+      typedef K Key;
       /// The value type of the map.
-      typedef _Value Value;
+      typedef V Value;
 
       /// \brief Construct a new map.
@@ -1056 +1052 @@
     /// map interface for the digraph structure.
     /// This concept is part of the Digraph concept.
-    template <typename _Base = BaseDigraphComponent>
-    class MappableDigraphComponent : public _Base  {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class MappableDigraphComponent : public BAS  {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -1070 +1066 @@
       /// ReadWrite map of the nodes.
       ///
-      template <typename _Value>
-      class NodeMap : public GraphMap<Digraph, Node, _Value> {
+      template <typename V>
+      class NodeMap : public GraphMap<Digraph, Node, V> {
       public:
-        typedef GraphMap<MappableDigraphComponent, Node, _Value> Parent;
+        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
 
         /// \brief Construct a new map.
@@ -1084 +1080 @@
         ///
         /// Construct a new map for the digraph and initalise the values.
-        NodeMap(const MappableDigraphComponent& digraph, const _Value& value)
+        NodeMap(const MappableDigraphComponent& digraph, const V& value)
           : Parent(digraph, value) {}
 
@@ -1098 +1094 @@
         template <typename CMap>
         NodeMap& operator=(const CMap&) {
-          checkConcept<ReadMap<Node, _Value>, CMap>();
+          checkConcept<ReadMap<Node, V>, CMap>();
           return *this;
         }
@@ -1108 +1104 @@
       /// ReadWrite map of the arcs.
       ///
-      template <typename _Value>
-      class ArcMap : public GraphMap<Digraph, Arc, _Value> {
+      template <typename V>
+      class ArcMap : public GraphMap<Digraph, Arc, V> {
       public:
-        typedef GraphMap<MappableDigraphComponent, Arc, _Value> Parent;
+        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
 
         /// \brief Construct a new map.
@@ -1122 +1118 @@
         ///
         /// Construct a new map for the digraph and initalise the values.
-        ArcMap(const MappableDigraphComponent& digraph, const _Value& value)
+        ArcMap(const MappableDigraphComponent& digraph, const V& value)
           : Parent(digraph, value) {}
 
@@ -1136 +1132 @@
         template <typename CMap>
         ArcMap& operator=(const CMap&) {
-          checkConcept<ReadMap<Arc, _Value>, CMap>();
+          checkConcept<ReadMap<Arc, V>, CMap>();
           return *this;
         }
@@ -1192 +1188 @@
     /// map interface for the graph structure.
     /// This concept is part of the Graph concept.
-    template <typename _Base = BaseGraphComponent>
-    class MappableGraphComponent : public MappableDigraphComponent<_Base>  {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Edge Edge;
 
@@ -1205 +1201 @@
       /// ReadWrite map of the edges.
       ///
-      template <typename _Value>
-      class EdgeMap : public GraphMap<Graph, Edge, _Value> {
+      template <typename V>
+      class EdgeMap : public GraphMap<Graph, Edge, V> {
       public:
-        typedef GraphMap<MappableGraphComponent, Edge, _Value> Parent;
+        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
 
         /// \brief Construct a new map.
@@ -1219 +1215 @@
         ///
         /// Construct a new map for the graph and initalise the values.
-        EdgeMap(const MappableGraphComponent& graph, const _Value& value)
+        EdgeMap(const MappableGraphComponent& graph, const V& value)
           : Parent(graph, value) {}
 
@@ -1233 +1229 @@
         template <typename CMap>
         EdgeMap& operator=(const CMap&) {
-          checkConcept<ReadMap<Edge, _Value>, CMap>();
+          checkConcept<ReadMap<Edge, V>, CMap>();
           return *this;
         }
@@ -1277 +1273 @@
     /// difference between the base and this interface is that the
     /// digraph alterations should handled already on this level.
-    template <typename _Base = BaseDigraphComponent>
-    class ExtendableDigraphComponent : public _Base {
-    public:
-      typedef _Base Base;
-
-      typedef typename _Base::Node Node;
-      typedef typename _Base::Arc Arc;
+    template <typename BAS = BaseDigraphComponent>
+    class ExtendableDigraphComponent : public BAS {
+    public:
+      typedef BAS Base;
+
+      typedef typename Base::Node Node;
+      typedef typename Base::Arc Arc;
 
       /// \brief Adds a new node to the digraph.
@@ -1322 +1318 @@
     /// that the graph alterations should handled already on this
     /// level.
-    template <typename _Base = BaseGraphComponent>
-    class ExtendableGraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
-      typedef typename _Base::Node Node;
-      typedef typename _Base::Edge Edge;
+    template <typename BAS = BaseGraphComponent>
+    class ExtendableGraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
+      typedef typename Base::Node Node;
+      typedef typename Base::Edge Edge;
 
       /// \brief Adds a new node to the graph.
@@ -1366 +1362 @@
     /// the base and this interface is that the digraph alterations
     /// should handled already on this level.
-    template <typename _Base = BaseDigraphComponent>
-    class ErasableDigraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class ErasableDigraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Arc Arc;
@@ -1406 +1402 @@
     /// main difference between the base and this interface is that
     /// the graph alterations should handled already on this level.
-    template <typename _Base = BaseGraphComponent>
-    class ErasableGraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class ErasableGraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
       typedef typename Base::Node Node;
       typedef typename Base::Edge Edge;
@@ -1446 +1442 @@
     /// the base and this interface is that the digraph alterations
     /// should handled already on this level.
-    template <typename _Base = BaseDigraphComponent>
-    class ClearableDigraphComponent : public _Base {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseDigraphComponent>
+    class ClearableDigraphComponent : public BAS {
+    public:
+
+      typedef BAS Base;
 
       /// \brief Erase all nodes and arcs from the digraph.
@@ -1475 +1471 @@
     /// main difference between the base and this interface is that
     /// the graph alterations should handled already on this level.
-    template <typename _Base = BaseGraphComponent>
-    class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {
-    public:
-
-      typedef _Base Base;
+    template <typename BAS = BaseGraphComponent>
+    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {
+    public:
+
+      typedef BAS Base;
 
       template <typename _Graph>

lemon/concepts/heap.h

@@ -36 +36 @@
     /// \brief The heap concept.
     ///
-    /// Concept class describing the main interface of heaps.
-    template <typename Priority, typename ItemIntMap>
+    /// Concept class describing the main interface of heaps. A \e heap
+    /// is a data structure for storing items with specified values called
+    /// \e priorities in such a way that finding the item with minimum
+    /// priority is efficient. In a heap one can change the priority of an
+    /// item, add or erase an item, etc.
+    ///
+    /// \tparam PR Type of the priority of the items.
+    /// \tparam IM A read and writable item map with int values, used
+    /// internally to handle the cross references.
+    /// \tparam Comp A functor class for the ordering of the priorities.
+    /// The default is \c std::less<PR>.
+#ifdef DOXYGEN
+    template <typename PR, typename IM, typename Comp = std::less<PR> >
+#else
+    template <typename PR, typename IM>
+#endif
     class Heap {
     public:
 
+      /// Type of the item-int map.
+      typedef IM ItemIntMap;
+      /// Type of the priorities.
+      typedef PR Prio;
       /// Type of the items stored in the heap.
       typedef typename ItemIntMap::Key Item;
-
-      /// Type of the priorities.
-      typedef Priority Prio;
 
       /// \brief Type to represent the states of the items.
@@ -54 +69 @@
       /// the user.
       ///
-      /// The \c ItemIntMap must be initialized in such a way, that it
-      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
+      /// The item-int map must be initialized in such way that it assigns
+      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
       enum State {
-        IN_HEAP = 0,
-        PRE_HEAP = -1,
-        POST_HEAP = -2
+        IN_HEAP = 0,    ///< The "in heap" state constant.
+        PRE_HEAP = -1,  ///< The "pre heap" state constant.
+        POST_HEAP = -2  ///< The "post heap" state constant.
       };
 
@@ -120 +135 @@
       ///
       /// Returns the priority of the given item.
+      /// \param i The item.
       /// \pre \c i must be in the heap.
-      /// \param i The item.
       Prio operator[](const Item &i) const {}
 
@@ -138 +153 @@
       ///
       /// Decreases the priority of an item to the given value.
+      /// \param i The item.
+      /// \param p The priority.
       /// \pre \c i must be stored in the heap with priority at least \c p.
+      void decrease(const Item &i, const Prio &p) {}
+
+      /// \brief Increases the priority of an item to the given value.
+      ///
+      /// Increases the priority of an item to the given value.
       /// \param i The item.
       /// \param p The priority.
-      void decrease(const Item &i, const Prio &p) {}
-
-      /// \brief Increases the priority of an item to the given value.
-      ///
-      /// Increases the priority of an item to the given value.
       /// \pre \c i must be stored in the heap with priority at most \c p.
-      /// \param i The item.
-      /// \param p The priority.
       void increase(const Item &i, const Prio &p) {}
 

lemon/concepts/path.h

@@ -39 +39 @@
     /// A skeleton structure for representing directed paths in a
     /// digraph.
-    /// \tparam _Digraph The digraph type in which the path is.
+    /// \tparam GR The digraph type in which the path is.
     ///
     /// In a sense, the path can be treated as a list of arcs. The
@@ -46 +46 @@
     /// paths cannot store the source.
     ///
-    template <typename _Digraph>
+    template <typename GR>
     class Path {
     public:
 
       /// Type of the underlying digraph.
-      typedef _Digraph Digraph;
+      typedef GR Digraph;
       /// Arc type of the underlying digraph.
       typedef typename Digraph::Arc Arc;
@@ -206 +206 @@
     /// assigned to a real path and the dumpers can be implemented as
     /// an adaptor class to the predecessor map.
-
-    /// \tparam _Digraph  The digraph type in which the path is.
+    ///
+    /// \tparam GR The digraph type in which the path is.
     ///
     /// The paths can be constructed from any path type by a
     /// template constructor or a template assignment operator.
-    ///
-    template <typename _Digraph>
+    template <typename GR>
     class PathDumper {
     public:
 
       /// Type of the underlying digraph.
-      typedef _Digraph Digraph;
+      typedef GR Digraph;
       /// Arc type of the underlying digraph.
       typedef typename Digraph::Arc Arc;