00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_EDGE_SET_H
00020 #define LEMON_EDGE_SET_H
00021
00027
00028 namespace lemon {
00029
00030 template <typename _Graph>
00031 class ListEdgeSetBase {
00032 public:
00033
00034 typedef _Graph Graph;
00035 typedef typename Graph::Node Node;
00036 typedef typename Graph::NodeIt NodeIt;
00037
00038 protected:
00039
00040 struct NodeT {
00041 int first_out, first_in;
00042 NodeT() : first_out(-1), first_in(-1) {}
00043 };
00044
00045 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
00046
00047 NodesImplBase* nodes;
00048
00049 struct EdgeT {
00050 Node source, target;
00051 int next_out, next_in;
00052 int prev_out, prev_in;
00053 EdgeT() : prev_out(-1), prev_in(-1) {}
00054 };
00055
00056 std::vector<EdgeT> edges;
00057
00058 int first_edge;
00059 int first_free_edge;
00060
00061 const Graph* graph;
00062
00063 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
00064 graph = &_graph;
00065 nodes = &_nodes;
00066 }
00067
00068 public:
00069
00070 class Edge {
00071 friend class ListEdgeSetBase<Graph>;
00072 protected:
00073 Edge(int _id) : id(_id) {}
00074 int id;
00075 public:
00076 Edge() {}
00077 Edge(Invalid) : id(-1) {}
00078 bool operator==(const Edge& edge) const { return id == edge.id; }
00079 bool operator!=(const Edge& edge) const { return id != edge.id; }
00080 bool operator<(const Edge& edge) const { return id < edge.id; }
00081 };
00082
00083 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
00084
00085 Edge addEdge(const Node& source, const Node& target) {
00086 int n;
00087 if (first_free_edge == -1) {
00088 n = edges.size();
00089 edges.push_back(EdgeT());
00090 } else {
00091 n = first_free_edge;
00092 first_free_edge = edges[first_free_edge].next_in;
00093 }
00094 edges[n].next_in = (*nodes)[target].first_in;
00095 (*nodes)[target].first_in = n;
00096 edges[n].next_out = (*nodes)[source].first_out;
00097 (*nodes)[source].first_out = n;
00098 edges[n].source = source;
00099 edges[n].target = target;
00100 return Edge(n);
00101 }
00102
00103 void erase(const Edge& edge) {
00104 int n = edge.id;
00105 if (edges[n].prev_in != -1) {
00106 edges[edges[n].prev_in].next_in = edges[n].next_in;
00107 } else {
00108 (*nodes)[edges[n].target].first_in = edges[n].next_in;
00109 }
00110 if (edges[n].next_in != -1) {
00111 edges[edges[n].next_in].prev_in = edges[n].prev_in;
00112 }
00113
00114 if (edges[n].prev_out != -1) {
00115 edges[edges[n].prev_out].next_out = edges[n].next_out;
00116 } else {
00117 (*nodes)[edges[n].source].first_out = edges[n].next_out;
00118 }
00119 if (edges[n].next_out != -1) {
00120 edges[edges[n].next_out].prev_out = edges[n].prev_out;
00121 }
00122
00123 }
00124
00125 void clear() {
00126 edges.clear();
00127 first_edge = -1;
00128 first_free_edge = -1;
00129 }
00130
00131 void first(Node& node) const {
00132 graph->first(node);
00133 }
00134
00135 void next(Node& node) const {
00136 graph->next(node);
00137 }
00138
00139 void first(Edge& edge) const {
00140 Node node;
00141 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
00142 next(node));
00143 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
00144 }
00145
00146 void next(Edge& edge) const {
00147 if (edges[edge.id].next_in != -1) {
00148 edge.id = edges[edge.id].next_in;
00149 } else {
00150 Node node = edges[edge.id].target;
00151 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
00152 next(node));
00153 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
00154 }
00155 }
00156
00157 void firstOut(Edge& edge, const Node& node) const {
00158 edge.id = (*nodes)[node].first_out;
00159 }
00160
00161 void nextOut(Edge& edge) const {
00162 edge.id = edges[edge.id].next_out;
00163 }
00164
00165 void firstIn(Edge& edge, const Node& node) const {
00166 edge.id = (*nodes)[node].first_in;
00167 }
00168
00169 void nextIn(Edge& edge) const {
00170 edge.id = edges[edge.id].next_in;
00171 }
00172
00173 int id(const Node& node) const { return graph->id(node); }
00174 int id(const Edge& edge) const { return edge.id; }
00175
00176 Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
00177 Edge edgeFromId(int id) const { return Edge(id); }
00178
00179 int maxNodeId() const { return graph->maxId(Node()); };
00180 int maxEdgeId() const { return edges.size() - 1; }
00181
00182 Node source(const Edge& edge) const { return edges[edge.id].source;}
00183 Node target(const Edge& edge) const { return edges[edge.id].target;}
00184
00185 template <typename _Value>
00186 class NodeMap : public Graph::template NodeMap<_Value> {
00187 public:
00188 typedef typename _Graph::template NodeMap<_Value> Parent;
00189 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
00190 : Parent(*edgeset.graph) { }
00191 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
00192 : Parent(*edgeset.graph, value) { }
00193 };
00194
00195 };
00196
00212 template <typename _Graph>
00213 class ListEdgeSet :
00214 public ErasableEdgeSetExtender<
00215 ClearableEdgeSetExtender<
00216 ExtendableEdgeSetExtender<
00217 MappableEdgeSetExtender<
00218 IterableGraphExtender<
00219 AlterableEdgeSetExtender<
00220 GraphExtender<
00221 ListEdgeSetBase<_Graph> > > > > > > > {
00222
00223 public:
00224
00225 typedef ErasableEdgeSetExtender<
00226 ClearableEdgeSetExtender<
00227 ExtendableEdgeSetExtender<
00228 MappableEdgeSetExtender<
00229 IterableGraphExtender<
00230 AlterableEdgeSetExtender<
00231 GraphExtender<
00232 ListEdgeSetBase<_Graph> > > > > > > > Parent;
00233
00234 typedef typename Parent::Node Node;
00235 typedef typename Parent::Edge Edge;
00236
00237 typedef _Graph Graph;
00238
00239
00240 typedef typename Parent::NodesImplBase NodesImplBase;
00241
00242 void eraseNode(const Node& node) {
00243 Edge edge;
00244 Parent::firstOut(edge, node);
00245 while (edge != INVALID ) {
00246 erase(edge);
00247 Parent::firstOut(edge, node);
00248 }
00249
00250 Parent::firstIn(edge, node);
00251 while (edge != INVALID ) {
00252 erase(edge);
00253 Parent::firstIn(edge, node);
00254 }
00255 }
00256
00257 void clearNodes() {
00258 Parent::clear();
00259 }
00260
00261 class NodesImpl : public NodesImplBase {
00262 public:
00263 typedef NodesImplBase Parent;
00264
00265 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
00266 : Parent(graph), _edgeset(edgeset) {}
00267
00268 protected:
00269
00270 virtual void erase(const Node& node) {
00271 _edgeset.eraseNode(node);
00272 Parent::erase(node);
00273 }
00274 virtual void clear() {
00275 _edgeset.clearNodes();
00276 Parent::clear();
00277 }
00278
00279 private:
00280 ListEdgeSet& _edgeset;
00281 };
00282
00283 NodesImpl nodes;
00284
00285 public:
00286
00290 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
00291 Parent::initalize(graph, nodes);
00292 }
00293
00294 };
00295
00311 template <typename _Graph>
00312 class ListUEdgeSet :
00313 public ErasableUEdgeSetExtender<
00314 ClearableUEdgeSetExtender<
00315 ExtendableUEdgeSetExtender<
00316 MappableUEdgeSetExtender<
00317 IterableUGraphExtender<
00318 AlterableUEdgeSetExtender<
00319 UGraphExtender<
00320 ListEdgeSetBase<_Graph> > > > > > > > {
00321
00322 public:
00323
00324 typedef ErasableUEdgeSetExtender<
00325 ClearableUEdgeSetExtender<
00326 ExtendableUEdgeSetExtender<
00327 MappableUEdgeSetExtender<
00328 IterableUGraphExtender<
00329 AlterableUEdgeSetExtender<
00330 UGraphExtender<
00331 ListEdgeSetBase<_Graph> > > > > > > > Parent;
00332
00333 typedef typename Parent::Node Node;
00334 typedef typename Parent::Edge Edge;
00335
00336 typedef _Graph Graph;
00337
00338
00339 typedef typename Parent::NodesImplBase NodesImplBase;
00340
00341 void eraseNode(const Node& node) {
00342 Edge edge;
00343 Parent::firstOut(edge, node);
00344 while (edge != INVALID ) {
00345 erase(edge);
00346 Parent::firstOut(edge, node);
00347 }
00348
00349 }
00350
00351 void clearNodes() {
00352 Parent::clear();
00353 }
00354
00355 class NodesImpl : public NodesImplBase {
00356 public:
00357 typedef NodesImplBase Parent;
00358
00359 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
00360 : Parent(graph), _edgeset(edgeset) {}
00361
00362 protected:
00363
00364 virtual void erase(const Node& node) {
00365 _edgeset.eraseNode(node);
00366 Parent::erase(node);
00367 }
00368 virtual void erase(const std::vector<Node>& nodes) {
00369 for (int i = 0; i < nodes.size(); ++i) {
00370 _edgeset.eraseNode(nodes[i]);
00371 }
00372 Parent::erase(nodes);
00373 }
00374 virtual void clear() {
00375 _edgeset.clearNodes();
00376 Parent::clear();
00377 }
00378
00379 private:
00380 ListUEdgeSet& _edgeset;
00381 };
00382
00383 NodesImpl nodes;
00384
00385 public:
00386
00390 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
00391 Parent::initalize(graph, nodes);
00392 }
00393
00394 };
00395
00396 }
00397
00398 #endif