Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/full_graph.h

Timestamp:

06/30/06 14:15:45 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822

Message:

Revert splitted files

File:

• lemon/full_graph.h (modified) (3 diffs)

lemon/full_graph.h

@@ -22 +22 @@
 #include <cmath>
 
+#include <lemon/bits/base_extender.h>
 #include <lemon/bits/graph_extender.h>
 
@@ -30 +31 @@
 ///\ingroup graphs
 ///\file
-///\brief FullGraph class.
+///\brief FullGraph and FullUGraph classes.
 
 
@@ -247 +248 @@
   };
 
+
+  /// \brief Base of the FullUGrpah.
+  ///
+  /// Base of the FullUGrpah.
+  class FullUGraphBase {
+    int _nodeNum;
+    int _edgeNum;
+  public:
+
+    typedef FullUGraphBase Graph;
+
+    class Node;
+    class Edge;
+
+  public:
+
+    FullUGraphBase() {}
+
+
+    ///Creates a full graph with \c n nodes.
+    void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
+
+    /// \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 indiced
+    /// by the range from 0 to \e nodeNum()-1 and the index of
+    /// the node can accessed by the \e index() member.
+    Node operator()(int index) const { return Node(index); }
+
+    /// \brief Returns the index of the node.
+    ///
+    /// Returns the index of the node. Because it is a
+    /// static size graph the node's of the graph can be indiced
+    /// by the range from 0 to \e nodeNum()-1 and the index of
+    /// the node can accessed by the \e index() member.
+    int index(const Node& node) const { return node.id; }
+
+    typedef True NodeNumTag;
+    typedef True EdgeNumTag;
+
+    ///Number of nodes.
+    int nodeNum() const { return _nodeNum; }
+    ///Number of edges.
+    int edgeNum() const { return _edgeNum; }
+
+    /// Maximum node ID.
+    
+    /// Maximum node ID.
+    ///\sa id(Node)
+    int maxNodeId() const { return _nodeNum-1; }
+    /// Maximum edge ID.
+    
+    /// Maximum edge ID.
+    ///\sa id(Edge)
+    int maxEdgeId() const { return _edgeNum-1; }
+
+    /// \brief Returns the node from its \c id.
+    ///
+    /// Returns the node from its \c id. If there is not node
+    /// with the given id the effect of the function is undefinied.
+    static Node nodeFromId(int id) { return Node(id);}
+
+    /// \brief Returns the edge from its \c id.
+    ///
+    /// Returns the edge from its \c id. If there is not edge
+    /// with the given id the effect of the function is undefinied.
+    static Edge edgeFromId(int id) { return Edge(id);}
+
+    Node source(Edge e) const { 
+      /// \todo we may do it faster
+      return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
+    }
+
+    Node target(Edge e) const { 
+      int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
+      return Node(e.id - (source) * (source - 1) / 2);
+    }
+
+
+    /// \brief Node ID.
+    ///
+    /// The ID of a valid Node is a nonnegative integer not greater than
+    /// \ref maxNodeId(). The range of the ID's is not surely continuous
+    /// and the greatest node ID can be actually less then \ref maxNodeId().
+    ///
+    /// The ID of the \ref INVALID node is -1.
+    /// \return The ID of the node \c v. 
+
+    static int id(Node v) { return v.id; }
+
+    /// \brief Edge ID.
+    ///
+    /// The ID of a valid Edge is a nonnegative integer not greater than
+    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
+    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
+    ///
+    /// The ID of the \ref INVALID edge is -1.
+    ///\return The ID of the edge \c e. 
+    static int id(Edge e) { return e.id; }
+
+    /// \brief Finds an edge between two nodes.
+    ///
+    /// Finds an edge from node \c u to node \c v.
+    ///
+    /// If \c prev is \ref INVALID (this is the default value), then
+    /// It finds the first edge from \c u to \c v. Otherwise it looks for
+    /// the next edge from \c u to \c v after \c prev.
+    /// \return The found edge or INVALID if there is no such an edge.
+    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
+      if (prev.id != -1 || u.id <= v.id) return Edge(-1);
+      return Edge(u.id * (u.id - 1) / 2 + v.id);
+    }
+
+    typedef True FindEdgeTag;
+    
+      
+    class Node {
+      friend class FullUGraphBase;
+
+    protected:
+      int id;
+      Node(int _id) { id = _id;}
+    public:
+      Node() {}
+      Node (Invalid) { id = -1; }
+      bool operator==(const Node node) const {return id == node.id;}
+      bool operator!=(const Node node) const {return id != node.id;}
+      bool operator<(const Node node) const {return id < node.id;}
+    };
+    
+
+
+    class Edge {
+      friend class FullUGraphBase;
+      
+    protected:
+      int id;  // _nodeNum * target + source;
+
+      Edge(int _id) : id(_id) {}
+
+    public:
+      Edge() { }
+      Edge (Invalid) { id = -1; }
+      bool operator==(const Edge edge) const {return id == edge.id;}
+      bool operator!=(const Edge edge) const {return id != edge.id;}
+      bool operator<(const Edge edge) const {return id < edge.id;}
+    };
+
+    void first(Node& node) const {
+      node.id = _nodeNum - 1;
+    }
+
+    static void next(Node& node) {
+      --node.id;
+    }
+
+    void first(Edge& edge) const {
+      edge.id = _edgeNum - 1;
+    }
+
+    static void next(Edge& edge) {
+      --edge.id;
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {      
+      int src = node.id;
+      int trg = 0;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
+    }
+
+    /// \todo with specialized iterators we can make faster iterating
+    void nextOut(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++trg;
+      edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      int src = node.id + 1;
+      int trg = node.id;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+    
+    void nextIn(Edge& edge) const {
+      int src = source(edge).id;
+      int trg = target(edge).id;
+      ++src;
+      edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
+    }
+
+  };
+
+  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> > 
+  ExtendedFullUGraphBase;
+
+  /// \ingroup graphs
+  ///
+  /// \brief An undirected full graph class.
+  ///
+  /// This is a simple and fast undirected full graph implementation.
+  /// It is completely static, so you can neither add nor delete either
+  /// edges or nodes.
+  ///
+  /// The main difference beetween the \e FullGraph and \e FullUGraph class
+  /// is that this class conforms to the undirected graph concept and
+  /// it does not contain the loop edges.
+  ///
+  /// \sa FullUGraphBase
+  /// \sa FullGraph
+  ///
+  /// \author Balazs Dezso
+  class FullUGraph : public ExtendedFullUGraphBase {
+  public:
+
+    typedef ExtendedFullUGraphBase Parent;
+
+    /// \brief Constructor
+    FullUGraph() { construct(0); }
+
+    /// \brief Constructor
+    FullUGraph(int n) { construct(n); }
+
+    /// \brief Resize the graph
+    ///
+    /// Resize the graph. The function will fully destroy and build 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::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      construct(n);
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
+  };
+
+
+  class FullBpUGraphBase {
+  protected:
+
+    int _aNodeNum;
+    int _bNodeNum;
+
+    int _edgeNum;
+
+  public:
+
+    class NodeSetError : public LogicError {
+      virtual const char* exceptionName() const { 
+        return "lemon::FullBpUGraph::NodeSetError";
+      }
+    };
+  
+    class Node {
+      friend class FullBpUGraphBase;
+    protected:
+      int id;
+
+      Node(int _id) : id(_id) {}
+    public:
+      Node() {}
+      Node(Invalid) { id = -1; }
+      bool operator==(const Node i) const {return id==i.id;}
+      bool operator!=(const Node i) const {return id!=i.id;}
+      bool operator<(const Node i) const {return id<i.id;}
+    };
+
+    class UEdge {
+      friend class FullBpUGraphBase;
+    protected:
+      int id;
+
+      UEdge(int _id) { id = _id;}
+    public:
+      UEdge() {}
+      UEdge (Invalid) { id = -1; }
+      bool operator==(const UEdge i) const {return id==i.id;}
+      bool operator!=(const UEdge i) const {return id!=i.id;}
+      bool operator<(const UEdge i) const {return id<i.id;}
+    };
+
+    void construct(int aNodeNum, int bNodeNum) {
+      _aNodeNum = aNodeNum;
+      _bNodeNum = bNodeNum;
+      _edgeNum = aNodeNum * bNodeNum;
+    }
+
+    void firstANode(Node& node) const {
+      node.id = 2 * _aNodeNum - 2;
+      if (node.id < 0) node.id = -1; 
+    }
+    void nextANode(Node& node) const {
+      node.id -= 2;
+      if (node.id < 0) node.id = -1; 
+    }
+
+    void firstBNode(Node& node) const {
+      node.id = 2 * _bNodeNum - 1;
+    }
+    void nextBNode(Node& node) const {
+      node.id -= 2;
+    }
+
+    void first(Node& node) const {
+      if (_aNodeNum > 0) {
+        node.id = 2 * _aNodeNum - 2;
+      } else {
+        node.id = 2 * _bNodeNum - 1;
+      }
+    }
+    void next(Node& node) const {
+      node.id -= 2;
+      if (node.id == -2) {
+        node.id = 2 * _bNodeNum - 1;
+      }
+    }
+  
+    void first(UEdge& edge) const {
+      edge.id = _edgeNum - 1;
+    }
+    void next(UEdge& edge) const {
+      --edge.id;
+    }
+
+    void firstFromANode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
+      edge.id = (node.id >> 1) * _bNodeNum;
+    }
+    void nextFromANode(UEdge& edge) const {
+      ++(edge.id);
+      if (edge.id % _bNodeNum == 0) edge.id = -1;
+    }
+
+    void firstFromBNode(UEdge& edge, const Node& node) const {
+      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
+      edge.id = (node.id >> 1);
+    }
+    void nextFromBNode(UEdge& edge) const {
+      edge.id += _bNodeNum;
+      if (edge.id >= _edgeNum) edge.id = -1;
+    }
+
+    static int id(const Node& node) {
+      return node.id;
+    }
+    static Node nodeFromId(int id) {
+      return Node(id);
+    }
+    int maxNodeId() const {
+      return _aNodeNum > _bNodeNum ? 
+        _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
+    }
+  
+    static int id(const UEdge& edge) {
+      return edge.id;
+    }
+    static UEdge uEdgeFromId(int id) {
+      return UEdge(id);
+    }
+    int maxUEdgeId() const {
+      return _edgeNum - 1;
+    }
+  
+    static int aNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromANodeId(int id) {
+      return Node(id << 1);
+    }
+    int maxANodeId() const {
+      return _aNodeNum;
+    }
+
+    static int bNodeId(const Node& node) {
+      return node.id >> 1;
+    }
+    static Node fromBNodeId(int id) {
+      return Node((id << 1) + 1);
+    }
+    int maxBNodeId() const {
+      return _bNodeNum;
+    }
+
+    Node aNode(const UEdge& edge) const {
+      return Node((edge.id / _bNodeNum) << 1);
+    }
+    Node bNode(const UEdge& edge) const {
+      return Node(((edge.id % _bNodeNum) << 1) + 1);
+    }
+
+    static bool aNode(const Node& node) {
+      return (node.id & 1) == 0;
+    }
+
+    static bool bNode(const Node& node) {
+      return (node.id & 1) == 1;
+    }
+
+    static Node aNode(int index) {
+      return Node(index << 1);
+    }
+
+    static Node bNode(int index) {
+      return Node((index << 1) + 1);
+    }
+
+    typedef True NodeNumTag;
+    int nodeNum() const { return _aNodeNum + _bNodeNum; }
+    int aNodeNum() const { return _aNodeNum; }
+    int bNodeNum() const { return _bNodeNum; }
+
+    typedef True EdgeNumTag;
+    int uEdgeNum() const { return _edgeNum; }
+
+  };
+
+
+  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
+
+
+  /// \ingroup graphs
+  ///
+  /// \brief An undirected full bipartite graph class.
+  ///
+  /// This is a simple and fast bipartite undirected full graph implementation.
+  /// It is completely static, so you can neither add nor delete either
+  /// edges or nodes.
+  ///
+  /// \sa FullUGraphBase
+  /// \sa FullGraph
+  ///
+  /// \author Balazs Dezso
+  class FullBpUGraph : 
+    public ExtendedFullBpUGraphBase {
+  public:
+
+    typedef ExtendedFullBpUGraphBase Parent;
+
+    FullBpUGraph() {
+      Parent::construct(0, 0);
+    }
+
+    FullBpUGraph(int aNodeNum, int bNodeNum) {
+      Parent::construct(aNodeNum, bNodeNum);
+    }
+
+    /// \brief Resize the graph
+    ///
+    void resize(int n, int m) {
+      Parent::getNotifier(Edge()).clear();
+      Parent::getNotifier(UEdge()).clear();
+      Parent::getNotifier(Node()).clear();
+      Parent::getNotifier(ANode()).clear();
+      Parent::getNotifier(BNode()).clear();
+      construct(n, m);
+      Parent::getNotifier(ANode()).build();
+      Parent::getNotifier(BNode()).build();
+      Parent::getNotifier(Node()).build();
+      Parent::getNotifier(UEdge()).build();
+      Parent::getNotifier(Edge()).build();
+    }
+  };
+
 } //namespace lemon