00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_SMART_GRAPH_H
00018 #define LEMON_SMART_GRAPH_H
00019
00023
00024 #include <vector>
00025
00026 #include <lemon/invalid.h>
00027
00028 #include <lemon/clearable_graph_extender.h>
00029 #include <lemon/extendable_graph_extender.h>
00030 #include <lemon/iterable_graph_extender.h>
00031 #include <lemon/alteration_notifier.h>
00032 #include <lemon/default_map.h>
00033
00034 #include <lemon/undir_graph_extender.h>
00035
00036 #include <lemon/utility.h>
00037
00038 namespace lemon {
00039
00040 class SmartGraph;
00042
00045 class SmartGraphBase {
00046
00047 friend class SmatGraph;
00048
00049 protected:
00050 struct NodeT
00051 {
00052 int first_in,first_out;
00053 NodeT() : first_in(-1), first_out(-1) {}
00054 };
00055 struct EdgeT
00056 {
00057 int target, source, next_in, next_out;
00058
00059 EdgeT() : next_in(-1), next_out(-1) {}
00060 };
00061
00062 std::vector<NodeT> nodes;
00063
00064 std::vector<EdgeT> edges;
00065
00066
00067 public:
00068
00069 typedef SmartGraphBase Graph;
00070
00071 class Node;
00072 class Edge;
00073
00074
00075 public:
00076
00077 SmartGraphBase() : nodes(), edges() { }
00078 SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
00079
00080 typedef True NodeNumTag;
00081 typedef True EdgeNumTag;
00082
00084 int nodeNum() const { return nodes.size(); }
00086 int edgeNum() const { return edges.size(); }
00087
00089
00092 int maxId(Node = INVALID) const { return nodes.size()-1; }
00094
00097 int maxId(Edge = INVALID) const { return edges.size()-1; }
00098
00099 Node source(Edge e) const { return edges[e.n].source; }
00100 Node target(Edge e) const { return edges[e.n].target; }
00101
00103
00110 static int id(Node v) { return v.n; }
00112
00119 static int id(Edge e) { return e.n; }
00120
00121 static Node fromId(int id, Node) { return Node(id);}
00122
00123 static Edge fromId(int id, Edge) { return Edge(id);}
00124
00125 Node addNode() {
00126 Node n; n.n=nodes.size();
00127 nodes.push_back(NodeT());
00128 return n;
00129 }
00130
00131 Edge addEdge(Node u, Node v) {
00132 Edge e; e.n=edges.size(); edges.push_back(EdgeT());
00133 edges[e.n].source=u.n; edges[e.n].target=v.n;
00134 edges[e.n].next_out=nodes[u.n].first_out;
00135 edges[e.n].next_in=nodes[v.n].first_in;
00136 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
00137
00138 return e;
00139 }
00140
00141 void clear() {
00142 edges.clear();
00143 nodes.clear();
00144 }
00145
00146
00147 class Node {
00148 friend class SmartGraphBase;
00149 friend class SmartGraph;
00150
00151 protected:
00152 int n;
00155 Node(int nn) {n=nn;}
00156 public:
00157 Node() {}
00158 Node (Invalid) { n=-1; }
00159 bool operator==(const Node i) const {return n==i.n;}
00160 bool operator!=(const Node i) const {return n!=i.n;}
00161 bool operator<(const Node i) const {return n<i.n;}
00162 };
00163
00164
00165 class Edge {
00166 friend class SmartGraphBase;
00167 friend class SmartGraph;
00168
00169 protected:
00170 int n;
00173 Edge(int nn) {n=nn;}
00174 public:
00175 Edge() { }
00176 Edge (Invalid) { n=-1; }
00177 bool operator==(const Edge i) const {return n==i.n;}
00178 bool operator!=(const Edge i) const {return n!=i.n;}
00179 bool operator<(const Edge i) const {return n<i.n;}
00180 };
00181
00182 void first(Node& node) const {
00183 node.n = nodes.size() - 1;
00184 }
00185
00186 static void next(Node& node) {
00187 --node.n;
00188 }
00189
00190 void first(Edge& edge) const {
00191 edge.n = edges.size() - 1;
00192 }
00193
00194 static void next(Edge& edge) {
00195 --edge.n;
00196 }
00197
00198 void firstOut(Edge& edge, const Node& node) const {
00199 edge.n = nodes[node.n].first_out;
00200 }
00201
00202 void nextOut(Edge& edge) const {
00203 edge.n = edges[edge.n].next_out;
00204 }
00205
00206 void firstIn(Edge& edge, const Node& node) const {
00207 edge.n = nodes[node.n].first_in;
00208 }
00209
00210 void nextIn(Edge& edge) const {
00211 edge.n = edges[edge.n].next_in;
00212 }
00213
00214 Edge _findEdge(Node u,Node v, Edge prev = INVALID)
00215 {
00216 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
00217 while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out;
00218 prev.n=e;
00219 return prev;
00220 }
00221
00222 };
00223
00224 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
00225 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
00226 typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
00227 typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
00228 typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
00229
00232
00234
00244 class SmartGraph : public ClearableSmartGraphBase {
00245 public:
00247
00262 Edge findEdge(Node u,Node v, Edge prev = INVALID)
00263 {
00264 return _findEdge(u,v,prev);
00265 }
00266
00267 class SnapShot;
00268 friend class SnapShot;
00269
00270 protected:
00271 void restoreSnapShot(const SnapShot &s)
00272 {
00273 while(s.edge_num>edges.size()) {
00274 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
00275 nodes[edges.back().target].first_in=edges.back().next_in;
00276 nodes[edges.back().source].first_out=edges.back().next_out;
00277 edges.pop_back();
00278 }
00279
00280 while(s.node_num>nodes.size()) {
00281 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
00282 nodes.pop_back();
00283 }
00284 }
00285
00286 public:
00288
00297 class SnapShot
00298 {
00299 SmartGraph *g;
00300 protected:
00301 friend class SmartGraph;
00302 unsigned int node_num;
00303 unsigned int edge_num;
00304 public:
00306
00310 SnapShot() : g(0) {}
00312
00315 SnapShot(SmartGraph &_g) :g(&_g) {
00316 node_num=g->nodes.size();
00317 edge_num=g->edges.size();
00318 }
00319
00321
00327 void save(SmartGraph &_g)
00328 {
00329 g=&_g;
00330 node_num=g->nodes.size();
00331 edge_num=g->edges.size();
00332 }
00333
00335
00344
00345 void restore()
00346 {
00347 g->restoreSnapShot(*this);
00348 }
00349 };
00350 };
00351
00352
00353
00354
00355 typedef ClearableUndirGraphExtender<
00356 ExtendableUndirGraphExtender<
00357 MappableUndirGraphExtender<
00358 IterableUndirGraphExtender<
00359 AlterableUndirGraphExtender<
00360 UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;
00361
00363
00374 class UndirSmartGraph : public UndirSmartGraphBase {
00375 };
00376
00377
00379 }
00380
00381
00382 #endif //LEMON_SMART_GRAPH_H