1.1 --- a/src/lemon/smart_graph.h Mon Oct 04 16:03:25 2004 +0000
1.2 +++ b/src/lemon/smart_graph.h Mon Oct 04 17:13:21 2004 +0000
1.3 @@ -26,8 +26,8 @@
1.4
1.5 #include <lemon/invalid.h>
1.6
1.7 +
1.8 #include <lemon/array_map.h>
1.9 -#include <lemon/sym_map.h>
1.10
1.11 #include <lemon/map_registry.h>
1.12
1.13 @@ -298,6 +298,381 @@
1.14
1.15 };
1.16
1.17 +
1.18 +
1.19 + class SymSmartGraph : public SmartGraph {
1.20 + typedef SmartGraph Parent;
1.21 + public:
1.22 +
1.23 + typedef SymSmartGraph Graph;
1.24 +
1.25 + typedef SmartGraph::Node Node;
1.26 + typedef SmartGraph::NodeIt NodeIt;
1.27 +
1.28 + class SymEdge;
1.29 + class SymEdgeIt;
1.30 +
1.31 + class Edge;
1.32 + class EdgeIt;
1.33 + class OutEdgeIt;
1.34 + class InEdgeIt;
1.35 +
1.36 + template <typename Value>
1.37 + class NodeMap : public Parent::NodeMap<Value> {
1.38 + public:
1.39 + NodeMap(const SymSmartGraph& g)
1.40 + : SymSmartGraph::Parent::NodeMap<Value>(g) {}
1.41 + NodeMap(const SymSmartGraph& g, Value v)
1.42 + : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
1.43 + template<typename TT>
1.44 + NodeMap(const NodeMap<TT>& copy)
1.45 + : SymSmartGraph::Parent::NodeMap<Value>(copy) { }
1.46 + };
1.47 +
1.48 + template <typename Value>
1.49 + class SymEdgeMap : public Parent::EdgeMap<Value> {
1.50 + public:
1.51 + typedef SymEdge KeyType;
1.52 +
1.53 + SymEdgeMap(const SymSmartGraph& g)
1.54 + : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
1.55 + SymEdgeMap(const SymSmartGraph& g, Value v)
1.56 + : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
1.57 + template<typename TT>
1.58 + SymEdgeMap(const SymEdgeMap<TT>& copy)
1.59 + : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
1.60 +
1.61 + };
1.62 +
1.63 + // Create edge map registry.
1.64 + CREATE_EDGE_MAP_REGISTRY;
1.65 + // Create edge maps.
1.66 + CREATE_EDGE_MAP(ArrayMap);
1.67 +
1.68 + class Edge {
1.69 + friend class SymSmartGraph;
1.70 + friend class SymSmartGraph::EdgeIt;
1.71 + friend class SymSmartGraph::OutEdgeIt;
1.72 + friend class SymSmartGraph::InEdgeIt;
1.73 +
1.74 + protected:
1.75 + int id;
1.76 +
1.77 + Edge(int pid) { id = pid; }
1.78 +
1.79 + public:
1.80 + /// An Edge with id \c n.
1.81 +
1.82 + Edge() { }
1.83 + Edge (Invalid) { id = -1; }
1.84 +
1.85 + operator SymEdge(){ return SymEdge(id >> 1);}
1.86 +
1.87 + bool operator==(const Edge i) const {return id == i.id;}
1.88 + bool operator!=(const Edge i) const {return id != i.id;}
1.89 + bool operator<(const Edge i) const {return id < i.id;}
1.90 + // ///Validity check
1.91 + // operator bool() { return n!=-1; }
1.92 + };
1.93 +
1.94 + class SymEdge : public SmartGraph::Edge {
1.95 + friend class SymSmartGraph;
1.96 + friend class SymSmartGraph::Edge;
1.97 + typedef SmartGraph::Edge Parent;
1.98 +
1.99 + protected:
1.100 + SymEdge(int pid) : Parent(pid) {}
1.101 + public:
1.102 +
1.103 + SymEdge() { }
1.104 + SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
1.105 + SymEdge (Invalid) : Parent(INVALID) {}
1.106 +
1.107 + };
1.108 +
1.109 + class OutEdgeIt {
1.110 + Parent::OutEdgeIt out;
1.111 + Parent::InEdgeIt in;
1.112 + public:
1.113 + OutEdgeIt() {}
1.114 + OutEdgeIt(const SymSmartGraph& g, Edge e) {
1.115 + if ((e.id & 1) == 0) {
1.116 + out = Parent::OutEdgeIt(g, SymEdge(e));
1.117 + in = Parent::InEdgeIt(g, g.tail(e));
1.118 + } else {
1.119 + out = Parent::OutEdgeIt(INVALID);
1.120 + in = Parent::InEdgeIt(g, SymEdge(e));
1.121 + }
1.122 + }
1.123 + OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
1.124 +
1.125 + OutEdgeIt(const SymSmartGraph& g, const Node v)
1.126 + : out(g, v), in(g, v) {}
1.127 + OutEdgeIt &operator++() {
1.128 + if (out != INVALID) {
1.129 + ++out;
1.130 + } else {
1.131 + ++in;
1.132 + }
1.133 + return *this;
1.134 + }
1.135 +
1.136 + operator Edge() const {
1.137 + if (out == INVALID && in == INVALID) return INVALID;
1.138 + return out != INVALID ? forward(out) : backward(in);
1.139 + }
1.140 +
1.141 + bool operator==(const Edge i) const {return Edge(*this) == i;}
1.142 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
1.143 + bool operator<(const Edge i) const {return Edge(*this) < i;}
1.144 + };
1.145 +
1.146 + class InEdgeIt {
1.147 + Parent::OutEdgeIt out;
1.148 + Parent::InEdgeIt in;
1.149 + public:
1.150 + InEdgeIt() {}
1.151 + InEdgeIt(const SymSmartGraph& g, Edge e) {
1.152 + if ((e.id & 1) == 0) {
1.153 + out = Parent::OutEdgeIt(g, SymEdge(e));
1.154 + in = Parent::InEdgeIt(g, g.tail(e));
1.155 + } else {
1.156 + out = Parent::OutEdgeIt(INVALID);
1.157 + in = Parent::InEdgeIt(g, SymEdge(e));
1.158 + }
1.159 + }
1.160 + InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
1.161 +
1.162 + InEdgeIt(const SymSmartGraph& g, const Node v)
1.163 + : out(g, v), in(g, v) {}
1.164 +
1.165 + InEdgeIt &operator++() {
1.166 + if (out != INVALID) {
1.167 + ++out;
1.168 + } else {
1.169 + ++in;
1.170 + }
1.171 + return *this;
1.172 + }
1.173 +
1.174 + operator Edge() const {
1.175 + if (out == INVALID && in == INVALID) return INVALID;
1.176 + return out != INVALID ? backward(out) : forward(in);
1.177 + }
1.178 +
1.179 + bool operator==(const Edge i) const {return Edge(*this) == i;}
1.180 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
1.181 + bool operator<(const Edge i) const {return Edge(*this) < i;}
1.182 + };
1.183 +
1.184 + class SymEdgeIt : public Parent::EdgeIt {
1.185 +
1.186 + public:
1.187 + SymEdgeIt() {}
1.188 +
1.189 + SymEdgeIt(const SymSmartGraph& g)
1.190 + : SymSmartGraph::Parent::EdgeIt(g) {}
1.191 +
1.192 + SymEdgeIt(const SymSmartGraph& g, SymEdge e)
1.193 + : SymSmartGraph::Parent::EdgeIt(g, e) {}
1.194 +
1.195 + SymEdgeIt(Invalid i)
1.196 + : SymSmartGraph::Parent::EdgeIt(INVALID) {}
1.197 +
1.198 + SymEdgeIt& operator++() {
1.199 + SymSmartGraph::Parent::EdgeIt::operator++();
1.200 + return *this;
1.201 + }
1.202 +
1.203 + operator SymEdge() const {
1.204 + return SymEdge
1.205 + (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
1.206 + }
1.207 + bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
1.208 + bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
1.209 + bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
1.210 + };
1.211 +
1.212 + class EdgeIt {
1.213 + SymEdgeIt it;
1.214 + bool fw;
1.215 + public:
1.216 + EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
1.217 + EdgeIt (Invalid i) : it(i) { }
1.218 + EdgeIt(const SymSmartGraph& g, Edge e)
1.219 + : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
1.220 + EdgeIt() { }
1.221 + EdgeIt& operator++() {
1.222 + fw = !fw;
1.223 + if (fw) ++it;
1.224 + return *this;
1.225 + }
1.226 + operator Edge() const {
1.227 + if (it == INVALID) return INVALID;
1.228 + return fw ? forward(it) : backward(it);
1.229 + }
1.230 + bool operator==(const Edge i) const {return Edge(*this) == i;}
1.231 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
1.232 + bool operator<(const Edge i) const {return Edge(*this) < i;}
1.233 +
1.234 + };
1.235 +
1.236 + ///Number of nodes.
1.237 + int nodeNum() const { return Parent::nodeNum(); }
1.238 + ///Number of edges.
1.239 + int edgeNum() const { return 2*Parent::edgeNum(); }
1.240 + ///Number of symmetric edges.
1.241 + int symEdgeNum() const { return Parent::edgeNum(); }
1.242 +
1.243 + /// Maximum node ID.
1.244 +
1.245 + /// Maximum node ID.
1.246 + ///\sa id(Node)
1.247 + int maxNodeId() const { return Parent::maxNodeId(); }
1.248 + /// Maximum edge ID.
1.249 +
1.250 + /// Maximum edge ID.
1.251 + ///\sa id(Edge)
1.252 + int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
1.253 + /// Maximum symmetric edge ID.
1.254 +
1.255 + /// Maximum symmetric edge ID.
1.256 + ///\sa id(SymEdge)
1.257 + int maxSymEdgeId() const { return Parent::maxEdgeId(); }
1.258 +
1.259 +
1.260 + Node tail(Edge e) const {
1.261 + return (e.id & 1) == 0 ?
1.262 + Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
1.263 + }
1.264 +
1.265 + Node head(Edge e) const {
1.266 + return (e.id & 1) == 0 ?
1.267 + Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
1.268 + }
1.269 +
1.270 + Node tail(SymEdge e) const {
1.271 + return Parent::tail(e);
1.272 + }
1.273 +
1.274 + Node head(SymEdge e) const {
1.275 + return Parent::head(e);
1.276 + }
1.277 +
1.278 + NodeIt& first(NodeIt& v) const {
1.279 + v=NodeIt(*this); return v; }
1.280 + EdgeIt& first(EdgeIt& e) const {
1.281 + e=EdgeIt(*this); return e; }
1.282 + SymEdgeIt& first(SymEdgeIt& e) const {
1.283 + e=SymEdgeIt(*this); return e; }
1.284 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.285 + e=OutEdgeIt(*this,v); return e; }
1.286 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.287 + e=InEdgeIt(*this,v); return e; }
1.288 +
1.289 + /// Node ID.
1.290 +
1.291 + /// The ID of a valid Node is a nonnegative integer not greater than
1.292 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
1.293 + /// and the greatest node ID can be actually less then \ref maxNodeId().
1.294 + ///
1.295 + /// The ID of the \ref INVALID node is -1.
1.296 + ///\return The ID of the node \c v.
1.297 + static int id(Node v) { return Parent::id(v); }
1.298 + /// Edge ID.
1.299 +
1.300 + /// The ID of a valid Edge is a nonnegative integer not greater than
1.301 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
1.302 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
1.303 + ///
1.304 + /// The ID of the \ref INVALID edge is -1.
1.305 + ///\return The ID of the edge \c e.
1.306 + static int id(Edge e) { return e.id; }
1.307 +
1.308 + /// The ID of a valid SymEdge is a nonnegative integer not greater than
1.309 + /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
1.310 + /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
1.311 + ///
1.312 + /// The ID of the \ref INVALID symmetric edge is -1.
1.313 + ///\return The ID of the edge \c e.
1.314 + static int id(SymEdge e) { return Parent::id(e); }
1.315 +
1.316 + /// Adds a new node to the graph.
1.317 +
1.318 + /// \warning It adds the new node to the front of the list.
1.319 + /// (i.e. the lastly added node becomes the first.)
1.320 + Node addNode() {
1.321 + return Parent::addNode();
1.322 + }
1.323 +
1.324 + SymEdge addEdge(Node u, Node v) {
1.325 + SymEdge se = Parent::addEdge(u, v);
1.326 + edge_maps.add(forward(se));
1.327 + edge_maps.add(backward(se));
1.328 + return se;
1.329 + }
1.330 +
1.331 + /// Finds an edge between two nodes.
1.332 +
1.333 + /// Finds an edge from node \c u to node \c v.
1.334 + ///
1.335 + /// If \c prev is \ref INVALID (this is the default value), then
1.336 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.337 + /// the next edge from \c u to \c v after \c prev.
1.338 + /// \return The found edge or INVALID if there is no such an edge.
1.339 + Edge findEdge(Node u, Node v, Edge prev = INVALID)
1.340 + {
1.341 + if (prev == INVALID || id(prev) & 1 == 0) {
1.342 + SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
1.343 + if (se != INVALID) return forward(se);
1.344 + } else {
1.345 + SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
1.346 + if (se != INVALID) return backward(se);
1.347 + }
1.348 + return INVALID;
1.349 + }
1.350 +
1.351 +// /// Finds an symmetric edge between two nodes.
1.352 +
1.353 +// /// Finds an symmetric edge from node \c u to node \c v.
1.354 +// ///
1.355 +// /// If \c prev is \ref INVALID (this is the default value), then
1.356 +// /// It finds the first edge from \c u to \c v. Otherwise it looks for
1.357 +// /// the next edge from \c u to \c v after \c prev.
1.358 +// /// \return The found edge or INVALID if there is no such an edge.
1.359 +
1.360 +// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
1.361 +// {
1.362 +// if (prev == INVALID || id(prev) & 1 == 0) {
1.363 +// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
1.364 +// if (se != INVALID) return se;
1.365 +// } else {
1.366 +// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
1.367 +// if (se != INVALID) return se;
1.368 +// }
1.369 +// return INVALID;
1.370 +// }
1.371 +
1.372 + public:
1.373 +
1.374 + void clear() {
1.375 + edge_maps.clear();
1.376 + Parent::clear();
1.377 + }
1.378 +
1.379 + static Edge opposite(Edge e) {
1.380 + return Edge(id(e) ^ 1);
1.381 + }
1.382 +
1.383 + static Edge forward(SymEdge e) {
1.384 + return Edge(id(e) << 1);
1.385 + }
1.386 +
1.387 + static Edge backward(SymEdge e) {
1.388 + return Edge((id(e) << 1) | 1);
1.389 + }
1.390 +
1.391 + };
1.392 ///Graph for bidirectional edges.
1.393
1.394 ///The purpose of this graph structure is to handle graphs
1.395 @@ -318,7 +693,7 @@
1.396 ///it is not possible to delete edges or nodes from the graph.
1.397 //\sa SmartGraph.
1.398
1.399 - class SymSmartGraph : public SmartGraph
1.400 + /* class SymSmartGraph : public SmartGraph
1.401 {
1.402 public:
1.403 typedef SymSmartGraph Graph;
1.404 @@ -353,7 +728,7 @@
1.405 }
1.406
1.407
1.408 - };
1.409 + };*/
1.410
1.411 /// @}
1.412 } //namespace lemon