New symmetric Graph concept.
New symmetric list and smart graph.
Symmetric Graph tests based on the Graph Tests.
1.1 --- a/src/hugo/Makefile.am Fri Sep 24 11:55:54 2004 +0000
1.2 +++ b/src/hugo/Makefile.am Sun Sep 26 21:43:38 2004 +0000
1.3 @@ -18,12 +18,11 @@
1.4 map_registry.h \
1.5 map_bits.h \
1.6 maps.h \
1.7 - min_cost_flow.h \
1.8 + min_cost_flow.h \
1.9 suurballe.h \
1.10 preflow.h \
1.11 path.h \
1.12 smart_graph.h \
1.13 - sym_map.h \
1.14 time_measure.h \
1.15 unionfind.h \
1.16 vector_map.h \
1.17 @@ -31,5 +30,6 @@
1.18
1.19 noinst_HEADERS = \
1.20 skeletons/graph.h \
1.21 + skeletons/sym_graph.h \
1.22 skeletons/maps.h \
1.23 skeletons/path.h
2.1 --- a/src/hugo/default_map.h Fri Sep 24 11:55:54 2004 +0000
2.2 +++ b/src/hugo/default_map.h Sun Sep 26 21:43:38 2004 +0000
2.3 @@ -59,12 +59,9 @@
2.4 : Parent(static_cast<const Parent&>(copy)) {} \
2.5 template <typename TT> \
2.6 DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
2.7 - : { \
2.8 - Parent::MapBase::operator= \
2.9 - (static_cast<const typename Parent::MapBase&>(copy)); \
2.10 + : Parent(*copy.getGraph()) { \
2.11 if (Parent::getGraph()) { \
2.12 for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
2.13 - Parent::add(it); \
2.14 Parent::operator[](it) = copy[it]; \
2.15 } \
2.16 } \
3.1 --- a/src/hugo/list_graph.h Fri Sep 24 11:55:54 2004 +0000
3.2 +++ b/src/hugo/list_graph.h Sun Sep 26 21:43:38 2004 +0000
3.3 @@ -29,8 +29,6 @@
3.4 #include <hugo/map_registry.h>
3.5 #include <hugo/array_map.h>
3.6
3.7 -#include <hugo/sym_map.h>
3.8 -
3.9 #include <hugo/map_defines.h>
3.10
3.11
3.12 @@ -438,7 +436,7 @@
3.13 ///
3.14 ///\todo this date structure need some reconsiderations. Maybe it
3.15 ///should be implemented independently from ListGraph.
3.16 -
3.17 + /*
3.18 class SymListGraph : public ListGraph
3.19 {
3.20 public:
3.21 @@ -483,9 +481,403 @@
3.22 ListGraph::erase(f);
3.23 ListGraph::erase(e);
3.24 }
3.25 + };*/
3.26 +
3.27 + class SymListGraph : public ListGraph {
3.28 + typedef ListGraph Parent;
3.29 + public:
3.30 +
3.31 + typedef SymListGraph Graph;
3.32 +
3.33 + typedef ListGraph::Node Node;
3.34 + typedef ListGraph::NodeIt NodeIt;
3.35 +
3.36 + class SymEdge;
3.37 + class SymEdgeIt;
3.38 +
3.39 + class Edge;
3.40 + class EdgeIt;
3.41 + class OutEdgeIt;
3.42 + class InEdgeIt;
3.43 +
3.44 + template <typename Value>
3.45 + class NodeMap : public Parent::NodeMap<Value> {
3.46 + public:
3.47 + NodeMap(const SymListGraph& g)
3.48 + : SymListGraph::Parent::NodeMap<Value>(g) {}
3.49 + NodeMap(const SymListGraph& g, Value v)
3.50 + : SymListGraph::Parent::NodeMap<Value>(g, v) {}
3.51 + template<typename TT>
3.52 + NodeMap(const NodeMap<TT>& copy)
3.53 + : SymListGraph::Parent::NodeMap<Value>(copy) { }
3.54 + };
3.55 +
3.56 + template <typename Value>
3.57 + class SymEdgeMap : public Parent::EdgeMap<Value> {
3.58 + public:
3.59 + typedef SymEdge KeyType;
3.60 +
3.61 + SymEdgeMap(const SymListGraph& g)
3.62 + : SymListGraph::Parent::EdgeMap<Value>(g) {}
3.63 + SymEdgeMap(const SymListGraph& g, Value v)
3.64 + : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
3.65 + template<typename TT>
3.66 + SymEdgeMap(const SymEdgeMap<TT>& copy)
3.67 + : SymListGraph::Parent::EdgeMap<Value>(copy) { }
3.68 +
3.69 + };
3.70 +
3.71 + // Create edge map registry.
3.72 + CREATE_EDGE_MAP_REGISTRY;
3.73 + // Create edge maps.
3.74 + CREATE_EDGE_MAP(ArrayMap);
3.75 +
3.76 + class Edge {
3.77 + friend class SymListGraph;
3.78 + friend class SymListGraph::EdgeIt;
3.79 + friend class SymListGraph::OutEdgeIt;
3.80 + friend class SymListGraph::InEdgeIt;
3.81 +
3.82 + protected:
3.83 + int id;
3.84 +
3.85 + Edge(int pid) { id = pid; }
3.86 +
3.87 + public:
3.88 + /// An Edge with id \c n.
3.89 +
3.90 + Edge() { }
3.91 + Edge (Invalid) { id = -1; }
3.92 +
3.93 + operator SymEdge(){ return SymEdge(id >> 1);}
3.94 +
3.95 + bool operator==(const Edge i) const {return id == i.id;}
3.96 + bool operator!=(const Edge i) const {return id != i.id;}
3.97 + bool operator<(const Edge i) const {return id < i.id;}
3.98 + // ///Validity check
3.99 + // operator bool() { return n!=-1; }
3.100 + };
3.101 +
3.102 + class SymEdge : public ListGraph::Edge {
3.103 + friend class SymListGraph;
3.104 + friend class SymListGraph::Edge;
3.105 + typedef ListGraph::Edge Parent;
3.106 +
3.107 + protected:
3.108 + SymEdge(int pid) : Parent(pid) {}
3.109 + public:
3.110 +
3.111 + SymEdge() { }
3.112 + SymEdge(const ListGraph::Edge& i) : Parent(i) {}
3.113 + SymEdge (Invalid) : Parent(INVALID) {}
3.114 +
3.115 + };
3.116 +
3.117 + class OutEdgeIt {
3.118 + Parent::OutEdgeIt out;
3.119 + Parent::InEdgeIt in;
3.120 + public:
3.121 + OutEdgeIt() {}
3.122 + OutEdgeIt(const SymListGraph& g, Edge e) {
3.123 + if (e.id & 1 == 0) {
3.124 + out = Parent::OutEdgeIt(g, SymEdge(e));
3.125 + in = Parent::InEdgeIt(g, g.tail(e));
3.126 + } else {
3.127 + out = Parent::OutEdgeIt(INVALID);
3.128 + in = Parent::InEdgeIt(g, SymEdge(e));
3.129 + }
3.130 + }
3.131 + OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
3.132 +
3.133 + OutEdgeIt(const SymListGraph& g, const Node v)
3.134 + : out(g, v), in(g, v) {}
3.135 + OutEdgeIt &operator++() {
3.136 + if (out != INVALID) {
3.137 + ++out;
3.138 + } else {
3.139 + ++in;
3.140 + }
3.141 + return *this;
3.142 + }
3.143 +
3.144 + operator Edge() const {
3.145 + if (out == INVALID && in == INVALID) return INVALID;
3.146 + return out != INVALID ? forward(out) : backward(in);
3.147 + }
3.148 +
3.149 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.150 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.151 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.152 + };
3.153 +
3.154 + class InEdgeIt {
3.155 + Parent::OutEdgeIt out;
3.156 + Parent::InEdgeIt in;
3.157 + public:
3.158 + InEdgeIt() {}
3.159 + InEdgeIt(const SymListGraph& g, Edge e) {
3.160 + if (e.id & 1 == 0) {
3.161 + out = Parent::OutEdgeIt(g, SymEdge(e));
3.162 + in = Parent::InEdgeIt(g, g.tail(e));
3.163 + } else {
3.164 + out = Parent::OutEdgeIt(INVALID);
3.165 + in = Parent::InEdgeIt(g, SymEdge(e));
3.166 + }
3.167 + }
3.168 + InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
3.169 +
3.170 + InEdgeIt(const SymListGraph& g, const Node v)
3.171 + : out(g, v), in(g, v) {}
3.172 +
3.173 + InEdgeIt &operator++() {
3.174 + if (out != INVALID) {
3.175 + ++out;
3.176 + } else {
3.177 + ++in;
3.178 + }
3.179 + return *this;
3.180 + }
3.181 +
3.182 + operator Edge() const {
3.183 + if (out == INVALID && in == INVALID) return INVALID;
3.184 + return out != INVALID ? backward(out) : forward(in);
3.185 + }
3.186 +
3.187 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.188 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.189 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.190 + };
3.191 +
3.192 + class SymEdgeIt : public Parent::EdgeIt {
3.193 +
3.194 + public:
3.195 + SymEdgeIt() {}
3.196 +
3.197 + SymEdgeIt(const SymListGraph& g)
3.198 + : SymListGraph::Parent::EdgeIt(g) {}
3.199 +
3.200 + SymEdgeIt(const SymListGraph& g, SymEdge e)
3.201 + : SymListGraph::Parent::EdgeIt(g, e) {}
3.202 +
3.203 + SymEdgeIt(Invalid i)
3.204 + : SymListGraph::Parent::EdgeIt(INVALID) {}
3.205 +
3.206 + SymEdgeIt& operator++() {
3.207 + SymListGraph::Parent::EdgeIt::operator++();
3.208 + return *this;
3.209 + }
3.210 +
3.211 + operator SymEdge() const {
3.212 + return SymEdge
3.213 + (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
3.214 + }
3.215 + bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
3.216 + bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
3.217 + bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
3.218 + };
3.219 +
3.220 + class EdgeIt {
3.221 + SymEdgeIt it;
3.222 + bool fw;
3.223 + public:
3.224 + EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
3.225 + EdgeIt (Invalid i) : it(i) { }
3.226 + EdgeIt(const SymListGraph& g, Edge e)
3.227 + : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
3.228 + EdgeIt() { }
3.229 + EdgeIt& operator++() {
3.230 + fw = !fw;
3.231 + if (fw) ++it;
3.232 + return *this;
3.233 + }
3.234 + operator Edge() const {
3.235 + if (it == INVALID) return INVALID;
3.236 + return fw ? forward(it) : backward(it);
3.237 + }
3.238 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.239 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.240 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.241 +
3.242 + };
3.243 +
3.244 + ///Number of nodes.
3.245 + int nodeNum() const { return Parent::nodeNum(); }
3.246 + ///Number of edges.
3.247 + int edgeNum() const { return 2*Parent::edgeNum(); }
3.248 + ///Number of symmetric edges.
3.249 + int symEdgeNum() const { return Parent::edgeNum(); }
3.250 +
3.251 + ///Set the expected maximum number of edges.
3.252 +
3.253 + ///With this function, it is possible to set the expected number of edges.
3.254 + ///The use of this fasten the building of the graph and makes
3.255 + ///it possible to avoid the superfluous memory allocation.
3.256 + void reserveSymEdge(int n) { Parent::reserveEdge(n); };
3.257 +
3.258 + /// Maximum node ID.
3.259 +
3.260 + /// Maximum node ID.
3.261 + ///\sa id(Node)
3.262 + int maxNodeId() const { return Parent::maxNodeId(); }
3.263 + /// Maximum edge ID.
3.264 +
3.265 + /// Maximum edge ID.
3.266 + ///\sa id(Edge)
3.267 + int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
3.268 + /// Maximum symmetric edge ID.
3.269 +
3.270 + /// Maximum symmetric edge ID.
3.271 + ///\sa id(SymEdge)
3.272 + int maxSymEdgeId() const { return Parent::maxEdgeId(); }
3.273 +
3.274 +
3.275 + Node tail(Edge e) const {
3.276 + return e.id & 1 == 0 ?
3.277 + Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
3.278 + }
3.279 +
3.280 + Node head(Edge e) const {
3.281 + return e.id & 1 == 0 ?
3.282 + Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
3.283 + }
3.284 +
3.285 + Node tail(SymEdge e) const {
3.286 + return Parent::tail(e);
3.287 + }
3.288 +
3.289 + Node head(SymEdge e) const {
3.290 + return Parent::head(e);
3.291 + }
3.292 +
3.293 + NodeIt& first(NodeIt& v) const {
3.294 + v=NodeIt(*this); return v; }
3.295 + EdgeIt& first(EdgeIt& e) const {
3.296 + e=EdgeIt(*this); return e; }
3.297 + SymEdgeIt& first(SymEdgeIt& e) const {
3.298 + e=SymEdgeIt(*this); return e; }
3.299 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.300 + e=OutEdgeIt(*this,v); return e; }
3.301 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.302 + e=InEdgeIt(*this,v); return e; }
3.303 +
3.304 + /// Node ID.
3.305 +
3.306 + /// The ID of a valid Node is a nonnegative integer not greater than
3.307 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
3.308 + /// and the greatest node ID can be actually less then \ref maxNodeId().
3.309 + ///
3.310 + /// The ID of the \ref INVALID node is -1.
3.311 + ///\return The ID of the node \c v.
3.312 + static int id(Node v) { return Parent::id(v); }
3.313 + /// Edge ID.
3.314 +
3.315 + /// The ID of a valid Edge is a nonnegative integer not greater than
3.316 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
3.317 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
3.318 + ///
3.319 + /// The ID of the \ref INVALID edge is -1.
3.320 + ///\return The ID of the edge \c e.
3.321 + static int id(Edge e) { return e.id; }
3.322 +
3.323 + /// The ID of a valid SymEdge is a nonnegative integer not greater than
3.324 + /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
3.325 + /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
3.326 + ///
3.327 + /// The ID of the \ref INVALID symmetric edge is -1.
3.328 + ///\return The ID of the edge \c e.
3.329 + static int id(SymEdge e) { return Parent::id(e); }
3.330 +
3.331 + /// Adds a new node to the graph.
3.332 +
3.333 + /// \warning It adds the new node to the front of the list.
3.334 + /// (i.e. the lastly added node becomes the first.)
3.335 + Node addNode() {
3.336 + return Parent::addNode();
3.337 + }
3.338 +
3.339 + SymEdge addEdge(Node u, Node v) {
3.340 + SymEdge se = Parent::addEdge(u, v);
3.341 + edge_maps.add(forward(se));
3.342 + edge_maps.add(backward(se));
3.343 + return se;
3.344 + }
3.345 +
3.346 + /// Finds an edge between two nodes.
3.347 +
3.348 + /// Finds an edge from node \c u to node \c v.
3.349 + ///
3.350 + /// If \c prev is \ref INVALID (this is the default value), then
3.351 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.352 + /// the next edge from \c u to \c v after \c prev.
3.353 + /// \return The found edge or INVALID if there is no such an edge.
3.354 + Edge findEdge(Node u, Node v, Edge prev = INVALID)
3.355 + {
3.356 + if (prev == INVALID || id(prev) & 1 == 0) {
3.357 + SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
3.358 + if (se != INVALID) return forward(se);
3.359 + } else {
3.360 + SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
3.361 + if (se != INVALID) return backward(se);
3.362 + }
3.363 + return INVALID;
3.364 + }
3.365 +
3.366 + /// Finds an symmetric edge between two nodes.
3.367 +
3.368 + /// Finds an symmetric edge from node \c u to node \c v.
3.369 + ///
3.370 + /// If \c prev is \ref INVALID (this is the default value), then
3.371 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.372 + /// the next edge from \c u to \c v after \c prev.
3.373 + /// \return The found edge or INVALID if there is no such an edge.
3.374 +
3.375 +// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
3.376 +// {
3.377 +// if (prev == INVALID || id(prev) & 1 == 0) {
3.378 +// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
3.379 +// if (se != INVALID) return se;
3.380 +// } else {
3.381 +// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
3.382 +// if (se != INVALID) return se;
3.383 +// }
3.384 +// return INVALID;
3.385 +// }
3.386 +
3.387 + public:
3.388 +
3.389 + void erase(Node n) {
3.390 + for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
3.391 + edge_maps.erase(it);
3.392 + edge_maps.erase(opposite(it));
3.393 + }
3.394 + Parent::erase(n);
3.395 + }
3.396 +
3.397 + void erase(SymEdge e) {
3.398 + edge_maps.erase(forward(e));
3.399 + edge_maps.erase(backward(e));
3.400 + Parent::erase(e);
3.401 + };
3.402 +
3.403 + void clear() {
3.404 + edge_maps.clear();
3.405 + Parent::clear();
3.406 + }
3.407 +
3.408 + static Edge opposite(Edge e) {
3.409 + return Edge(id(e) ^ 1);
3.410 + }
3.411 +
3.412 + static Edge forward(SymEdge e) {
3.413 + return Edge(id(e) << 1);
3.414 + }
3.415 +
3.416 + static Edge backward(SymEdge e) {
3.417 + return Edge((id(e) << 1) & 1);
3.418 + }
3.419 +
3.420 };
3.421
3.422 -
3.423 ///A graph class containing only nodes.
3.424
3.425 ///This class implements a graph structure without edges.
4.1 --- a/src/hugo/map_bits.h Fri Sep 24 11:55:54 2004 +0000
4.2 +++ b/src/hugo/map_bits.h Sun Sep 26 21:43:38 2004 +0000
4.3 @@ -54,10 +54,10 @@
4.4 template <typename Graph>
4.5 struct KeyInfo<Graph, typename Graph::SymEdgeIt> {
4.6 static int maxId(const Graph& graph) {
4.7 - return graph.maxEdgeId() >> 1;
4.8 + return graph.maxSymEdgeId();
4.9 }
4.10 - static int id(const Graph& graph, const typename Graph::Edge& edge) {
4.11 - return graph.id(edge) >> 1;
4.12 + static int id(const Graph& graph, const typename Graph::SymEdge& edge) {
4.13 + return graph.id(edge);
4.14 }
4.15 };
4.16
5.1 --- a/src/hugo/map_defines.h Fri Sep 24 11:55:54 2004 +0000
5.2 +++ b/src/hugo/map_defines.h Sun Sep 26 21:43:38 2004 +0000
5.3 @@ -114,8 +114,7 @@
5.4 /** This macro creates MapRegistry for Symmetric Edge Maps.
5.5 */
5.6 #define CREATE_SYM_EDGE_MAP_REGISTRY \
5.7 -typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
5.8 -typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
5.9 +typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \
5.10 mutable SymEdgeMapRegistry sym_edge_maps;
5.11
5.12
5.13 @@ -127,9 +126,9 @@
5.14 */
5.15 #define CREATE_SYM_EDGE_MAP(DynMap) \
5.16 template <typename Value> \
5.17 -class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \
5.18 +class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \
5.19 public: \
5.20 -typedef SymMap<DynMap, SymEdgeMapRegistry, Value> Parent; \
5.21 +typedef DynMap<SymEdgeMapRegistry, Value> Parent; \
5.22 \
5.23 SymEdgeMap(const typename Parent::Graph& g) \
5.24 : Parent(g, g.sym_edge_maps) {} \
6.1 --- a/src/hugo/map_registry.h Fri Sep 24 11:55:54 2004 +0000
6.2 +++ b/src/hugo/map_registry.h Sun Sep 26 21:43:38 2004 +0000
6.3 @@ -252,7 +252,7 @@
6.4 /**
6.5 * Notify all the registered maps about a Key added.
6.6 */
6.7 - void add(KeyType& key) {
6.8 + void add(const KeyType& key) {
6.9 typename Container::iterator it;
6.10 for (it = container.begin(); it != container.end(); ++it) {
6.11 (*it)->add(key);
6.12 @@ -262,7 +262,7 @@
6.13 /**
6.14 * Notify all the registered maps about a Key erased.
6.15 */
6.16 - void erase(KeyType& key) {
6.17 + void erase(const KeyType& key) {
6.18 typename Container::iterator it;
6.19 for (it = container.begin(); it != container.end(); ++it) {
6.20 (*it)->erase(key);
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/hugo/skeletons/sym_graph.h Sun Sep 26 21:43:38 2004 +0000
7.3 @@ -0,0 +1,653 @@
7.4 +/* -*- C++ -*-
7.5 + * src/hugo/skeletons/graph.h - Part of HUGOlib, a generic C++ optimization library
7.6 + *
7.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
7.9 + *
7.10 + * Permission to use, modify and distribute this software is granted
7.11 + * provided that this copyright notice appears in all copies. For
7.12 + * precise terms see the accompanying LICENSE file.
7.13 + *
7.14 + * This software is provided "AS IS" with no warranty of any kind,
7.15 + * express or implied, and with no claim as to its suitability for any
7.16 + * purpose.
7.17 + *
7.18 + */
7.19 +
7.20 +#ifndef HUGO_SKELETON_SYM_GRAPH_H
7.21 +#define HUGO_SKELETON_SYM_GRAPH_H
7.22 +
7.23 +///\ingroup skeletons
7.24 +///\file
7.25 +///\brief Declaration of SymGraph.
7.26 +
7.27 +#include <hugo/invalid.h>
7.28 +#include <hugo/skeletons/graph.h>
7.29 +#include <hugo/skeletons/maps.h>
7.30 +
7.31 +namespace hugo {
7.32 + namespace skeleton {
7.33 +
7.34 + /// \addtogroup skeletons
7.35 + /// @{
7.36 +
7.37 + /// An empty static graph class.
7.38 +
7.39 + /// This class provides all the common features of a symmetric
7.40 + /// graph structure, however completely without implementations and
7.41 + /// real data structures behind the interface.
7.42 + /// All graph algorithms should compile with this class, but it will not
7.43 + /// run properly, of course.
7.44 + ///
7.45 + /// It can be used for checking the interface compatibility,
7.46 + /// or it can serve as a skeleton of a new symmetric graph structure.
7.47 + ///
7.48 + /// Also, you will find here the full documentation of a certain graph
7.49 + /// feature, the documentation of a real symmetric graph imlementation
7.50 + /// like @ref SymListGraph or
7.51 + /// @ref SymSmartGraph will just refer to this structure.
7.52 + class StaticSymGraph
7.53 + {
7.54 + public:
7.55 + /// Defalult constructor.
7.56 +
7.57 + /// Defalult constructor.
7.58 + ///
7.59 + StaticSymGraph() { }
7.60 + ///Copy consructor.
7.61 +
7.62 +// ///\todo It is not clear, what we expect from a copy constructor.
7.63 +// ///E.g. How to assign the nodes/edges to each other? What about maps?
7.64 +// StaticGraph(const StaticGraph& g) { }
7.65 +
7.66 + /// The base type of node iterators,
7.67 + /// or in other words, the trivial node iterator.
7.68 +
7.69 + /// This is the base type of each node iterator,
7.70 + /// thus each kind of node iterator converts to this.
7.71 + /// More precisely each kind of node iterator should be inherited
7.72 + /// from the trivial node iterator.
7.73 + class Node {
7.74 + public:
7.75 + /// Default constructor
7.76 +
7.77 + /// @warning The default constructor sets the iterator
7.78 + /// to an undefined value.
7.79 + Node() { }
7.80 + /// Copy constructor.
7.81 +
7.82 + /// Copy constructor.
7.83 + ///
7.84 + Node(const Node&) { }
7.85 +
7.86 + /// Invalid constructor \& conversion.
7.87 +
7.88 + /// This constructor initializes the iterator to be invalid.
7.89 + /// \sa Invalid for more details.
7.90 + Node(Invalid) { }
7.91 + /// Equality operator
7.92 +
7.93 + /// Two iterators are equal if and only if they point to the
7.94 + /// same object or both are invalid.
7.95 + bool operator==(Node) const { return true; }
7.96 +
7.97 + /// Inequality operator
7.98 +
7.99 + /// \sa \ref operator==(Node n)
7.100 + ///
7.101 + bool operator!=(Node) const { return true; }
7.102 +
7.103 + ///Comparison operator.
7.104 +
7.105 + ///This is a strict ordering between the nodes.
7.106 + ///
7.107 + ///This ordering can be different from the order in which NodeIt
7.108 + ///goes through the nodes.
7.109 + ///\todo Possibly we don't need it.
7.110 + bool operator<(Node) const { return true; }
7.111 + };
7.112 +
7.113 + /// This iterator goes through each node.
7.114 +
7.115 + /// This iterator goes through each node.
7.116 + /// Its usage is quite simple, for example you can count the number
7.117 + /// of nodes in graph \c g of type \c Graph like this:
7.118 + /// \code
7.119 + /// int count=0;
7.120 + /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
7.121 + /// \endcode
7.122 + class NodeIt : public Node {
7.123 + public:
7.124 + /// Default constructor
7.125 +
7.126 + /// @warning The default constructor sets the iterator
7.127 + /// to an undefined value.
7.128 + NodeIt() { }
7.129 + /// Copy constructor.
7.130 +
7.131 + /// Copy constructor.
7.132 + ///
7.133 + NodeIt(const NodeIt&) { }
7.134 + /// Invalid constructor \& conversion.
7.135 +
7.136 + /// Initialize the iterator to be invalid.
7.137 + /// \sa Invalid for more details.
7.138 + NodeIt(Invalid) { }
7.139 + /// Sets the iterator to the first node.
7.140 +
7.141 + /// Sets the iterator to the first node of \c g.
7.142 + ///
7.143 + NodeIt(const StaticSymGraph& g) { }
7.144 + /// Node -> NodeIt conversion.
7.145 +
7.146 + /// Sets the iterator to the node of \c g pointed by the trivial
7.147 + /// iterator n.
7.148 + /// This feature necessitates that each time we
7.149 + /// iterate the edge-set, the iteration order is the same.
7.150 + NodeIt(const StaticSymGraph& g, const Node& n) { }
7.151 + /// Next node.
7.152 +
7.153 + /// Assign the iterator to the next node.
7.154 + ///
7.155 + NodeIt& operator++() { return *this; }
7.156 + };
7.157 +
7.158 +
7.159 + /// The base type of the symmetric edge iterators.
7.160 +
7.161 + /// The base type of the symmetric edge iterators.
7.162 + ///
7.163 + class SymEdge {
7.164 + public:
7.165 + /// Default constructor
7.166 +
7.167 + /// @warning The default constructor sets the iterator
7.168 + /// to an undefined value.
7.169 + SymEdge() { }
7.170 + /// Copy constructor.
7.171 +
7.172 + /// Copy constructor.
7.173 + ///
7.174 + SymEdge(const SymEdge&) { }
7.175 + /// Initialize the iterator to be invalid.
7.176 +
7.177 + /// Initialize the iterator to be invalid.
7.178 + ///
7.179 + SymEdge(Invalid) { }
7.180 + /// Equality operator
7.181 +
7.182 + /// Two iterators are equal if and only if they point to the
7.183 + /// same object or both are invalid.
7.184 + bool operator==(SymEdge) const { return true; }
7.185 + /// Inequality operator
7.186 +
7.187 + /// \sa \ref operator==(Node n)
7.188 + ///
7.189 + bool operator!=(SymEdge) const { return true; }
7.190 + ///Comparison operator.
7.191 +
7.192 + ///This is a strict ordering between the nodes.
7.193 + ///
7.194 + ///This ordering can be different from the order in which NodeIt
7.195 + ///goes through the nodes.
7.196 + ///\todo Possibly we don't need it.
7.197 + bool operator<(SymEdge) const { return true; }
7.198 + };
7.199 +
7.200 +
7.201 + /// The base type of the edge iterators.
7.202 +
7.203 + /// The base type of the edge iterators.
7.204 + ///
7.205 + class Edge : public SymEdge {
7.206 + public:
7.207 + /// Default constructor
7.208 +
7.209 + /// @warning The default constructor sets the iterator
7.210 + /// to an undefined value.
7.211 + Edge() { }
7.212 + /// Copy constructor.
7.213 +
7.214 + /// Copy constructor.
7.215 + ///
7.216 + Edge(const Edge&) { }
7.217 + /// Initialize the iterator to be invalid.
7.218 +
7.219 + /// Initialize the iterator to be invalid.
7.220 + ///
7.221 + Edge(Invalid) { }
7.222 + /// Equality operator
7.223 +
7.224 + /// Two iterators are equal if and only if they point to the
7.225 + /// same object or both are invalid.
7.226 + bool operator==(Edge) const { return true; }
7.227 + /// Inequality operator
7.228 +
7.229 + /// \sa \ref operator==(Node n)
7.230 + ///
7.231 + bool operator!=(Edge) const { return true; }
7.232 + ///Comparison operator.
7.233 +
7.234 + ///This is a strict ordering between the nodes.
7.235 + ///
7.236 + ///This ordering can be different from the order in which NodeIt
7.237 + ///goes through the nodes.
7.238 + ///\todo Possibly we don't need it.
7.239 + bool operator<(Edge) const { return true; }
7.240 + };
7.241 +
7.242 + /// This iterator goes trough the outgoing edges of a node.
7.243 +
7.244 + /// This iterator goes trough the \e outgoing edges of a certain node
7.245 + /// of a graph.
7.246 + /// Its usage is quite simple, for example you can count the number
7.247 + /// of outgoing edges of a node \c n
7.248 + /// in graph \c g of type \c Graph as follows.
7.249 + /// \code
7.250 + /// int count=0;
7.251 + /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
7.252 + /// \endcode
7.253 +
7.254 + class OutEdgeIt : public Edge {
7.255 + public:
7.256 + /// Default constructor
7.257 +
7.258 + /// @warning The default constructor sets the iterator
7.259 + /// to an undefined value.
7.260 + OutEdgeIt() { }
7.261 + /// Copy constructor.
7.262 +
7.263 + /// Copy constructor.
7.264 + ///
7.265 + OutEdgeIt(const OutEdgeIt&) { }
7.266 + /// Initialize the iterator to be invalid.
7.267 +
7.268 + /// Initialize the iterator to be invalid.
7.269 + ///
7.270 + OutEdgeIt(Invalid) { }
7.271 + /// This constructor sets the iterator to first outgoing edge.
7.272 +
7.273 + /// This constructor set the iterator to the first outgoing edge of
7.274 + /// node
7.275 + ///@param n the node
7.276 + ///@param g the graph
7.277 + OutEdgeIt(const StaticSymGraph& g, const Node& n) { }
7.278 + /// Edge -> OutEdgeIt conversion
7.279 +
7.280 + /// Sets the iterator to the value of the trivial iterator \c e.
7.281 + /// This feature necessitates that each time we
7.282 + /// iterate the edge-set, the iteration order is the same.
7.283 + OutEdgeIt(const StaticSymGraph& g, const Edge& e) { }
7.284 + ///Next outgoing edge
7.285 +
7.286 + /// Assign the iterator to the next
7.287 + /// outgoing edge of the corresponding node.
7.288 + OutEdgeIt& operator++() { return *this; }
7.289 + };
7.290 +
7.291 + /// This iterator goes trough the incoming edges of a node.
7.292 +
7.293 + /// This iterator goes trough the \e incoming edges of a certain node
7.294 + /// of a graph.
7.295 + /// Its usage is quite simple, for example you can count the number
7.296 + /// of outgoing edges of a node \c n
7.297 + /// in graph \c g of type \c Graph as follows.
7.298 + /// \code
7.299 + /// int count=0;
7.300 + /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
7.301 + /// \endcode
7.302 +
7.303 + class InEdgeIt : public Edge {
7.304 + public:
7.305 + /// Default constructor
7.306 +
7.307 + /// @warning The default constructor sets the iterator
7.308 + /// to an undefined value.
7.309 + InEdgeIt() { }
7.310 + /// Copy constructor.
7.311 +
7.312 + /// Copy constructor.
7.313 + ///
7.314 + InEdgeIt(const InEdgeIt&) { }
7.315 + /// Initialize the iterator to be invalid.
7.316 +
7.317 + /// Initialize the iterator to be invalid.
7.318 + ///
7.319 + InEdgeIt(Invalid) { }
7.320 + /// This constructor sets the iterator to first incoming edge.
7.321 +
7.322 + /// This constructor set the iterator to the first incoming edge of
7.323 + /// node
7.324 + ///@param n the node
7.325 + ///@param g the graph
7.326 + InEdgeIt(const StaticSymGraph& g, const Node& n) { }
7.327 + /// Edge -> InEdgeIt conversion
7.328 +
7.329 + /// Sets the iterator to the value of the trivial iterator \c e.
7.330 + /// This feature necessitates that each time we
7.331 + /// iterate the edge-set, the iteration order is the same.
7.332 + InEdgeIt(const StaticSymGraph& g, const Edge& n) { }
7.333 + /// Next incoming edge
7.334 +
7.335 + /// Assign the iterator to the next inedge of the corresponding node.
7.336 + ///
7.337 + InEdgeIt& operator++() { return *this; }
7.338 + };
7.339 + /// This iterator goes through each symmetric edge.
7.340 +
7.341 + /// This iterator goes through each symmetric edge of a graph.
7.342 + /// Its usage is quite simple, for example you can count the number
7.343 + /// of symmetric edges in a graph \c g of type \c Graph as follows:
7.344 + /// \code
7.345 + /// int count=0;
7.346 + /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count;
7.347 + /// \endcode
7.348 + class SymEdgeIt : public SymEdge {
7.349 + public:
7.350 + /// Default constructor
7.351 +
7.352 + /// @warning The default constructor sets the iterator
7.353 + /// to an undefined value.
7.354 + SymEdgeIt() { }
7.355 + /// Copy constructor.
7.356 +
7.357 + /// Copy constructor.
7.358 + ///
7.359 + SymEdgeIt(const SymEdgeIt&) { }
7.360 + /// Initialize the iterator to be invalid.
7.361 +
7.362 + /// Initialize the iterator to be invalid.
7.363 + ///
7.364 + SymEdgeIt(Invalid) { }
7.365 + /// This constructor sets the iterator to first edge.
7.366 +
7.367 + /// This constructor set the iterator to the first edge of
7.368 + /// node
7.369 + ///@param g the graph
7.370 + SymEdgeIt(const StaticSymGraph& g) { }
7.371 + /// Edge -> EdgeIt conversion
7.372 +
7.373 + /// Sets the iterator to the value of the trivial iterator \c e.
7.374 + /// This feature necessitates that each time we
7.375 + /// iterate the edge-set, the iteration order is the same.
7.376 + SymEdgeIt(const StaticSymGraph&, const SymEdge&) { }
7.377 + ///Next edge
7.378 +
7.379 + /// Assign the iterator to the next
7.380 + /// edge of the corresponding node.
7.381 + SymEdgeIt& operator++() { return *this; }
7.382 + };
7.383 + /// This iterator goes through each edge.
7.384 +
7.385 + /// This iterator goes through each edge of a graph.
7.386 + /// Its usage is quite simple, for example you can count the number
7.387 + /// of edges in a graph \c g of type \c Graph as follows:
7.388 + /// \code
7.389 + /// int count=0;
7.390 + /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
7.391 + /// \endcode
7.392 + class EdgeIt : public Edge {
7.393 + public:
7.394 + /// Default constructor
7.395 +
7.396 + /// @warning The default constructor sets the iterator
7.397 + /// to an undefined value.
7.398 + EdgeIt() { }
7.399 + /// Copy constructor.
7.400 +
7.401 + /// Copy constructor.
7.402 + ///
7.403 + EdgeIt(const EdgeIt&) { }
7.404 + /// Initialize the iterator to be invalid.
7.405 +
7.406 + /// Initialize the iterator to be invalid.
7.407 + ///
7.408 + EdgeIt(Invalid) { }
7.409 + /// This constructor sets the iterator to first edge.
7.410 +
7.411 + /// This constructor set the iterator to the first edge of
7.412 + /// node
7.413 + ///@param g the graph
7.414 + EdgeIt(const StaticSymGraph& g) { }
7.415 + /// Edge -> EdgeIt conversion
7.416 +
7.417 + /// Sets the iterator to the value of the trivial iterator \c e.
7.418 + /// This feature necessitates that each time we
7.419 + /// iterate the edge-set, the iteration order is the same.
7.420 + EdgeIt(const StaticSymGraph&, const Edge&) { }
7.421 + ///Next edge
7.422 +
7.423 + /// Assign the iterator to the next
7.424 + /// edge of the corresponding node.
7.425 + EdgeIt& operator++() { return *this; }
7.426 + };
7.427 +
7.428 + /// First node of the graph.
7.429 +
7.430 + /// \retval i the first node.
7.431 + /// \return the first node.
7.432 + ///
7.433 + NodeIt& first(NodeIt& i) const { return i; }
7.434 +
7.435 + /// The first incoming edge.
7.436 +
7.437 + /// The first incoming edge.
7.438 + ///
7.439 + InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
7.440 + /// The first outgoing edge.
7.441 +
7.442 + /// The first outgoing edge.
7.443 + ///
7.444 + OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
7.445 + /// The first edge of the Graph.
7.446 +
7.447 + /// The first edge of the Graph.
7.448 + ///
7.449 + EdgeIt& first(EdgeIt& i) const { return i; }
7.450 + /// The first symmetric edge of the Graph.
7.451 +
7.452 + /// The first symmetric edge of the Graph.
7.453 + ///
7.454 + SymEdgeIt& first(SymEdgeIt& i) const { return i; }
7.455 +
7.456 + ///Gives back the head node of an edge.
7.457 +
7.458 + ///Gives back the head node of an edge.
7.459 + ///
7.460 + Node head(Edge) const { return INVALID; }
7.461 + ///Gives back the tail node of an edge.
7.462 +
7.463 + ///Gives back the tail node of an edge.
7.464 + ///
7.465 + Node tail(Edge) const { return INVALID; }
7.466 +
7.467 + ///Gives back the first node of an symmetric edge.
7.468 +
7.469 + ///Gives back the first node of an symmetric edge.
7.470 + ///
7.471 + Node head(SymEdge) const { return INVALID; }
7.472 + ///Gives back the second node of an symmetric edge.
7.473 +
7.474 + ///Gives back the second node of an symmetric edge.
7.475 + ///
7.476 + Node tail(SymEdge) const { return INVALID; }
7.477 + ///Gives back the \e id of a node.
7.478 +
7.479 + ///\warning Not all graph structures provide this feature.
7.480 + ///
7.481 + ///\todo Should each graph provide \c id?
7.482 + int id(const Node&) const { return 0; }
7.483 + ///Gives back the \e id of an edge.
7.484 +
7.485 + ///\warning Not all graph structures provide this feature.
7.486 + ///
7.487 + ///\todo Should each graph provide \c id?
7.488 + int id(const Edge&) const { return 0; }
7.489 +
7.490 + ///\warning Not all graph structures provide this feature.
7.491 + ///
7.492 + ///\todo Should each graph provide \c id?
7.493 + int id(const SymEdge&) const { return 0; }
7.494 +
7.495 + /// .
7.496 +
7.497 + ///\todo Should it be in the concept?
7.498 + ///
7.499 + int nodeNum() const { return 0; }
7.500 + /// .
7.501 +
7.502 + ///\todo Should it be in the concept?
7.503 + ///
7.504 + int edgeNum() const { return 0; }
7.505 +
7.506 + ///\todo Should it be in the concept?
7.507 + ///
7.508 + int symEdgeNum() const { return 0; }
7.509 +
7.510 +
7.511 + /// Gives back the forward directed edge of the symmetric edge.
7.512 + Edge forward(SymEdge) const {return INVALID;}
7.513 +
7.514 + /// Gives back the backward directed edge of the symmetric edge.
7.515 + Edge backward(SymEdge) const {return INVALID;};
7.516 +
7.517 + /// Gives back the opposite of the edge.
7.518 + Edge opposite(Edge) const {return INVALID;}
7.519 +
7.520 + ///Reference map of the nodes to type \c T.
7.521 + /// \ingroup skeletons
7.522 + ///Reference map of the nodes to type \c T.
7.523 + /// \sa Reference
7.524 + /// \warning Making maps that can handle bool type (NodeMap<bool>)
7.525 + /// needs some extra attention!
7.526 + template<class T> class NodeMap : public ReferenceMap< Node, T >
7.527 + {
7.528 + public:
7.529 +
7.530 + /// .
7.531 + NodeMap(const StaticSymGraph&) { }
7.532 + /// .
7.533 + NodeMap(const StaticSymGraph&, T) { }
7.534 +
7.535 + ///Copy constructor
7.536 + template<typename TT> NodeMap(const NodeMap<TT>&) { }
7.537 + ///Assignment operator
7.538 + template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
7.539 + { return *this; }
7.540 + };
7.541 +
7.542 + ///Reference map of the edges to type \c T.
7.543 +
7.544 + /// \ingroup skeletons
7.545 + ///Reference map of the edges to type \c T.
7.546 + /// \sa Reference
7.547 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
7.548 + /// needs some extra attention!
7.549 + template<class T> class EdgeMap
7.550 + : public ReferenceMap<Edge,T>
7.551 + {
7.552 + public:
7.553 +
7.554 + /// .
7.555 + EdgeMap(const StaticSymGraph&) { }
7.556 + /// .
7.557 + EdgeMap(const StaticSymGraph&, T) { }
7.558 +
7.559 + ///Copy constructor
7.560 + template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
7.561 + ///Assignment operator
7.562 + template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
7.563 + { return *this; }
7.564 + };
7.565 +
7.566 + ///Reference map of the edges to type \c T.
7.567 +
7.568 + /// \ingroup skeletons
7.569 + ///Reference map of the symmetric edges to type \c T.
7.570 + /// \sa Reference
7.571 + /// \warning Making maps that can handle bool type (EdgeMap<bool>)
7.572 + /// needs some extra attention!
7.573 + template<class T> class SymEdgeMap
7.574 + : public ReferenceMap<SymEdge,T>
7.575 + {
7.576 + public:
7.577 +
7.578 + /// .
7.579 + SymEdgeMap(const StaticSymGraph&) { }
7.580 + /// .
7.581 + SymEdgeMap(const StaticSymGraph&, T) { }
7.582 +
7.583 + ///Copy constructor
7.584 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { }
7.585 + ///Assignment operator
7.586 + template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&)
7.587 + { return *this; }
7.588 + };
7.589 + };
7.590 +
7.591 +
7.592 +
7.593 + /// An empty non-static graph class.
7.594 +
7.595 + /// This class provides everything that \ref StaticGraph
7.596 + /// with additional functionality which enables to build a
7.597 + /// graph from scratch.
7.598 + class ExtendableSymGraph : public StaticSymGraph
7.599 + {
7.600 + public:
7.601 + /// Defalult constructor.
7.602 +
7.603 + /// Defalult constructor.
7.604 + ///
7.605 + ExtendableSymGraph() { }
7.606 + ///Add a new node to the graph.
7.607 +
7.608 + /// \return the new node.
7.609 + ///
7.610 + Node addNode() { return INVALID; }
7.611 + ///Add a new edge to the graph.
7.612 +
7.613 + ///Add a new symmetric edge to the graph with tail node \c t
7.614 + ///and head node \c h.
7.615 + ///\return the new edge.
7.616 + SymEdge addEdge(Node h, Node t) { return INVALID; }
7.617 +
7.618 + /// Resets the graph.
7.619 +
7.620 + /// This function deletes all edges and nodes of the graph.
7.621 + /// It also frees the memory allocated to store them.
7.622 + /// \todo It might belong to \ref ErasableGraph.
7.623 + void clear() { }
7.624 + };
7.625 +
7.626 + /// An empty erasable graph class.
7.627 +
7.628 + /// This class is an extension of \ref ExtendableGraph. It also makes it
7.629 + /// possible to erase edges or nodes.
7.630 + class ErasableSymGraph : public ExtendableSymGraph
7.631 + {
7.632 + public:
7.633 + /// Defalult constructor.
7.634 +
7.635 + /// Defalult constructor.
7.636 + ///
7.637 + ErasableSymGraph() { }
7.638 + /// Deletes a node.
7.639 +
7.640 + /// Deletes node \c n node.
7.641 + ///
7.642 + void erase(Node n) { }
7.643 + /// Deletes an edge.
7.644 +
7.645 + /// Deletes edge \c e edge.
7.646 + ///
7.647 + void erase(SymEdge e) { }
7.648 + };
7.649 +
7.650 + // @}
7.651 + } //namespace skeleton
7.652 +} //namespace hugo
7.653 +
7.654 +
7.655 +
7.656 +#endif // HUGO_SKELETON_GRAPH_H
8.1 --- a/src/hugo/smart_graph.h Fri Sep 24 11:55:54 2004 +0000
8.2 +++ b/src/hugo/smart_graph.h Sun Sep 26 21:43:38 2004 +0000
8.3 @@ -27,8 +27,6 @@
8.4 #include <hugo/invalid.h>
8.5
8.6 #include <hugo/array_map.h>
8.7 -#include <hugo/sym_map.h>
8.8 -
8.9 #include <hugo/map_registry.h>
8.10
8.11 #include <hugo/map_defines.h>
8.12 @@ -298,6 +296,381 @@
8.13
8.14 };
8.15
8.16 +
8.17 +
8.18 + class SymSmartGraph : public SmartGraph {
8.19 + typedef SmartGraph Parent;
8.20 + public:
8.21 +
8.22 + typedef SymSmartGraph Graph;
8.23 +
8.24 + typedef SmartGraph::Node Node;
8.25 + typedef SmartGraph::NodeIt NodeIt;
8.26 +
8.27 + class SymEdge;
8.28 + class SymEdgeIt;
8.29 +
8.30 + class Edge;
8.31 + class EdgeIt;
8.32 + class OutEdgeIt;
8.33 + class InEdgeIt;
8.34 +
8.35 + template <typename Value>
8.36 + class NodeMap : public Parent::NodeMap<Value> {
8.37 + public:
8.38 + NodeMap(const SymSmartGraph& g)
8.39 + : SymSmartGraph::Parent::NodeMap<Value>(g) {}
8.40 + NodeMap(const SymSmartGraph& g, Value v)
8.41 + : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
8.42 + template<typename TT>
8.43 + NodeMap(const NodeMap<TT>& copy)
8.44 + : SymSmartGraph::Parent::NodeMap<Value>(copy) { }
8.45 + };
8.46 +
8.47 + template <typename Value>
8.48 + class SymEdgeMap : public Parent::EdgeMap<Value> {
8.49 + public:
8.50 + typedef SymEdge KeyType;
8.51 +
8.52 + SymEdgeMap(const SymSmartGraph& g)
8.53 + : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
8.54 + SymEdgeMap(const SymSmartGraph& g, Value v)
8.55 + : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
8.56 + template<typename TT>
8.57 + SymEdgeMap(const SymEdgeMap<TT>& copy)
8.58 + : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
8.59 +
8.60 + };
8.61 +
8.62 + // Create edge map registry.
8.63 + CREATE_EDGE_MAP_REGISTRY;
8.64 + // Create edge maps.
8.65 + CREATE_EDGE_MAP(ArrayMap);
8.66 +
8.67 + class Edge {
8.68 + friend class SymSmartGraph;
8.69 + friend class SymSmartGraph::EdgeIt;
8.70 + friend class SymSmartGraph::OutEdgeIt;
8.71 + friend class SymSmartGraph::InEdgeIt;
8.72 +
8.73 + protected:
8.74 + int id;
8.75 +
8.76 + Edge(int pid) { id = pid; }
8.77 +
8.78 + public:
8.79 + /// An Edge with id \c n.
8.80 +
8.81 + Edge() { }
8.82 + Edge (Invalid) { id = -1; }
8.83 +
8.84 + operator SymEdge(){ return SymEdge(id >> 1);}
8.85 +
8.86 + bool operator==(const Edge i) const {return id == i.id;}
8.87 + bool operator!=(const Edge i) const {return id != i.id;}
8.88 + bool operator<(const Edge i) const {return id < i.id;}
8.89 + // ///Validity check
8.90 + // operator bool() { return n!=-1; }
8.91 + };
8.92 +
8.93 + class SymEdge : public SmartGraph::Edge {
8.94 + friend class SymSmartGraph;
8.95 + friend class SymSmartGraph::Edge;
8.96 + typedef SmartGraph::Edge Parent;
8.97 +
8.98 + protected:
8.99 + SymEdge(int pid) : Parent(pid) {}
8.100 + public:
8.101 +
8.102 + SymEdge() { }
8.103 + SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
8.104 + SymEdge (Invalid) : Parent(INVALID) {}
8.105 +
8.106 + };
8.107 +
8.108 + class OutEdgeIt {
8.109 + Parent::OutEdgeIt out;
8.110 + Parent::InEdgeIt in;
8.111 + public:
8.112 + OutEdgeIt() {}
8.113 + OutEdgeIt(const SymSmartGraph& g, Edge e) {
8.114 + if (e.id & 1 == 0) {
8.115 + out = Parent::OutEdgeIt(g, SymEdge(e));
8.116 + in = Parent::InEdgeIt(g, g.tail(e));
8.117 + } else {
8.118 + out = Parent::OutEdgeIt(INVALID);
8.119 + in = Parent::InEdgeIt(g, SymEdge(e));
8.120 + }
8.121 + }
8.122 + OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
8.123 +
8.124 + OutEdgeIt(const SymSmartGraph& g, const Node v)
8.125 + : out(g, v), in(g, v) {}
8.126 + OutEdgeIt &operator++() {
8.127 + if (out != INVALID) {
8.128 + ++out;
8.129 + } else {
8.130 + ++in;
8.131 + }
8.132 + return *this;
8.133 + }
8.134 +
8.135 + operator Edge() const {
8.136 + if (out == INVALID && in == INVALID) return INVALID;
8.137 + return out != INVALID ? forward(out) : backward(in);
8.138 + }
8.139 +
8.140 + bool operator==(const Edge i) const {return Edge(*this) == i;}
8.141 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
8.142 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.143 + };
8.144 +
8.145 + class InEdgeIt {
8.146 + Parent::OutEdgeIt out;
8.147 + Parent::InEdgeIt in;
8.148 + public:
8.149 + InEdgeIt() {}
8.150 + InEdgeIt(const SymSmartGraph& g, Edge e) {
8.151 + if (e.id & 1 == 0) {
8.152 + out = Parent::OutEdgeIt(g, SymEdge(e));
8.153 + in = Parent::InEdgeIt(g, g.tail(e));
8.154 + } else {
8.155 + out = Parent::OutEdgeIt(INVALID);
8.156 + in = Parent::InEdgeIt(g, SymEdge(e));
8.157 + }
8.158 + }
8.159 + InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
8.160 +
8.161 + InEdgeIt(const SymSmartGraph& g, const Node v)
8.162 + : out(g, v), in(g, v) {}
8.163 +
8.164 + InEdgeIt &operator++() {
8.165 + if (out != INVALID) {
8.166 + ++out;
8.167 + } else {
8.168 + ++in;
8.169 + }
8.170 + return *this;
8.171 + }
8.172 +
8.173 + operator Edge() const {
8.174 + if (out == INVALID && in == INVALID) return INVALID;
8.175 + return out != INVALID ? backward(out) : forward(in);
8.176 + }
8.177 +
8.178 + bool operator==(const Edge i) const {return Edge(*this) == i;}
8.179 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
8.180 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.181 + };
8.182 +
8.183 + class SymEdgeIt : public Parent::EdgeIt {
8.184 +
8.185 + public:
8.186 + SymEdgeIt() {}
8.187 +
8.188 + SymEdgeIt(const SymSmartGraph& g)
8.189 + : SymSmartGraph::Parent::EdgeIt(g) {}
8.190 +
8.191 + SymEdgeIt(const SymSmartGraph& g, SymEdge e)
8.192 + : SymSmartGraph::Parent::EdgeIt(g, e) {}
8.193 +
8.194 + SymEdgeIt(Invalid i)
8.195 + : SymSmartGraph::Parent::EdgeIt(INVALID) {}
8.196 +
8.197 + SymEdgeIt& operator++() {
8.198 + SymSmartGraph::Parent::EdgeIt::operator++();
8.199 + return *this;
8.200 + }
8.201 +
8.202 + operator SymEdge() const {
8.203 + return SymEdge
8.204 + (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
8.205 + }
8.206 + bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
8.207 + bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
8.208 + bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
8.209 + };
8.210 +
8.211 + class EdgeIt {
8.212 + SymEdgeIt it;
8.213 + bool fw;
8.214 + public:
8.215 + EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
8.216 + EdgeIt (Invalid i) : it(i) { }
8.217 + EdgeIt(const SymSmartGraph& g, Edge e)
8.218 + : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
8.219 + EdgeIt() { }
8.220 + EdgeIt& operator++() {
8.221 + fw = !fw;
8.222 + if (fw) ++it;
8.223 + return *this;
8.224 + }
8.225 + operator Edge() const {
8.226 + if (it == INVALID) return INVALID;
8.227 + return fw ? forward(it) : backward(it);
8.228 + }
8.229 + bool operator==(const Edge i) const {return Edge(*this) == i;}
8.230 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
8.231 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.232 +
8.233 + };
8.234 +
8.235 + ///Number of nodes.
8.236 + int nodeNum() const { return Parent::nodeNum(); }
8.237 + ///Number of edges.
8.238 + int edgeNum() const { return 2*Parent::edgeNum(); }
8.239 + ///Number of symmetric edges.
8.240 + int symEdgeNum() const { return Parent::edgeNum(); }
8.241 +
8.242 + /// Maximum node ID.
8.243 +
8.244 + /// Maximum node ID.
8.245 + ///\sa id(Node)
8.246 + int maxNodeId() const { return Parent::maxNodeId(); }
8.247 + /// Maximum edge ID.
8.248 +
8.249 + /// Maximum edge ID.
8.250 + ///\sa id(Edge)
8.251 + int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
8.252 + /// Maximum symmetric edge ID.
8.253 +
8.254 + /// Maximum symmetric edge ID.
8.255 + ///\sa id(SymEdge)
8.256 + int maxSymEdgeId() const { return Parent::maxEdgeId(); }
8.257 +
8.258 +
8.259 + Node tail(Edge e) const {
8.260 + return e.id & 1 == 0 ?
8.261 + Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
8.262 + }
8.263 +
8.264 + Node head(Edge e) const {
8.265 + return e.id & 1 == 0 ?
8.266 + Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
8.267 + }
8.268 +
8.269 + Node tail(SymEdge e) const {
8.270 + return Parent::tail(e);
8.271 + }
8.272 +
8.273 + Node head(SymEdge e) const {
8.274 + return Parent::head(e);
8.275 + }
8.276 +
8.277 + NodeIt& first(NodeIt& v) const {
8.278 + v=NodeIt(*this); return v; }
8.279 + EdgeIt& first(EdgeIt& e) const {
8.280 + e=EdgeIt(*this); return e; }
8.281 + SymEdgeIt& first(SymEdgeIt& e) const {
8.282 + e=SymEdgeIt(*this); return e; }
8.283 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
8.284 + e=OutEdgeIt(*this,v); return e; }
8.285 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
8.286 + e=InEdgeIt(*this,v); return e; }
8.287 +
8.288 + /// Node ID.
8.289 +
8.290 + /// The ID of a valid Node is a nonnegative integer not greater than
8.291 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
8.292 + /// and the greatest node ID can be actually less then \ref maxNodeId().
8.293 + ///
8.294 + /// The ID of the \ref INVALID node is -1.
8.295 + ///\return The ID of the node \c v.
8.296 + static int id(Node v) { return Parent::id(v); }
8.297 + /// Edge ID.
8.298 +
8.299 + /// The ID of a valid Edge is a nonnegative integer not greater than
8.300 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
8.301 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
8.302 + ///
8.303 + /// The ID of the \ref INVALID edge is -1.
8.304 + ///\return The ID of the edge \c e.
8.305 + static int id(Edge e) { return e.id; }
8.306 +
8.307 + /// The ID of a valid SymEdge is a nonnegative integer not greater than
8.308 + /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
8.309 + /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
8.310 + ///
8.311 + /// The ID of the \ref INVALID symmetric edge is -1.
8.312 + ///\return The ID of the edge \c e.
8.313 + static int id(SymEdge e) { return Parent::id(e); }
8.314 +
8.315 + /// Adds a new node to the graph.
8.316 +
8.317 + /// \warning It adds the new node to the front of the list.
8.318 + /// (i.e. the lastly added node becomes the first.)
8.319 + Node addNode() {
8.320 + return Parent::addNode();
8.321 + }
8.322 +
8.323 + SymEdge addEdge(Node u, Node v) {
8.324 + SymEdge se = Parent::addEdge(u, v);
8.325 + edge_maps.add(forward(se));
8.326 + edge_maps.add(backward(se));
8.327 + return se;
8.328 + }
8.329 +
8.330 + /// Finds an edge between two nodes.
8.331 +
8.332 + /// Finds an edge from node \c u to node \c v.
8.333 + ///
8.334 + /// If \c prev is \ref INVALID (this is the default value), then
8.335 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
8.336 + /// the next edge from \c u to \c v after \c prev.
8.337 + /// \return The found edge or INVALID if there is no such an edge.
8.338 + Edge findEdge(Node u, Node v, Edge prev = INVALID)
8.339 + {
8.340 + if (prev == INVALID || id(prev) & 1 == 0) {
8.341 + SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
8.342 + if (se != INVALID) return forward(se);
8.343 + } else {
8.344 + SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
8.345 + if (se != INVALID) return backward(se);
8.346 + }
8.347 + return INVALID;
8.348 + }
8.349 +
8.350 + /// Finds an symmetric edge between two nodes.
8.351 +
8.352 + /// Finds an symmetric edge from node \c u to node \c v.
8.353 + ///
8.354 + /// If \c prev is \ref INVALID (this is the default value), then
8.355 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
8.356 + /// the next edge from \c u to \c v after \c prev.
8.357 + /// \return The found edge or INVALID if there is no such an edge.
8.358 +
8.359 +// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
8.360 +// {
8.361 +// if (prev == INVALID || id(prev) & 1 == 0) {
8.362 +// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
8.363 +// if (se != INVALID) return se;
8.364 +// } else {
8.365 +// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
8.366 +// if (se != INVALID) return se;
8.367 +// }
8.368 +// return INVALID;
8.369 +// }
8.370 +
8.371 + public:
8.372 +
8.373 + void clear() {
8.374 + edge_maps.clear();
8.375 + Parent::clear();
8.376 + }
8.377 +
8.378 + static Edge opposite(Edge e) {
8.379 + return Edge(id(e) ^ 1);
8.380 + }
8.381 +
8.382 + static Edge forward(SymEdge e) {
8.383 + return Edge(id(e) << 1);
8.384 + }
8.385 +
8.386 + static Edge backward(SymEdge e) {
8.387 + return Edge((id(e) << 1) & 1);
8.388 + }
8.389 +
8.390 + };
8.391 ///Graph for bidirectional edges.
8.392
8.393 ///The purpose of this graph structure is to handle graphs
8.394 @@ -318,7 +691,7 @@
8.395 ///it is not possible to delete edges or nodes from the graph.
8.396 //\sa SmartGraph.
8.397
8.398 - class SymSmartGraph : public SmartGraph
8.399 + /* class SymSmartGraph : public SmartGraph
8.400 {
8.401 public:
8.402 typedef SymSmartGraph Graph;
8.403 @@ -353,7 +726,7 @@
8.404 }
8.405
8.406
8.407 - };
8.408 + };*/
8.409
8.410 /// @}
8.411 } //namespace hugo
9.1 --- a/src/hugo/sym_map.h Fri Sep 24 11:55:54 2004 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,144 +0,0 @@
9.4 -/* -*- C++ -*-
9.5 - * src/hugo/sym_map.h - Part of HUGOlib, a generic C++ optimization library
9.6 - *
9.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
9.9 - *
9.10 - * Permission to use, modify and distribute this software is granted
9.11 - * provided that this copyright notice appears in all copies. For
9.12 - * precise terms see the accompanying LICENSE file.
9.13 - *
9.14 - * This software is provided "AS IS" with no warranty of any kind,
9.15 - * express or implied, and with no claim as to its suitability for any
9.16 - * purpose.
9.17 - *
9.18 - */
9.19 -
9.20 -#ifndef HUGO_SYM_MAP_H
9.21 -#define HUGO_SYM_MAP_H
9.22 -
9.23 -///\ingroup graphmaps
9.24 -///\file
9.25 -///\brief Graph maps that construates and destruates
9.26 -///their elements dynamically.
9.27 -
9.28 -namespace hugo {
9.29 -
9.30 -/// \addtogroup graphmaps
9.31 -/// @{
9.32 -
9.33 - /** The SymEdgeIt is wrapper class for the EdgeIt. It can be used to
9.34 - * iterate on the symmetric maps when all of the edge - reverse edge pair
9.35 - * has different parity.
9.36 - */
9.37 -
9.38 -
9.39 - template <typename Graph, typename Edge, typename EdgeIt>
9.40 - class SymEdgeIt : public EdgeIt {
9.41 - public:
9.42 -
9.43 - /** Default constructor.
9.44 - */
9.45 - SymEdgeIt()
9.46 - : EdgeIt() {}
9.47 -
9.48 - /** Graph initialized constructor.
9.49 - */
9.50 - SymEdgeIt(const Graph& graph)
9.51 - : EdgeIt(graph) {
9.52 - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
9.53 - EdgeIt::operator++();
9.54 - }
9.55 - }
9.56 -
9.57 - /** Creating invelid SymEdgeIt.
9.58 - */
9.59 - SymEdgeIt(Invalid invalid)
9.60 - : EdgeIt(invalid) {}
9.61 -
9.62 - /** SymEdgeIt from the given Edge.
9.63 - */
9.64 - SymEdgeIt(const Graph& graph, const Edge& edge)
9.65 - : EdgeIt(graph, edge) {
9.66 - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
9.67 - EdgeIt::operator++();
9.68 - }
9.69 - }
9.70 -
9.71 - /** Increase operator.
9.72 - */
9.73 - SymEdgeIt& operator++() {
9.74 - EdgeIt::operator++();
9.75 - while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
9.76 - EdgeIt::operator++();
9.77 - }
9.78 - return *this;
9.79 - }
9.80 - };
9.81 -
9.82 - /** The SymMap template class is graph map structure what
9.83 - * wraps an other map structure to use as symmetric map structure.
9.84 - *
9.85 - * The template parameter is the MapRegistry that the maps
9.86 - * will belong to and the ValueType.
9.87 - */
9.88 - template <template <typename, typename> class DynMap,
9.89 - typename MapRegistry, typename Value>
9.90 - class SymMap : public DynMap<MapRegistry, Value>{
9.91 -
9.92 - private:
9.93 -
9.94 - typedef DynMap<MapRegistry, Value> MapImpl;
9.95 -
9.96 - public:
9.97 -
9.98 - /// The graph type of the maps.
9.99 - typedef typename MapRegistry::Graph Graph;
9.100 -
9.101 - typedef typename MapImpl::KeyType KeyType;
9.102 -
9.103 - public:
9.104 -
9.105 -
9.106 - /** Graph and Registry initialized map constructor.
9.107 - */
9.108 - SymMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
9.109 -
9.110 - /** Constructor to use default value to initialize the map.
9.111 - */
9.112 - SymMap(const Graph& g, MapRegistry& r, const Value& v)
9.113 - : MapImpl(g, r, v) {}
9.114 -
9.115 - /** Constructor to copy a map of the same map type.
9.116 - */
9.117 - SymMap(const SymMap& copy)
9.118 - : MapImpl(static_cast<const MapImpl&>(copy)) {}
9.119 -
9.120 - /** Assign operator to copy a map of the same map type.
9.121 - */
9.122 - SymMap& operator=(const SymMap& copy) {
9.123 - MapImpl::operator=(static_cast<const MapImpl&>(copy));
9.124 - return *this;
9.125 - }
9.126 -
9.127 - /** Add a new key to the map. It called by the map registry.
9.128 - */
9.129 - void add(const KeyType& key) {
9.130 - int id = MapImpl::getGraph()->id(key);
9.131 - if (id & 1) return;
9.132 - MapImpl::add(key);
9.133 - }
9.134 -
9.135 - /** Erase a key from the map. It called by the map registry.
9.136 - */
9.137 - void erase(const KeyType& key) {
9.138 - int id = MapImpl::getGraph()->id(key);
9.139 - if (id & 1) return;
9.140 - MapImpl::add(key);
9.141 - }
9.142 - };
9.143 -
9.144 - /// @}
9.145 -}
9.146 -
9.147 -#endif
10.1 --- a/src/test/Makefile.am Fri Sep 24 11:55:54 2004 +0000
10.2 +++ b/src/test/Makefile.am Sun Sep 26 21:43:38 2004 +0000
10.3 @@ -9,6 +9,7 @@
10.4 dfs_test \
10.5 dijkstra_test \
10.6 graph_test \
10.7 + sym_graph_test \
10.8 graph_wrapper_test \
10.9 kruskal_test \
10.10 min_cost_flow_test \
10.11 @@ -28,6 +29,7 @@
10.12 dfs_test_SOURCES = dfs_test.cc
10.13 dijkstra_test_SOURCES = dijkstra_test.cc
10.14 graph_test_SOURCES = graph_test.cc
10.15 +sym_graph_test_SOURCES = sym_graph_test.cc
10.16 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
10.17 kruskal_test_SOURCES = kruskal_test.cc
10.18 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
11.1 --- a/src/test/graph_test.cc Fri Sep 24 11:55:54 2004 +0000
11.2 +++ b/src/test/graph_test.cc Sun Sep 26 21:43:38 2004 +0000
11.3 @@ -63,7 +63,6 @@
11.4 for(NodeIt n(G);n!=INVALID;++n) {
11.5 checkGraphInEdgeList(G,n,3);
11.6 checkGraphOutEdgeList(G,n,3);
11.7 - ++n;
11.8 }
11.9 }
11.10
11.11 @@ -82,8 +81,8 @@
11.12 template void hugo::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
11.13
11.14 //Compile SymSmartGraph
11.15 -template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
11.16 -template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
11.17 +//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
11.18 +//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
11.19
11.20 //Compile ListGraph
11.21 template void hugo::checkCompileGraph<ListGraph>(ListGraph &);
11.22 @@ -92,9 +91,9 @@
11.23
11.24
11.25 //Compile SymListGraph
11.26 -template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
11.27 -template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
11.28 -template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
11.29 +//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
11.30 +//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
11.31 +//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
11.32
11.33 //Compile FullGraph
11.34 template void hugo::checkCompileStaticGraph<FullGraph>(FullGraph &);
11.35 @@ -131,14 +130,14 @@
11.36 checkPetersen(G);
11.37 }
11.38 {
11.39 - SymSmartGraph G;
11.40 - addPetersen(G);
11.41 - checkPetersen(G);
11.42 + // SymSmartGraph G;
11.43 + // addPetersen(G);
11.44 + // checkPetersen(G);
11.45 }
11.46 {
11.47 - SymListGraph G;
11.48 - addPetersen(G);
11.49 - checkPetersen(G);
11.50 + // SymListGraph G;
11.51 + // addPetersen(G);
11.52 + // checkPetersen(G);
11.53 }
11.54
11.55 ///\file
12.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
12.2 +++ b/src/test/sym_graph_test.cc Sun Sep 26 21:43:38 2004 +0000
12.3 @@ -0,0 +1,96 @@
12.4 +/* -*- C++ -*-
12.5 + * src/test/sym_graph_test.cc - Part of HUGOlib, a generic C++ optimization library
12.6 + *
12.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
12.9 + *
12.10 + * Permission to use, modify and distribute this software is granted
12.11 + * provided that this copyright notice appears in all copies. For
12.12 + * precise terms see the accompanying LICENSE file.
12.13 + *
12.14 + * This software is provided "AS IS" with no warranty of any kind,
12.15 + * express or implied, and with no claim as to its suitability for any
12.16 + * purpose.
12.17 + *
12.18 + */
12.19 +
12.20 +#include<iostream>
12.21 +
12.22 +#include<hugo/skeletons/sym_graph.h>
12.23 +
12.24 +#include<hugo/list_graph.h>
12.25 +#include<hugo/smart_graph.h>
12.26 +#include<hugo/full_graph.h>
12.27 +
12.28 +#include"test_tools.h"
12.29 +#include"graph_test.h"
12.30 +#include"sym_graph_test.h"
12.31 +
12.32 +/**
12.33 +\file
12.34 +This test makes consistency checks of list graph structures.
12.35 +
12.36 +G.addNode(), G.addEdge(), G.tail(), G.head()
12.37 +
12.38 +\todo Checks for empty graphs and isolated points.
12.39 +conversion.
12.40 +*/
12.41 +
12.42 +using namespace hugo;
12.43 +
12.44 +template<class Graph> void checkPetersen(Graph &G)
12.45 +{
12.46 + typedef typename Graph::NodeIt NodeIt;
12.47 +
12.48 +
12.49 + checkGraphNodeList(G,10);
12.50 + checkGraphEdgeList(G,30);
12.51 + checkGraphSymEdgeList(G,15);
12.52 +
12.53 + for(NodeIt n(G);n!=INVALID;++n) {
12.54 + checkGraphInEdgeList(G,n,3);
12.55 + checkGraphOutEdgeList(G,n,3);
12.56 + }
12.57 +}
12.58 +
12.59 +//Compile Graph
12.60 +template void hugo::checkCompileStaticSymGraph<skeleton::StaticSymGraph>
12.61 +(skeleton::StaticSymGraph &);
12.62 +
12.63 +template void hugo::checkCompileSymGraph<skeleton::ExtendableSymGraph>
12.64 +(skeleton::ExtendableSymGraph &);
12.65 +
12.66 +template void hugo::checkCompileErasableSymGraph<skeleton::ErasableSymGraph>
12.67 +(skeleton::ErasableSymGraph &);
12.68 +
12.69 +
12.70 +//Compile SymSmartGraph
12.71 +template void hugo::checkCompileSymGraph<SymSmartGraph>(SymSmartGraph &);
12.72 +template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
12.73 +
12.74 +//Compile SymListGraph
12.75 +template void hugo::checkCompileSymGraph<SymListGraph>(SymListGraph &);
12.76 +template void hugo::checkCompileErasableSymGraph<SymListGraph>(SymListGraph &);
12.77 +template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
12.78 +
12.79 +int main()
12.80 +{
12.81 + {
12.82 + SymSmartGraph G;
12.83 + addSymPetersen(G);
12.84 + checkPetersen(G);
12.85 + }
12.86 + {
12.87 + SymListGraph G;
12.88 + addSymPetersen(G);
12.89 + checkPetersen(G);
12.90 + }
12.91 +
12.92 + ///\file
12.93 + ///\todo map tests.
12.94 + ///\todo copy constr tests.
12.95 +
12.96 + std::cout << __FILE__ ": All tests passed.\n";
12.97 +
12.98 + return 0;
12.99 +}
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/src/test/sym_graph_test.h Sun Sep 26 21:43:38 2004 +0000
13.3 @@ -0,0 +1,179 @@
13.4 +/* -*- C++ -*-
13.5 + * src/test/sym_graph_test.h - Part of HUGOlib, a generic C++ optimization library
13.6 + *
13.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
13.9 + *
13.10 + * Permission to use, modify and distribute this software is granted
13.11 + * provided that this copyright notice appears in all copies. For
13.12 + * precise terms see the accompanying LICENSE file.
13.13 + *
13.14 + * This software is provided "AS IS" with no warranty of any kind,
13.15 + * express or implied, and with no claim as to its suitability for any
13.16 + * purpose.
13.17 + *
13.18 + */
13.19 +#ifndef HUGO_TEST_SYM_GRAPH_TEST_H
13.20 +#define HUGO_TEST_SYM_GRAPH_TEST_H
13.21 +
13.22 +
13.23 +#include "graph_test.h"
13.24 +#include "test_tools.h"
13.25 +
13.26 +//! \ingroup misc
13.27 +//! \file
13.28 +//! \brief Some utility to test symmetric graph classes.
13.29 +namespace hugo {
13.30 +
13.31 + template<class Graph> void checkCompileStaticSymGraph(Graph &G)
13.32 + {
13.33 + typedef typename Graph::Node Node;
13.34 + typedef typename Graph::NodeIt NodeIt;
13.35 + typedef typename Graph::SymEdge SymEdge;
13.36 + typedef typename Graph::SymEdgeIt SymEdgeIt;
13.37 + typedef typename Graph::Edge Edge;
13.38 + typedef typename Graph::EdgeIt EdgeIt;
13.39 + typedef typename Graph::InEdgeIt InEdgeIt;
13.40 + typedef typename Graph::OutEdgeIt OutEdgeIt;
13.41 +
13.42 + checkCompileStaticGraph(G);
13.43 +
13.44 + {
13.45 + SymEdge i; SymEdge j(i); SymEdge k(INVALID);
13.46 + i=j;
13.47 + bool b; b=true;
13.48 + b=(i==INVALID); b=(i!=INVALID);
13.49 + b=(i==j); b=(i!=j); b=(i<j);
13.50 + Edge e;
13.51 + e = G.forward(i);
13.52 + e = G.backward(i);
13.53 + }
13.54 + {
13.55 + SymEdgeIt i; SymEdgeIt j(i); SymEdgeIt k(INVALID); SymEdgeIt l(G);
13.56 + i=j;
13.57 + j=G.first(i);
13.58 + j=++i;
13.59 + bool b; b=true;
13.60 + b=(i==INVALID); b=(i!=INVALID);
13.61 + SymEdge n(i);
13.62 + n=i;
13.63 + b=(i==j); b=(i!=j); b=(i<j);
13.64 + //SymEdge ->SymEdgeIt conversion
13.65 + SymEdgeIt ni(G,n);
13.66 + }
13.67 + {
13.68 + Edge i, j;
13.69 + j = G.opposite(i);
13.70 + }
13.71 + {
13.72 + Node n;
13.73 + SymEdge se;
13.74 + se=INVALID;
13.75 + n=G.tail(se);
13.76 + n=G.head(se);
13.77 + }
13.78 + // id tests
13.79 + { SymEdge n; int i=G.id(n); i=i; }
13.80 + //SymEdgeMap tests
13.81 + {
13.82 + SymEdge k;
13.83 + typename Graph::template SymEdgeMap<int> m(G);
13.84 + typename Graph::template SymEdgeMap<int> const &cm = m; //Const map
13.85 + //Inicialize with default value
13.86 + typename Graph::template SymEdgeMap<int> mdef(G,12);
13.87 + typename Graph::template SymEdgeMap<int> mm(cm); //Copy
13.88 + typename Graph::template SymEdgeMap<double> dm(cm); //Copy from another type
13.89 + int v;
13.90 + v=m[k]; m[k]=v; m.set(k,v);
13.91 + v=cm[k];
13.92 +
13.93 + m=cm;
13.94 + dm=cm; //Copy from another type
13.95 + {
13.96 + //Check the typedef's
13.97 + typename Graph::template SymEdgeMap<int>::ValueType val;
13.98 + val = 1;
13.99 + typename Graph::template SymEdgeMap<int>::KeyType key;
13.100 + key = typename Graph::SymEdgeIt(G);
13.101 + }
13.102 + }
13.103 + { //bool SymEdgeMap
13.104 + SymEdge k;
13.105 + typename Graph::template SymEdgeMap<bool> m(G);
13.106 + typename Graph::template SymEdgeMap<bool> const &cm = m; //Const map
13.107 + //Inicialize with default value
13.108 + typename Graph::template SymEdgeMap<bool> mdef(G,12);
13.109 + typename Graph::template SymEdgeMap<bool> mm(cm); //Copy
13.110 + typename Graph::template SymEdgeMap<int> dm(cm); //Copy from another type
13.111 + bool v;
13.112 + v=m[k]; m[k]=v; m.set(k,v);
13.113 + v=cm[k];
13.114 +
13.115 + m=cm;
13.116 + dm=cm; //Copy from another type
13.117 + m=dm; //Copy to another type
13.118 + {
13.119 + //Check the typedef's
13.120 + typename Graph::template SymEdgeMap<bool>::ValueType val;
13.121 + val=true;
13.122 + typename Graph::template SymEdgeMap<bool>::KeyType key;
13.123 + key= typename Graph::SymEdgeIt(G);
13.124 + }
13.125 + }
13.126 + }
13.127 +
13.128 + template<class Graph> void checkCompileSymGraph(Graph &G)
13.129 + {
13.130 + checkCompileStaticSymGraph(G);
13.131 +
13.132 + typedef typename Graph::Node Node;
13.133 + typedef typename Graph::NodeIt NodeIt;
13.134 + typedef typename Graph::SymEdge SymEdge;
13.135 + typedef typename Graph::SymEdgeIt SymEdgeIt;
13.136 + typedef typename Graph::Edge Edge;
13.137 + typedef typename Graph::EdgeIt EdgeIt;
13.138 + typedef typename Graph::InEdgeIt InEdgeIt;
13.139 + typedef typename Graph::OutEdgeIt OutEdgeIt;
13.140 +
13.141 + Node n,m;
13.142 + n=G.addNode();
13.143 + m=G.addNode();
13.144 + SymEdge e;
13.145 + e = G.addEdge(n,m);
13.146 +
13.147 + // G.clear();
13.148 + }
13.149 +
13.150 + template<class Graph> void checkCompileSymGraphEraseSymEdge(Graph &G)
13.151 + {
13.152 + typename Graph::SymEdge n;
13.153 + G.erase(n);
13.154 + }
13.155 +
13.156 + template<class Graph> void checkCompileErasableSymGraph(Graph &G)
13.157 + {
13.158 + checkCompileSymGraph(G);
13.159 + checkCompileGraphEraseNode(G);
13.160 + checkCompileSymGraphEraseSymEdge(G);
13.161 + }
13.162 +
13.163 + template<class Graph> void checkGraphSymEdgeList(Graph &G, int nn)
13.164 + {
13.165 + typedef typename Graph::SymEdgeIt SymEdgeIt;
13.166 +
13.167 + SymEdgeIt e(G);
13.168 + for(int i=0;i<nn;i++) {
13.169 + check(e!=INVALID,"Wrong SymEdge list linking.");
13.170 + ++e;
13.171 + }
13.172 + check(e==INVALID,"Wrong SymEdge list linking.");
13.173 + }
13.174 +
13.175 + ///\file
13.176 + ///\todo Check head(), tail() as well;
13.177 +
13.178 +
13.179 +} //namespace hugo
13.180 +
13.181 +
13.182 +#endif
14.1 --- a/src/test/test_tools.h Fri Sep 24 11:55:54 2004 +0000
14.2 +++ b/src/test/test_tools.h Sun Sep 26 21:43:38 2004 +0000
14.3 @@ -67,7 +67,7 @@
14.4 ///Adds a Petersen graph to \c G.
14.5
14.6 ///Adds a Petersen graph to \c G.
14.7 -///\return The nodes end edges og the generated graph.
14.8 +///\return The nodes and edges of the generated graph.
14.9
14.10 template<typename Graph>
14.11 PetStruct<Graph> addPetersen(Graph &G,int num=5)
14.12 @@ -87,6 +87,45 @@
14.13 return n;
14.14 }
14.15
14.16 +///Structure returned by \ref addSymPetersen().
14.17
14.18 +///Structure returned by \ref addSymPetersen().
14.19 +///
14.20 +template<class Graph> struct SymPetStruct
14.21 +{
14.22 + ///Vector containing the outer nodes.
14.23 + std::vector<typename Graph::Node> outer;
14.24 + ///Vector containing the inner nodes.
14.25 + std::vector<typename Graph::Node> inner;
14.26 + ///Vector containing the edges of the inner circle.
14.27 + std::vector<typename Graph::SymEdge> incir;
14.28 + ///Vector containing the edges of the outer circle.
14.29 + std::vector<typename Graph::SymEdge> outcir;
14.30 + ///Vector containing the chord edges.
14.31 + std::vector<typename Graph::SymEdge> chords;
14.32 +};
14.33 +
14.34 +///Adds a Petersen graph to the symmetric \c G.
14.35 +
14.36 +///Adds a Petersen graph to the symmetric \c G.
14.37 +///\return The nodes and edges of the generated graph.
14.38 +
14.39 +template<typename Graph>
14.40 +SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5)
14.41 +{
14.42 + SymPetStruct<Graph> n;
14.43 +
14.44 + for(int i=0;i<num;i++) {
14.45 + n.outer.push_back(G.addNode());
14.46 + n.inner.push_back(G.addNode());
14.47 + }
14.48 +
14.49 + for(int i=0;i<num;i++) {
14.50 + n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
14.51 + n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
14.52 + n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
14.53 + }
14.54 + return n;
14.55 +}
14.56
14.57 #endif