vmap.h: Enables one to create maps with a virtual base class.
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
22 #include <lemon/bits/erasable_graph_extender.h>
23 #include <lemon/bits/clearable_graph_extender.h>
24 #include <lemon/bits/extendable_graph_extender.h>
25 #include <lemon/bits/iterable_graph_extender.h>
26 #include <lemon/bits/alteration_notifier.h>
27 #include <lemon/bits/default_map.h>
28 #include <lemon/bits/graph_extender.h>
32 /// \brief EdgeSet classes.
34 /// Graphs which use another graph's node-set as own.
38 template <typename _Graph>
39 class ListEdgeSetBase {
43 typedef typename Graph::Node Node;
44 typedef typename Graph::NodeIt NodeIt;
49 int first_out, first_in;
50 NodeT() : first_out(-1), first_in(-1) {}
53 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
59 int next_out, next_in;
60 int prev_out, prev_in;
61 EdgeT() : prev_out(-1), prev_in(-1) {}
64 std::vector<EdgeT> edges;
71 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
79 friend class ListEdgeSetBase<Graph>;
81 Edge(int _id) : id(_id) {}
85 Edge(Invalid) : id(-1) {}
86 bool operator==(const Edge& edge) const { return id == edge.id; }
87 bool operator!=(const Edge& edge) const { return id != edge.id; }
88 bool operator<(const Edge& edge) const { return id < edge.id; }
91 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
93 Edge addEdge(const Node& source, const Node& target) {
95 if (first_free_edge == -1) {
97 edges.push_back(EdgeT());
100 first_free_edge = edges[first_free_edge].next_in;
102 edges[n].next_in = (*nodes)[target].first_in;
103 if ((*nodes)[target].first_in != -1) {
104 edges[(*nodes)[target].first_in].prev_in = n;
106 (*nodes)[target].first_in = n;
107 edges[n].next_out = (*nodes)[source].first_out;
108 if ((*nodes)[source].first_out != -1) {
109 edges[(*nodes)[source].first_out].prev_out = n;
111 (*nodes)[source].first_out = n;
112 edges[n].source = source;
113 edges[n].target = target;
117 void erase(const Edge& edge) {
119 if (edges[n].prev_in != -1) {
120 edges[edges[n].prev_in].next_in = edges[n].next_in;
122 (*nodes)[edges[n].target].first_in = edges[n].next_in;
124 if (edges[n].next_in != -1) {
125 edges[edges[n].next_in].prev_in = edges[n].prev_in;
128 if (edges[n].prev_out != -1) {
129 edges[edges[n].prev_out].next_out = edges[n].next_out;
131 (*nodes)[edges[n].source].first_out = edges[n].next_out;
133 if (edges[n].next_out != -1) {
134 edges[edges[n].next_out].prev_out = edges[n].prev_out;
141 for (first(node); node != INVALID; next(node)) {
142 (*nodes)[node].first_in = -1;
143 (*nodes)[node].first_out = -1;
147 first_free_edge = -1;
150 void first(Node& node) const {
154 void next(Node& node) const {
158 void first(Edge& edge) const {
160 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
162 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
165 void next(Edge& edge) const {
166 if (edges[edge.id].next_in != -1) {
167 edge.id = edges[edge.id].next_in;
169 Node node = edges[edge.id].target;
170 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
172 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
176 void firstOut(Edge& edge, const Node& node) const {
177 edge.id = (*nodes)[node].first_out;
180 void nextOut(Edge& edge) const {
181 edge.id = edges[edge.id].next_out;
184 void firstIn(Edge& edge, const Node& node) const {
185 edge.id = (*nodes)[node].first_in;
188 void nextIn(Edge& edge) const {
189 edge.id = edges[edge.id].next_in;
192 int id(const Node& node) const { return graph->id(node); }
193 int id(const Edge& edge) const { return edge.id; }
195 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
196 Edge edgeFromId(int id) const { return Edge(id); }
198 int maxNodeId() const { return graph->maxNodeId(); };
199 int maxEdgeId() const { return edges.size() - 1; }
201 Node source(const Edge& edge) const { return edges[edge.id].source;}
202 Node target(const Edge& edge) const { return edges[edge.id].target;}
204 template <typename _Value>
205 class NodeMap : public Graph::template NodeMap<_Value> {
207 typedef typename _Graph::template NodeMap<_Value> Parent;
208 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
209 : Parent(*edgeset.graph) { }
210 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
211 : Parent(*edgeset.graph, value) { }
216 /// \ingroup semi_adaptors
218 /// \brief Graph using a node set of another graph and an
221 /// This structure can be used to establish another graph over a node set
222 /// of an existing one. The node iterator will go through the nodes of the
225 /// \param _Graph The type of the graph which shares its node set with
226 /// this class. Its interface must conform to the \ref concept::StaticGraph
227 /// "StaticGraph" concept.
229 /// In the edge extension and removing it conforms to the
230 /// \ref concept::ErasableGraph "ErasableGraph" concept.
231 template <typename _Graph>
233 public ErasableEdgeSetExtender<
234 ClearableEdgeSetExtender<
235 ExtendableEdgeSetExtender<
236 MappableEdgeSetExtender<
237 IterableGraphExtender<
238 AlterableEdgeSetExtender<
240 ListEdgeSetBase<_Graph> > > > > > > > {
244 typedef ErasableEdgeSetExtender<
245 ClearableEdgeSetExtender<
246 ExtendableEdgeSetExtender<
247 MappableEdgeSetExtender<
248 IterableGraphExtender<
249 AlterableEdgeSetExtender<
251 ListEdgeSetBase<_Graph> > > > > > > > Parent;
253 typedef typename Parent::Node Node;
254 typedef typename Parent::Edge Edge;
256 typedef _Graph Graph;
259 typedef typename Parent::NodesImplBase NodesImplBase;
261 void eraseNode(const Node& node) {
263 Parent::firstOut(edge, node);
264 while (edge != INVALID ) {
266 Parent::firstOut(edge, node);
269 Parent::firstIn(edge, node);
270 while (edge != INVALID ) {
272 Parent::firstIn(edge, node);
280 class NodesImpl : public NodesImplBase {
282 typedef NodesImplBase Parent;
284 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
285 : Parent(graph), _edgeset(edgeset) {}
287 virtual ~NodesImpl() {}
291 virtual void erase(const Node& node) {
292 _edgeset.eraseNode(node);
295 virtual void erase(const std::vector<Node>& nodes) {
296 for (int i = 0; i < (int)nodes.size(); ++i) {
297 _edgeset.eraseNode(nodes[i]);
299 Parent::erase(nodes);
301 virtual void clear() {
302 _edgeset.clearNodes();
307 ListEdgeSet& _edgeset;
314 /// \brief Constructor of the adaptor.
316 /// Constructor of the adaptor.
317 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
318 Parent::initalize(graph, nodes);
323 /// \ingroup semi_adaptors
325 /// \brief Graph using a node set of another graph and an
328 /// This structure can be used to establish another graph over a node set
329 /// of an existing one. The node iterator will go through the nodes of the
332 /// \param _Graph The type of the graph which shares its node set with
333 /// this class. Its interface must conform to the \ref concept::StaticGraph
334 /// "StaticGraph" concept.
336 /// In the edge extension and removing it conforms to the
337 /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
338 template <typename _Graph>
340 public ErasableUEdgeSetExtender<
341 ClearableUEdgeSetExtender<
342 ExtendableUEdgeSetExtender<
343 MappableUEdgeSetExtender<
344 IterableUGraphExtender<
345 AlterableUEdgeSetExtender<
347 ListEdgeSetBase<_Graph> > > > > > > > {
351 typedef ErasableUEdgeSetExtender<
352 ClearableUEdgeSetExtender<
353 ExtendableUEdgeSetExtender<
354 MappableUEdgeSetExtender<
355 IterableUGraphExtender<
356 AlterableUEdgeSetExtender<
358 ListEdgeSetBase<_Graph> > > > > > > > Parent;
360 typedef typename Parent::Node Node;
361 typedef typename Parent::Edge Edge;
363 typedef _Graph Graph;
366 typedef typename Parent::NodesImplBase NodesImplBase;
368 void eraseNode(const Node& node) {
370 Parent::firstOut(edge, node);
371 while (edge != INVALID ) {
373 Parent::firstOut(edge, node);
382 class NodesImpl : public NodesImplBase {
384 typedef NodesImplBase Parent;
386 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
387 : Parent(graph), _edgeset(edgeset) {}
389 virtual ~NodesImpl() {}
393 virtual void erase(const Node& node) {
394 _edgeset.eraseNode(node);
397 virtual void erase(const std::vector<Node>& nodes) {
398 for (int i = 0; i < (int)nodes.size(); ++i) {
399 _edgeset.eraseNode(nodes[i]);
401 Parent::erase(nodes);
403 virtual void clear() {
404 _edgeset.clearNodes();
409 ListUEdgeSet& _edgeset;
416 /// \brief Constructor of the adaptor.
418 /// Constructor of the adaptor.
419 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
420 Parent::initalize(graph, nodes);
425 template <typename _Graph>
426 class SmartEdgeSetBase {
429 typedef _Graph Graph;
430 typedef typename Graph::Node Node;
431 typedef typename Graph::NodeIt NodeIt;
436 int first_out, first_in;
437 NodeT() : first_out(-1), first_in(-1) {}
440 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
442 NodesImplBase* nodes;
446 int next_out, next_in;
450 std::vector<EdgeT> edges;
454 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
462 friend class SmartEdgeSetBase<Graph>;
464 Edge(int _id) : id(_id) {}
468 Edge(Invalid) : id(-1) {}
469 bool operator==(const Edge& edge) const { return id == edge.id; }
470 bool operator!=(const Edge& edge) const { return id != edge.id; }
471 bool operator<(const Edge& edge) const { return id < edge.id; }
474 SmartEdgeSetBase() {}
476 Edge addEdge(const Node& source, const Node& target) {
477 int n = edges.size();
478 edges.push_back(EdgeT());
479 edges[n].next_in = (*nodes)[target].first_in;
480 (*nodes)[target].first_in = n;
481 edges[n].next_out = (*nodes)[source].first_out;
482 (*nodes)[source].first_out = n;
483 edges[n].source = source;
484 edges[n].target = target;
490 for (first(node); node != INVALID; next(node)) {
491 (*nodes)[node].first_in = -1;
492 (*nodes)[node].first_out = -1;
497 void first(Node& node) const {
501 void next(Node& node) const {
505 void first(Edge& edge) const {
506 edge.id = edges.size() - 1;
509 void next(Edge& edge) const {
513 void firstOut(Edge& edge, const Node& node) const {
514 edge.id = (*nodes)[node].first_out;
517 void nextOut(Edge& edge) const {
518 edge.id = edges[edge.id].next_out;
521 void firstIn(Edge& edge, const Node& node) const {
522 edge.id = (*nodes)[node].first_in;
525 void nextIn(Edge& edge) const {
526 edge.id = edges[edge.id].next_in;
529 int id(const Node& node) const { return graph->id(node); }
530 int id(const Edge& edge) const { return edge.id; }
532 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
533 Edge edgeFromId(int id) const { return Edge(id); }
535 int maxNodeId() const { return graph->maxNodeId(); };
536 int maxEdgeId() const { return edges.size() - 1; }
538 Node source(const Edge& edge) const { return edges[edge.id].source;}
539 Node target(const Edge& edge) const { return edges[edge.id].target;}
541 template <typename _Value>
542 class NodeMap : public Graph::template NodeMap<_Value> {
544 typedef typename _Graph::template NodeMap<_Value> Parent;
545 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
546 : Parent(*edgeset.graph) { }
547 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
548 : Parent(*edgeset.graph, value) { }
554 /// \ingroup semi_adaptors
556 /// \brief Graph using a node set of another graph and an
559 /// This structure can be used to establish another graph over a node set
560 /// of an existing one. The node iterator will go through the nodes of the
563 /// \param _Graph The type of the graph which shares its node set with
564 /// this class. Its interface must conform to the \ref concept::StaticGraph
565 /// "StaticGraph" concept.
567 /// In the edge extension and removing it conforms to the
568 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
569 template <typename _Graph>
571 public ClearableEdgeSetExtender<
572 ExtendableEdgeSetExtender<
573 MappableEdgeSetExtender<
574 IterableGraphExtender<
575 AlterableEdgeSetExtender<
577 SmartEdgeSetBase<_Graph> > > > > > > {
581 typedef ClearableEdgeSetExtender<
582 ExtendableEdgeSetExtender<
583 MappableEdgeSetExtender<
584 IterableGraphExtender<
585 AlterableEdgeSetExtender<
587 SmartEdgeSetBase<_Graph> > > > > > > Parent;
589 typedef typename Parent::Node Node;
590 typedef typename Parent::Edge Edge;
592 typedef _Graph Graph;
594 class UnsupportedOperation : public LogicError {
596 virtual const char* exceptionName() const {
597 return "lemon::SmartEdgeSet::UnsupportedOperation";
605 typedef typename Parent::NodesImplBase NodesImplBase;
607 void eraseNode(const Node&) {
608 throw UnsupportedOperation();
615 class NodesImpl : public NodesImplBase {
617 typedef NodesImplBase Parent;
619 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
620 : Parent(graph), _edgeset(edgeset) {}
622 virtual ~NodesImpl() {}
626 virtual void erase(const Node& node) {
627 _edgeset.eraseNode(node);
630 virtual void erase(const std::vector<Node>& nodes) {
631 for (int i = 0; i < (int)nodes.size(); ++i) {
632 _edgeset.eraseNode(nodes[i]);
634 Parent::erase(nodes);
636 virtual void clear() {
637 _edgeset.clearNodes();
642 SmartEdgeSet& _edgeset;
649 /// \brief Constructor of the adaptor.
651 /// Constructor of the adaptor.
652 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
653 Parent::initalize(graph, nodes);
658 /// \ingroup semi_adaptors
660 /// \brief Graph using a node set of another graph and an
663 /// This structure can be used to establish another graph over a node set
664 /// of an existing one. The node iterator will go through the nodes of the
667 /// \param _Graph The type of the graph which shares its node set with
668 /// this class. Its interface must conform to the \ref concept::StaticGraph
669 /// "StaticGraph" concept.
671 /// In the edge extension and removing it conforms to the
672 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
673 template <typename _Graph>
674 class SmartUEdgeSet :
675 public ClearableUEdgeSetExtender<
676 ExtendableUEdgeSetExtender<
677 MappableUEdgeSetExtender<
678 IterableUGraphExtender<
679 AlterableUEdgeSetExtender<
681 SmartEdgeSetBase<_Graph> > > > > > > {
685 typedef ClearableUEdgeSetExtender<
686 ExtendableUEdgeSetExtender<
687 MappableUEdgeSetExtender<
688 IterableUGraphExtender<
689 AlterableUEdgeSetExtender<
691 SmartEdgeSetBase<_Graph> > > > > > > Parent;
693 typedef typename Parent::Node Node;
694 typedef typename Parent::Edge Edge;
696 typedef _Graph Graph;
698 class UnsupportedOperation : public LogicError {
700 virtual const char* exceptionName() const {
701 return "lemon::SmartUEdgeSet::UnsupportedOperation";
707 typedef typename Parent::NodesImplBase NodesImplBase;
709 void eraseNode(const Node&) {
710 throw UnsupportedOperation();
717 class NodesImpl : public NodesImplBase {
719 typedef NodesImplBase Parent;
721 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
722 : Parent(graph), _edgeset(edgeset) {}
724 virtual ~NodesImpl() {}
728 virtual void erase(const Node& node) {
729 _edgeset.eraseNode(node);
732 virtual void erase(const std::vector<Node>& nodes) {
733 for (int i = 0; i < (int)nodes.size(); ++i) {
734 _edgeset.eraseNode(nodes[i]);
736 Parent::erase(nodes);
738 virtual void clear() {
739 _edgeset.clearNodes();
744 SmartUEdgeSet& _edgeset;
751 /// \brief Constructor of the adaptor.
753 /// Constructor of the adaptor.
754 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
755 Parent::initalize(graph, nodes);