Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
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> {
210 typedef typename _Graph::template NodeMap<_Value> Parent;
212 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
213 : Parent(*edgeset.graph) {}
215 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
216 : Parent(*edgeset.graph, value) {}
218 NodeMap& operator=(const NodeMap& cmap) {
219 return operator=<NodeMap>(cmap);
222 template <typename CMap>
223 NodeMap& operator=(const CMap& cmap) {
224 Parent::operator=(cmap);
231 /// \ingroup semi_adaptors
233 /// \brief Graph using a node set of another graph and an
236 /// This structure can be used to establish another graph over a node set
237 /// of an existing one. The node iterator will go through the nodes of the
240 /// \param _Graph The type of the graph which shares its node set with
241 /// this class. Its interface must conform to the \ref concept::StaticGraph
242 /// "StaticGraph" concept.
244 /// In the edge extension and removing it conforms to the
245 /// \ref concept::ErasableGraph "ErasableGraph" concept.
246 template <typename _Graph>
247 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
251 typedef EdgeSetExtender<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 UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
344 typedef UEdgeSetExtender<UGraphBaseExtender<
345 ListEdgeSetBase<_Graph> > > Parent;
347 typedef typename Parent::Node Node;
348 typedef typename Parent::Edge Edge;
350 typedef _Graph Graph;
353 typedef typename Parent::NodesImplBase NodesImplBase;
355 void eraseNode(const Node& node) {
357 Parent::firstOut(edge, node);
358 while (edge != INVALID ) {
360 Parent::firstOut(edge, node);
369 class NodesImpl : public NodesImplBase {
371 typedef NodesImplBase Parent;
373 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
374 : Parent(graph), _edgeset(edgeset) {}
376 virtual ~NodesImpl() {}
380 virtual void erase(const Node& node) {
381 _edgeset.eraseNode(node);
384 virtual void erase(const std::vector<Node>& nodes) {
385 for (int i = 0; i < (int)nodes.size(); ++i) {
386 _edgeset.eraseNode(nodes[i]);
388 Parent::erase(nodes);
390 virtual void clear() {
391 _edgeset.clearNodes();
396 ListUEdgeSet& _edgeset;
403 /// \brief Constructor of the adaptor.
405 /// Constructor of the adaptor.
406 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
407 Parent::initalize(graph, nodes);
412 template <typename _Graph>
413 class SmartEdgeSetBase {
416 typedef _Graph Graph;
417 typedef typename Graph::Node Node;
418 typedef typename Graph::NodeIt NodeIt;
423 int first_out, first_in;
424 NodeT() : first_out(-1), first_in(-1) {}
427 typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
429 NodesImplBase* nodes;
433 int next_out, next_in;
437 std::vector<EdgeT> edges;
441 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
449 friend class SmartEdgeSetBase<Graph>;
451 Edge(int _id) : id(_id) {}
455 Edge(Invalid) : id(-1) {}
456 bool operator==(const Edge& edge) const { return id == edge.id; }
457 bool operator!=(const Edge& edge) const { return id != edge.id; }
458 bool operator<(const Edge& edge) const { return id < edge.id; }
461 SmartEdgeSetBase() {}
463 Edge addEdge(const Node& source, const Node& target) {
464 int n = edges.size();
465 edges.push_back(EdgeT());
466 edges[n].next_in = (*nodes)[target].first_in;
467 (*nodes)[target].first_in = n;
468 edges[n].next_out = (*nodes)[source].first_out;
469 (*nodes)[source].first_out = n;
470 edges[n].source = source;
471 edges[n].target = target;
477 for (first(node); node != INVALID; next(node)) {
478 (*nodes)[node].first_in = -1;
479 (*nodes)[node].first_out = -1;
484 void first(Node& node) const {
488 void next(Node& node) const {
492 void first(Edge& edge) const {
493 edge.id = edges.size() - 1;
496 void next(Edge& edge) const {
500 void firstOut(Edge& edge, const Node& node) const {
501 edge.id = (*nodes)[node].first_out;
504 void nextOut(Edge& edge) const {
505 edge.id = edges[edge.id].next_out;
508 void firstIn(Edge& edge, const Node& node) const {
509 edge.id = (*nodes)[node].first_in;
512 void nextIn(Edge& edge) const {
513 edge.id = edges[edge.id].next_in;
516 int id(const Node& node) const { return graph->id(node); }
517 int id(const Edge& edge) const { return edge.id; }
519 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
520 Edge edgeFromId(int id) const { return Edge(id); }
522 int maxNodeId() const { return graph->maxNodeId(); };
523 int maxEdgeId() const { return edges.size() - 1; }
525 Node source(const Edge& edge) const { return edges[edge.id].source;}
526 Node target(const Edge& edge) const { return edges[edge.id].target;}
528 typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
530 NodeNotifier& getNotifier(Node) const {
531 return graph->getNotifier(Node());
534 template <typename _Value>
535 class NodeMap : public Graph::template NodeMap<_Value> {
538 typedef typename _Graph::template NodeMap<_Value> Parent;
540 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
541 : Parent(*edgeset.graph) { }
543 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
544 : Parent(*edgeset.graph, value) { }
546 NodeMap& operator=(const NodeMap& cmap) {
547 return operator=<NodeMap>(cmap);
550 template <typename CMap>
551 NodeMap& operator=(const CMap& cmap) {
552 Parent::operator=(cmap);
560 /// \ingroup semi_adaptors
562 /// \brief Graph using a node set of another graph and an
565 /// This structure can be used to establish another graph over a node set
566 /// of an existing one. The node iterator will go through the nodes of the
569 /// \param _Graph The type of the graph which shares its node set with
570 /// this class. Its interface must conform to the \ref concept::StaticGraph
571 /// "StaticGraph" concept.
573 /// In the edge extension and removing it conforms to the
574 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
575 template <typename _Graph>
576 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
580 typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
582 typedef typename Parent::Node Node;
583 typedef typename Parent::Edge Edge;
585 typedef _Graph Graph;
587 class UnsupportedOperation : public LogicError {
589 virtual const char* exceptionName() const {
590 return "lemon::SmartEdgeSet::UnsupportedOperation";
598 typedef typename Parent::NodesImplBase NodesImplBase;
600 void eraseNode(const Node& node) {
601 if (Parent::InEdgeIt(*this, node) == INVALID &&
602 Parent::OutEdgeIt(*this, node) == INVALID) {
605 throw UnsupportedOperation();
612 class NodesImpl : public NodesImplBase {
614 typedef NodesImplBase Parent;
616 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
617 : Parent(graph), _edgeset(edgeset) {}
619 virtual ~NodesImpl() {}
623 virtual void erase(const Node& node) {
624 _edgeset.eraseNode(node);
627 virtual void erase(const std::vector<Node>& nodes) {
628 for (int i = 0; i < (int)nodes.size(); ++i) {
629 _edgeset.eraseNode(nodes[i]);
631 Parent::erase(nodes);
633 virtual void clear() {
634 _edgeset.clearNodes();
639 SmartEdgeSet& _edgeset;
646 /// \brief Constructor of the adaptor.
648 /// Constructor of the adaptor.
649 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
650 Parent::initalize(graph, nodes);
655 /// \ingroup semi_adaptors
657 /// \brief Graph using a node set of another graph and an
660 /// This structure can be used to establish another graph over a node set
661 /// of an existing one. The node iterator will go through the nodes of the
664 /// \param _Graph The type of the graph which shares its node set with
665 /// this class. Its interface must conform to the \ref concept::StaticGraph
666 /// "StaticGraph" concept.
668 /// In the edge extension and removing it conforms to the
669 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
670 template <typename _Graph>
672 : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
676 typedef UEdgeSetExtender<UGraphBaseExtender<
677 SmartEdgeSetBase<_Graph> > > Parent;
679 typedef typename Parent::Node Node;
680 typedef typename Parent::Edge Edge;
682 typedef _Graph Graph;
684 class UnsupportedOperation : public LogicError {
686 virtual const char* exceptionName() const {
687 return "lemon::SmartUEdgeSet::UnsupportedOperation";
693 typedef typename Parent::NodesImplBase NodesImplBase;
695 void eraseNode(const Node& node) {
696 if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
699 throw UnsupportedOperation();
706 class NodesImpl : public NodesImplBase {
708 typedef NodesImplBase Parent;
710 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
711 : Parent(graph), _edgeset(edgeset) {}
713 virtual ~NodesImpl() {}
717 virtual void erase(const Node& node) {
718 _edgeset.eraseNode(node);
721 virtual void erase(const std::vector<Node>& nodes) {
722 for (int i = 0; i < (int)nodes.size(); ++i) {
723 _edgeset.eraseNode(nodes[i]);
725 Parent::erase(nodes);
727 virtual void clear() {
728 _edgeset.clearNodes();
733 SmartUEdgeSet& _edgeset;
740 /// \brief Constructor of the adaptor.
742 /// Constructor of the adaptor.
743 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
744 Parent::initalize(graph, nodes);