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/smart_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_SMART_GRAPH_H
18 #define LEMON_SMART_GRAPH_H
22 ///\brief SmartGraph and UndirSmartGraph classes.
26 #include <lemon/invalid.h>
28 #include <lemon/bits/clearable_graph_extender.h>
29 #include <lemon/bits/extendable_graph_extender.h>
30 #include <lemon/bits/iterable_graph_extender.h>
31 #include <lemon/bits/alteration_notifier.h>
32 #include <lemon/bits/default_map.h>
33 #include <lemon/bits/graph_extender.h>
35 #include <lemon/utility.h>
36 #include <lemon/error.h>
45 class SmartGraphBase {
47 friend class SmatGraph;
52 int first_in,first_out;
53 NodeT() : first_in(-1), first_out(-1) {}
57 int target, source, next_in, next_out;
58 //FIXME: is this necessary?
59 EdgeT() : next_in(-1), next_out(-1) {}
62 std::vector<NodeT> nodes;
64 std::vector<EdgeT> edges;
69 typedef SmartGraphBase Graph;
77 SmartGraphBase() : nodes(), edges() { }
78 SmartGraphBase(const SmartGraphBase &_g)
79 : nodes(_g.nodes), edges(_g.edges) { }
81 typedef True NodeNumTag;
82 typedef True EdgeNumTag;
85 int nodeNum() const { return nodes.size(); }
87 int edgeNum() const { return edges.size(); }
93 int maxNodeId() const { return nodes.size()-1; }
98 int maxEdgeId() const { return edges.size()-1; }
100 Node source(Edge e) const { return edges[e.n].source; }
101 Node target(Edge e) const { return edges[e.n].target; }
105 /// The ID of a valid Node is a nonnegative integer not greater than
106 /// \ref maxNodeId(). The range of the ID's is not surely continuous
107 /// and the greatest node ID can be actually less then \ref maxNodeId().
109 /// The ID of the \ref INVALID node is -1.
110 ///\return The ID of the node \c v.
111 static int id(Node v) { return v.n; }
114 /// The ID of a valid Edge is a nonnegative integer not greater than
115 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
116 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
118 /// The ID of the \ref INVALID edge is -1.
119 ///\return The ID of the edge \c e.
120 static int id(Edge e) { return e.n; }
122 static Node nodeFromId(int id) { return Node(id);}
124 static Edge edgeFromId(int id) { return Edge(id);}
127 Node n; n.n=nodes.size();
128 nodes.push_back(NodeT()); //FIXME: Hmmm...
132 Edge addEdge(Node u, Node v) {
133 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
134 edges[e.n].source=u.n; edges[e.n].target=v.n;
135 edges[e.n].next_out=nodes[u.n].first_out;
136 edges[e.n].next_in=nodes[v.n].first_in;
137 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
149 friend class SmartGraphBase;
150 friend class SmartGraph;
157 Node (Invalid) { n=-1; }
158 bool operator==(const Node i) const {return n==i.n;}
159 bool operator!=(const Node i) const {return n!=i.n;}
160 bool operator<(const Node i) const {return n<i.n;}
165 friend class SmartGraphBase;
166 friend class SmartGraph;
173 Edge (Invalid) { n=-1; }
174 bool operator==(const Edge i) const {return n==i.n;}
175 bool operator!=(const Edge i) const {return n!=i.n;}
176 bool operator<(const Edge i) const {return n<i.n;}
179 void first(Node& node) const {
180 node.n = nodes.size() - 1;
183 static void next(Node& node) {
187 void first(Edge& edge) const {
188 edge.n = edges.size() - 1;
191 static void next(Edge& edge) {
195 void firstOut(Edge& edge, const Node& node) const {
196 edge.n = nodes[node.n].first_out;
199 void nextOut(Edge& edge) const {
200 edge.n = edges[edge.n].next_out;
203 void firstIn(Edge& edge, const Node& node) const {
204 edge.n = nodes[node.n].first_in;
207 void nextIn(Edge& edge) const {
208 edge.n = edges[edge.n].next_in;
211 Node _split(Node n, bool connect = true)
214 nodes[b.n].first_out=nodes[n.n].first_out;
215 nodes[n.n].first_out=-1;
216 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
217 if(connect) addEdge(n,b);
223 typedef ClearableGraphExtender<
224 ExtendableGraphExtender<
225 MappableGraphExtender<
226 IterableGraphExtender<
227 AlterableGraphExtender<
228 GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
232 ///A smart graph class.
234 ///This is a simple and fast graph implementation.
235 ///It is also quite memory efficient, but at the price
236 ///that <b> it does support only limited (only stack-like)
237 ///node and edge deletions</b>.
239 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
240 ///\sa concept::ExtendableGraph.
242 ///\author Alpar Juttner
243 class SmartGraph : public ExtendedSmartGraphBase {
247 friend class Snapshot;
250 void restoreSnapshot(const Snapshot &s)
252 while(s.edge_num<edges.size()) {
253 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
254 nodes[edges.back().target].first_in=edges.back().next_in;
255 nodes[edges.back().source].first_out=edges.back().next_out;
258 //nodes.resize(s.nodes_num);
259 while(s.node_num<nodes.size()) {
260 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
269 ///This function splits a node. First a new node is added to the graph,
270 ///then the source of each outgoing edge of \c n is moved to this new node.
271 ///If \c connect is \c true (this is the default value), then a new edge
272 ///from \c n to the newly created node is also added.
273 ///\return The newly created node.
275 ///\note The <tt>Edge</tt>s
276 ///referencing a moved edge remain
277 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
278 ///may be invalidated.
279 ///\warning This functionality cannot be used together with the Snapshot
281 ///\todo It could be implemented in a bit faster way.
282 Node split(Node n, bool connect = true)
284 Node b = _split(n,connect);
289 ///Class to make a snapshot of the graph and to restrore to it later.
291 ///Class to make a snapshot of the graph and to restrore to it later.
293 ///The newly added nodes and edges can be removed using the
294 ///restore() function.
295 ///\note After you restore a state, you cannot restore
296 ///a later state, in other word you cannot add again the edges deleted
297 ///by restore() using another Snapshot instance.
303 friend class SmartGraph;
304 unsigned int node_num;
305 unsigned int edge_num;
307 ///Default constructor.
309 ///Default constructor.
310 ///To actually make a snapshot you must call save().
313 ///Constructor that immediately makes a snapshot
315 ///This constructor immediately makes a snapshot of the graph.
316 ///\param _g The graph we make a snapshot of.
317 Snapshot(SmartGraph &_g) :g(&_g) {
318 node_num=g->nodes.size();
319 edge_num=g->edges.size();
324 ///Make a snapshot of the graph.
326 ///This function can be called more than once. In case of a repeated
327 ///call, the previous snapshot gets lost.
328 ///\param _g The graph we make the snapshot of.
329 void save(SmartGraph &_g)
332 node_num=g->nodes.size();
333 edge_num=g->edges.size();
336 ///Undo the changes until a snapshot.
338 ///Undo the changes until a snapshot created by save().
340 ///\note After you restored a state, you cannot restore
341 ///a later state, in other word you cannot add again the edges deleted
344 ///\todo This function might be called undo().
348 g->restoreSnapshot(*this);
354 /**************** Undirected List Graph ****************/
356 typedef ClearableUndirGraphExtender<
357 ExtendableUndirGraphExtender<
358 MappableUndirGraphExtender<
359 IterableUndirGraphExtender<
360 AlterableUndirGraphExtender<
361 UndirGraphExtender<SmartGraphBase> > > > > > ExtendedUndirSmartGraphBase;
363 ///A smart undirected graph class.
365 ///This is a simple and fast undirected graph implementation.
366 ///It is also quite memory efficient, but at the price
367 ///that <b> it does support only limited (only stack-like)
368 ///node and edge deletions</b>.
369 ///Except from this it conforms to
370 ///the \ref concept::UndirGraph "UndirGraph" concept.
371 ///\sa concept::UndirGraph.
373 ///\todo Snapshot hasn't been implemented yet.
375 class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
379 class SmartUndirBipartiteGraphBase {
382 class NodeSetError : public LogicError {
383 virtual const char* exceptionName() const {
384 return "lemon::FullUndirBipartiteGraph::NodeSetError";
393 NodeT(int _first) : first(_first) {}
397 int upper, next_down;
401 std::vector<NodeT> upperNodes;
402 std::vector<NodeT> lowerNodes;
404 std::vector<EdgeT> edges;
409 friend class SmartUndirBipartiteGraphBase;
413 Node(int _id) : id(_id) {}
416 Node(Invalid) { id = -1; }
417 bool operator==(const Node i) const {return id==i.id;}
418 bool operator!=(const Node i) const {return id!=i.id;}
419 bool operator<(const Node i) const {return id<i.id;}
423 friend class SmartUndirBipartiteGraphBase;
427 Edge(int _id) { id = _id;}
430 Edge (Invalid) { id = -1; }
431 bool operator==(const Edge i) const {return id==i.id;}
432 bool operator!=(const Edge i) const {return id!=i.id;}
433 bool operator<(const Edge i) const {return id<i.id;}
436 void firstUpper(Node& node) const {
437 node.id = 2 * upperNodes.size() - 2;
438 if (node.id < 0) node.id = -1;
440 void nextUpper(Node& node) const {
442 if (node.id < 0) node.id = -1;
445 void firstLower(Node& node) const {
446 node.id = 2 * lowerNodes.size() - 1;
448 void nextLower(Node& node) const {
452 void first(Node& node) const {
453 if (upperNodes.size() > 0) {
454 node.id = 2 * upperNodes.size() - 2;
456 node.id = 2 * lowerNodes.size() - 1;
459 void next(Node& node) const {
462 node.id = 2 * lowerNodes.size() - 1;
466 void first(Edge& edge) const {
467 edge.id = edges.size() - 1;
469 void next(Edge& edge) const {
473 void firstDown(Edge& edge, const Node& node) const {
474 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
475 edge.id = upperNodes[node.id >> 1].first;
477 void nextDown(Edge& edge) const {
478 edge.id = edges[edge.id].next_down;
481 void firstUp(Edge& edge, const Node& node) const {
482 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
483 edge.id = lowerNodes[node.id >> 1].first;
485 void nextUp(Edge& edge) const {
486 edge.id = edges[edge.id].next_up;
489 static int id(const Node& node) {
492 static Node nodeFromId(int id) {
495 int maxNodeId() const {
496 return upperNodes.size() > lowerNodes.size() ?
497 upperNodes.size() * 2 - 2 : lowerNodes.size() * 2 - 1;
500 static int id(const Edge& edge) {
503 static Edge edgeFromId(int id) {
506 int maxEdgeId() const {
510 static int upperId(const Node& node) {
513 static Node fromUpperId(int id, Node) {
514 return Node(id << 1);
516 int maxUpperId() const {
517 return upperNodes.size();
520 static int lowerId(const Node& node) {
523 static Node fromLowerId(int id) {
524 return Node((id << 1) + 1);
526 int maxLowerId() const {
527 return lowerNodes.size();
530 Node upperNode(const Edge& edge) const {
531 return Node(edges[edge.id].upper);
533 Node lowerNode(const Edge& edge) const {
534 return Node(edges[edge.id].lower);
537 static bool upper(const Node& node) {
538 return (node.id & 1) == 0;
541 static bool lower(const Node& node) {
542 return (node.id & 1) == 1;
545 Node addUpperNode() {
548 upperNodes.push_back(nodeT);
549 return Node(upperNodes.size() * 2 - 2);
552 Node addLowerNode() {
555 lowerNodes.push_back(nodeT);
556 return Node(lowerNodes.size() * 2 - 1);
559 Edge addEdge(const Node& source, const Node& target) {
560 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
562 if ((source.id & 1) == 0) {
563 edgeT.upper = source.id;
564 edgeT.lower = target.id;
566 edgeT.upper = target.id;
567 edgeT.lower = source.id;
569 edgeT.next_down = upperNodes[edgeT.upper >> 1].first;
570 upperNodes[edgeT.upper >> 1].first = edges.size();
571 edgeT.next_up = lowerNodes[edgeT.lower >> 1].first;
572 lowerNodes[edgeT.lower >> 1].first = edges.size();
573 edges.push_back(edgeT);
574 return Edge(edges.size() - 1);
586 typedef ClearableUndirBipartiteGraphExtender<
587 ExtendableUndirBipartiteGraphExtender<
588 MappableUndirBipartiteGraphExtender<
589 IterableUndirBipartiteGraphExtender<
590 AlterableUndirBipartiteGraphExtender<
591 UndirBipartiteGraphExtender <
592 SmartUndirBipartiteGraphBase> > > > > >
593 ExtendedSmartUndirBipartiteGraphBase;
596 class SmartUndirBipartiteGraph :
597 public ExtendedSmartUndirBipartiteGraphBase {
605 #endif //LEMON_SMART_GRAPH_H