The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_EDGE_SET_H
20 #define LEMON_EDGE_SET_H
23 #include <lemon/bits/default_map.h>
24 #include <lemon/bits/edge_set_extender.h>
28 /// \brief EdgeSet classes.
30 /// Graphs which use another graph's node-set as own.
34 template <typename _Graph>
35 class ListEdgeSetBase {
39 typedef typename Graph::Node Node;
40 typedef typename Graph::NodeIt NodeIt;
45 int first_out, first_in;
46 NodeT() : first_out(-1), first_in(-1) {}
49 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
55 int next_out, next_in;
56 int prev_out, prev_in;
57 EdgeT() : prev_out(-1), prev_in(-1) {}
60 std::vector<EdgeT> edges;
67 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
75 friend class ListEdgeSetBase<Graph>;
77 Edge(int _id) : id(_id) {}
81 Edge(Invalid) : id(-1) {}
82 bool operator==(const Edge& edge) const { return id == edge.id; }
83 bool operator!=(const Edge& edge) const { return id != edge.id; }
84 bool operator<(const Edge& edge) const { return id < edge.id; }
87 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
89 Edge addEdge(const Node& source, const Node& target) {
91 if (first_free_edge == -1) {
93 edges.push_back(EdgeT());
96 first_free_edge = edges[first_free_edge].next_in;
98 edges[n].next_in = (*nodes)[target].first_in;
99 if ((*nodes)[target].first_in != -1) {
100 edges[(*nodes)[target].first_in].prev_in = n;
102 (*nodes)[target].first_in = n;
103 edges[n].next_out = (*nodes)[source].first_out;
104 if ((*nodes)[source].first_out != -1) {
105 edges[(*nodes)[source].first_out].prev_out = n;
107 (*nodes)[source].first_out = n;
108 edges[n].source = source;
109 edges[n].target = target;
113 void erase(const Edge& edge) {
115 if (edges[n].prev_in != -1) {
116 edges[edges[n].prev_in].next_in = edges[n].next_in;
118 (*nodes)[edges[n].target].first_in = edges[n].next_in;
120 if (edges[n].next_in != -1) {
121 edges[edges[n].next_in].prev_in = edges[n].prev_in;
124 if (edges[n].prev_out != -1) {
125 edges[edges[n].prev_out].next_out = edges[n].next_out;
127 (*nodes)[edges[n].source].first_out = edges[n].next_out;
129 if (edges[n].next_out != -1) {
130 edges[edges[n].next_out].prev_out = edges[n].prev_out;
137 for (first(node); node != INVALID; next(node)) {
138 (*nodes)[node].first_in = -1;
139 (*nodes)[node].first_out = -1;
143 first_free_edge = -1;
146 void first(Node& node) const {
150 void next(Node& node) const {
154 void first(Edge& edge) const {
156 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
158 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
161 void next(Edge& edge) const {
162 if (edges[edge.id].next_in != -1) {
163 edge.id = edges[edge.id].next_in;
165 Node node = edges[edge.id].target;
166 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
168 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
172 void firstOut(Edge& edge, const Node& node) const {
173 edge.id = (*nodes)[node].first_out;
176 void nextOut(Edge& edge) const {
177 edge.id = edges[edge.id].next_out;
180 void firstIn(Edge& edge, const Node& node) const {
181 edge.id = (*nodes)[node].first_in;
184 void nextIn(Edge& edge) const {
185 edge.id = edges[edge.id].next_in;
188 int id(const Node& node) const { return graph->id(node); }
189 int id(const Edge& edge) const { return edge.id; }
191 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
192 Edge edgeFromId(int id) const { return Edge(id); }
194 int maxNodeId() const { return graph->maxNodeId(); };
195 int maxEdgeId() const { return edges.size() - 1; }
197 Node source(const Edge& edge) const { return edges[edge.id].source;}
198 Node target(const Edge& edge) const { return edges[edge.id].target;}
200 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
202 NodeNotifier& getNotifier(Node) const {
203 return graph->getNotifier(Node());
206 template <typename _Value>
207 class NodeMap : public Graph::template NodeMap<_Value> {
209 typedef typename _Graph::template NodeMap<_Value> Parent;
210 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
211 : Parent(*edgeset.graph) { }
212 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
213 : Parent(*edgeset.graph, value) { }
218 /// \ingroup semi_adaptors
220 /// \brief Graph using a node set of another graph and an
223 /// This structure can be used to establish another graph over a node set
224 /// of an existing one. The node iterator will go through the nodes of the
227 /// \param _Graph The type of the graph which shares its node set with
228 /// this class. Its interface must conform to the \ref concept::StaticGraph
229 /// "StaticGraph" concept.
231 /// In the edge extension and removing it conforms to the
232 /// \ref concept::ErasableGraph "ErasableGraph" concept.
233 template <typename _Graph>
234 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
238 typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
240 typedef typename Parent::Node Node;
241 typedef typename Parent::Edge Edge;
243 typedef _Graph Graph;
246 typedef typename Parent::NodesImplBase NodesImplBase;
248 void eraseNode(const Node& node) {
250 Parent::firstOut(edge, node);
251 while (edge != INVALID ) {
253 Parent::firstOut(edge, node);
256 Parent::firstIn(edge, node);
257 while (edge != INVALID ) {
259 Parent::firstIn(edge, node);
267 class NodesImpl : public NodesImplBase {
269 typedef NodesImplBase Parent;
271 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
272 : Parent(graph), _edgeset(edgeset) {}
274 virtual ~NodesImpl() {}
278 virtual void erase(const Node& node) {
279 _edgeset.eraseNode(node);
282 virtual void erase(const std::vector<Node>& nodes) {
283 for (int i = 0; i < (int)nodes.size(); ++i) {
284 _edgeset.eraseNode(nodes[i]);
286 Parent::erase(nodes);
288 virtual void clear() {
289 _edgeset.clearNodes();
294 ListEdgeSet& _edgeset;
301 /// \brief Constructor of the adaptor.
303 /// Constructor of the adaptor.
304 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
305 Parent::initalize(graph, nodes);
310 /// \ingroup semi_adaptors
312 /// \brief Graph using a node set of another graph and an
315 /// This structure can be used to establish another graph over a node set
316 /// of an existing one. The node iterator will go through the nodes of the
319 /// \param _Graph The type of the graph which shares its node set with
320 /// this class. Its interface must conform to the \ref concept::StaticGraph
321 /// "StaticGraph" concept.
323 /// In the edge extension and removing it conforms to the
324 /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
325 template <typename _Graph>
327 : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
331 typedef UEdgeSetExtender<UGraphBaseExtender<
332 ListEdgeSetBase<_Graph> > > Parent;
334 typedef typename Parent::Node Node;
335 typedef typename Parent::Edge Edge;
337 typedef _Graph Graph;
340 typedef typename Parent::NodesImplBase NodesImplBase;
342 void eraseNode(const Node& node) {
344 Parent::firstOut(edge, node);
345 while (edge != INVALID ) {
347 Parent::firstOut(edge, node);
356 class NodesImpl : public NodesImplBase {
358 typedef NodesImplBase Parent;
360 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
361 : Parent(graph), _edgeset(edgeset) {}
363 virtual ~NodesImpl() {}
367 virtual void erase(const Node& node) {
368 _edgeset.eraseNode(node);
371 virtual void erase(const std::vector<Node>& nodes) {
372 for (int i = 0; i < (int)nodes.size(); ++i) {
373 _edgeset.eraseNode(nodes[i]);
375 Parent::erase(nodes);
377 virtual void clear() {
378 _edgeset.clearNodes();
383 ListUEdgeSet& _edgeset;
390 /// \brief Constructor of the adaptor.
392 /// Constructor of the adaptor.
393 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
394 Parent::initalize(graph, nodes);
399 template <typename _Graph>
400 class SmartEdgeSetBase {
403 typedef _Graph Graph;
404 typedef typename Graph::Node Node;
405 typedef typename Graph::NodeIt NodeIt;
410 int first_out, first_in;
411 NodeT() : first_out(-1), first_in(-1) {}
414 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
416 NodesImplBase* nodes;
420 int next_out, next_in;
424 std::vector<EdgeT> edges;
428 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
436 friend class SmartEdgeSetBase<Graph>;
438 Edge(int _id) : id(_id) {}
442 Edge(Invalid) : id(-1) {}
443 bool operator==(const Edge& edge) const { return id == edge.id; }
444 bool operator!=(const Edge& edge) const { return id != edge.id; }
445 bool operator<(const Edge& edge) const { return id < edge.id; }
448 SmartEdgeSetBase() {}
450 Edge addEdge(const Node& source, const Node& target) {
451 int n = edges.size();
452 edges.push_back(EdgeT());
453 edges[n].next_in = (*nodes)[target].first_in;
454 (*nodes)[target].first_in = n;
455 edges[n].next_out = (*nodes)[source].first_out;
456 (*nodes)[source].first_out = n;
457 edges[n].source = source;
458 edges[n].target = target;
464 for (first(node); node != INVALID; next(node)) {
465 (*nodes)[node].first_in = -1;
466 (*nodes)[node].first_out = -1;
471 void first(Node& node) const {
475 void next(Node& node) const {
479 void first(Edge& edge) const {
480 edge.id = edges.size() - 1;
483 void next(Edge& edge) const {
487 void firstOut(Edge& edge, const Node& node) const {
488 edge.id = (*nodes)[node].first_out;
491 void nextOut(Edge& edge) const {
492 edge.id = edges[edge.id].next_out;
495 void firstIn(Edge& edge, const Node& node) const {
496 edge.id = (*nodes)[node].first_in;
499 void nextIn(Edge& edge) const {
500 edge.id = edges[edge.id].next_in;
503 int id(const Node& node) const { return graph->id(node); }
504 int id(const Edge& edge) const { return edge.id; }
506 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
507 Edge edgeFromId(int id) const { return Edge(id); }
509 int maxNodeId() const { return graph->maxNodeId(); };
510 int maxEdgeId() const { return edges.size() - 1; }
512 Node source(const Edge& edge) const { return edges[edge.id].source;}
513 Node target(const Edge& edge) const { return edges[edge.id].target;}
515 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
517 NodeNotifier& getNotifier(Node) const {
518 return graph->getNotifier(Node());
521 template <typename _Value>
522 class NodeMap : public Graph::template NodeMap<_Value> {
524 typedef typename _Graph::template NodeMap<_Value> Parent;
525 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
526 : Parent(*edgeset.graph) { }
527 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
528 : Parent(*edgeset.graph, value) { }
534 /// \ingroup semi_adaptors
536 /// \brief Graph using a node set of another graph and an
539 /// This structure can be used to establish another graph over a node set
540 /// of an existing one. The node iterator will go through the nodes of the
543 /// \param _Graph The type of the graph which shares its node set with
544 /// this class. Its interface must conform to the \ref concept::StaticGraph
545 /// "StaticGraph" concept.
547 /// In the edge extension and removing it conforms to the
548 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
549 template <typename _Graph>
550 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
554 typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
556 typedef typename Parent::Node Node;
557 typedef typename Parent::Edge Edge;
559 typedef _Graph Graph;
561 class UnsupportedOperation : public LogicError {
563 virtual const char* exceptionName() const {
564 return "lemon::SmartEdgeSet::UnsupportedOperation";
572 typedef typename Parent::NodesImplBase NodesImplBase;
574 void eraseNode(const Node&) {
575 throw UnsupportedOperation();
582 class NodesImpl : public NodesImplBase {
584 typedef NodesImplBase Parent;
586 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
587 : Parent(graph), _edgeset(edgeset) {}
589 virtual ~NodesImpl() {}
593 virtual void erase(const Node& node) {
594 _edgeset.eraseNode(node);
597 virtual void erase(const std::vector<Node>& nodes) {
598 for (int i = 0; i < (int)nodes.size(); ++i) {
599 _edgeset.eraseNode(nodes[i]);
601 Parent::erase(nodes);
603 virtual void clear() {
604 _edgeset.clearNodes();
609 SmartEdgeSet& _edgeset;
616 /// \brief Constructor of the adaptor.
618 /// Constructor of the adaptor.
619 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
620 Parent::initalize(graph, nodes);
625 /// \ingroup semi_adaptors
627 /// \brief Graph using a node set of another graph and an
630 /// This structure can be used to establish another graph over a node set
631 /// of an existing one. The node iterator will go through the nodes of the
634 /// \param _Graph The type of the graph which shares its node set with
635 /// this class. Its interface must conform to the \ref concept::StaticGraph
636 /// "StaticGraph" concept.
638 /// In the edge extension and removing it conforms to the
639 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
640 template <typename _Graph>
642 : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
646 typedef UEdgeSetExtender<UGraphBaseExtender<
647 SmartEdgeSetBase<_Graph> > > Parent;
649 typedef typename Parent::Node Node;
650 typedef typename Parent::Edge Edge;
652 typedef _Graph Graph;
654 class UnsupportedOperation : public LogicError {
656 virtual const char* exceptionName() const {
657 return "lemon::SmartUEdgeSet::UnsupportedOperation";
663 typedef typename Parent::NodesImplBase NodesImplBase;
665 void eraseNode(const Node&) {
666 throw UnsupportedOperation();
673 class NodesImpl : public NodesImplBase {
675 typedef NodesImplBase Parent;
677 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
678 : Parent(graph), _edgeset(edgeset) {}
680 virtual ~NodesImpl() {}
684 virtual void erase(const Node& node) {
685 _edgeset.eraseNode(node);
688 virtual void erase(const std::vector<Node>& nodes) {
689 for (int i = 0; i < (int)nodes.size(); ++i) {
690 _edgeset.eraseNode(nodes[i]);
692 Parent::erase(nodes);
694 virtual void clear() {
695 _edgeset.clearNodes();
700 SmartUEdgeSet& _edgeset;
707 /// \brief Constructor of the adaptor.
709 /// Constructor of the adaptor.
710 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
711 Parent::initalize(graph, nodes);