An additional simplier interface for static size graphs.
Node operator()(int) for getting node by index
int index(Node node) for getting index by node
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/edge_set_extender.h>
27 /// \brief EdgeSet classes.
29 /// Graphs which use another graph's node-set as own.
33 template <typename _Graph>
34 class ListEdgeSetBase {
38 typedef typename Graph::Node Node;
39 typedef typename Graph::NodeIt NodeIt;
44 int first_out, first_in;
45 NodeT() : first_out(-1), first_in(-1) {}
48 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
54 int next_out, next_in;
55 int prev_out, prev_in;
56 EdgeT() : prev_out(-1), prev_in(-1) {}
59 std::vector<EdgeT> edges;
66 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
74 friend class ListEdgeSetBase<Graph>;
76 Edge(int _id) : id(_id) {}
80 Edge(Invalid) : id(-1) {}
81 bool operator==(const Edge& edge) const { return id == edge.id; }
82 bool operator!=(const Edge& edge) const { return id != edge.id; }
83 bool operator<(const Edge& edge) const { return id < edge.id; }
86 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
88 Edge addEdge(const Node& source, const Node& target) {
90 if (first_free_edge == -1) {
92 edges.push_back(EdgeT());
95 first_free_edge = edges[first_free_edge].next_in;
97 edges[n].next_in = (*nodes)[target].first_in;
98 if ((*nodes)[target].first_in != -1) {
99 edges[(*nodes)[target].first_in].prev_in = n;
101 (*nodes)[target].first_in = n;
102 edges[n].next_out = (*nodes)[source].first_out;
103 if ((*nodes)[source].first_out != -1) {
104 edges[(*nodes)[source].first_out].prev_out = n;
106 (*nodes)[source].first_out = n;
107 edges[n].source = source;
108 edges[n].target = target;
112 void erase(const Edge& edge) {
114 if (edges[n].prev_in != -1) {
115 edges[edges[n].prev_in].next_in = edges[n].next_in;
117 (*nodes)[edges[n].target].first_in = edges[n].next_in;
119 if (edges[n].next_in != -1) {
120 edges[edges[n].next_in].prev_in = edges[n].prev_in;
123 if (edges[n].prev_out != -1) {
124 edges[edges[n].prev_out].next_out = edges[n].next_out;
126 (*nodes)[edges[n].source].first_out = edges[n].next_out;
128 if (edges[n].next_out != -1) {
129 edges[edges[n].next_out].prev_out = edges[n].prev_out;
136 for (first(node); node != INVALID; next(node)) {
137 (*nodes)[node].first_in = -1;
138 (*nodes)[node].first_out = -1;
142 first_free_edge = -1;
145 void first(Node& node) const {
149 void next(Node& node) const {
153 void first(Edge& edge) const {
155 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
157 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
160 void next(Edge& edge) const {
161 if (edges[edge.id].next_in != -1) {
162 edge.id = edges[edge.id].next_in;
164 Node node = edges[edge.id].target;
165 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
167 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
171 void firstOut(Edge& edge, const Node& node) const {
172 edge.id = (*nodes)[node].first_out;
175 void nextOut(Edge& edge) const {
176 edge.id = edges[edge.id].next_out;
179 void firstIn(Edge& edge, const Node& node) const {
180 edge.id = (*nodes)[node].first_in;
183 void nextIn(Edge& edge) const {
184 edge.id = edges[edge.id].next_in;
187 int id(const Node& node) const { return graph->id(node); }
188 int id(const Edge& edge) const { return edge.id; }
190 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
191 Edge edgeFromId(int id) const { return Edge(id); }
193 int maxNodeId() const { return graph->maxNodeId(); };
194 int maxEdgeId() const { return edges.size() - 1; }
196 Node source(const Edge& edge) const { return edges[edge.id].source;}
197 Node target(const Edge& edge) const { return edges[edge.id].target;}
199 template <typename _Value>
200 class NodeMap : public Graph::template NodeMap<_Value> {
202 typedef typename _Graph::template NodeMap<_Value> Parent;
203 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
204 : Parent(*edgeset.graph) { }
205 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
206 : Parent(*edgeset.graph, value) { }
211 /// \ingroup semi_adaptors
213 /// \brief Graph using a node set of another graph and an
216 /// This structure can be used to establish another graph over a node set
217 /// of an existing one. The node iterator will go through the nodes of the
220 /// \param _Graph The type of the graph which shares its node set with
221 /// this class. Its interface must conform to the \ref concept::StaticGraph
222 /// "StaticGraph" concept.
224 /// In the edge extension and removing it conforms to the
225 /// \ref concept::ErasableGraph "ErasableGraph" concept.
226 template <typename _Graph>
227 class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
231 typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
233 typedef typename Parent::Node Node;
234 typedef typename Parent::Edge Edge;
236 typedef _Graph Graph;
239 typedef typename Parent::NodesImplBase NodesImplBase;
241 void eraseNode(const Node& node) {
243 Parent::firstOut(edge, node);
244 while (edge != INVALID ) {
246 Parent::firstOut(edge, node);
249 Parent::firstIn(edge, node);
250 while (edge != INVALID ) {
252 Parent::firstIn(edge, node);
260 class NodesImpl : public NodesImplBase {
262 typedef NodesImplBase Parent;
264 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
265 : Parent(graph), _edgeset(edgeset) {}
267 virtual ~NodesImpl() {}
271 virtual void erase(const Node& node) {
272 _edgeset.eraseNode(node);
275 virtual void erase(const std::vector<Node>& nodes) {
276 for (int i = 0; i < (int)nodes.size(); ++i) {
277 _edgeset.eraseNode(nodes[i]);
279 Parent::erase(nodes);
281 virtual void clear() {
282 _edgeset.clearNodes();
287 ListEdgeSet& _edgeset;
294 /// \brief Constructor of the adaptor.
296 /// Constructor of the adaptor.
297 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
298 Parent::initalize(graph, nodes);
303 /// \ingroup semi_adaptors
305 /// \brief Graph using a node set of another graph and an
308 /// This structure can be used to establish another graph over a node set
309 /// of an existing one. The node iterator will go through the nodes of the
312 /// \param _Graph The type of the graph which shares its node set with
313 /// this class. Its interface must conform to the \ref concept::StaticGraph
314 /// "StaticGraph" concept.
316 /// In the edge extension and removing it conforms to the
317 /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
318 template <typename _Graph>
320 : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
324 typedef UEdgeSetExtender<UGraphBaseExtender<
325 ListEdgeSetBase<_Graph> > > Parent;
327 typedef typename Parent::Node Node;
328 typedef typename Parent::Edge Edge;
330 typedef _Graph Graph;
333 typedef typename Parent::NodesImplBase NodesImplBase;
335 void eraseNode(const Node& node) {
337 Parent::firstOut(edge, node);
338 while (edge != INVALID ) {
340 Parent::firstOut(edge, node);
349 class NodesImpl : public NodesImplBase {
351 typedef NodesImplBase Parent;
353 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
354 : Parent(graph), _edgeset(edgeset) {}
356 virtual ~NodesImpl() {}
360 virtual void erase(const Node& node) {
361 _edgeset.eraseNode(node);
364 virtual void erase(const std::vector<Node>& nodes) {
365 for (int i = 0; i < (int)nodes.size(); ++i) {
366 _edgeset.eraseNode(nodes[i]);
368 Parent::erase(nodes);
370 virtual void clear() {
371 _edgeset.clearNodes();
376 ListUEdgeSet& _edgeset;
383 /// \brief Constructor of the adaptor.
385 /// Constructor of the adaptor.
386 ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
387 Parent::initalize(graph, nodes);
392 template <typename _Graph>
393 class SmartEdgeSetBase {
396 typedef _Graph Graph;
397 typedef typename Graph::Node Node;
398 typedef typename Graph::NodeIt NodeIt;
403 int first_out, first_in;
404 NodeT() : first_out(-1), first_in(-1) {}
407 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
409 NodesImplBase* nodes;
413 int next_out, next_in;
417 std::vector<EdgeT> edges;
421 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
429 friend class SmartEdgeSetBase<Graph>;
431 Edge(int _id) : id(_id) {}
435 Edge(Invalid) : id(-1) {}
436 bool operator==(const Edge& edge) const { return id == edge.id; }
437 bool operator!=(const Edge& edge) const { return id != edge.id; }
438 bool operator<(const Edge& edge) const { return id < edge.id; }
441 SmartEdgeSetBase() {}
443 Edge addEdge(const Node& source, const Node& target) {
444 int n = edges.size();
445 edges.push_back(EdgeT());
446 edges[n].next_in = (*nodes)[target].first_in;
447 (*nodes)[target].first_in = n;
448 edges[n].next_out = (*nodes)[source].first_out;
449 (*nodes)[source].first_out = n;
450 edges[n].source = source;
451 edges[n].target = target;
457 for (first(node); node != INVALID; next(node)) {
458 (*nodes)[node].first_in = -1;
459 (*nodes)[node].first_out = -1;
464 void first(Node& node) const {
468 void next(Node& node) const {
472 void first(Edge& edge) const {
473 edge.id = edges.size() - 1;
476 void next(Edge& edge) const {
480 void firstOut(Edge& edge, const Node& node) const {
481 edge.id = (*nodes)[node].first_out;
484 void nextOut(Edge& edge) const {
485 edge.id = edges[edge.id].next_out;
488 void firstIn(Edge& edge, const Node& node) const {
489 edge.id = (*nodes)[node].first_in;
492 void nextIn(Edge& edge) const {
493 edge.id = edges[edge.id].next_in;
496 int id(const Node& node) const { return graph->id(node); }
497 int id(const Edge& edge) const { return edge.id; }
499 Node nodeFromId(int id) const { return graph->nodeFromId(id); }
500 Edge edgeFromId(int id) const { return Edge(id); }
502 int maxNodeId() const { return graph->maxNodeId(); };
503 int maxEdgeId() const { return edges.size() - 1; }
505 Node source(const Edge& edge) const { return edges[edge.id].source;}
506 Node target(const Edge& edge) const { return edges[edge.id].target;}
508 template <typename _Value>
509 class NodeMap : public Graph::template NodeMap<_Value> {
511 typedef typename _Graph::template NodeMap<_Value> Parent;
512 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
513 : Parent(*edgeset.graph) { }
514 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
515 : Parent(*edgeset.graph, value) { }
521 /// \ingroup semi_adaptors
523 /// \brief Graph using a node set of another graph and an
526 /// This structure can be used to establish another graph over a node set
527 /// of an existing one. The node iterator will go through the nodes of the
530 /// \param _Graph The type of the graph which shares its node set with
531 /// this class. Its interface must conform to the \ref concept::StaticGraph
532 /// "StaticGraph" concept.
534 /// In the edge extension and removing it conforms to the
535 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
536 template <typename _Graph>
537 class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
541 typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
543 typedef typename Parent::Node Node;
544 typedef typename Parent::Edge Edge;
546 typedef _Graph Graph;
548 class UnsupportedOperation : public LogicError {
550 virtual const char* exceptionName() const {
551 return "lemon::SmartEdgeSet::UnsupportedOperation";
559 typedef typename Parent::NodesImplBase NodesImplBase;
561 void eraseNode(const Node&) {
562 throw UnsupportedOperation();
569 class NodesImpl : public NodesImplBase {
571 typedef NodesImplBase Parent;
573 NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
574 : Parent(graph), _edgeset(edgeset) {}
576 virtual ~NodesImpl() {}
580 virtual void erase(const Node& node) {
581 _edgeset.eraseNode(node);
584 virtual void erase(const std::vector<Node>& nodes) {
585 for (int i = 0; i < (int)nodes.size(); ++i) {
586 _edgeset.eraseNode(nodes[i]);
588 Parent::erase(nodes);
590 virtual void clear() {
591 _edgeset.clearNodes();
596 SmartEdgeSet& _edgeset;
603 /// \brief Constructor of the adaptor.
605 /// Constructor of the adaptor.
606 SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
607 Parent::initalize(graph, nodes);
612 /// \ingroup semi_adaptors
614 /// \brief Graph using a node set of another graph and an
617 /// This structure can be used to establish another graph over a node set
618 /// of an existing one. The node iterator will go through the nodes of the
621 /// \param _Graph The type of the graph which shares its node set with
622 /// this class. Its interface must conform to the \ref concept::StaticGraph
623 /// "StaticGraph" concept.
625 /// In the edge extension and removing it conforms to the
626 /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
627 template <typename _Graph>
629 : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
633 typedef UEdgeSetExtender<UGraphBaseExtender<
634 SmartEdgeSetBase<_Graph> > > Parent;
636 typedef typename Parent::Node Node;
637 typedef typename Parent::Edge Edge;
639 typedef _Graph Graph;
641 class UnsupportedOperation : public LogicError {
643 virtual const char* exceptionName() const {
644 return "lemon::SmartUEdgeSet::UnsupportedOperation";
650 typedef typename Parent::NodesImplBase NodesImplBase;
652 void eraseNode(const Node&) {
653 throw UnsupportedOperation();
660 class NodesImpl : public NodesImplBase {
662 typedef NodesImplBase Parent;
664 NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
665 : Parent(graph), _edgeset(edgeset) {}
667 virtual ~NodesImpl() {}
671 virtual void erase(const Node& node) {
672 _edgeset.eraseNode(node);
675 virtual void erase(const std::vector<Node>& nodes) {
676 for (int i = 0; i < (int)nodes.size(); ++i) {
677 _edgeset.eraseNode(nodes[i]);
679 Parent::erase(nodes);
681 virtual void clear() {
682 _edgeset.clearNodes();
687 SmartUEdgeSet& _edgeset;
694 /// \brief Constructor of the adaptor.
696 /// Constructor of the adaptor.
697 SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
698 Parent::initalize(graph, nodes);