1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/smart_graph.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,364 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, 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 +#include <climits>
1.29 +
1.30 +#include <lemon/invalid.h>
1.31 +
1.32 +#include <lemon/array_map.h>
1.33 +#include <lemon/sym_map.h>
1.34 +
1.35 +#include <lemon/map_registry.h>
1.36 +
1.37 +#include <lemon/map_defines.h>
1.38 +
1.39 +namespace lemon {
1.40 +
1.41 +/// \addtogroup graphs
1.42 +/// @{
1.43 +// class SymSmartGraph;
1.44 +
1.45 + ///A smart graph class.
1.46 +
1.47 + ///This is a simple and fast graph implementation.
1.48 + ///It is also quite memory efficient, but at the price
1.49 + ///that <b> it does not support node and edge deletion</b>.
1.50 + ///It conforms to
1.51 + ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
1.52 + ///\sa skeleton::ExtendableGraph.
1.53 + ///
1.54 + ///\todo Some member functions could be \c static.
1.55 + ///
1.56 + ///\todo A possibly useful functionality: a function saveState() would
1.57 + ///give back a data sturcture X and then the function restoreState(X)
1.58 + ///would remove the nodes and edges added after the call of saveState().
1.59 + ///Of course it should be used as a stack. (Maybe X is not necessary.)
1.60 + ///
1.61 + ///\author Alpar Juttner
1.62 + class SmartGraph {
1.63 +
1.64 + struct NodeT
1.65 + {
1.66 + int first_in,first_out;
1.67 + NodeT() : first_in(-1), first_out(-1) {}
1.68 + };
1.69 + struct EdgeT
1.70 + {
1.71 + int head, tail, next_in, next_out;
1.72 + //FIXME: is this necessary?
1.73 + EdgeT() : next_in(-1), next_out(-1) {}
1.74 + };
1.75 +
1.76 + std::vector<NodeT> nodes;
1.77 +
1.78 + std::vector<EdgeT> edges;
1.79 +
1.80 +
1.81 + public:
1.82 +
1.83 + typedef SmartGraph Graph;
1.84 +
1.85 + class Node;
1.86 + class Edge;
1.87 +
1.88 + class NodeIt;
1.89 + class EdgeIt;
1.90 + class OutEdgeIt;
1.91 + class InEdgeIt;
1.92 +
1.93 + // Create map registries.
1.94 + CREATE_MAP_REGISTRIES;
1.95 + // Create node and edge maps.
1.96 + CREATE_MAPS(ArrayMap);
1.97 +
1.98 + public:
1.99 +
1.100 + SmartGraph() : nodes(), edges() { }
1.101 + SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
1.102 +
1.103 + ///Number of nodes.
1.104 + int nodeNum() const { return nodes.size(); }
1.105 + ///Number of edges.
1.106 + int edgeNum() const { return edges.size(); }
1.107 +
1.108 + /// Maximum node ID.
1.109 +
1.110 + /// Maximum node ID.
1.111 + ///\sa id(Node)
1.112 + int maxNodeId() const { return nodes.size()-1; }
1.113 + /// Maximum edge ID.
1.114 +
1.115 + /// Maximum edge ID.
1.116 + ///\sa id(Edge)
1.117 + int maxEdgeId() const { return edges.size()-1; }
1.118 +
1.119 + Node tail(Edge e) const { return edges[e.n].tail; }
1.120 + Node head(Edge e) const { return edges[e.n].head; }
1.121 +
1.122 + NodeIt& first(NodeIt& v) const {
1.123 + v=NodeIt(*this); return v; }
1.124 + EdgeIt& first(EdgeIt& e) const {
1.125 + e=EdgeIt(*this); return e; }
1.126 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.127 + e=OutEdgeIt(*this,v); return e; }
1.128 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.129 + e=InEdgeIt(*this,v); return e; }
1.130 +
1.131 + /// Node ID.
1.132 +
1.133 + /// The ID of a valid Node is a nonnegative integer not greater than
1.134 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.135 + /// and the greatest node ID can be actually less then \ref maxNodeId().
1.136 + ///
1.137 + /// The ID of the \ref INVALID node is -1.
1.138 + ///\return The ID of the node \c v.
1.139 + static int id(Node v) { return v.n; }
1.140 + /// Edge ID.
1.141 +
1.142 + /// The ID of a valid Edge is a nonnegative integer not greater than
1.143 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.144 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.145 + ///
1.146 + /// The ID of the \ref INVALID edge is -1.
1.147 + ///\return The ID of the edge \c e.
1.148 + static int id(Edge e) { return e.n; }
1.149 +
1.150 + Node addNode() {
1.151 + Node n; n.n=nodes.size();
1.152 + nodes.push_back(NodeT()); //FIXME: Hmmm...
1.153 +
1.154 +
1.155 + node_maps.add(n);
1.156 + return n;
1.157 + }
1.158 +
1.159 + Edge addEdge(Node u, Node v) {
1.160 + Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
1.161 + edges[e.n].tail=u.n; edges[e.n].head=v.n;
1.162 + edges[e.n].next_out=nodes[u.n].first_out;
1.163 + edges[e.n].next_in=nodes[v.n].first_in;
1.164 + nodes[u.n].first_out=nodes[v.n].first_in=e.n;
1.165 +
1.166 + edge_maps.add(e);
1.167 +
1.168 + return e;
1.169 + }
1.170 +
1.171 + /// Finds an edge between two nodes.
1.172 +
1.173 + /// Finds an edge from node \c u to node \c v.
1.174 + ///
1.175 + /// If \c prev is \ref INVALID (this is the default value), then
1.176 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.177 + /// the next edge from \c u to \c v after \c prev.
1.178 + /// \return The found edge or INVALID if there is no such an edge.
1.179 + Edge findEdge(Node u,Node v, Edge prev = INVALID)
1.180 + {
1.181 + int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
1.182 + while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
1.183 + prev.n=e;
1.184 + return prev;
1.185 + }
1.186 +
1.187 + void clear() {
1.188 + edge_maps.clear();
1.189 + edges.clear();
1.190 + node_maps.clear();
1.191 + nodes.clear();
1.192 + }
1.193 +
1.194 + class Node {
1.195 + friend class SmartGraph;
1.196 + template <typename T> friend class NodeMap;
1.197 +
1.198 + friend class Edge;
1.199 + friend class OutEdgeIt;
1.200 + friend class InEdgeIt;
1.201 + friend class SymEdge;
1.202 +
1.203 + protected:
1.204 + int n;
1.205 + friend int SmartGraph::id(Node v);
1.206 + Node(int nn) {n=nn;}
1.207 + public:
1.208 + Node() {}
1.209 + Node (Invalid) { n=-1; }
1.210 + bool operator==(const Node i) const {return n==i.n;}
1.211 + bool operator!=(const Node i) const {return n!=i.n;}
1.212 + bool operator<(const Node i) const {return n<i.n;}
1.213 + // ///Validity check
1.214 + // operator bool() { return n!=-1; }
1.215 + };
1.216 +
1.217 + class NodeIt : public Node {
1.218 + const SmartGraph *G;
1.219 + friend class SmartGraph;
1.220 + public:
1.221 + NodeIt() : Node() { }
1.222 + NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
1.223 + NodeIt(Invalid i) : Node(i) { }
1.224 + NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
1.225 + NodeIt &operator++() {
1.226 + n=(n+2)%(G->nodes.size()+1)-1;
1.227 + return *this;
1.228 + }
1.229 +// ///Validity check
1.230 +// operator bool() { return Node::operator bool(); }
1.231 + };
1.232 +
1.233 + class Edge {
1.234 + friend class SmartGraph;
1.235 + template <typename T> friend class EdgeMap;
1.236 +
1.237 + friend class SymSmartGraph;
1.238 +
1.239 + friend class Node;
1.240 + friend class NodeIt;
1.241 + protected:
1.242 + int n;
1.243 + friend int SmartGraph::id(Edge e);
1.244 + Edge(int nn) {n=nn;}
1.245 + public:
1.246 + /// An Edge with id \c n.
1.247 +
1.248 + Edge() { }
1.249 + Edge (Invalid) { n=-1; }
1.250 + bool operator==(const Edge i) const {return n==i.n;}
1.251 + bool operator!=(const Edge i) const {return n!=i.n;}
1.252 + bool operator<(const Edge i) const {return n<i.n;}
1.253 +// ///Validity check
1.254 +// operator bool() { return n!=-1; }
1.255 +
1.256 + ///Set the edge to that have ID \c ID.
1.257 + void setToId(int id) { n=id; }
1.258 + };
1.259 +
1.260 + class EdgeIt : public Edge {
1.261 + const SmartGraph *G;
1.262 + friend class SmartGraph;
1.263 + public:
1.264 + EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
1.265 + EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.266 + EdgeIt (Invalid i) : Edge(i) { }
1.267 + EdgeIt() : Edge() { }
1.268 + EdgeIt &operator++() { --n; return *this; }
1.269 +// ///Validity check
1.270 +// operator bool() { return Edge::operator bool(); }
1.271 + };
1.272 +
1.273 + class OutEdgeIt : public Edge {
1.274 + const SmartGraph *G;
1.275 + friend class SmartGraph;
1.276 + public:
1.277 + OutEdgeIt() : Edge() { }
1.278 + OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.279 + OutEdgeIt (Invalid i) : Edge(i) { }
1.280 +
1.281 + OutEdgeIt(const SmartGraph& _G,const Node v)
1.282 + : Edge(_G.nodes[v.n].first_out), G(&_G) {}
1.283 + OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
1.284 +// ///Validity check
1.285 +// operator bool() { return Edge::operator bool(); }
1.286 + };
1.287 +
1.288 + class InEdgeIt : public Edge {
1.289 + const SmartGraph *G;
1.290 + friend class SmartGraph;
1.291 + public:
1.292 + InEdgeIt() : Edge() { }
1.293 + InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
1.294 + InEdgeIt (Invalid i) : Edge(i) { }
1.295 + InEdgeIt(const SmartGraph& _G,Node v)
1.296 + : Edge(_G.nodes[v.n].first_in), G(&_G) { }
1.297 + InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
1.298 +// ///Validity check
1.299 +// operator bool() { return Edge::operator bool(); }
1.300 + };
1.301 +
1.302 + };
1.303 +
1.304 + ///Graph for bidirectional edges.
1.305 +
1.306 + ///The purpose of this graph structure is to handle graphs
1.307 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.308 + ///of oppositely directed edges.
1.309 + ///There is a new edge map type called
1.310 + ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
1.311 + ///that complements this
1.312 + ///feature by
1.313 + ///storing shared values for the edge pairs. The usual
1.314 + ///\ref Graph::EdgeMap "EdgeMap"
1.315 + ///can be used
1.316 + ///as well.
1.317 + ///
1.318 + ///The oppositely directed edge can also be obtained easily
1.319 + ///using \ref opposite.
1.320 + ///\warning It shares the similarity with \ref SmartGraph that
1.321 + ///it is not possible to delete edges or nodes from the graph.
1.322 + //\sa SmartGraph.
1.323 +
1.324 + class SymSmartGraph : public SmartGraph
1.325 + {
1.326 + public:
1.327 + typedef SymSmartGraph Graph;
1.328 +
1.329 + // Create symmetric map registry.
1.330 + CREATE_SYM_EDGE_MAP_REGISTRY;
1.331 + // Create symmetric edge map.
1.332 + CREATE_SYM_EDGE_MAP(ArrayMap);
1.333 +
1.334 +
1.335 + SymSmartGraph() : SmartGraph() { }
1.336 + SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
1.337 + ///Adds a pair of oppositely directed edges to the graph.
1.338 + Edge addEdge(Node u, Node v)
1.339 + {
1.340 + Edge e = SmartGraph::addEdge(u,v);
1.341 + Edge f = SmartGraph::addEdge(v,u);
1.342 + sym_edge_maps.add(e);
1.343 + sym_edge_maps.add(f);
1.344 + return e;
1.345 + }
1.346 +
1.347 + ///The oppositely directed edge.
1.348 +
1.349 + ///Returns the oppositely directed
1.350 + ///pair of the edge \c e.
1.351 + static Edge opposite(Edge e)
1.352 + {
1.353 + Edge f;
1.354 + f.n = e.n - 2*(e.n%2) + 1;
1.355 + return f;
1.356 + }
1.357 +
1.358 +
1.359 + };
1.360 +
1.361 + /// @}
1.362 +} //namespace lemon
1.363 +
1.364 +
1.365 +
1.366 +
1.367 +#endif //LEMON_SMART_GRAPH_H