NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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_LIST_GRAPH_H
18 #define LEMON_LIST_GRAPH_H
22 ///\brief ListGraph, UndirListGraph classes.
24 #include <lemon/bits/erasable_graph_extender.h>
25 #include <lemon/bits/clearable_graph_extender.h>
26 #include <lemon/bits/extendable_graph_extender.h>
27 #include <lemon/bits/iterable_graph_extender.h>
28 #include <lemon/bits/alteration_notifier.h>
29 #include <lemon/bits/default_map.h>
30 #include <lemon/bits/graph_extender.h>
32 #include <lemon/error.h>
42 int first_in, first_out;
48 int prev_in, prev_out;
49 int next_in, next_out;
52 std::vector<NodeT> nodes;
58 std::vector<EdgeT> edges;
64 typedef ListGraphBase Graph;
67 friend class ListGraphBase;
71 Node(int pid) { id = pid;}
75 Node (Invalid) { id = -1; }
76 bool operator==(const Node& node) const {return id == node.id;}
77 bool operator!=(const Node& node) const {return id != node.id;}
78 bool operator<(const Node& node) const {return id < node.id;}
82 friend class ListGraphBase;
86 Edge(int pid) { id = pid;}
90 Edge (Invalid) { id = -1; }
91 bool operator==(const Edge& edge) const {return id == edge.id;}
92 bool operator!=(const Edge& edge) const {return id != edge.id;}
93 bool operator<(const Edge& edge) const {return id < edge.id;}
99 : nodes(), first_node(-1),
100 first_free_node(-1), edges(), first_free_edge(-1) {}
107 int maxNodeId() const { return nodes.size()-1; }
113 int maxEdgeId() const { return edges.size()-1; }
115 Node source(Edge e) const { return edges[e.id].source; }
116 Node target(Edge e) const { return edges[e.id].target; }
119 void first(Node& node) const {
120 node.id = first_node;
123 void next(Node& node) const {
124 node.id = nodes[node.id].next;
128 void first(Edge& e) const {
131 n!=-1 && nodes[n].first_in == -1;
133 e.id = (n == -1) ? -1 : nodes[n].first_in;
136 void next(Edge& edge) const {
137 if (edges[edge.id].next_in != -1) {
138 edge.id = edges[edge.id].next_in;
141 for(n = nodes[edges[edge.id].target].next;
142 n!=-1 && nodes[n].first_in == -1;
144 edge.id = (n == -1) ? -1 : nodes[n].first_in;
148 void firstOut(Edge &e, const Node& v) const {
149 e.id = nodes[v.id].first_out;
151 void nextOut(Edge &e) const {
152 e.id=edges[e.id].next_out;
155 void firstIn(Edge &e, const Node& v) const {
156 e.id = nodes[v.id].first_in;
158 void nextIn(Edge &e) const {
159 e.id=edges[e.id].next_in;
163 static int id(Node v) { return v.id; }
164 static int id(Edge e) { return e.id; }
166 static Node nodeFromId(int id) { return Node(id);}
167 static Edge edgeFromId(int id) { return Edge(id);}
169 /// Adds a new node to the graph.
171 /// \warning It adds the new node to the front of the list.
172 /// (i.e. the lastly added node becomes the first.)
176 if(first_free_node==-1) {
178 nodes.push_back(NodeT());
181 first_free_node = nodes[n].next;
184 nodes[n].next = first_node;
185 if(first_node != -1) nodes[first_node].prev = n;
189 nodes[n].first_in = nodes[n].first_out = -1;
194 Edge addEdge(Node u, Node v) {
197 if (first_free_edge == -1) {
199 edges.push_back(EdgeT());
202 first_free_edge = edges[n].next_in;
205 edges[n].source = u.id;
206 edges[n].target = v.id;
208 edges[n].next_out = nodes[u.id].first_out;
209 if(nodes[u.id].first_out != -1) {
210 edges[nodes[u.id].first_out].prev_out = n;
213 edges[n].next_in = nodes[v.id].first_in;
214 if(nodes[v.id].first_in != -1) {
215 edges[nodes[v.id].first_in].prev_in = n;
218 edges[n].prev_in = edges[n].prev_out = -1;
220 nodes[u.id].first_out = nodes[v.id].first_in = n;
225 void erase(const Node& node) {
228 if(nodes[n].next != -1) {
229 nodes[nodes[n].next].prev = nodes[n].prev;
232 if(nodes[n].prev != -1) {
233 nodes[nodes[n].prev].next = nodes[n].next;
235 first_node = nodes[n].next;
238 nodes[n].next = first_free_node;
243 void erase(const Edge& edge) {
246 if(edges[n].next_in!=-1) {
247 edges[edges[n].next_in].prev_in = edges[n].prev_in;
250 if(edges[n].prev_in!=-1) {
251 edges[edges[n].prev_in].next_in = edges[n].next_in;
253 nodes[edges[n].target].first_in = edges[n].next_in;
257 if(edges[n].next_out!=-1) {
258 edges[edges[n].next_out].prev_out = edges[n].prev_out;
261 if(edges[n].prev_out!=-1) {
262 edges[edges[n].prev_out].next_out = edges[n].next_out;
264 nodes[edges[n].source].first_out = edges[n].next_out;
267 edges[n].next_in = first_free_edge;
275 first_node = first_free_node = first_free_edge = -1;
279 void _changeTarget(Edge e, Node n)
281 if(edges[e.id].next_in != -1)
282 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
283 if(edges[e.id].prev_in != -1)
284 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
285 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
286 if (nodes[n.id].first_in != -1) {
287 edges[nodes[n.id].first_in].prev_in = e.id;
289 edges[e.id].target = n.id;
290 edges[e.id].prev_in = -1;
291 edges[e.id].next_in = nodes[n.id].first_in;
292 nodes[n.id].first_in = e.id;
294 void _changeSource(Edge e, Node n)
296 if(edges[e.id].next_out != -1)
297 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
298 if(edges[e.id].prev_out != -1)
299 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
300 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
301 if (nodes[n.id].first_out != -1) {
302 edges[nodes[n.id].first_out].prev_out = e.id;
304 edges[e.id].source = n.id;
305 edges[e.id].prev_out = -1;
306 edges[e.id].next_out = nodes[n.id].first_out;
307 nodes[n.id].first_out = e.id;
312 typedef ErasableGraphExtender<
313 ClearableGraphExtender<
314 ExtendableGraphExtender<
315 MappableGraphExtender<
316 IterableGraphExtender<
317 AlterableGraphExtender<
318 GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase;
320 /// \addtogroup graphs
323 ///A list graph class.
325 ///This is a simple and fast erasable graph implementation.
327 ///It addition that it conforms to the
328 ///\ref concept::ErasableGraph "ErasableGraph" concept,
329 ///it also provides several additional useful extra functionalities.
330 ///\sa concept::ErasableGraph.
332 class ListGraph : public ExtendedListGraphBase
335 /// Changes the target of \c e to \c n
337 /// Changes the target of \c e to \c n
339 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
340 ///referencing the changed edge remain
341 ///valid. However <tt>InEdge</tt>'s are invalidated.
342 void changeTarget(Edge e, Node n) {
345 /// Changes the source of \c e to \c n
347 /// Changes the source of \c e to \c n
349 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
350 ///referencing the changed edge remain
351 ///valid. However <tt>OutEdge</tt>'s are invalidated.
352 void changeSource(Edge e, Node n) {
356 /// Invert the direction of an edge.
358 ///\note The <tt>Edge</tt>'s
359 ///referencing the changed edge remain
360 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated.
361 void reverseEdge(Edge e) {
363 _changeTarget(e,source(e));
367 ///Using this it possible to avoid the superfluous memory allocation.
369 ///Using this it possible to avoid the superfluous memory allocation.
370 ///\todo more docs...
371 void reserveEdge(int n) { edges.reserve(n); };
373 ///Contract two nodes.
375 ///This function contracts two nodes.
377 ///Node \p b will be removed but instead of deleting
378 ///its neighboring edges, they will be joined to \p a.
379 ///The last parameter \p r controls whether to remove loops. \c true
380 ///means that loops will be removed.
382 ///\note The <tt>Edge</tt>s
383 ///referencing a moved edge remain
384 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
385 ///may be invalidated.
386 void contract(Node a, Node b, bool r = true)
388 for(OutEdgeIt e(*this,b);e!=INVALID;) {
391 if(r && target(e)==a) erase(e);
392 else changeSource(e,a);
395 for(InEdgeIt e(*this,b);e!=INVALID;) {
398 if(r && source(e)==a) erase(e);
399 else changeTarget(e,a);
407 ///This function splits a node. First a new node is added to the graph,
408 ///then the source of each outgoing edge of \c n is moved to this new node.
409 ///If \c connect is \c true (this is the default value), then a new edge
410 ///from \c n to the newly created node is also added.
411 ///\return The newly created node.
413 ///\note The <tt>Edge</tt>s
414 ///referencing a moved edge remain
415 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
416 ///may be invalidated.
417 ///\warning This functionality cannot be used together with the Snapshot
419 ///\todo It could be implemented in a bit faster way.
420 Node split(Node n, bool connect = true)
423 for(OutEdgeIt e(*this,n);e!=INVALID;) {
429 if(connect) addEdge(n,b);
435 ///This function splits an edge. First a new node \c b is added to the graph,
436 ///then the original edge is re-targetes to \c b. Finally an edge
437 ///from \c b to the original target is added.
438 ///\return The newly created node.
439 ///\warning This functionality cannot be used together with the Snapshot
444 addEdge(b,target(e));
449 ///Class to make a snapshot of the graph and to restrore to it later.
451 ///Class to make a snapshot of the graph and to restrore to it later.
453 ///The newly added nodes and edges can be removed using the
454 ///restore() function.
456 ///\warning Edge and node deletions cannot be restored.
457 ///\warning Snapshots cannot be nested.
458 class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
459 protected AlterationNotifier<Edge>::ObserverBase
463 class UnsupportedOperation : public LogicError {
465 virtual const char* exceptionName() const {
466 return "lemon::ListGraph::Snapshot::UnsupportedOperation";
474 std::list<Node> added_nodes;
475 std::list<Edge> added_edges;
478 virtual void add(const Node& n) {
479 added_nodes.push_back(n);
481 virtual void erase(const Node&)
483 throw UnsupportedOperation();
485 virtual void add(const Edge& n) {
486 added_edges.push_back(n);
488 virtual void erase(const Edge&)
490 throw UnsupportedOperation();
493 ///\bug What is this used for?
495 virtual void build() {}
496 ///\bug What is this used for?
498 virtual void clear() {}
500 void regist(ListGraph &_g) {
502 AlterationNotifier<Node>::ObserverBase::
503 attach(g->getNotifier(Node()));
504 AlterationNotifier<Edge>::ObserverBase::
505 attach(g->getNotifier(Edge()));
509 AlterationNotifier<Node>::ObserverBase::
511 AlterationNotifier<Edge>::ObserverBase::
517 ///Default constructur.
519 ///Default constructur.
520 ///To actually make a snapshot you must call save().
523 ///Constructor that immediately makes a snapshot.
525 ///This constructor immediately makes a snapshot of the graph.
526 ///\param _g The graph we make a snapshot of.
527 Snapshot(ListGraph &_g) {
530 ///\bug Is it necessary?
539 ///Make a snapshot of the graph.
541 ///This function can be called more than once. In case of a repeated
542 ///call, the previous snapshot gets lost.
543 ///\param _g The graph we make the snapshot of.
544 void save(ListGraph &_g)
554 ///Undo the changes until the last snapshot.
556 ///Undo the changes until last snapshot created by save().
558 ///\todo This function might be called undo().
562 while(!added_edges.empty()) {
563 old_g.erase(added_edges.front());
564 added_edges.pop_front();
566 while(!added_nodes.empty()) {
567 old_g.erase(added_nodes.front());
568 added_nodes.pop_front();
577 /**************** Undirected List Graph ****************/
579 typedef ErasableUndirGraphExtender<
580 ClearableUndirGraphExtender<
581 ExtendableUndirGraphExtender<
582 MappableUndirGraphExtender<
583 IterableUndirGraphExtender<
584 AlterableUndirGraphExtender<
585 UndirGraphExtender<ListGraphBase> > > > > > > ExtendedUndirListGraphBase;
587 /// \addtogroup graphs
590 ///An undirected list graph class.
592 ///This is a simple and fast erasable undirected graph implementation.
594 ///It conforms to the
595 ///\ref concept::UndirGraph "UndirGraph" concept.
597 ///\sa concept::UndirGraph.
599 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
600 ///haven't been implemented yet.
602 class UndirListGraph : public ExtendedUndirListGraphBase {
604 typedef ExtendedUndirListGraphBase Parent;
605 /// \brief Changes the target of \c e to \c n
607 /// Changes the target of \c e to \c n
609 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
610 /// referencing the changed edge remain
611 /// valid. However <tt>InEdge</tt>'s are invalidated.
612 void changeTarget(UndirEdge e, Node n) {
615 /// Changes the source of \c e to \c n
617 /// Changes the source of \c e to \c n
619 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
620 ///referencing the changed edge remain
621 ///valid. However <tt>OutEdge</tt>'s are invalidated.
622 void changeSource(UndirEdge e, Node n) {
625 /// \brief Contract two nodes.
627 /// This function contracts two nodes.
629 /// Node \p b will be removed but instead of deleting
630 /// its neighboring edges, they will be joined to \p a.
631 /// The last parameter \p r controls whether to remove loops. \c true
632 /// means that loops will be removed.
634 /// \note The <tt>Edge</tt>s
635 /// referencing a moved edge remain
637 void contract(Node a, Node b, bool r = true) {
638 for(IncEdgeIt e(*this, b); e!=INVALID;) {
639 IncEdgeIt f = e; ++f;
640 if (r && runningNode(e) == a) {
642 } else if (source(e) == b) {