Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/full_graph.h

Timestamp:

06/30/06 14:14:36 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Splitted graph 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>
 
@@ -31 +30 @@
 ///\ingroup graphs
 ///\file
-///\brief FullGraph and FullUGraph classes.
+///\brief FullGraph class.
 
 
@@ -248 +247 @@
   };
 
-
-  /// \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