COIN-OR::LEMON - Graph Library

Changeset 354:80a4d0742e98 in lemon-1.2


Ignore:
Timestamp:
11/01/08 19:22:18 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements related to full graphs (#57)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/full_graph.h

    r353 r354  
    2020#define LEMON_FULL_GRAPH_H
    2121
    22 #include <lemon/math.h>
    23 
    2422#include <lemon/core.h>
    2523#include <lemon/bits/graph_extender.h>
     
    2725///\ingroup graphs
    2826///\file
    29 ///\brief FullDigraph and FullGraph classes.
     27///\brief FullGraph and FullDigraph classes.
     28
    3029namespace lemon {
    3130
     
    6867    Node target(Arc arc) const { return arc._id % _node_num; }
    6968
    70 
    7169    static int id(Node node) { return node._id; }
    7270    static int id(Arc arc) { return arc._id; }
    7371
    7472    static Node nodeFromId(int id) { return Node(id);}
    75 
    7673    static Arc arcFromId(int id) { return Arc(id);}
    7774
     
    8178      return prev != INVALID ? arc(s, t) : INVALID;
    8279    }
    83 
    8480
    8581    class Node {
     
    158154  /// From each node go arcs to each node (including the source node),
    159155  /// therefore the number of the arcs in the digraph is the square of
    160   /// the node number. The digraph is completely static, so you can
    161   /// neither add nor delete either arcs or nodes, and it needs just
     156  /// the node number. This digraph type is completely static, so you
     157  /// can neither add nor delete either arcs or nodes, and it needs
    162158  /// constant space in memory.
    163159  ///
    164   /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
     160  /// This class conforms to the \ref concepts::Digraph "Digraph" concept
    165161  /// and it also has an important extra feature that its maps are
    166162  /// real \ref concepts::ReferenceMap "reference map"s.
    167   /// \sa concepts::Digraph.
     163  ///
     164  /// The \c FullDigraph and \c FullGraph classes are very similar,
     165  /// but there are two differences. While this class conforms only
     166  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
     167  /// class conforms to the \ref concepts::Graph "Graph" concept,
     168  /// moreover \c FullGraph does not contain a loop arc for each
     169  /// node as \c FullDigraph does.
    168170  ///
    169171  /// \sa FullGraph
     
    178180    /// \brief Constructor
    179181    ///
     182    /// Constructor.
    180183    /// \param n The number of the nodes.
    181184    FullDigraph(int n) { construct(n); }
    182185
    183     /// \brief Resize the digraph
    184     ///
    185     /// Resize the digraph. The function will fully destroy and
    186     /// rebuild the digraph.  This cause that the maps of the digraph
    187     /// will reallocated automatically and the previous values will be
    188     /// lost.
     186    /// \brief Resizes the digraph
     187    ///
     188    /// Resizes the digraph. The function will fully destroy and
     189    /// rebuild the digraph. This cause that the maps of the digraph will
     190    /// reallocated automatically and the previous values will be lost.
    189191    void resize(int n) {
    190192      Parent::notifier(Arc()).clear();
     
    197199    /// \brief Returns the node with the given index.
    198200    ///
    199     /// Returns the node with the given index. Because it is a
    200     /// static size digraph the node's of the digraph can be indexed
    201     /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
    202     /// the node can accessed by the \e index() member.
     201    /// Returns the node with the given index. Since it is a static
     202    /// digraph its nodes can be indexed with integers from the range
     203    /// <tt>[0..nodeNum()-1]</tt>.
     204    /// \sa index()
    203205    Node operator()(int ix) const { return Parent::operator()(ix); }
    204206
    205     /// \brief Returns the index of the node.
    206     ///
    207     /// Returns the index of the node. Because it is a
    208     /// static size digraph the node's of the digraph can be indexed
    209     /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
    210     /// the node can accessed by the \e index() member.
     207    /// \brief Returns the index of the given node.
     208    ///
     209    /// Returns the index of the given node. Since it is a static
     210    /// digraph its nodes can be indexed with integers from the range
     211    /// <tt>[0..nodeNum()-1]</tt>.
     212    /// \sa operator()
    211213    int index(const Node& node) const { return Parent::index(node); }
    212214
    213     /// \brief Returns the arc connects the given nodes.
    214     ///
    215     /// Returns the arc connects the given nodes.
     215    /// \brief Returns the arc connecting the given nodes.
     216    ///
     217    /// Returns the arc connecting the given nodes.
    216218    Arc arc(const Node& u, const Node& v) const {
    217219      return Parent::arc(u, v);
     
    280282
    281283  public:
    282 
    283284
    284285    Node operator()(int ix) const { return Node(ix); }
     
    368369    class Edge {
    369370      friend class FullGraphBase;
     371      friend class Arc;
    370372
    371373    protected:
     
    519521  /// This is a simple and fast undirected full graph
    520522  /// implementation. From each node go edge to each other node,
    521   /// therefore the number of edges in the graph is
    522   /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
    523   /// add nor delete either edges or nodes, and it needs just constant
     523  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
     524  /// This graph type is completely static, so you can neither
     525  /// add nor delete either edges or nodes, and it needs constant
    524526  /// space in memory.
    525527  ///
    526   /// The \e FullDigraph and \e FullGraph classes are very similar,
    527   /// but there are two differences. While the \e FullDigraph class is
    528   /// conform just to the \ref concepts::Digraph "Digraph" concept,
    529   /// this class is conform to the \ref concepts::Graph "Graph"
    530   /// concept. In addition, the \e FullGraph class does not contain a
    531   /// loop arc from each node as the \e FullDigraph does.
    532   ///
    533   /// It also has an important extra feature that its maps are real
    534   /// \ref concepts::ReferenceMap "reference map"s.
     528  /// This class conforms to the \ref concepts::Graph "Graph" concept
     529  /// and it also has an important extra feature that its maps are
     530  /// real \ref concepts::ReferenceMap "reference map"s.
     531  ///
     532  /// The \c FullGraph and \c FullDigraph classes are very similar,
     533  /// but there are two differences. While the \c FullDigraph class
     534  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
     535  /// this class conforms to the \ref concepts::Graph "Graph" concept,
     536  /// moreover \c FullGraph does not contain a loop arc for each
     537  /// node as \c FullDigraph does.
    535538  ///
    536539  /// \sa FullDigraph
     
    545548    /// \brief Constructor
    546549    ///
     550    /// Constructor.
    547551    /// \param n The number of the nodes.
    548552    FullGraph(int n) { construct(n); }
    549553
    550     /// \brief Resize the graph
    551     ///
    552     /// Resize the graph. The function will fully destroy and rebuild
    553     /// the graph.  This cause that the maps of the graph will
    554     /// reallocated automatically and the previous values will be
    555     /// lost.
     554    /// \brief Resizes the graph
     555    ///
     556    /// Resizes the graph. The function will fully destroy and
     557    /// rebuild the graph. This cause that the maps of the graph will
     558    /// reallocated automatically and the previous values will be lost.
    556559    void resize(int n) {
    557560      Parent::notifier(Arc()).clear();
     
    566569    /// \brief Returns the node with the given index.
    567570    ///
    568     /// Returns the node with the given index. Because it is a static
    569     /// size graph the node's of the graph can be indexed in the range
    570     /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
    571     /// accessed by the \e index() member.
     571    /// Returns the node with the given index. Since it is a static
     572    /// graph its nodes can be indexed with integers from the range
     573    /// <tt>[0..nodeNum()-1]</tt>.
     574    /// \sa index()
    572575    Node operator()(int ix) const { return Parent::operator()(ix); }
    573576
    574     /// \brief Returns the index of the node.
    575     ///
    576     /// Returns the index of the node. Because it is a static size
    577     /// graph the node's of the graph can be indexed in the range
    578     /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
    579     /// accessed by the \e index() member.
     577    /// \brief Returns the index of the given node.
     578    ///
     579    /// Returns the index of the given node. Since it is a static
     580    /// graph its nodes can be indexed with integers from the range
     581    /// <tt>[0..nodeNum()-1]</tt>.
     582    /// \sa operator()
    580583    int index(const Node& node) const { return Parent::index(node); }
     584
     585    /// \brief Returns the arc connecting the given nodes.
     586    ///
     587    /// Returns the arc connecting the given nodes.
     588    Arc arc(const Node& s, const Node& t) const {
     589      return Parent::arc(s, t);
     590    }
     591
     592    /// \brief Returns the edge connects the given nodes.
     593    ///
     594    /// Returns the edge connects the given nodes.
     595    Edge edge(const Node& u, const Node& v) const {
     596      return Parent::edge(u, v);
     597    }
    581598
    582599    /// \brief Number of nodes.
     
    587604    int edgeNum() const { return Parent::edgeNum(); }
    588605
    589     /// \brief Returns the arc connects the given nodes.
    590     ///
    591     /// Returns the arc connects the given nodes.
    592     Arc arc(const Node& s, const Node& t) const {
    593       return Parent::arc(s, t);
    594     }
    595 
    596     /// \brief Returns the edge connects the given nodes.
    597     ///
    598     /// Returns the edge connects the given nodes.
    599     Edge edge(const Node& u, const Node& v) const {
    600       return Parent::edge(u, v);
    601     }
    602606  };
    603607
  • test/digraph_test.cc

    r353 r354  
    143143    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    144144  }
    145 //  { // Checking FullDigraph
    146 //    checkConcept<Digraph, FullDigraph>();
    147 //  }
     145  { // Checking FullDigraph
     146    checkConcept<Digraph, FullDigraph>();
     147  }
    148148//  { // Checking HyperCubeDigraph
    149149//    checkConcept<Digraph, HyperCubeDigraph>();
Note: See TracChangeset for help on using the changeset viewer.