2 * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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 SymSmartGraph classes.
26 #include <lemon/invalid.h>
28 #include <lemon/clearable_graph_extender.h>
29 #include <lemon/extendable_graph_extender.h>
30 #include <lemon/idmappable_graph_extender.h>
31 #include <lemon/iterable_graph_extender.h>
32 #include <lemon/alteration_observer_registry.h>
33 #include <lemon/default_map.h>
35 #include <lemon/utility.h>
39 /// \addtogroup graphs
47 class SmartGraphBase {
49 friend class SmatGraph;
54 int first_in,first_out;
55 NodeT() : first_in(-1), first_out(-1) {}
59 int head, tail, 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) : nodes(_g.nodes), edges(_g.edges) { }
82 typedef True NodeNumTag;
83 typedef True EdgeNumTag;
86 int nodeNum() const { return nodes.size(); }
88 int edgeNum() const { return edges.size(); }
94 int maxNodeId() const { return nodes.size()-1; }
99 int maxEdgeId() const { return edges.size()-1; }
101 Node tail(Edge e) const { return edges[e.n].tail; }
102 Node head(Edge e) const { return edges[e.n].head; }
106 /// The ID of a valid Node is a nonnegative integer not greater than
107 /// \ref maxNodeId(). The range of the ID's is not surely continuous
108 /// and the greatest node ID can be actually less then \ref maxNodeId().
110 /// The ID of the \ref INVALID node is -1.
111 ///\return The ID of the node \c v.
112 static int id(Node v) { return v.n; }
115 /// The ID of a valid Edge is a nonnegative integer not greater than
116 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
117 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
119 /// The ID of the \ref INVALID edge is -1.
120 ///\return The ID of the edge \c e.
121 static int id(Edge e) { return e.n; }
124 Node n; n.n=nodes.size();
125 nodes.push_back(NodeT()); //FIXME: Hmmm...
129 Edge addEdge(Node u, Node v) {
130 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
131 edges[e.n].tail=u.n; edges[e.n].head=v.n;
132 edges[e.n].next_out=nodes[u.n].first_out;
133 edges[e.n].next_in=nodes[v.n].first_in;
134 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
146 friend class SmartGraphBase;
147 friend class SmartGraph;
151 ///\todo It should be removed (or at least define a setToId() instead).
156 Node (Invalid) { n=-1; }
157 bool operator==(const Node i) const {return n==i.n;}
158 bool operator!=(const Node i) const {return n!=i.n;}
159 bool operator<(const Node i) const {return n<i.n;}
164 friend class SmartGraphBase;
165 friend class SmartGraph;
169 ///\todo It should be removed (or at least define a setToId() instead).
174 Edge (Invalid) { n=-1; }
175 bool operator==(const Edge i) const {return n==i.n;}
176 bool operator!=(const Edge i) const {return n!=i.n;}
177 bool operator<(const Edge i) const {return n<i.n;}
180 void first(Node& node) const {
181 node.n = nodes.size() - 1;
184 static void next(Node& node) {
188 void first(Edge& edge) const {
189 edge.n = edges.size() - 1;
192 static void next(Edge& edge) {
196 void firstOut(Edge& edge, const Node& node) const {
197 edge.n = nodes[node.n].first_out;
200 void nextOut(Edge& edge) const {
201 edge.n = edges[edge.n].next_out;
204 void firstIn(Edge& edge, const Node& node) const {
205 edge.n = nodes[node.n].first_in;
208 void nextIn(Edge& edge) const {
209 edge.n = edges[edge.n].next_in;
212 Edge _findEdge(Node u,Node v, Edge prev = INVALID)
214 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
215 while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
222 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
223 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
224 typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;
225 typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;
226 typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
227 typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
229 ///A smart graph class.
231 ///This is a simple and fast graph implementation.
232 ///It is also quite memory efficient, but at the price
233 ///that <b> it does support only limited (only stack-like)
234 ///node and edge deletions</b>.
236 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
237 ///\sa concept::ExtendableGraph.
239 ///\todo Some member functions could be \c static.
241 ///\author Alpar Juttner
242 class SmartGraph :public ClearableSmartGraphBase {
244 /// Finds an edge between two nodes.
246 /// Finds an edge from node \c u to node \c v.
248 /// If \c prev is \ref INVALID (this is the default value), then
249 /// it finds the first edge from \c u to \c v. Otherwise it looks for
250 /// the next edge from \c u to \c v after \c prev.
251 /// \return The found edge or \ref INVALID if there is no such an edge.
253 /// Thus you can iterate through each edge from \c u to \c v as it follows.
255 /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {
259 /// \todo Possibly it should be a global function.
260 Edge findEdge(Node u,Node v, Edge prev = INVALID)
262 return _findEdge(u,v,prev);
265 ///Internal data structure to store snapshots
268 ///\sa makeSnapShot()
272 unsigned int node_num;
273 unsigned int edge_num;
276 ///Make a snapshot of the graph.
278 ///Make a snapshot of the graph.
280 ///The newly added nodes and edges can be removed using the
281 ///rollBack() function.
283 ///\return An stucture SnapShot describing the pesent state of the
285 ///\note After you rolled back to a state, you cannot roll "back" to
286 ///a later state, in other word you cannot add again the edges deleted
288 ///\todo This function might be called saveState() or getState().
289 SnapShot makeSnapShot()
292 s.node_num=nodes.size();
293 s.edge_num=edges.size();
297 ///Undo the changes until a snapshot.
299 ///Undo the changes until a snapshot created by makeSnapShot().
301 ///\param s an internal stucture given back by makeSnapShot()
302 ///\note After you rolled back to a state, you cannot "roll forward" to
303 ///a later state, in other word you cannot add again the edges deleted
306 ///\todo This function might be called undo().
308 void rollBack(const SnapShot &s)
310 while(s.edge_num>edges.size()) {
311 edge_observers.erase(Edge(edges.size()-1));
312 nodes[edges.back().head].first_in=edges.back().next_in;
313 nodes[edges.back().tail].first_out=edges.back().next_out;
316 //nodes.resize(s.nodes_num);
317 while(s.node_num>nodes.size()) {
318 node_observers.erase(Node(nodes.size()-1));
328 #endif //LEMON_SMART_GRAPH_H