UndirFullGraphBase is added
authordeba
Thu, 11 Nov 2004 11:12:42 +0000
changeset 9833095ff2b5c18
parent 982 93dd862335af
child 984 f7538f6f4c61
UndirFullGraphBase is added
It is a graph base which contains only one way directed edges in a full graph.
src/lemon/full_graph.h
     1.1 --- a/src/lemon/full_graph.h	Thu Nov 11 10:29:25 2004 +0000
     1.2 +++ b/src/lemon/full_graph.h	Thu Nov 11 11:12:42 2004 +0000
     1.3 @@ -17,6 +17,8 @@
     1.4  #ifndef LEMON_FULL_GRAPH_H
     1.5  #define LEMON_FULL_GRAPH_H
     1.6  
     1.7 +#include <cmath>
     1.8 +
     1.9  
    1.10  #include <lemon/iterable_graph_extender.h>
    1.11  #include <lemon/alteration_observer_registry.h>
    1.12 @@ -197,8 +199,6 @@
    1.13    ///Thus it conforms to
    1.14    ///the \ref concept::StaticGraph "StaticGraph" concept
    1.15    ///\sa concept::StaticGraph.
    1.16 -  ///\todo What about loops?
    1.17 -  ///\todo Don't we need SymEdgeMap?
    1.18    ///
    1.19    ///\author Alpar Juttner
    1.20    class FullGraph : public MappableFullGraphBase {
    1.21 @@ -207,6 +207,173 @@
    1.22      FullGraph(int n) { construct(n); }
    1.23    };
    1.24  
    1.25 +
    1.26 +  /// Base graph class for UndirFullGraph.
    1.27 +
    1.28 +  class UndirFullGraphBase {
    1.29 +    int NodeNum;
    1.30 +    int EdgeNum;
    1.31 +  public:
    1.32 +
    1.33 +    typedef FullGraphBase Graph;
    1.34 +
    1.35 +    class Node;
    1.36 +    class Edge;
    1.37 +
    1.38 +  public:
    1.39 +
    1.40 +    FullGraphBase() {}
    1.41 +
    1.42 +
    1.43 +    ///Creates a full graph with \c n nodes.
    1.44 +    void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
    1.45 +    ///
    1.46 +    //    FullGraphBase(const FullGraphBase &_g)
    1.47 +    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    1.48 +    
    1.49 +    typedef True NodeNumTag;
    1.50 +    typedef True EdgeNumTag;
    1.51 +
    1.52 +    ///Number of nodes.
    1.53 +    int nodeNum() const { return NodeNum; }
    1.54 +    ///Number of edges.
    1.55 +    int edgeNum() const { return EdgeNum; }
    1.56 +
    1.57 +    /// Maximum node ID.
    1.58 +    
    1.59 +    /// Maximum node ID.
    1.60 +    ///\sa id(Node)
    1.61 +    int maxId(Node = INVALID) const { return NodeNum-1; }
    1.62 +    /// Maximum edge ID.
    1.63 +    
    1.64 +    /// Maximum edge ID.
    1.65 +    ///\sa id(Edge)
    1.66 +    int maxId(Edge = INVALID) const { return EdgeNum-1; }
    1.67 +
    1.68 +    Node tail(Edge e) const { 
    1.69 +      /// \todo we may do it faster
    1.70 +      return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; 
    1.71 +    }
    1.72 +
    1.73 +    Node head(Edge e) const { 
    1.74 +      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
    1.75 +      return e.id - (tail) * (tail - 1) / 2; 
    1.76 +    }
    1.77 +
    1.78 +
    1.79 +    /// Node ID.
    1.80 +    
    1.81 +    /// The ID of a valid Node is a nonnegative integer not greater than
    1.82 +    /// \ref maxNodeId(). The range of the ID's is not surely continuous
    1.83 +    /// and the greatest node ID can be actually less then \ref maxNodeId().
    1.84 +    ///
    1.85 +    /// The ID of the \ref INVALID node is -1.
    1.86 +    ///\return The ID of the node \c v. 
    1.87 +
    1.88 +    static int id(Node v) { return v.id; }
    1.89 +    /// Edge ID.
    1.90 +    
    1.91 +    /// The ID of a valid Edge is a nonnegative integer not greater than
    1.92 +    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    1.93 +    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    1.94 +    ///
    1.95 +    /// The ID of the \ref INVALID edge is -1.
    1.96 +    ///\return The ID of the edge \c e. 
    1.97 +    static int id(Edge e) { return e.id; }
    1.98 +
    1.99 +    /// Finds an edge between two nodes.
   1.100 +    
   1.101 +    /// Finds an edge from node \c u to node \c v.
   1.102 +    ///
   1.103 +    /// If \c prev is \ref INVALID (this is the default value), then
   1.104 +    /// It finds the first edge from \c u to \c v. Otherwise it looks for
   1.105 +    /// the next edge from \c u to \c v after \c prev.
   1.106 +    /// \return The found edge or INVALID if there is no such an edge.
   1.107 +    Edge findEdge(Node u,Node v, Edge prev = INVALID) 
   1.108 +    {
   1.109 +      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
   1.110 +    }
   1.111 +    
   1.112 +      
   1.113 +    class Node {
   1.114 +      friend class FullGraphBase;
   1.115 +
   1.116 +    protected:
   1.117 +      int id;
   1.118 +      Node(int _id) { id = _id;}
   1.119 +    public:
   1.120 +      Node() {}
   1.121 +      Node (Invalid) { id = -1; }
   1.122 +      bool operator==(const Node node) const {return id == node.id;}
   1.123 +      bool operator!=(const Node node) const {return id != node.id;}
   1.124 +      bool operator<(const Node node) const {return id < node.id;}
   1.125 +    };
   1.126 +    
   1.127 +
   1.128 +
   1.129 +    class Edge {
   1.130 +      friend class FullGraphBase;
   1.131 +      
   1.132 +    protected:
   1.133 +      int id;  // NodeNum * head + tail;
   1.134 +
   1.135 +      Edge(int _id) : id(_id) {}
   1.136 +
   1.137 +      Edge(const FullGraphBase& _graph, int tail, int head) 
   1.138 +	: id(_graph.NodeNum * head+tail) {}
   1.139 +    public:
   1.140 +      Edge() { }
   1.141 +      Edge (Invalid) { id = -1; }
   1.142 +      bool operator==(const Edge edge) const {return id == edge.id;}
   1.143 +      bool operator!=(const Edge edge) const {return id != edge.id;}
   1.144 +      bool operator<(const Edge edge) const {return id < edge.id;}
   1.145 +    };
   1.146 +
   1.147 +    void first(Node& node) const {
   1.148 +      node.id = NodeNum-1;
   1.149 +    }
   1.150 +
   1.151 +    static void next(Node& node) {
   1.152 +      --node.id;
   1.153 +    }
   1.154 +
   1.155 +    void first(Edge& edge) const {
   1.156 +      edge.id = EdgeNum-1;
   1.157 +    }
   1.158 +
   1.159 +    static void next(Edge& edge) {
   1.160 +      --edge.id;
   1.161 +    }
   1.162 +
   1.163 +    void firstOut(Edge& edge, const Node& node) const {      
   1.164 +      edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
   1.165 +    }
   1.166 +
   1.167 +    /// \todo with specialized iterators we can make faster iterating
   1.168 +    void nextOut(Edge& edge) const {
   1.169 +      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
   1.170 +      int head = e.id - (tail) * (tail - 1) / 2; 
   1.171 +      ++head;
   1.172 +      return head < tail ? tail * (tail - 1) / 2 + head : -1;
   1.173 +    }
   1.174 +
   1.175 +    void firstIn(Edge& edge, const Node& node) const {
   1.176 +      edge.id = node.id * (node.id + 1) / 2 - 1;
   1.177 +    }
   1.178 +    
   1.179 +    void nextIn(Edge& edge) const {
   1.180 +      int tail = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
   1.181 +      int head = e.id - (tail) * (tail - 1) / 2; ++head;
   1.182 +      ++tail;
   1.183 +      return tail < nodeNum ? tail * (tail - 1) / 2 + head : -1;
   1.184 +    }
   1.185 +
   1.186 +  };
   1.187 +
   1.188 +  /// \todo UndirFullGraph from the UndirFullGraphBase
   1.189 +
   1.190 +  
   1.191 +
   1.192    /// @}  
   1.193  
   1.194  } //namespace lemon