1.1 --- a/src/lemon/smart_graph.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,414 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_SMART_GRAPH_H
1.21 -#define LEMON_SMART_GRAPH_H
1.22 -
1.23 -///\ingroup graphs
1.24 -///\file
1.25 -///\brief SmartGraph and SymSmartGraph classes.
1.26 -
1.27 -#include <vector>
1.28 -
1.29 -#include <lemon/invalid.h>
1.30 -
1.31 -#include <lemon/bits/clearable_graph_extender.h>
1.32 -#include <lemon/bits/extendable_graph_extender.h>
1.33 -#include <lemon/bits/iterable_graph_extender.h>
1.34 -#include <lemon/bits/alteration_notifier.h>
1.35 -#include <lemon/bits/default_map.h>
1.36 -
1.37 -#include <lemon/bits/undir_graph_extender.h>
1.38 -
1.39 -#include <lemon/utility.h>
1.40 -
1.41 -namespace lemon {
1.42 -
1.43 - class SmartGraph;
1.44 - ///Base of SmartGraph
1.45 -
1.46 - ///Base of SmartGraph
1.47 - ///
1.48 - class SmartGraphBase {
1.49 -
1.50 - friend class SmatGraph;
1.51 -
1.52 - protected:
1.53 - struct NodeT
1.54 - {
1.55 - int first_in,first_out;
1.56 - NodeT() : first_in(-1), first_out(-1) {}
1.57 - };
1.58 - struct EdgeT
1.59 - {
1.60 - int target, source, next_in, next_out;
1.61 - //FIXME: is this necessary?
1.62 - EdgeT() : next_in(-1), next_out(-1) {}
1.63 - };
1.64 -
1.65 - std::vector<NodeT> nodes;
1.66 -
1.67 - std::vector<EdgeT> edges;
1.68 -
1.69 -
1.70 - public:
1.71 -
1.72 - typedef SmartGraphBase Graph;
1.73 -
1.74 - class Node;
1.75 - class Edge;
1.76 -
1.77 -
1.78 - public:
1.79 -
1.80 - SmartGraphBase() : nodes(), edges() { }
1.81 - SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
1.82 -
1.83 - typedef True NodeNumTag;
1.84 - typedef True EdgeNumTag;
1.85 -
1.86 - ///Number of nodes.
1.87 - int nodeNum() const { return nodes.size(); }
1.88 - ///Number of edges.
1.89 - int edgeNum() const { return edges.size(); }
1.90 -
1.91 - /// Maximum node ID.
1.92 -
1.93 - /// Maximum node ID.
1.94 - ///\sa id(Node)
1.95 - int maxId(Node = INVALID) const { return nodes.size()-1; }
1.96 - /// Maximum edge ID.
1.97 -
1.98 - /// Maximum edge ID.
1.99 - ///\sa id(Edge)
1.100 - int maxId(Edge = INVALID) const { return edges.size()-1; }
1.101 -
1.102 - Node source(Edge e) const { return edges[e.n].source; }
1.103 - Node target(Edge e) const { return edges[e.n].target; }
1.104 -
1.105 - /// Node ID.
1.106 -
1.107 - /// The ID of a valid Node is a nonnegative integer not greater than
1.108 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.109 - /// and the greatest node ID can be actually less then \ref maxNodeId().
1.110 - ///
1.111 - /// The ID of the \ref INVALID node is -1.
1.112 - ///\return The ID of the node \c v.
1.113 - static int id(Node v) { return v.n; }
1.114 - /// Edge ID.
1.115 -
1.116 - /// The ID of a valid Edge is a nonnegative integer not greater than
1.117 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.118 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.119 - ///
1.120 - /// The ID of the \ref INVALID edge is -1.
1.121 - ///\return The ID of the edge \c e.
1.122 - static int id(Edge e) { return e.n; }
1.123 -
1.124 - static Node fromId(int id, Node) { return Node(id);}
1.125 -
1.126 - static Edge fromId(int id, Edge) { return Edge(id);}
1.127 -
1.128 - Node addNode() {
1.129 - Node n; n.n=nodes.size();
1.130 - nodes.push_back(NodeT()); //FIXME: Hmmm...
1.131 - return n;
1.132 - }
1.133 -
1.134 - Edge addEdge(Node u, Node v) {
1.135 - Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
1.136 - edges[e.n].source=u.n; edges[e.n].target=v.n;
1.137 - edges[e.n].next_out=nodes[u.n].first_out;
1.138 - edges[e.n].next_in=nodes[v.n].first_in;
1.139 - nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.140 -
1.141 - return e;
1.142 - }
1.143 -
1.144 - void clear() {
1.145 - edges.clear();
1.146 - nodes.clear();
1.147 - }
1.148 -
1.149 -
1.150 - class Node {
1.151 - friend class SmartGraphBase;
1.152 - friend class SmartGraph;
1.153 -
1.154 - protected:
1.155 - int n;
1.156 - ///\todo It should be removed (or at least define a setToId() instead).
1.157 - ///
1.158 - Node(int nn) {n=nn;}
1.159 - public:
1.160 - Node() {}
1.161 - Node (Invalid) { n=-1; }
1.162 - bool operator==(const Node i) const {return n==i.n;}
1.163 - bool operator!=(const Node i) const {return n!=i.n;}
1.164 - bool operator<(const Node i) const {return n<i.n;}
1.165 - };
1.166 -
1.167 -
1.168 - class Edge {
1.169 - friend class SmartGraphBase;
1.170 - friend class SmartGraph;
1.171 -
1.172 - protected:
1.173 - int n;
1.174 - ///\todo It should be removed (or at least define a setToId() instead).
1.175 - ///
1.176 - Edge(int nn) {n=nn;}
1.177 - public:
1.178 - Edge() { }
1.179 - Edge (Invalid) { n=-1; }
1.180 - bool operator==(const Edge i) const {return n==i.n;}
1.181 - bool operator!=(const Edge i) const {return n!=i.n;}
1.182 - bool operator<(const Edge i) const {return n<i.n;}
1.183 - };
1.184 -
1.185 - void first(Node& node) const {
1.186 - node.n = nodes.size() - 1;
1.187 - }
1.188 -
1.189 - static void next(Node& node) {
1.190 - --node.n;
1.191 - }
1.192 -
1.193 - void first(Edge& edge) const {
1.194 - edge.n = edges.size() - 1;
1.195 - }
1.196 -
1.197 - static void next(Edge& edge) {
1.198 - --edge.n;
1.199 - }
1.200 -
1.201 - void firstOut(Edge& edge, const Node& node) const {
1.202 - edge.n = nodes[node.n].first_out;
1.203 - }
1.204 -
1.205 - void nextOut(Edge& edge) const {
1.206 - edge.n = edges[edge.n].next_out;
1.207 - }
1.208 -
1.209 - void firstIn(Edge& edge, const Node& node) const {
1.210 - edge.n = nodes[node.n].first_in;
1.211 - }
1.212 -
1.213 - void nextIn(Edge& edge) const {
1.214 - edge.n = edges[edge.n].next_in;
1.215 - }
1.216 -
1.217 - Edge _findEdge(Node u,Node v, Edge prev = INVALID)
1.218 - {
1.219 - int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
1.220 - while(e!=-1 && edges[e].target!=v.n) e = edges[e].next_out;
1.221 - prev.n=e;
1.222 - return prev;
1.223 - }
1.224 -
1.225 - Node _split(Node n, bool connect = true)
1.226 - {
1.227 - Node b = addNode();
1.228 - nodes[b.n].first_out=nodes[n.n].first_out;
1.229 - nodes[n.n].first_out=-1;
1.230 - for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
1.231 - if(connect) addEdge(n,b);
1.232 - return b;
1.233 - }
1.234 -
1.235 - };
1.236 -
1.237 - typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
1.238 - typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
1.239 - typedef DefaultMappableGraphExtender<IterableSmartGraphBase> MappableSmartGraphBase;
1.240 - typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
1.241 - typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
1.242 -
1.243 - /// \addtogroup graphs
1.244 - /// @{
1.245 -
1.246 - ///A smart graph class.
1.247 -
1.248 - ///This is a simple and fast graph implementation.
1.249 - ///It is also quite memory efficient, but at the price
1.250 - ///that <b> it does support only limited (only stack-like)
1.251 - ///node and edge deletions</b>.
1.252 - ///It conforms to
1.253 - ///the \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.254 - ///\sa concept::ExtendableGraph.
1.255 - ///
1.256 - ///\author Alpar Juttner
1.257 - class SmartGraph : public ClearableSmartGraphBase {
1.258 - public:
1.259 - /// Finds an edge between two nodes.
1.260 -
1.261 - /// Finds an edge from node \c u to node \c v.
1.262 - ///
1.263 - /// If \c prev is \ref INVALID (this is the default value), then
1.264 - /// it finds the first edge from \c u to \c v. Otherwise it looks for
1.265 - /// the next edge from \c u to \c v after \c prev.
1.266 - /// \return The found edge or \ref INVALID if there is no such an edge.
1.267 - ///
1.268 - /// Thus you can iterate through each edge from \c u to \c v as it follows.
1.269 - /// \code
1.270 - /// for(Edge e=G.findEdge(u,v);e!=INVALID;e=G.findEdge(u,v,e)) {
1.271 - /// ...
1.272 - /// }
1.273 - /// \endcode
1.274 - /// \todo Possibly it should be a global function.
1.275 - Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.276 - {
1.277 - return _findEdge(u,v,prev);
1.278 - }
1.279 -
1.280 - class SnapShot;
1.281 - friend class SnapShot;
1.282 -
1.283 - protected:
1.284 - void restoreSnapShot(const SnapShot &s)
1.285 - {
1.286 - while(s.edge_num>edges.size()) {
1.287 - Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
1.288 - nodes[edges.back().target].first_in=edges.back().next_in;
1.289 - nodes[edges.back().source].first_out=edges.back().next_out;
1.290 - edges.pop_back();
1.291 - }
1.292 - //nodes.resize(s.nodes_num);
1.293 - while(s.node_num>nodes.size()) {
1.294 - Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
1.295 - nodes.pop_back();
1.296 - }
1.297 - }
1.298 -
1.299 - public:
1.300 -
1.301 - ///Split a node.
1.302 -
1.303 - ///This function splits a node. First a new node is added to the graph,
1.304 - ///then the source of each outgoing edge of \c n is moved to this new node.
1.305 - ///If \c connect is \c true (this is the default value), then a new edge
1.306 - ///from \c n to the newly created node is also added.
1.307 - ///\return The newly created node.
1.308 - ///
1.309 - ///\note The <tt>Edge</tt>s
1.310 - ///referencing a moved edge remain
1.311 - ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
1.312 - ///may be invalidated.
1.313 - ///\warning This functionality cannot be used together with the SnapShot
1.314 - ///feature.
1.315 - ///\todo It could be implemented in a bit faster way.
1.316 - Node split(Node n, bool connect = true)
1.317 - {
1.318 - return _split(n,connect);
1.319 - }
1.320 -
1.321 -
1.322 - ///Class to make a snapshot of the graph and to restrore to it later.
1.323 -
1.324 - ///Class to make a snapshot of the graph and to restrore to it later.
1.325 - ///
1.326 - ///The newly added nodes and edges can be removed using the
1.327 - ///restore() function.
1.328 - ///\note After you restore a state, you cannot restore
1.329 - ///a later state, in other word you cannot add again the edges deleted
1.330 - ///by restore() using another SnapShot instance.
1.331 - ///
1.332 - class SnapShot
1.333 - {
1.334 - SmartGraph *g;
1.335 - protected:
1.336 - friend class SmartGraph;
1.337 - unsigned int node_num;
1.338 - unsigned int edge_num;
1.339 - public:
1.340 - ///Default constructor.
1.341 -
1.342 - ///Default constructor.
1.343 - ///To actually make a snapshot you must call save().
1.344 - ///
1.345 - SnapShot() : g(0) {}
1.346 - ///Constructor that immediately makes a snapshot
1.347 -
1.348 - ///This constructor immediately makes a snapshot of the graph.
1.349 - ///\param _g The graph we make a snapshot of.
1.350 - SnapShot(SmartGraph &_g) :g(&_g) {
1.351 - node_num=g->nodes.size();
1.352 - edge_num=g->edges.size();
1.353 - }
1.354 -
1.355 - ///Make a snapshot.
1.356 -
1.357 - ///Make a snapshot of the graph.
1.358 - ///
1.359 - ///This function can be called more than once. In case of a repeated
1.360 - ///call, the previous snapshot gets lost.
1.361 - ///\param _g The graph we make the snapshot of.
1.362 - void save(SmartGraph &_g)
1.363 - {
1.364 - g=&_g;
1.365 - node_num=g->nodes.size();
1.366 - edge_num=g->edges.size();
1.367 - }
1.368 -
1.369 - ///Undo the changes until a snapshot.
1.370 -
1.371 - ///Undo the changes until a snapshot created by save().
1.372 - ///
1.373 - ///\param s an internal stucture given back by save()
1.374 - ///\note After you restored a state, you cannot restore
1.375 - ///a later state, in other word you cannot add again the edges deleted
1.376 - ///by restore().
1.377 - ///
1.378 - ///\todo This function might be called undo().
1.379 -
1.380 - void restore()
1.381 - {
1.382 - g->restoreSnapShot(*this);
1.383 - }
1.384 - };
1.385 - };
1.386 -
1.387 -
1.388 - /**************** Undirected List Graph ****************/
1.389 -
1.390 - typedef ClearableUndirGraphExtender<
1.391 - ExtendableUndirGraphExtender<
1.392 - MappableUndirGraphExtender<
1.393 - IterableUndirGraphExtender<
1.394 - AlterableUndirGraphExtender<
1.395 - UndirGraphExtender<SmartGraphBase> > > > > > UndirSmartGraphBase;
1.396 -
1.397 - ///A smart undirected graph class.
1.398 -
1.399 - ///This is a simple and fast undirected graph implementation.
1.400 - ///It is also quite memory efficient, but at the price
1.401 - ///that <b> it does support only limited (only stack-like)
1.402 - ///node and edge deletions</b>.
1.403 - ///Except from this it conforms to
1.404 - ///the \ref concept::UndirGraph "UndirGraph" concept.
1.405 - ///\sa concept::UndirGraph.
1.406 - ///
1.407 - ///\todo SnapShot hasn't been implemented yet.
1.408 - ///
1.409 - class UndirSmartGraph : public UndirSmartGraphBase {
1.410 - };
1.411 -
1.412 -
1.413 - /// @}
1.414 -} //namespace lemon
1.415 -
1.416 -
1.417 -#endif //LEMON_SMART_GRAPH_H