Removed references to the gui.
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_BITS_EDGE_SET_EXTENDER_H
20 #define LEMON_BITS_EDGE_SET_EXTENDER_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/error.h>
25 #include <lemon/bits/default_map.h>
29 ///\brief Extenders for the edge set types
32 /// \ingroup graphbits
34 /// \brief Extender for the EdgeSets
35 template <typename Base>
36 class EdgeSetExtender : public Base {
40 typedef EdgeSetExtender Graph;
44 typedef typename Parent::Node Node;
45 typedef typename Parent::Edge Edge;
47 int maxId(Node) const {
48 return Parent::maxNodeId();
51 int maxId(Edge) const {
52 return Parent::maxEdgeId();
55 Node fromId(int id, Node) const {
56 return Parent::nodeFromId(id);
59 Edge fromId(int id, Edge) const {
60 return Parent::edgeFromId(id);
63 Node oppositeNode(const Node &n, const Edge &e) const {
64 if (n == Parent::source(e))
65 return Parent::target(e);
66 else if(n==Parent::target(e))
67 return Parent::source(e);
73 // Alteration notifier extensions
75 /// The edge observer registry.
76 typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
80 mutable EdgeNotifier edge_notifier;
84 using Parent::getNotifier;
86 /// \brief Gives back the edge alteration notifier.
88 /// Gives back the edge alteration notifier.
89 EdgeNotifier& getNotifier(Edge) const {
93 // Iterable extensions
95 class NodeIt : public Node {
101 NodeIt(Invalid i) : Node(i) { }
103 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
104 _graph.first(static_cast<Node&>(*this));
107 NodeIt(const Graph& _graph, const Node& node)
108 : Node(node), graph(&_graph) {}
110 NodeIt& operator++() {
118 class EdgeIt : public Edge {
124 EdgeIt(Invalid i) : Edge(i) { }
126 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
127 _graph.first(static_cast<Edge&>(*this));
130 EdgeIt(const Graph& _graph, const Edge& e) :
131 Edge(e), graph(&_graph) { }
133 EdgeIt& operator++() {
141 class OutEdgeIt : public Edge {
147 OutEdgeIt(Invalid i) : Edge(i) { }
149 OutEdgeIt(const Graph& _graph, const Node& node)
151 _graph.firstOut(*this, node);
154 OutEdgeIt(const Graph& _graph, const Edge& edge)
155 : Edge(edge), graph(&_graph) {}
157 OutEdgeIt& operator++() {
158 graph->nextOut(*this);
165 class InEdgeIt : public Edge {
171 InEdgeIt(Invalid i) : Edge(i) { }
173 InEdgeIt(const Graph& _graph, const Node& node)
175 _graph.firstIn(*this, node);
178 InEdgeIt(const Graph& _graph, const Edge& edge) :
179 Edge(edge), graph(&_graph) {}
181 InEdgeIt& operator++() {
182 graph->nextIn(*this);
188 /// \brief Base node of the iterator
190 /// Returns the base node (ie. the source in this case) of the iterator
191 Node baseNode(const OutEdgeIt &e) const {
192 return Parent::source((Edge)e);
194 /// \brief Running node of the iterator
196 /// Returns the running node (ie. the target in this case) of the
198 Node runningNode(const OutEdgeIt &e) const {
199 return Parent::target((Edge)e);
202 /// \brief Base node of the iterator
204 /// Returns the base node (ie. the target in this case) of the iterator
205 Node baseNode(const InEdgeIt &e) const {
206 return Parent::target((Edge)e);
208 /// \brief Running node of the iterator
210 /// Returns the running node (ie. the source in this case) of the
212 Node runningNode(const InEdgeIt &e) const {
213 return Parent::source((Edge)e);
218 // Mappable extension
220 template <typename _Value>
222 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
224 typedef EdgeSetExtender Graph;
225 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
227 explicit EdgeMap(const Graph& _g)
229 EdgeMap(const Graph& _g, const _Value& _v)
232 EdgeMap& operator=(const EdgeMap& cmap) {
233 return operator=<EdgeMap>(cmap);
236 template <typename CMap>
237 EdgeMap& operator=(const CMap& cmap) {
238 Parent::operator=(cmap);
245 // Alteration extension
247 Edge addEdge(const Node& from, const Node& to) {
248 Edge edge = Parent::addEdge(from, to);
249 getNotifier(Edge()).add(edge);
254 getNotifier(Edge()).clear();
258 void erase(const Edge& edge) {
259 getNotifier(Edge()).erase(edge);
264 edge_notifier.setContainer(*this);
268 edge_notifier.clear();
274 /// \ingroup graphbits
276 /// \brief Extender for the UEdgeSets
277 template <typename Base>
278 class UEdgeSetExtender : public Base {
283 typedef UEdgeSetExtender Graph;
285 typedef typename Parent::Node Node;
286 typedef typename Parent::Edge Edge;
287 typedef typename Parent::UEdge UEdge;
290 int maxId(Node) const {
291 return Parent::maxNodeId();
294 int maxId(Edge) const {
295 return Parent::maxEdgeId();
298 int maxId(UEdge) const {
299 return Parent::maxUEdgeId();
302 Node fromId(int id, Node) const {
303 return Parent::nodeFromId(id);
306 Edge fromId(int id, Edge) const {
307 return Parent::edgeFromId(id);
310 UEdge fromId(int id, UEdge) const {
311 return Parent::uEdgeFromId(id);
314 Node oppositeNode(const Node &n, const UEdge &e) const {
315 if( n == Parent::source(e))
316 return Parent::target(e);
317 else if( n == Parent::target(e))
318 return Parent::source(e);
323 Edge oppositeEdge(const Edge &e) const {
324 return Parent::direct(e, !Parent::direction(e));
327 using Parent::direct;
328 Edge direct(const UEdge &ue, const Node &s) const {
329 return Parent::direct(ue, Parent::source(ue) == s);
332 typedef AlterationNotifier<UEdgeSetExtender, Edge> EdgeNotifier;
333 typedef AlterationNotifier<UEdgeSetExtender, UEdge> UEdgeNotifier;
338 mutable EdgeNotifier edge_notifier;
339 mutable UEdgeNotifier uedge_notifier;
343 using Parent::getNotifier;
345 EdgeNotifier& getNotifier(Edge) const {
346 return edge_notifier;
349 UEdgeNotifier& getNotifier(UEdge) const {
350 return uedge_notifier;
354 class NodeIt : public Node {
360 NodeIt(Invalid i) : Node(i) { }
362 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
363 _graph.first(static_cast<Node&>(*this));
366 NodeIt(const Graph& _graph, const Node& node)
367 : Node(node), graph(&_graph) {}
369 NodeIt& operator++() {
377 class EdgeIt : public Edge {
383 EdgeIt(Invalid i) : Edge(i) { }
385 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
386 _graph.first(static_cast<Edge&>(*this));
389 EdgeIt(const Graph& _graph, const Edge& e) :
390 Edge(e), graph(&_graph) { }
392 EdgeIt& operator++() {
400 class OutEdgeIt : public Edge {
406 OutEdgeIt(Invalid i) : Edge(i) { }
408 OutEdgeIt(const Graph& _graph, const Node& node)
410 _graph.firstOut(*this, node);
413 OutEdgeIt(const Graph& _graph, const Edge& edge)
414 : Edge(edge), graph(&_graph) {}
416 OutEdgeIt& operator++() {
417 graph->nextOut(*this);
424 class InEdgeIt : public Edge {
430 InEdgeIt(Invalid i) : Edge(i) { }
432 InEdgeIt(const Graph& _graph, const Node& node)
434 _graph.firstIn(*this, node);
437 InEdgeIt(const Graph& _graph, const Edge& edge) :
438 Edge(edge), graph(&_graph) {}
440 InEdgeIt& operator++() {
441 graph->nextIn(*this);
448 class UEdgeIt : public Parent::UEdge {
454 UEdgeIt(Invalid i) : UEdge(i) { }
456 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
457 _graph.first(static_cast<UEdge&>(*this));
460 UEdgeIt(const Graph& _graph, const UEdge& e) :
461 UEdge(e), graph(&_graph) { }
463 UEdgeIt& operator++() {
470 class IncEdgeIt : public Parent::UEdge {
471 friend class UEdgeSetExtender;
478 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
480 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
481 _graph.firstInc(*this, direction, n);
484 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
485 : graph(&_graph), UEdge(ue) {
486 direction = (_graph.source(ue) == n);
489 IncEdgeIt& operator++() {
490 graph->nextInc(*this, direction);
495 /// \brief Base node of the iterator
497 /// Returns the base node (ie. the source in this case) of the iterator
498 Node baseNode(const OutEdgeIt &e) const {
499 return Parent::source((Edge)e);
501 /// \brief Running node of the iterator
503 /// Returns the running node (ie. the target in this case) of the
505 Node runningNode(const OutEdgeIt &e) const {
506 return Parent::target((Edge)e);
509 /// \brief Base node of the iterator
511 /// Returns the base node (ie. the target in this case) of the iterator
512 Node baseNode(const InEdgeIt &e) const {
513 return Parent::target((Edge)e);
515 /// \brief Running node of the iterator
517 /// Returns the running node (ie. the source in this case) of the
519 Node runningNode(const InEdgeIt &e) const {
520 return Parent::source((Edge)e);
523 /// Base node of the iterator
525 /// Returns the base node of the iterator
526 Node baseNode(const IncEdgeIt &e) const {
527 return e.direction ? source(e) : target(e);
529 /// Running node of the iterator
531 /// Returns the running node of the iterator
532 Node runningNode(const IncEdgeIt &e) const {
533 return e.direction ? target(e) : source(e);
537 template <typename _Value>
539 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
541 typedef UEdgeSetExtender Graph;
542 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
544 EdgeMap(const Graph& _g)
546 EdgeMap(const Graph& _g, const _Value& _v)
549 EdgeMap& operator=(const EdgeMap& cmap) {
550 return operator=<EdgeMap>(cmap);
553 template <typename CMap>
554 EdgeMap& operator=(const CMap& cmap) {
555 Parent::operator=(cmap);
562 template <typename _Value>
564 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
566 typedef UEdgeSetExtender Graph;
567 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
569 UEdgeMap(const Graph& _g)
572 UEdgeMap(const Graph& _g, const _Value& _v)
575 UEdgeMap& operator=(const UEdgeMap& cmap) {
576 return operator=<UEdgeMap>(cmap);
579 template <typename CMap>
580 UEdgeMap& operator=(const CMap& cmap) {
581 Parent::operator=(cmap);
588 // Alteration extension
590 UEdge addEdge(const Node& from, const Node& to) {
591 UEdge uedge = Parent::addEdge(from, to);
592 getNotifier(UEdge()).add(uedge);
593 getNotifier(Edge()).add(Parent::direct(uedge, true));
594 getNotifier(Edge()).add(Parent::direct(uedge, false));
599 getNotifier(Edge()).clear();
600 getNotifier(UEdge()).clear();
604 void erase(const UEdge& uedge) {
605 getNotifier(Edge()).erase(Parent::direct(uedge, true));
606 getNotifier(Edge()).erase(Parent::direct(uedge, false));
607 getNotifier(UEdge()).erase(uedge);
608 Parent::erase(uedge);
613 edge_notifier.setContainer(*this);
614 uedge_notifier.setContainer(*this);
617 ~UEdgeSetExtender() {
618 uedge_notifier.clear();
619 edge_notifier.clear();