00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_FULL_GRAPH_H
00018 #define LEMON_FULL_GRAPH_H
00019
00020 #include <cmath>
00021
00022
00023 #include <lemon/iterable_graph_extender.h>
00024 #include <lemon/alteration_notifier.h>
00025 #include <lemon/default_map.h>
00026
00027 #include <lemon/invalid.h>
00028 #include <lemon/utility.h>
00029
00030
00034
00035
00036 namespace lemon {
00037
00040
00041 class FullGraphBase {
00042 int NodeNum;
00043 int EdgeNum;
00044 public:
00045
00046 typedef FullGraphBase Graph;
00047
00048 class Node;
00049 class Edge;
00050
00051 public:
00052
00053 FullGraphBase() {}
00054
00055
00057 void construct(int n) { NodeNum = n; EdgeNum = n * n; }
00059
00060
00061
00062 typedef True NodeNumTag;
00063 typedef True EdgeNumTag;
00064
00066 int nodeNum() const { return NodeNum; }
00068 int edgeNum() const { return EdgeNum; }
00069
00071
00074 int maxId(Node = INVALID) const { return NodeNum-1; }
00076
00079 int maxId(Edge = INVALID) const { return EdgeNum-1; }
00080
00081 Node source(Edge e) const { return e.id % NodeNum; }
00082 Node target(Edge e) const { return e.id / NodeNum; }
00083
00084
00086
00093
00094 static int id(Node v) { return v.id; }
00096
00103 static int id(Edge e) { return e.id; }
00104
00105 static Node fromId(int id, Node) { return Node(id);}
00106
00107 static Edge fromId(int id, Edge) { return Edge(id);}
00108
00110
00117 Edge findEdge(Node u,Node v, Edge prev = INVALID)
00118 {
00119 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00120 }
00121
00122
00123 class Node {
00124 friend class FullGraphBase;
00125
00126 protected:
00127 int id;
00128 Node(int _id) { id = _id;}
00129 public:
00130 Node() {}
00131 Node (Invalid) { id = -1; }
00132 bool operator==(const Node node) const {return id == node.id;}
00133 bool operator!=(const Node node) const {return id != node.id;}
00134 bool operator<(const Node node) const {return id < node.id;}
00135 };
00136
00137
00138
00139 class Edge {
00140 friend class FullGraphBase;
00141
00142 protected:
00143 int id;
00144
00145 Edge(int _id) : id(_id) {}
00146
00147 Edge(const FullGraphBase& _graph, int source, int target)
00148 : id(_graph.NodeNum * target+source) {}
00149 public:
00150 Edge() { }
00151 Edge (Invalid) { id = -1; }
00152 bool operator==(const Edge edge) const {return id == edge.id;}
00153 bool operator!=(const Edge edge) const {return id != edge.id;}
00154 bool operator<(const Edge edge) const {return id < edge.id;}
00155 };
00156
00157 void first(Node& node) const {
00158 node.id = NodeNum-1;
00159 }
00160
00161 static void next(Node& node) {
00162 --node.id;
00163 }
00164
00165 void first(Edge& edge) const {
00166 edge.id = EdgeNum-1;
00167 }
00168
00169 static void next(Edge& edge) {
00170 --edge.id;
00171 }
00172
00173 void firstOut(Edge& edge, const Node& node) const {
00174 edge.id = EdgeNum + node.id - NodeNum;
00175 }
00176
00177 void nextOut(Edge& edge) const {
00178 edge.id -= NodeNum;
00179 if (edge.id < 0) edge.id = -1;
00180 }
00181
00182 void firstIn(Edge& edge, const Node& node) const {
00183 edge.id = node.id * NodeNum;
00184 }
00185
00186 void nextIn(Edge& edge) const {
00187 ++edge.id;
00188 if (edge.id % NodeNum == 0) edge.id = -1;
00189 }
00190
00191 };
00192
00193
00194 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
00195 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
00196 typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase;
00197
00199
00208 class FullGraph : public MappableFullGraphBase {
00209 public:
00210
00211 FullGraph(int n) { construct(n); }
00212 };
00213
00214
00215
00216 class UndirFullGraphBase {
00217 int NodeNum;
00218 int EdgeNum;
00219 public:
00220
00221 typedef UndirFullGraphBase Graph;
00222
00223 class Node;
00224 class Edge;
00225
00226 public:
00227
00228 UndirFullGraphBase() {}
00229
00230
00232 void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; }
00234
00235
00236
00237 typedef True NodeNumTag;
00238 typedef True EdgeNumTag;
00239
00241 int nodeNum() const { return NodeNum; }
00243 int edgeNum() const { return EdgeNum; }
00244
00246
00249 int maxId(Node = INVALID) const { return NodeNum-1; }
00251
00254 int maxId(Edge = INVALID) const { return EdgeNum-1; }
00255
00256 Node source(Edge e) const {
00258 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;
00259 }
00260
00261 Node target(Edge e) const {
00262 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00263 return e.id - (source) * (source - 1) / 2;
00264 }
00265
00266
00268
00275
00276 static int id(Node v) { return v.id; }
00278
00285 static int id(Edge e) { return e.id; }
00286
00288
00295 Edge findEdge(Node u,Node v, Edge prev = INVALID)
00296 {
00297 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
00298 }
00299
00300
00301 class Node {
00302 friend class UndirFullGraphBase;
00303
00304 protected:
00305 int id;
00306 Node(int _id) { id = _id;}
00307 public:
00308 Node() {}
00309 Node (Invalid) { id = -1; }
00310 bool operator==(const Node node) const {return id == node.id;}
00311 bool operator!=(const Node node) const {return id != node.id;}
00312 bool operator<(const Node node) const {return id < node.id;}
00313 };
00314
00315
00316
00317 class Edge {
00318 friend class UndirFullGraphBase;
00319
00320 protected:
00321 int id;
00322
00323 Edge(int _id) : id(_id) {}
00324
00325 Edge(const UndirFullGraphBase& _graph, int source, int target)
00326 : id(_graph.NodeNum * target+source) {}
00327 public:
00328 Edge() { }
00329 Edge (Invalid) { id = -1; }
00330 bool operator==(const Edge edge) const {return id == edge.id;}
00331 bool operator!=(const Edge edge) const {return id != edge.id;}
00332 bool operator<(const Edge edge) const {return id < edge.id;}
00333 };
00334
00335 void first(Node& node) const {
00336 node.id = NodeNum-1;
00337 }
00338
00339 static void next(Node& node) {
00340 --node.id;
00341 }
00342
00343 void first(Edge& edge) const {
00344 edge.id = EdgeNum-1;
00345 }
00346
00347 static void next(Edge& edge) {
00348 --edge.id;
00349 }
00350
00351 void firstOut(Edge& edge, const Node& node) const {
00352 edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1;
00353 }
00354
00356 void nextOut(Edge& e) const {
00357 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00358 int target = e.id - (source) * (source - 1) / 2;
00359 ++target;
00360 e.id = target < source ? source * (source - 1) / 2 + target : -1;
00361 }
00362
00363 void firstIn(Edge& edge, const Node& node) const {
00364 edge.id = node.id * (node.id + 1) / 2 - 1;
00365 }
00366
00367 void nextIn(Edge& e) const {
00368 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
00369 int target = e.id - (source) * (source - 1) / 2; ++target;
00370 ++source;
00371 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1;
00372 }
00373
00374 };
00375
00377
00378
00379
00381
00382 }
00383
00384
00385 #endif //LEMON_FULL_GRAPH_H