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_UGRAPH_EXTENDER_H
20 #define LEMON_BITS_UGRAPH_EXTENDER_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/error.h>
25 #include <lemon/bits/map_extender.h>
26 #include <lemon/bits/default_map.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concept/maps.h>
33 ///\brief Extenders for the graph types
36 /// \ingroup graphbits
38 /// \brief Extender for the UGraphs
39 template <typename Base>
40 class UGraphExtender : public Base {
44 typedef UGraphExtender Graph;
46 typedef typename Parent::Node Node;
47 typedef typename Parent::Edge Edge;
48 typedef typename Parent::UEdge UEdge;
52 int maxId(Node) const {
53 return Parent::maxNodeId();
56 int maxId(Edge) const {
57 return Parent::maxEdgeId();
60 int maxId(UEdge) const {
61 return Parent::maxUEdgeId();
64 Node fromId(int id, Node) const {
65 return Parent::nodeFromId(id);
68 Edge fromId(int id, Edge) const {
69 return Parent::edgeFromId(id);
72 UEdge fromId(int id, UEdge) const {
73 return Parent::uEdgeFromId(id);
76 Node oppositeNode(const Node &n, const UEdge &e) const {
77 if( n == Parent::source(e))
78 return Parent::target(e);
79 else if( n == Parent::target(e))
80 return Parent::source(e);
85 Edge oppositeEdge(const Edge &e) const {
86 return Parent::direct(e, !Parent::direction(e));
90 Edge direct(const UEdge &ue, const Node &s) const {
91 return Parent::direct(ue, Parent::source(ue) == s);
94 // Alterable extension
96 typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
97 typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
98 typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
103 mutable NodeNotifier node_notifier;
104 mutable EdgeNotifier edge_notifier;
105 mutable UEdgeNotifier uedge_notifier;
109 NodeNotifier& getNotifier(Node) const {
110 return node_notifier;
113 EdgeNotifier& getNotifier(Edge) const {
114 return edge_notifier;
117 UEdgeNotifier& getNotifier(UEdge) const {
118 return uedge_notifier;
123 class NodeIt : public Node {
129 NodeIt(Invalid i) : Node(i) { }
131 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
132 _graph.first(static_cast<Node&>(*this));
135 NodeIt(const Graph& _graph, const Node& node)
136 : Node(node), graph(&_graph) {}
138 NodeIt& operator++() {
146 class EdgeIt : public Edge {
152 EdgeIt(Invalid i) : Edge(i) { }
154 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
155 _graph.first(static_cast<Edge&>(*this));
158 EdgeIt(const Graph& _graph, const Edge& e) :
159 Edge(e), graph(&_graph) { }
161 EdgeIt& operator++() {
169 class OutEdgeIt : public Edge {
175 OutEdgeIt(Invalid i) : Edge(i) { }
177 OutEdgeIt(const Graph& _graph, const Node& node)
179 _graph.firstOut(*this, node);
182 OutEdgeIt(const Graph& _graph, const Edge& edge)
183 : Edge(edge), graph(&_graph) {}
185 OutEdgeIt& operator++() {
186 graph->nextOut(*this);
193 class InEdgeIt : public Edge {
199 InEdgeIt(Invalid i) : Edge(i) { }
201 InEdgeIt(const Graph& _graph, const Node& node)
203 _graph.firstIn(*this, node);
206 InEdgeIt(const Graph& _graph, const Edge& edge) :
207 Edge(edge), graph(&_graph) {}
209 InEdgeIt& operator++() {
210 graph->nextIn(*this);
217 class UEdgeIt : public Parent::UEdge {
223 UEdgeIt(Invalid i) : UEdge(i) { }
225 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
226 _graph.first(static_cast<UEdge&>(*this));
229 UEdgeIt(const Graph& _graph, const UEdge& e) :
230 UEdge(e), graph(&_graph) { }
232 UEdgeIt& operator++() {
239 class IncEdgeIt : public Parent::UEdge {
240 friend class UGraphExtender;
247 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
249 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
250 _graph.firstInc(*this, direction, n);
253 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
254 : graph(&_graph), UEdge(ue) {
255 direction = (_graph.source(ue) == n);
258 IncEdgeIt& operator++() {
259 graph->nextInc(*this, direction);
264 /// \brief Base node of the iterator
266 /// Returns the base node (ie. the source in this case) of the iterator
267 Node baseNode(const OutEdgeIt &e) const {
268 return Parent::source((Edge)e);
270 /// \brief Running node of the iterator
272 /// Returns the running node (ie. the target in this case) of the
274 Node runningNode(const OutEdgeIt &e) const {
275 return Parent::target((Edge)e);
278 /// \brief Base node of the iterator
280 /// Returns the base node (ie. the target in this case) of the iterator
281 Node baseNode(const InEdgeIt &e) const {
282 return Parent::target((Edge)e);
284 /// \brief Running node of the iterator
286 /// Returns the running node (ie. the source in this case) of the
288 Node runningNode(const InEdgeIt &e) const {
289 return Parent::source((Edge)e);
292 /// Base node of the iterator
294 /// Returns the base node of the iterator
295 Node baseNode(const IncEdgeIt &e) const {
296 return e.direction ? source(e) : target(e);
298 /// Running node of the iterator
300 /// Returns the running node of the iterator
301 Node runningNode(const IncEdgeIt &e) const {
302 return e.direction ? target(e) : source(e);
305 // Mappable extension
307 template <typename _Value>
309 : public MapExtender<DefaultMap<Graph, Node, _Value> > {
311 typedef UGraphExtender Graph;
312 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
314 NodeMap(const Graph& graph)
316 NodeMap(const Graph& graph, const _Value& value)
317 : Parent(graph, value) {}
319 NodeMap& operator=(const NodeMap& cmap) {
320 return operator=<NodeMap>(cmap);
323 template <typename CMap>
324 NodeMap& operator=(const CMap& cmap) {
325 Parent::operator=(cmap);
331 template <typename _Value>
333 : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
335 typedef UGraphExtender Graph;
336 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
338 EdgeMap(const Graph& graph)
340 EdgeMap(const Graph& graph, const _Value& value)
341 : Parent(graph, value) {}
343 EdgeMap& operator=(const EdgeMap& cmap) {
344 return operator=<EdgeMap>(cmap);
347 template <typename CMap>
348 EdgeMap& operator=(const CMap& cmap) {
349 Parent::operator=(cmap);
355 template <typename _Value>
357 : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
359 typedef UGraphExtender Graph;
360 typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
362 UEdgeMap(const Graph& graph)
365 UEdgeMap(const Graph& graph, const _Value& value)
366 : Parent(graph, value) {}
368 UEdgeMap& operator=(const UEdgeMap& cmap) {
369 return operator=<UEdgeMap>(cmap);
372 template <typename CMap>
373 UEdgeMap& operator=(const CMap& cmap) {
374 Parent::operator=(cmap);
380 // Alteration extension
383 Node node = Parent::addNode();
384 getNotifier(Node()).add(node);
388 UEdge addEdge(const Node& from, const Node& to) {
389 UEdge uedge = Parent::addEdge(from, to);
390 getNotifier(UEdge()).add(uedge);
391 getNotifier(Edge()).add(Parent::direct(uedge, true));
392 getNotifier(Edge()).add(Parent::direct(uedge, false));
397 getNotifier(Edge()).clear();
398 getNotifier(UEdge()).clear();
399 getNotifier(Node()).clear();
403 void erase(const Node& node) {
405 Parent::firstOut(edge, node);
406 while (edge != INVALID ) {
408 Parent::firstOut(edge, node);
411 Parent::firstIn(edge, node);
412 while (edge != INVALID ) {
414 Parent::firstIn(edge, node);
417 getNotifier(Node()).erase(node);
421 void erase(const UEdge& uedge) {
422 getNotifier(Edge()).erase(Parent::direct(uedge, true));
423 getNotifier(Edge()).erase(Parent::direct(uedge, false));
424 getNotifier(UEdge()).erase(uedge);
425 Parent::erase(uedge);
429 node_notifier.setContainer(*this);
430 edge_notifier.setContainer(*this);
431 uedge_notifier.setContainer(*this);
435 uedge_notifier.clear();
436 edge_notifier.clear();
437 node_notifier.clear();