- A primitive function type interface for Preflow.
- A compilation bug fixed
2 * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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/iterable_graph_extender.h>
31 #include <lemon/alteration_notifier.h>
32 #include <lemon/default_map.h>
34 #include <lemon/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) : nodes(_g.nodes), edges(_g.edges) { }
80 typedef True NodeNumTag;
81 typedef True EdgeNumTag;
84 int nodeNum() const { return nodes.size(); }
86 int edgeNum() const { return edges.size(); }
92 int maxId(Node = INVALID) const { return nodes.size()-1; }
97 int maxId(Edge = INVALID) const { return edges.size()-1; }
99 Node source(Edge e) const { return edges[e.n].source; }
100 Node target(Edge e) const { return edges[e.n].target; }
104 /// The ID of a valid Node is a nonnegative integer not greater than
105 /// \ref maxNodeId(). The range of the ID's is not surely continuous
106 /// and the greatest node ID can be actually less then \ref maxNodeId().
108 /// The ID of the \ref INVALID node is -1.
109 ///\return The ID of the node \c v.
110 static int id(Node v) { return v.n; }
113 /// The ID of a valid Edge is a nonnegative integer not greater than
114 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
115 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
117 /// The ID of the \ref INVALID edge is -1.
118 ///\return The ID of the edge \c e.
119 static int id(Edge e) { return e.n; }
121 static Node fromId(int id, Node) { return Node(id);}
123 static Edge fromId(int id, Edge) { return Edge(id);}
126 Node n; n.n=nodes.size();
127 nodes.push_back(NodeT()); //FIXME: Hmmm...
131 Edge addEdge(Node u, Node v) {
132 Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
133 edges[e.n].source=u.n; edges[e.n].target=v.n;
134 edges[e.n].next_out=nodes[u.n].first_out;
135 edges[e.n].next_in=nodes[v.n].first_in;
136 nodes[u.n].first_out=nodes[v.n].first_in=e.n;
148 friend class SmartGraphBase;
149 friend class SmartGraph;
153 ///\todo It should be removed (or at least define a setToId() instead).
158 Node (Invalid) { n=-1; }
159 bool operator==(const Node i) const {return n==i.n;}
160 bool operator!=(const Node i) const {return n!=i.n;}
161 bool operator<(const Node i) const {return n<i.n;}
166 friend class SmartGraphBase;
167 friend class SmartGraph;
171 ///\todo It should be removed (or at least define a setToId() instead).
176 Edge (Invalid) { n=-1; }
177 bool operator==(const Edge i) const {return n==i.n;}
178 bool operator!=(const Edge i) const {return n!=i.n;}
179 bool operator<(const Edge i) const {return n<i.n;}
182 void first(Node& node) const {
183 node.n = nodes.size() - 1;
186 static void next(Node& node) {
190 void first(Edge& edge) const {
191 edge.n = edges.size() - 1;
194 static void next(Edge& edge) {
198 void firstOut(Edge& edge, const Node& node) const {
199 edge.n = nodes[node.n].first_out;
202 void nextOut(Edge& edge) const {
203 edge.n = edges[edge.n].next_out;
206 void firstIn(Edge& edge, const Node& node) const {
207 edge.n = nodes[node.n].first_in;
210 void nextIn(Edge& edge) const {
211 edge.n = edges[edge.n].next_in;
214 Edge _findEdge(Node u,Node v, Edge prev = INVALID)
216 int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
217 while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out;
224 typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
225 typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
226 typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
227 typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
228 typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
230 /// \addtogroup graphs
233 ///A smart graph class.
235 ///This is a simple and fast graph implementation.
236 ///It is also quite memory efficient, but at the price
237 ///that <b> it does support only limited (only stack-like)
238 ///node and edge deletions</b>.
240 ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
241 ///\sa concept::ExtendableGraph.
243 ///\author Alpar Juttner
244 class SmartGraph : public ClearableSmartGraphBase {
246 /// Finds an edge between two nodes.
248 /// Finds an edge from node \c u to node \c v.
250 /// If \c prev is \ref INVALID (this is the default value), then
251 /// it finds the first edge from \c u to \c v. Otherwise it looks for
252 /// the next edge from \c u to \c v after \c prev.
253 /// \return The found edge or \ref INVALID if there is no such an edge.
255 /// Thus you can iterate through each edge from \c u to \c v as it follows.
257 /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {
261 /// \todo Possibly it should be a global function.
262 Edge findEdge(Node u,Node v, Edge prev = INVALID)
264 return _findEdge(u,v,prev);
268 friend class SnapShot;
271 void restoreSnapShot(const SnapShot &s)
273 while(s.edge_num>edges.size()) {
274 Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
275 nodes[edges.back().target].first_in=edges.back().next_in;
276 nodes[edges.back().source].first_out=edges.back().next_out;
279 //nodes.resize(s.nodes_num);
280 while(s.node_num>nodes.size()) {
281 Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
287 ///Class to make a snapshot of the graph and to restrore to it later.
289 ///Class to make a snapshot of the graph and to restrore to it later.
291 ///The newly added nodes and edges can be removed using the
292 ///restore() function.
293 ///\note After you restore a state, you cannot restore
294 ///a later state, in other word you cannot add again the edges deleted
295 ///by restore() using another SnapShot instance.
301 friend class SmartGraph;
302 unsigned int node_num;
303 unsigned int edge_num;
305 ///Default constructur.
307 ///Default constructur.
308 ///To actually make a snapshot you must call save().
311 ///Constructor that immediately makes a snapshot
313 ///This constructor immediately makes a snapshot of the graph.
314 ///\param _g The graph we make a snapshot of.
315 SnapShot(SmartGraph &_g) :g(&_g) {
316 node_num=g->nodes.size();
317 edge_num=g->edges.size();
322 ///Make a snapshot of the graph.
324 ///This function can be called more than once. In case of a repeated
325 ///call, the previous snapshot gets lost.
326 ///\param _g The graph we make the snapshot of.
327 void save(SmartGraph &_g)
330 node_num=g->nodes.size();
331 edge_num=g->edges.size();
334 ///Undo the changes until a snapshot.
336 ///Undo the changes until a snapshot created by save().
338 ///\param s an internal stucture given back by save()
339 ///\note After you restored a state, you cannot restore
340 ///a later state, in other word you cannot add again the edges deleted
343 ///\todo This function might be called undo().
347 g->restoreSnapShot(*this);
353 /**************** Undirected List Graph ****************/
355 typedef ClearableUndirGraphExtender<
356 ExtendableUndirGraphExtender<
357 MappableUndirGraphExtender<
358 IterableUndirGraphExtender<
359 AlterableUndirGraphExtender<
360 UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;
362 ///A smart undirected graph class.
364 ///This is a simple and fast undirected graph implementation.
365 ///It is also quite memory efficient, but at the price
366 ///that <b> it does support only limited (only stack-like)
367 ///node and edge deletions</b>.
368 ///Except from this it conforms to
369 ///the \ref concept::UndirGraph "UndirGraph" concept.
370 ///\sa concept::UndirGraph.
372 ///\todo SnapShot hasn't been implemented yet.
374 class UndirSmartGraph : public UndirSmartGraphBase {
382 #endif //LEMON_SMART_GRAPH_H