vmap.h: Enables one to create maps with a virtual base class.
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_SMART_GRAPH_H
20 #define LEMON_SMART_GRAPH_H
24 ///\brief SmartGraph and SmartUGraph classes.
28 #include <lemon/invalid.h>
30 #include <lemon/bits/clearable_graph_extender.h>
31 #include <lemon/bits/extendable_graph_extender.h>
32 #include <lemon/bits/iterable_graph_extender.h>
33 #include <lemon/bits/alteration_notifier.h>
34 #include <lemon/bits/default_map.h>
35 #include <lemon/bits/graph_extender.h>
37 #include <lemon/utility.h>
38 #include <lemon/error.h>
47 class SmartGraphBase {
49 friend class SmatGraph;
54 int first_in,first_out;
55 NodeT() : first_in(-1), first_out(-1) {}
59 int target, source, next_in, next_out;
60 //FIXME: is this necessary?
61 EdgeT() : next_in(-1), next_out(-1) {}
64 std::vector<NodeT> nodes;
66 std::vector<EdgeT> edges;
71 typedef SmartGraphBase Graph;
79 SmartGraphBase() : nodes(), edges() { }
80 SmartGraphBase(const SmartGraphBase &_g)
81 : nodes(_g.nodes), edges(_g.edges) { }
83 typedef True NodeNumTag;
84 typedef True EdgeNumTag;
87 int nodeNum() const { return nodes.size(); }
89 int edgeNum() const { return edges.size(); }
95 int maxNodeId() const { return nodes.size()-1; }
100 int maxEdgeId() const { return edges.size()-1; }
102 Node source(Edge e) const { return edges[e.n].source; }
103 Node target(Edge e) const { return edges[e.n].target; }
107 /// The ID of a valid Node is a nonnegative integer not greater than
108 /// \ref maxNodeId(). The range of the ID's is not surely continuous
109 /// and the greatest node ID can be actually less then \ref maxNodeId().
111 /// The ID of the \ref INVALID node is -1.
112 ///\return The ID of the node \c v.
113 static int id(Node v) { return v.n; }
116 /// The ID of a valid Edge is a nonnegative integer not greater than
117 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
118 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
120 /// The ID of the \ref INVALID edge is -1.
121 ///\return The ID of the edge \c e.
122 static int id(Edge e) { return e.n; }
124 static Node nodeFromId(int id) { return Node(id);}
126 static Edge edgeFromId(int id) { return Edge(id);}
129 Node n; n.n=nodes.size();
130 nodes.push_back(NodeT()); //FIXME: Hmmm...
134 Edge addEdge(Node u, Node v) {
135 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
136 edges[e.n].source=u.n; edges[e.n].target=v.n;
137 edges[e.n].next_out=nodes[u.n].first_out;
138 edges[e.n].next_in=nodes[v.n].first_in;
139 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
151 friend class SmartGraphBase;
152 friend class SmartGraph;
159 Node (Invalid) { n=-1; }
160 bool operator==(const Node i) const {return n==i.n;}
161 bool operator!=(const Node i) const {return n!=i.n;}
162 bool operator<(const Node i) const {return n<i.n;}
167 friend class SmartGraphBase;
168 friend class SmartGraph;
175 Edge (Invalid) { n=-1; }
176 bool operator==(const Edge i) const {return n==i.n;}
177 bool operator!=(const Edge i) const {return n!=i.n;}
178 bool operator<(const Edge i) const {return n<i.n;}
181 void first(Node& node) const {
182 node.n = nodes.size() - 1;
185 static void next(Node& node) {
189 void first(Edge& edge) const {
190 edge.n = edges.size() - 1;
193 static void next(Edge& edge) {
197 void firstOut(Edge& edge, const Node& node) const {
198 edge.n = nodes[node.n].first_out;
201 void nextOut(Edge& edge) const {
202 edge.n = edges[edge.n].next_out;
205 void firstIn(Edge& edge, const Node& node) const {
206 edge.n = nodes[node.n].first_in;
209 void nextIn(Edge& edge) const {
210 edge.n = edges[edge.n].next_in;
213 Node _split(Node n, bool connect = true)
216 nodes[b.n].first_out=nodes[n.n].first_out;
217 nodes[n.n].first_out=-1;
218 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
219 if(connect) addEdge(n,b);
225 typedef ClearableGraphExtender<
226 ExtendableGraphExtender<
227 MappableGraphExtender<
228 IterableGraphExtender<
229 AlterableGraphExtender<
230 GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
234 ///A smart graph class.
236 ///This is a simple and fast graph implementation.
237 ///It is also quite memory efficient, but at the price
238 ///that <b> it does support only limited (only stack-like)
239 ///node and edge deletions</b>.
241 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
242 ///\sa concept::ExtendableGraph.
244 ///\author Alpar Juttner
245 class SmartGraph : public ExtendedSmartGraphBase {
249 friend class Snapshot;
252 void restoreSnapshot(const Snapshot &s)
254 while(s.edge_num<edges.size()) {
255 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
256 nodes[edges.back().target].first_in=edges.back().next_in;
257 nodes[edges.back().source].first_out=edges.back().next_out;
260 //nodes.resize(s.nodes_num);
261 while(s.node_num<nodes.size()) {
262 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
271 ///This function splits a node. First a new node is added to the graph,
272 ///then the source of each outgoing edge of \c n is moved to this new node.
273 ///If \c connect is \c true (this is the default value), then a new edge
274 ///from \c n to the newly created node is also added.
275 ///\return The newly created node.
277 ///\note The <tt>Edge</tt>s
278 ///referencing a moved edge remain
279 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
280 ///may be invalidated.
281 ///\warning This functionality cannot be used together with the Snapshot
283 ///\todo It could be implemented in a bit faster way.
284 Node split(Node n, bool connect = true)
286 Node b = _split(n,connect);
291 ///Class to make a snapshot of the graph and to restrore to it later.
293 ///Class to make a snapshot of the graph and to restrore to it later.
295 ///The newly added nodes and edges can be removed using the
296 ///restore() function.
297 ///\note After you restore a state, you cannot restore
298 ///a later state, in other word you cannot add again the edges deleted
299 ///by restore() using another Snapshot instance.
305 friend class SmartGraph;
306 unsigned int node_num;
307 unsigned int edge_num;
309 ///Default constructor.
311 ///Default constructor.
312 ///To actually make a snapshot you must call save().
315 ///Constructor that immediately makes a snapshot
317 ///This constructor immediately makes a snapshot of the graph.
318 ///\param _g The graph we make a snapshot of.
319 Snapshot(SmartGraph &_g) :g(&_g) {
320 node_num=g->nodes.size();
321 edge_num=g->edges.size();
326 ///Make a snapshot of the graph.
328 ///This function can be called more than once. In case of a repeated
329 ///call, the previous snapshot gets lost.
330 ///\param _g The graph we make the snapshot of.
331 void save(SmartGraph &_g)
334 node_num=g->nodes.size();
335 edge_num=g->edges.size();
338 ///Undo the changes until a snapshot.
340 ///Undo the changes until a snapshot created by save().
342 ///\note After you restored a state, you cannot restore
343 ///a later state, in other word you cannot add again the edges deleted
346 ///\todo This function might be called undo().
350 g->restoreSnapshot(*this);
356 /**************** Undirected List Graph ****************/
358 typedef ClearableUGraphExtender<
359 ExtendableUGraphExtender<
360 MappableUGraphExtender<
361 IterableUGraphExtender<
362 AlterableUGraphExtender<
363 UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
367 /// \brief A smart undirected graph class.
369 /// This is a simple and fast undirected graph implementation.
370 /// It is also quite memory efficient, but at the price
371 /// that <b> it does support only limited (only stack-like)
372 /// node and edge deletions</b>.
373 /// Except from this it conforms to
374 /// the \ref concept::UGraph "UGraph" concept.
375 /// \sa concept::UGraph.
377 /// \todo Snapshot hasn't been implemented yet.
379 class SmartUGraph : public ExtendedSmartUGraphBase {
383 class SmartBpUGraphBase {
386 class NodeSetError : public LogicError {
387 virtual const char* exceptionName() const {
388 return "lemon::SmartBpUGraph::NodeSetError";
397 NodeT(int _first) : first(_first) {}
405 std::vector<NodeT> aNodes;
406 std::vector<NodeT> bNodes;
408 std::vector<EdgeT> edges;
413 friend class SmartBpUGraphBase;
417 Node(int _id) : id(_id) {}
420 Node(Invalid) { id = -1; }
421 bool operator==(const Node i) const {return id==i.id;}
422 bool operator!=(const Node i) const {return id!=i.id;}
423 bool operator<(const Node i) const {return id<i.id;}
427 friend class SmartBpUGraphBase;
431 Edge(int _id) { id = _id;}
434 Edge (Invalid) { id = -1; }
435 bool operator==(const Edge i) const {return id==i.id;}
436 bool operator!=(const Edge i) const {return id!=i.id;}
437 bool operator<(const Edge i) const {return id<i.id;}
440 void firstANode(Node& node) const {
441 node.id = 2 * aNodes.size() - 2;
442 if (node.id < 0) node.id = -1;
444 void nextANode(Node& node) const {
446 if (node.id < 0) node.id = -1;
449 void firstBNode(Node& node) const {
450 node.id = 2 * bNodes.size() - 1;
452 void nextBNode(Node& node) const {
456 void first(Node& node) const {
457 if (aNodes.size() > 0) {
458 node.id = 2 * aNodes.size() - 2;
460 node.id = 2 * bNodes.size() - 1;
463 void next(Node& node) const {
466 node.id = 2 * bNodes.size() - 1;
470 void first(Edge& edge) const {
471 edge.id = edges.size() - 1;
473 void next(Edge& edge) const {
477 void firstOut(Edge& edge, const Node& node) const {
478 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
479 edge.id = aNodes[node.id >> 1].first;
481 void nextOut(Edge& edge) const {
482 edge.id = edges[edge.id].next_out;
485 void firstIn(Edge& edge, const Node& node) const {
486 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
487 edge.id = bNodes[node.id >> 1].first;
489 void nextIn(Edge& edge) const {
490 edge.id = edges[edge.id].next_in;
493 static int id(const Node& node) {
496 static Node nodeFromId(int id) {
499 int maxNodeId() const {
500 return aNodes.size() > bNodes.size() ?
501 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
504 static int id(const Edge& edge) {
507 static Edge edgeFromId(int id) {
510 int maxEdgeId() const {
514 static int aNodeId(const Node& node) {
517 static Node fromANodeId(int id, Node) {
518 return Node(id << 1);
520 int maxANodeId() const {
521 return aNodes.size();
524 static int bNodeId(const Node& node) {
527 static Node fromBNodeId(int id) {
528 return Node((id << 1) + 1);
530 int maxBNodeId() const {
531 return bNodes.size();
534 Node aNode(const Edge& edge) const {
535 return Node(edges[edge.id].aNode);
537 Node bNode(const Edge& edge) const {
538 return Node(edges[edge.id].bNode);
541 static bool aNode(const Node& node) {
542 return (node.id & 1) == 0;
545 static bool bNode(const Node& node) {
546 return (node.id & 1) == 1;
552 aNodes.push_back(nodeT);
553 return Node(aNodes.size() * 2 - 2);
559 bNodes.push_back(nodeT);
560 return Node(bNodes.size() * 2 - 1);
563 Edge addEdge(const Node& source, const Node& target) {
564 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
566 if ((source.id & 1) == 0) {
567 edgeT.aNode = source.id;
568 edgeT.bNode = target.id;
570 edgeT.aNode = target.id;
571 edgeT.bNode = source.id;
573 edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
574 aNodes[edgeT.aNode >> 1].first = edges.size();
575 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
576 bNodes[edgeT.bNode >> 1].first = edges.size();
577 edges.push_back(edgeT);
578 return Edge(edges.size() - 1);
590 typedef ClearableBpUGraphExtender<
591 ExtendableBpUGraphExtender<
592 MappableBpUGraphExtender<
593 IterableBpUGraphExtender<
594 AlterableBpUGraphExtender<
596 SmartBpUGraphBase> > > > > >
597 ExtendedSmartBpUGraphBase;
601 /// \brief A smart bipartite undirected graph class.
603 /// This is a simple and fast bipartite undirected graph implementation.
604 /// It is also quite memory efficient, but at the price
605 /// that <b> it does not support node and edge deletions</b>.
606 /// Except from this it conforms to
607 /// the \ref concept::BpUGraph "BpUGraph" concept.
608 /// \sa concept::BpUGraph.
610 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {};
617 #endif //LEMON_SMART_GRAPH_H