LEMON/LEMON-main Changeset - r354:80a4d0742e98

Repositories » LEMON » LEMON-main

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

Changeset - r354:80a4d0742e98

« 353:37557a

355:aa75d2 »

r354:80a4d0742e98

Sat, 01 Nov 2008 19:22:18

[Not Reviewed]

0 comments (0 inline)

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

Improvements related to full graphs (#57)

0 2 0

default

2 files changed with 68 insertions and 64 deletions:

lemon/full_graph.h

test/digraph_test.cc

↑ Collapse diff ↑

lemon/full_graph.h

Show inline comments

@@ -16,20 +16,19 @@
+		 *
 		 */
 		#ifndef LEMON_FULL_GRAPH_H
 		#define LEMON_FULL_GRAPH_H
 		#include <lemon/math.h>
 		#include <lemon/core.h>
 		#include <lemon/bits/graph_extender.h>
 		///\ingroup graphs
 		///\file
-		///\brief FullDigraph and FullGraph classes.
+		///\brief FullGraph and FullDigraph classes.
 		namespace lemon {
 		  class FullDigraphBase {
 		  public:
 		    typedef FullDigraphBase Graph;
@@ -64,27 +63,24 @@
 		    int maxNodeId() const { return _node_num - 1; }
 		    int maxArcId() const { return _arc_num - 1; }
 		    Node source(Arc arc) const { return arc._id / _node_num; }
 		    Node target(Arc arc) const { return arc._id % _node_num; }
 		    static int id(Node node) { return node._id; }
 		    static int id(Arc arc) { return arc._id; }
 		    static Node nodeFromId(int id) { return Node(id);}
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    typedef True FindArcTag;
 		    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
 		      return prev != INVALID ? arc(s, t) : INVALID;
+		    }
 		    class Node {
 		      friend class FullDigraphBase;
 		    protected:
 		      int _id;
 		      Node(int id) : _id(id) {}
@@ -154,68 +150,74 @@
 		  ///
 		  /// \brief A full digraph class.
 		  ///
 		  /// This is a simple and fast directed full graph implementation.
 		  /// From each node go arcs to each node (including the source node),
 		  /// therefore the number of the arcs in the digraph is the square of
 		  /// the node number. The digraph is completely static, so you can
 		  /// neither add nor delete either arcs or nodes, and it needs just
 		  /// the node number. This digraph type is completely static, so you
 		  /// can neither add nor delete either arcs or nodes, and it needs
 		  /// constant space in memory.
 		  ///
-		  /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept
+		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept
 		  /// and it also has an important extra feature that its maps are
 		  /// real \ref concepts::ReferenceMap "reference map"s.
-		  /// \sa concepts::Digraph.
 		  ///
 		  /// The \c FullDigraph and \c FullGraph classes are very similar,
 		  /// but there are two differences. While this class conforms only
 		  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
 		  /// class conforms to the \ref concepts::Graph "Graph" concept,
 		  /// moreover \c FullGraph does not contain a loop arc for each
 		  /// node as \c FullDigraph does.
 		  ///
 		  /// \sa FullGraph
 		  class FullDigraph : public ExtendedFullDigraphBase {
 		  public:
 		    typedef ExtendedFullDigraphBase Parent;
 		    /// \brief Constructor
 		    FullDigraph() { construct(0); }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param n The number of the nodes.
 		    FullDigraph(int n) { construct(n); }
-		    /// \brief Resize the digraph
+		    /// \brief Resizes the digraph
 		    ///
 		    /// Resize the digraph. The function will fully destroy and
 		    /// rebuild the digraph.  This cause that the maps of the digraph
 		    /// will reallocated automatically and the previous values will be
 		    /// lost.
 		    /// Resizes the digraph. The function will fully destroy and
 		    /// rebuild the digraph. This cause that the maps of the digraph will
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int n) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(n);
 		      Parent::notifier(Node()).build();
 		      Parent::notifier(Arc()).build();
+		    }
 		    /// \brief Returns the node with the given index.
 		    ///
 		    /// Returns the node with the given index. Because it is a
 		    /// static size digraph the node's of the digraph can be indexed
 		    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
 		    /// the node can accessed by the \e index() member.
 		    /// Returns the node with the given index. Since it is a static
 		    /// digraph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
 		    /// \brief Returns the index of the node.
+		    /// \brief Returns the index of the given node.
 		    ///
 		    /// Returns the index of the node. Because it is a
 		    /// static size digraph the node's of the digraph can be indexed
 		    /// in the range <tt>[0..nodeNum()-1]</tt> and the index of
 		    /// the node can accessed by the \e index() member.
 		    /// Returns the index of the given node. Since it is a static
 		    /// digraph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()
 		    int index(const Node& node) const { return Parent::index(node); }
-		    /// \brief Returns the arc connects the given nodes.
+		    /// \brief Returns the arc connecting the given nodes.
 		    ///
-		    /// Returns the arc connects the given nodes.
+		    /// Returns the arc connecting the given nodes.
 		    Arc arc(const Node& u, const Node& v) const {
 		      return Parent::arc(u, v);
+		    }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
@@ -277,13 +279,12 @@
 		        return (_node_num - 1 - u) * _node_num - v - 1;
+		      }
+		    }
 		  public:
 		    Node operator()(int ix) const { return Node(ix); }
 		    int index(const Node& node) const { return node._id; }
 		    Edge edge(const Node& u, const Node& v) const {
 		      if (u._id < v._id) {
 		        return Edge(_eid(u._id, v._id));
@@ -364,12 +365,13 @@
 		      bool operator!=(const Node node) const {return _id != node._id;}
 		      bool operator<(const Node node) const {return _id < node._id;}
 		    };
 		    class Edge {
 		      friend class FullGraphBase;
 		      friend class Arc;
 		    protected:
 		      int _id;
 		      Edge(int id) : _id(id) {}
@@ -515,93 +517,95 @@
 		  /// \ingroup graphs
 		  ///
 		  /// \brief An undirected full graph class.
 		  ///
 		  /// This is a simple and fast undirected full graph
 		  /// implementation. From each node go edge to each other node,
 		  /// therefore the number of edges in the graph is
 		  /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither
-		  /// add nor delete either edges or nodes, and it needs just constant
+		  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
 		  /// This graph type is completely static, so you can neither
 		  /// add nor delete either edges or nodes, and it needs constant
 		  /// space in memory.
 		  ///
 		  /// The \e FullDigraph and \e FullGraph classes are very similar,
 		  /// but there are two differences. While the \e FullDigraph class is
 		  /// conform just to the \ref concepts::Digraph "Digraph" concept,
 		  /// this class is conform to the \ref concepts::Graph "Graph"
 		  /// concept. In addition, the \e FullGraph class does not contain a
 		  /// loop arc from each node as the \e FullDigraph does.
 		  /// This class conforms to the \ref concepts::Graph "Graph" concept
 		  /// and it also has an important extra feature that its maps are
 		  /// real \ref concepts::ReferenceMap "reference map"s.
 		  ///
 		  /// It also has an important extra feature that its maps are real
 		  /// \ref concepts::ReferenceMap "reference map"s.
 		  /// The \c FullGraph and \c FullDigraph classes are very similar,
 		  /// but there are two differences. While the \c FullDigraph class
 		  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
 		  /// this class conforms to the \ref concepts::Graph "Graph" concept,
 		  /// moreover \c FullGraph does not contain a loop arc for each
 		  /// node as \c FullDigraph does.
 		  ///
 		  /// \sa FullDigraph
 		  class FullGraph : public ExtendedFullGraphBase {
 		  public:
 		    typedef ExtendedFullGraphBase Parent;
 		    /// \brief Constructor
 		    FullGraph() { construct(0); }
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param n The number of the nodes.
 		    FullGraph(int n) { construct(n); }
-		    /// \brief Resize the graph
+		    /// \brief Resizes the graph
 		    ///
 		    /// Resize the graph. The function will fully destroy and rebuild
 		    /// the graph.  This cause that the maps of the graph will
 		    /// reallocated automatically and the previous values will be
 		    /// lost.
 		    /// Resizes the graph. The function will fully destroy and
 		    /// rebuild the graph. This cause that the maps of the graph will
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int n) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Edge()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(n);
 		      Parent::notifier(Node()).build();
 		      Parent::notifier(Edge()).build();
 		      Parent::notifier(Arc()).build();
+		    }
 		    /// \brief Returns the node with the given index.
 		    ///
 		    /// Returns the node with the given index. Because it is a static
 		    /// size graph the node's of the graph can be indexed in the range
 		    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
 		    /// accessed by the \e index() member.
 		    /// Returns the node with the given index. Since it is a static
 		    /// graph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa index()
 		    Node operator()(int ix) const { return Parent::operator()(ix); }
 		    /// \brief Returns the index of the node.
+		    /// \brief Returns the index of the given node.
 		    ///
 		    /// Returns the index of the node. Because it is a static size
 		    /// graph the node's of the graph can be indexed in the range
 		    /// <tt>[0..nodeNum()-1]</tt> and the index of the node can
 		    /// accessed by the \e index() member.
 		    /// Returns the index of the given node. Since it is a static
 		    /// graph its nodes can be indexed with integers from the range
 		    /// <tt>[0..nodeNum()-1]</tt>.
 		    /// \sa operator()
 		    int index(const Node& node) const { return Parent::index(node); }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
 		    /// \brief Number of arcs.
 		    int arcNum() const { return Parent::arcNum(); }
 		    /// \brief Number of edges.
 		    int edgeNum() const { return Parent::edgeNum(); }
 		    /// \brief Returns the arc connects the given nodes.
 		    /// \brief Returns the arc connecting the given nodes.
 		    ///
-		    /// Returns the arc connects the given nodes.
+		    /// Returns the arc connecting the given nodes.
 		    Arc arc(const Node& s, const Node& t) const {
 		      return Parent::arc(s, t);
+		    }
 		    /// \brief Returns the edge connects the given nodes.
 		    ///
 		    /// Returns the edge connects the given nodes.
 		    Edge edge(const Node& u, const Node& v) const {
 		      return Parent::edge(u, v);
+		    }
 		    /// \brief Number of nodes.
 		    int nodeNum() const { return Parent::nodeNum(); }
 		    /// \brief Number of arcs.
 		    int arcNum() const { return Parent::arcNum(); }
 		    /// \brief Number of edges.
 		    int edgeNum() const { return Parent::edgeNum(); }
 		  };
 		} //namespace lemon

test/digraph_test.cc

Show inline comments

@@ -139,15 +139,15 @@
 		  { // Checking SmartDigraph
 		    checkConcept<Digraph, SmartDigraph>();
 		    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
 		    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
 		    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
+		  }
 		//  { // Checking FullDigraph
 		//    checkConcept<Digraph, FullDigraph>();
-		//  }
+		  { // Checking FullDigraph
 		    checkConcept<Digraph, FullDigraph>();
+		  }
 		//  { // Checking HyperCubeDigraph
 		//    checkConcept<Digraph, HyperCubeDigraph>();
 		//  }
+		}
 		template <typename Digraph>

0 comments (0 inline)

RhodeCode

Login to your account