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