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>
34 #include <lemon/bits/undir_graph_extender.h>
36 #include <lemon/utility.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 maxId(Node) const { return nodes.size()-1; }
98 int maxId(Edge) 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 maxId(Node). The range of the ID's is not surely continuous
107 /// and the greatest node ID can be actually less then \ref maxId(Node).
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 maxId(Edge). The range of the ID's is not surely continuous
116 /// and the greatest edge ID can be actually less then \ref maxId(Edge).
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 fromId(int id, Node) { return Node(id);}
124 static Edge fromId(int id, Edge) { 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;
156 ///\todo It should be removed (or at least define a setToId() instead).
161 Node (Invalid) { n=-1; }
162 bool operator==(const Node i) const {return n==i.n;}
163 bool operator!=(const Node i) const {return n!=i.n;}
164 bool operator<(const Node i) const {return n<i.n;}
169 friend class SmartGraphBase;
170 friend class SmartGraph;
174 ///\todo It should be removed (or at least define a setToId() instead).
179 Edge (Invalid) { n=-1; }
180 bool operator==(const Edge i) const {return n==i.n;}
181 bool operator!=(const Edge i) const {return n!=i.n;}
182 bool operator<(const Edge i) const {return n<i.n;}
185 void first(Node& node) const {
186 node.n = nodes.size() - 1;
189 static void next(Node& node) {
193 void first(Edge& edge) const {
194 edge.n = edges.size() - 1;
197 static void next(Edge& edge) {
201 void firstOut(Edge& edge, const Node& node) const {
202 edge.n = nodes[node.n].first_out;
205 void nextOut(Edge& edge) const {
206 edge.n = edges[edge.n].next_out;
209 void firstIn(Edge& edge, const Node& node) const {
210 edge.n = nodes[node.n].first_in;
213 void nextIn(Edge& edge) const {
214 edge.n = edges[edge.n].next_in;
217 Node _split(Node n, bool connect = true)
220 nodes[b.n].first_out=nodes[n.n].first_out;
221 nodes[n.n].first_out=-1;
222 for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
223 if(connect) addEdge(n,b);
229 typedef ClearableGraphExtender<
230 ExtendableGraphExtender<
231 MappableGraphExtender<
232 IterableGraphExtender<
233 AlterableGraphExtender<SmartGraphBase> > > > > ExtendedSmartGraphBase;
235 /// \addtogroup graphs
238 ///A smart graph class.
240 ///This is a simple and fast graph implementation.
241 ///It is also quite memory efficient, but at the price
242 ///that <b> it does support only limited (only stack-like)
243 ///node and edge deletions</b>.
245 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
246 ///\sa concept::ExtendableGraph.
248 ///\author Alpar Juttner
249 class SmartGraph : public ExtendedSmartGraphBase {
253 friend class Snapshot;
256 void restoreSnapshot(const Snapshot &s)
258 while(s.edge_num<edges.size()) {
259 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
260 nodes[edges.back().target].first_in=edges.back().next_in;
261 nodes[edges.back().source].first_out=edges.back().next_out;
264 //nodes.resize(s.nodes_num);
265 while(s.node_num<nodes.size()) {
266 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
275 ///This function splits a node. First a new node is added to the graph,
276 ///then the source of each outgoing edge of \c n is moved to this new node.
277 ///If \c connect is \c true (this is the default value), then a new edge
278 ///from \c n to the newly created node is also added.
279 ///\return The newly created node.
281 ///\note The <tt>Edge</tt>s
282 ///referencing a moved edge remain
283 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
284 ///may be invalidated.
285 ///\warning This functionality cannot be used together with the Snapshot
287 ///\todo It could be implemented in a bit faster way.
288 Node split(Node n, bool connect = true)
290 Node b = _split(n,connect);
295 ///Class to make a snapshot of the graph and to restrore to it later.
297 ///Class to make a snapshot of the graph and to restrore to it later.
299 ///The newly added nodes and edges can be removed using the
300 ///restore() function.
301 ///\note After you restore a state, you cannot restore
302 ///a later state, in other word you cannot add again the edges deleted
303 ///by restore() using another Snapshot instance.
309 friend class SmartGraph;
310 unsigned int node_num;
311 unsigned int edge_num;
313 ///Default constructor.
315 ///Default constructor.
316 ///To actually make a snapshot you must call save().
319 ///Constructor that immediately makes a snapshot
321 ///This constructor immediately makes a snapshot of the graph.
322 ///\param _g The graph we make a snapshot of.
323 Snapshot(SmartGraph &_g) :g(&_g) {
324 node_num=g->nodes.size();
325 edge_num=g->edges.size();
330 ///Make a snapshot of the graph.
332 ///This function can be called more than once. In case of a repeated
333 ///call, the previous snapshot gets lost.
334 ///\param _g The graph we make the snapshot of.
335 void save(SmartGraph &_g)
338 node_num=g->nodes.size();
339 edge_num=g->edges.size();
342 ///Undo the changes until a snapshot.
344 ///Undo the changes until a snapshot created by save().
346 ///\note After you restored a state, you cannot restore
347 ///a later state, in other word you cannot add again the edges deleted
350 ///\todo This function might be called undo().
354 g->restoreSnapshot(*this);
360 /**************** Undirected List Graph ****************/
362 typedef ClearableUndirGraphExtender<
363 ExtendableUndirGraphExtender<
364 MappableUndirGraphExtender<
365 IterableUndirGraphExtender<
366 AlterableUndirGraphExtender<
367 UndirGraphExtender<SmartGraphBase> > > > > > ExtendedUndirSmartGraphBase;
369 ///A smart undirected graph class.
371 ///This is a simple and fast undirected graph implementation.
372 ///It is also quite memory efficient, but at the price
373 ///that <b> it does support only limited (only stack-like)
374 ///node and edge deletions</b>.
375 ///Except from this it conforms to
376 ///the \ref concept::UndirGraph "UndirGraph" concept.
377 ///\sa concept::UndirGraph.
379 ///\todo Snapshot hasn't been implemented yet.
381 class UndirSmartGraph : public ExtendedUndirSmartGraphBase {
389 #endif //LEMON_SMART_GRAPH_H