Lemon Graph Format uses label instead of id named map.
2 * lemon/edge_set.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_EDGE_SET_H
18 #define LEMON_EDGE_SET_H
22 /// \brief EdgeSet classes.
24 /// Graphs which use another graph's node-set as own.
28 template <typename _Graph>
29 class ListEdgeSetBase {
33 typedef typename Graph::Node Node;
34 typedef typename Graph::NodeIt NodeIt;
39 int first_out, first_in;
40 NodeT() : first_out(-1), first_in(-1) {}
43 typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
49 int next_out, next_in;
50 int prev_out, prev_in;
51 EdgeT() : prev_out(-1), prev_in(-1) {}
54 std::vector<EdgeT> edges;
61 void initalize(const Graph& _graph, NodesImplBase& _nodes) {
69 friend class ListEdgeSetBase<Graph>;
71 Edge(int _id) : id(_id) {}
75 Edge(Invalid) : id(-1) {}
76 bool operator==(const Edge& edge) const { return id == edge.id; }
77 bool operator!=(const Edge& edge) const { return id != edge.id; }
78 bool operator<(const Edge& edge) const { return id < edge.id; }
81 ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
83 Edge addEdge(const Node& source, const Node& target) {
85 if (first_free_edge == -1) {
87 edges.push_back(EdgeT());
90 first_free_edge = edges[first_free_edge].next_in;
92 edges[n].next_in = (*nodes)[target].first_in;
93 (*nodes)[target].first_in = n;
94 edges[n].next_out = (*nodes)[source].first_out;
95 (*nodes)[source].first_out = n;
96 edges[n].source = source;
97 edges[n].target = target;
101 void erase(const Edge& edge) {
103 if (edges[n].prev_in != -1) {
104 edges[edges[n].prev_in].next_in = edges[n].next_in;
106 (*nodes)[edges[n].target].first_in = edges[n].next_in;
108 if (edges[n].next_in != -1) {
109 edges[edges[n].next_in].prev_in = edges[n].prev_in;
112 if (edges[n].prev_out != -1) {
113 edges[edges[n].prev_out].next_out = edges[n].next_out;
115 (*nodes)[edges[n].source].first_out = edges[n].next_out;
117 if (edges[n].next_out != -1) {
118 edges[edges[n].next_out].prev_out = edges[n].prev_out;
126 first_free_edge = -1;
129 void first(Node& node) const {
133 void next(Node& node) const {
137 void first(Edge& edge) const {
139 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
141 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
144 void next(Edge& edge) const {
145 if (edges[edge.id].next_in != -1) {
146 edge.id = edges[edge.id].next_in;
148 Node node = edges[edge.id].target;
149 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
151 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
155 void firstOut(Edge& edge, const Node& node) const {
156 edge.id = (*nodes)[node].first_out;
159 void nextOut(Edge& edge) const {
160 edge.id = edges[edge.id].next_out;
163 void firstIn(Edge& edge, const Node& node) const {
164 edge.id = (*nodes)[node].first_in;
167 void nextIn(Edge& edge) const {
168 edge.id = edges[edge.id].next_in;
171 int id(const Node& node) const { return graph->id(node); }
172 int id(const Edge& edge) const { return edge.id; }
174 Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
175 Edge edgeFromId(int id) const { return Edge(id); }
177 int maxNodeId() const { return graph->maxId(Node()); };
178 int maxEdgeId() const { return edges.size() - 1; }
180 Node source(const Edge& edge) const { return edges[edge.id].source;}
181 Node target(const Edge& edge) const { return edges[edge.id].target;}
183 template <typename _Value>
184 class NodeMap : public Graph::template NodeMap<_Value> {
186 typedef typename _Graph::template NodeMap<_Value> Parent;
187 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
188 : Parent(*edgeset.graph) { }
189 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
190 : Parent(*edgeset.graph, value) { }
195 /// \ingroup semi_adaptors
197 /// \brief Graph using a node set of another graph and an
200 /// This structure can be used to establish another graph over a node set
201 /// of an existing one. The node iterator will go through the nodes of the
204 /// \param _Graph The type of the graph which shares its node set with
205 /// this class. Its interface must conform to the \ref concept::StaticGraph
206 /// "StaticGraph" concept.
208 /// In the edge extension and removing it conforms to the
209 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
210 template <typename _Graph>
212 public ErasableEdgeSetExtender<
213 ClearableEdgeSetExtender<
214 ExtendableEdgeSetExtender<
215 MappableEdgeSetExtender<
216 IterableGraphExtender<
217 AlterableEdgeSetExtender<
219 ListEdgeSetBase<_Graph> > > > > > > > {
223 typedef ErasableEdgeSetExtender<
224 ClearableEdgeSetExtender<
225 ExtendableEdgeSetExtender<
226 MappableEdgeSetExtender<
227 IterableGraphExtender<
228 AlterableEdgeSetExtender<
230 ListEdgeSetBase<_Graph> > > > > > > > Parent;
232 typedef typename Parent::Node Node;
233 typedef typename Parent::Edge Edge;
235 typedef _Graph Graph;
238 typedef typename Parent::NodesImplBase NodesImplBase;
240 void eraseNode(const Node& node) {
242 Parent::firstOut(edge, node);
243 while (edge != INVALID ) {
245 Parent::firstOut(edge, node);
248 Parent::firstIn(edge, node);
249 while (edge != INVALID ) {
251 Parent::firstIn(edge, node);
259 class NodesImpl : public NodesImplBase {
261 typedef NodesImplBase Parent;
263 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
264 : Parent(graph), _edgeset(edgeset) {}
268 virtual void erase(const Node& node) {
269 _edgeset.eraseNode(node);
272 virtual void clear() {
273 _edgeset.clearNodes();
278 ListEdgeSet& _edgeset;
285 /// \brief Constructor of the adaptor.
287 /// Constructor of the adaptor.
288 ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
289 Parent::initalize(graph, nodes);
294 /// \ingroup semi_adaptors
296 /// \brief Graph using a node set of another graph and an
297 /// own undir edge set.
299 /// This structure can be used to establish another graph over a node set
300 /// of an existing one. The node iterator will go through the nodes of the
303 /// \param _Graph The type of the graph which shares its node set with
304 /// this class. Its interface must conform to the \ref concept::StaticGraph
305 /// "StaticGraph" concept.
307 /// In the edge extension and removing it conforms to the
308 /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
309 template <typename _Graph>
310 class ListUndirEdgeSet :
311 public ErasableUndirEdgeSetExtender<
312 ClearableUndirEdgeSetExtender<
313 ExtendableUndirEdgeSetExtender<
314 MappableUndirEdgeSetExtender<
315 IterableUndirGraphExtender<
316 AlterableUndirEdgeSetExtender<
318 ListEdgeSetBase<_Graph> > > > > > > > {
322 typedef ErasableUndirEdgeSetExtender<
323 ClearableUndirEdgeSetExtender<
324 ExtendableUndirEdgeSetExtender<
325 MappableUndirEdgeSetExtender<
326 IterableUndirGraphExtender<
327 AlterableUndirEdgeSetExtender<
329 ListEdgeSetBase<_Graph> > > > > > > > Parent;
331 typedef typename Parent::Node Node;
332 typedef typename Parent::Edge Edge;
334 typedef _Graph Graph;
337 typedef typename Parent::NodesImplBase NodesImplBase;
339 void eraseNode(const Node& node) {
341 Parent::firstOut(edge, node);
342 while (edge != INVALID ) {
344 Parent::firstOut(edge, node);
353 class NodesImpl : public NodesImplBase {
355 typedef NodesImplBase Parent;
357 NodesImpl(const Graph& graph, ListUndirEdgeSet& edgeset)
358 : Parent(graph), _edgeset(edgeset) {}
362 virtual void erase(const Node& node) {
363 _edgeset.eraseNode(node);
366 virtual void erase(const std::vector<Node>& nodes) {
367 for (int i = 0; i < nodes.size(); ++i) {
368 _edgeset.eraseNode(nodes[i]);
370 Parent::erase(nodes);
372 virtual void clear() {
373 _edgeset.clearNodes();
378 ListUndirEdgeSet& _edgeset;
385 /// \brief Constructor of the adaptor.
387 /// Constructor of the adaptor.
388 ListUndirEdgeSet(const Graph& graph) : nodes(graph, *this) {
389 Parent::initalize(graph, nodes);