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
22 template <typename Base>
23 class EdgeSetExtender : public Base {
27 typedef EdgeSetExtender Graph;
31 typedef typename Parent::Node Node;
32 typedef typename Parent::Edge Edge;
34 int maxId(Node) const {
35 return Parent::maxNodeId();
38 int maxId(Edge) const {
39 return Parent::maxEdgeId();
42 Node fromId(int id, Node) const {
43 return Parent::nodeFromId(id);
46 Edge fromId(int id, Edge) const {
47 return Parent::edgeFromId(id);
50 Node oppositeNode(const Node &n, const Edge &e) const {
51 if (n == Parent::source(e))
52 return Parent::target(e);
53 else if(n==Parent::target(e))
54 return Parent::source(e);
60 // Alteration notifier extensions
62 /// The edge observer registry.
63 typedef AlterationNotifier<Edge> EdgeNotifier;
67 mutable EdgeNotifier edge_notifier;
71 using Parent::getNotifier;
73 /// \brief Gives back the edge alteration notifier.
75 /// Gives back the edge alteration notifier.
76 EdgeNotifier& getNotifier(Edge) const {
80 // Iterable extensions
82 class NodeIt : public Node {
88 NodeIt(Invalid i) : Node(i) { }
90 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
91 _graph.first(*static_cast<Node*>(this));
94 NodeIt(const Graph& _graph, const Node& node)
95 : Node(node), graph(&_graph) {}
97 NodeIt& operator++() {
105 class EdgeIt : public Edge {
111 EdgeIt(Invalid i) : Edge(i) { }
113 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
114 _graph.first(*static_cast<Edge*>(this));
117 EdgeIt(const Graph& _graph, const Edge& e) :
118 Edge(e), graph(&_graph) { }
120 EdgeIt& operator++() {
128 class OutEdgeIt : public Edge {
134 OutEdgeIt(Invalid i) : Edge(i) { }
136 OutEdgeIt(const Graph& _graph, const Node& node)
138 _graph.firstOut(*this, node);
141 OutEdgeIt(const Graph& _graph, const Edge& edge)
142 : Edge(edge), graph(&_graph) {}
144 OutEdgeIt& operator++() {
145 graph->nextOut(*this);
152 class InEdgeIt : public Edge {
158 InEdgeIt(Invalid i) : Edge(i) { }
160 InEdgeIt(const Graph& _graph, const Node& node)
162 _graph.firstIn(*this, node);
165 InEdgeIt(const Graph& _graph, const Edge& edge) :
166 Edge(edge), graph(&_graph) {}
168 InEdgeIt& operator++() {
169 graph->nextIn(*this);
175 /// \brief Base node of the iterator
177 /// Returns the base node (ie. the source in this case) of the iterator
178 Node baseNode(const OutEdgeIt &e) const {
179 return Parent::source((Edge)e);
181 /// \brief Running node of the iterator
183 /// Returns the running node (ie. the target in this case) of the
185 Node runningNode(const OutEdgeIt &e) const {
186 return Parent::target((Edge)e);
189 /// \brief Base node of the iterator
191 /// Returns the base node (ie. the target in this case) of the iterator
192 Node baseNode(const InEdgeIt &e) const {
193 return Parent::target((Edge)e);
195 /// \brief Running node of the iterator
197 /// Returns the running node (ie. the source in this case) of the
199 Node runningNode(const InEdgeIt &e) const {
200 return Parent::source((Edge)e);
205 // Mappable extension
207 template <typename _Value>
209 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
211 typedef EdgeSetExtender Graph;
212 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
214 EdgeMap(const Graph& _g)
216 EdgeMap(const Graph& _g, const _Value& _v)
219 EdgeMap& operator=(const EdgeMap& cmap) {
220 return operator=<EdgeMap>(cmap);
223 template <typename CMap>
224 EdgeMap& operator=(const CMap& cmap) {
225 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
226 const typename Parent::Graph* graph = Parent::getGraph();
228 for (graph->first(it); it != INVALID; graph->next(it)) {
229 Parent::set(it, cmap[it]);
236 // Alteration extension
238 Edge addEdge(const Node& from, const Node& to) {
239 Edge edge = Parent::addEdge(from, to);
240 getNotifier(Edge()).add(edge);
245 getNotifier(Edge()).clear();
249 void erase(const Edge& edge) {
250 getNotifier(Edge()).erase(edge);
256 edge_notifier.clear();
262 template <typename Base>
263 class UEdgeSetExtender : public Base {
268 typedef UEdgeSetExtender Graph;
270 typedef typename Parent::Node Node;
271 typedef typename Parent::Edge Edge;
272 typedef typename Parent::UEdge UEdge;
275 int maxId(Node) const {
276 return Parent::maxNodeId();
279 int maxId(Edge) const {
280 return Parent::maxEdgeId();
283 int maxId(UEdge) const {
284 return Parent::maxUEdgeId();
287 Node fromId(int id, Node) const {
288 return Parent::nodeFromId(id);
291 Edge fromId(int id, Edge) const {
292 return Parent::edgeFromId(id);
295 UEdge fromId(int id, UEdge) const {
296 return Parent::uEdgeFromId(id);
299 Node oppositeNode(const Node &n, const UEdge &e) const {
300 if( n == Parent::source(e))
301 return Parent::target(e);
302 else if( n == Parent::target(e))
303 return Parent::source(e);
308 Edge oppositeEdge(const Edge &e) const {
309 return Parent::direct(e, !Parent::direction(e));
312 using Parent::direct;
313 Edge direct(const UEdge &ue, const Node &s) const {
314 return Parent::direct(ue, Parent::source(ue) == s);
317 typedef AlterationNotifier<Edge> EdgeNotifier;
318 typedef AlterationNotifier<UEdge> UEdgeNotifier;
323 mutable EdgeNotifier edge_notifier;
324 mutable UEdgeNotifier uedge_notifier;
328 using Parent::getNotifier;
330 EdgeNotifier& getNotifier(Edge) const {
331 return edge_notifier;
334 UEdgeNotifier& getNotifier(UEdge) const {
335 return uedge_notifier;
339 class NodeIt : public Node {
345 NodeIt(Invalid i) : Node(i) { }
347 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
348 _graph.first(*static_cast<Node*>(this));
351 NodeIt(const Graph& _graph, const Node& node)
352 : Node(node), graph(&_graph) {}
354 NodeIt& operator++() {
362 class EdgeIt : public Edge {
368 EdgeIt(Invalid i) : Edge(i) { }
370 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
371 _graph.first(*static_cast<Edge*>(this));
374 EdgeIt(const Graph& _graph, const Edge& e) :
375 Edge(e), graph(&_graph) { }
377 EdgeIt& operator++() {
385 class OutEdgeIt : public Edge {
391 OutEdgeIt(Invalid i) : Edge(i) { }
393 OutEdgeIt(const Graph& _graph, const Node& node)
395 _graph.firstOut(*this, node);
398 OutEdgeIt(const Graph& _graph, const Edge& edge)
399 : Edge(edge), graph(&_graph) {}
401 OutEdgeIt& operator++() {
402 graph->nextOut(*this);
409 class InEdgeIt : public Edge {
415 InEdgeIt(Invalid i) : Edge(i) { }
417 InEdgeIt(const Graph& _graph, const Node& node)
419 _graph.firstIn(*this, node);
422 InEdgeIt(const Graph& _graph, const Edge& edge) :
423 Edge(edge), graph(&_graph) {}
425 InEdgeIt& operator++() {
426 graph->nextIn(*this);
433 class UEdgeIt : public Parent::UEdge {
439 UEdgeIt(Invalid i) : UEdge(i) { }
441 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
442 _graph.first(*static_cast<UEdge*>(this));
445 UEdgeIt(const Graph& _graph, const UEdge& e) :
446 UEdge(e), graph(&_graph) { }
448 UEdgeIt& operator++() {
455 class IncEdgeIt : public Parent::UEdge {
456 friend class UEdgeSetExtender;
463 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
465 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
466 _graph.firstInc(*this, direction, n);
469 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
470 : graph(&_graph), UEdge(ue) {
471 direction = (_graph.source(ue) == n);
474 IncEdgeIt& operator++() {
475 graph->nextInc(*this, direction);
480 /// \brief Base node of the iterator
482 /// Returns the base node (ie. the source in this case) of the iterator
483 Node baseNode(const OutEdgeIt &e) const {
484 return Parent::source((Edge)e);
486 /// \brief Running node of the iterator
488 /// Returns the running node (ie. the target in this case) of the
490 Node runningNode(const OutEdgeIt &e) const {
491 return Parent::target((Edge)e);
494 /// \brief Base node of the iterator
496 /// Returns the base node (ie. the target in this case) of the iterator
497 Node baseNode(const InEdgeIt &e) const {
498 return Parent::target((Edge)e);
500 /// \brief Running node of the iterator
502 /// Returns the running node (ie. the source in this case) of the
504 Node runningNode(const InEdgeIt &e) const {
505 return Parent::source((Edge)e);
508 /// Base node of the iterator
510 /// Returns the base node of the iterator
511 Node baseNode(const IncEdgeIt &e) const {
512 return e.direction ? source(e) : target(e);
514 /// Running node of the iterator
516 /// Returns the running node of the iterator
517 Node runningNode(const IncEdgeIt &e) const {
518 return e.direction ? target(e) : source(e);
522 template <typename _Value>
524 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
526 typedef UEdgeSetExtender Graph;
527 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
529 EdgeMap(const Graph& _g)
531 EdgeMap(const Graph& _g, const _Value& _v)
534 EdgeMap& operator=(const EdgeMap& cmap) {
535 return operator=<EdgeMap>(cmap);
538 template <typename CMap>
539 EdgeMap& operator=(const CMap& cmap) {
540 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
541 const typename Parent::Graph* graph = Parent::getGraph();
543 for (graph->first(it); it != INVALID; graph->next(it)) {
544 Parent::set(it, cmap[it]);
551 template <typename _Value>
553 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
555 typedef UEdgeSetExtender Graph;
556 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
558 UEdgeMap(const Graph& _g)
560 UEdgeMap(const Graph& _g, const _Value& _v)
563 UEdgeMap& operator=(const UEdgeMap& cmap) {
564 return operator=<UEdgeMap>(cmap);
567 template <typename CMap>
568 UEdgeMap& operator=(const CMap& cmap) {
569 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
570 const typename Parent::Graph* graph = Parent::getGraph();
572 for (graph->first(it); it != INVALID; graph->next(it)) {
573 Parent::set(it, cmap[it]);
580 // Alteration extension
582 UEdge addEdge(const Node& from, const Node& to) {
583 UEdge uedge = Parent::addEdge(from, to);
584 getNotifier(UEdge()).add(uedge);
585 getNotifier(Edge()).add(Parent::direct(uedge, true));
586 getNotifier(Edge()).add(Parent::direct(uedge, false));
591 getNotifier(Edge()).clear();
592 getNotifier(UEdge()).clear();
596 void erase(const UEdge& uedge) {
597 getNotifier(Edge()).erase(Parent::direct(uedge, true));
598 getNotifier(Edge()).erase(Parent::direct(uedge, false));
599 getNotifier(UEdge()).erase(uedge);
600 Parent::erase(uedge);
604 ~UEdgeSetExtender() {
605 getNotifier(Edge()).clear();
606 getNotifier(UEdge()).clear();