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