1.1 --- a/src/lemon/Makefile.am Mon Oct 04 16:03:25 2004 +0000
1.2 +++ b/src/lemon/Makefile.am Mon Oct 04 17:13:21 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/lemon/default_map.h Mon Oct 04 16:03:25 2004 +0000
2.2 +++ b/src/lemon/default_map.h Mon Oct 04 17:13:21 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/lemon/list_graph.h Mon Oct 04 16:03:25 2004 +0000
3.2 +++ b/src/lemon/list_graph.h Mon Oct 04 17:13:21 2004 +0000
3.3 @@ -29,8 +29,6 @@
3.4 #include <lemon/map_registry.h>
3.5 #include <lemon/array_map.h>
3.6
3.7 -#include <lemon/sym_map.h>
3.8 -
3.9 #include <lemon/map_defines.h>
3.10
3.11
3.12 @@ -104,6 +102,7 @@
3.13 first_free_node(_g.first_free_node), edges(_g.edges),
3.14 first_free_edge(_g.first_free_edge) {}
3.15
3.16 + /// \bug In the vector can be hole if a node is erased from the graph.
3.17 ///Number of nodes.
3.18 int nodeNum() const { return nodes.size(); }
3.19 ///Number of edges.
3.20 @@ -438,7 +437,7 @@
3.21 ///
3.22 ///\todo this date structure need some reconsiderations. Maybe it
3.23 ///should be implemented independently from ListGraph.
3.24 -
3.25 + /*
3.26 class SymListGraph : public ListGraph
3.27 {
3.28 public:
3.29 @@ -483,9 +482,403 @@
3.30 ListGraph::erase(f);
3.31 ListGraph::erase(e);
3.32 }
3.33 + };*/
3.34 +
3.35 + class SymListGraph : public ListGraph {
3.36 + typedef ListGraph Parent;
3.37 + public:
3.38 +
3.39 + typedef SymListGraph Graph;
3.40 +
3.41 + typedef ListGraph::Node Node;
3.42 + typedef ListGraph::NodeIt NodeIt;
3.43 +
3.44 + class SymEdge;
3.45 + class SymEdgeIt;
3.46 +
3.47 + class Edge;
3.48 + class EdgeIt;
3.49 + class OutEdgeIt;
3.50 + class InEdgeIt;
3.51 +
3.52 + template <typename Value>
3.53 + class NodeMap : public Parent::NodeMap<Value> {
3.54 + public:
3.55 + NodeMap(const SymListGraph& g)
3.56 + : SymListGraph::Parent::NodeMap<Value>(g) {}
3.57 + NodeMap(const SymListGraph& g, Value v)
3.58 + : SymListGraph::Parent::NodeMap<Value>(g, v) {}
3.59 + template<typename TT>
3.60 + NodeMap(const NodeMap<TT>& copy)
3.61 + : SymListGraph::Parent::NodeMap<Value>(copy) { }
3.62 + };
3.63 +
3.64 + template <typename Value>
3.65 + class SymEdgeMap : public Parent::EdgeMap<Value> {
3.66 + public:
3.67 + typedef SymEdge KeyType;
3.68 +
3.69 + SymEdgeMap(const SymListGraph& g)
3.70 + : SymListGraph::Parent::EdgeMap<Value>(g) {}
3.71 + SymEdgeMap(const SymListGraph& g, Value v)
3.72 + : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
3.73 + template<typename TT>
3.74 + SymEdgeMap(const SymEdgeMap<TT>& copy)
3.75 + : SymListGraph::Parent::EdgeMap<Value>(copy) { }
3.76 +
3.77 + };
3.78 +
3.79 + // Create edge map registry.
3.80 + CREATE_EDGE_MAP_REGISTRY;
3.81 + // Create edge maps.
3.82 + CREATE_EDGE_MAP(ArrayMap);
3.83 +
3.84 + class Edge {
3.85 + friend class SymListGraph;
3.86 + friend class SymListGraph::EdgeIt;
3.87 + friend class SymListGraph::OutEdgeIt;
3.88 + friend class SymListGraph::InEdgeIt;
3.89 +
3.90 + protected:
3.91 + int id;
3.92 +
3.93 + Edge(int pid) { id = pid; }
3.94 +
3.95 + public:
3.96 + /// An Edge with id \c n.
3.97 +
3.98 + Edge() { }
3.99 + Edge (Invalid) { id = -1; }
3.100 +
3.101 + operator SymEdge(){ return SymEdge(id >> 1);}
3.102 +
3.103 + bool operator==(const Edge i) const {return id == i.id;}
3.104 + bool operator!=(const Edge i) const {return id != i.id;}
3.105 + bool operator<(const Edge i) const {return id < i.id;}
3.106 + // ///Validity check
3.107 + // operator bool() { return n!=-1; }
3.108 + };
3.109 +
3.110 + class SymEdge : public ListGraph::Edge {
3.111 + friend class SymListGraph;
3.112 + friend class SymListGraph::Edge;
3.113 + typedef ListGraph::Edge Parent;
3.114 +
3.115 + protected:
3.116 + SymEdge(int pid) : Parent(pid) {}
3.117 + public:
3.118 +
3.119 + SymEdge() { }
3.120 + SymEdge(const ListGraph::Edge& i) : Parent(i) {}
3.121 + SymEdge (Invalid) : Parent(INVALID) {}
3.122 +
3.123 + };
3.124 +
3.125 + class OutEdgeIt {
3.126 + Parent::OutEdgeIt out;
3.127 + Parent::InEdgeIt in;
3.128 + public:
3.129 + OutEdgeIt() {}
3.130 + OutEdgeIt(const SymListGraph& g, Edge e) {
3.131 + if ((e.id & 1) == 0) {
3.132 + out = Parent::OutEdgeIt(g, SymEdge(e));
3.133 + in = Parent::InEdgeIt(g, g.tail(e));
3.134 + } else {
3.135 + out = Parent::OutEdgeIt(INVALID);
3.136 + in = Parent::InEdgeIt(g, SymEdge(e));
3.137 + }
3.138 + }
3.139 + OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
3.140 +
3.141 + OutEdgeIt(const SymListGraph& g, const Node v)
3.142 + : out(g, v), in(g, v) {}
3.143 + OutEdgeIt &operator++() {
3.144 + if (out != INVALID) {
3.145 + ++out;
3.146 + } else {
3.147 + ++in;
3.148 + }
3.149 + return *this;
3.150 + }
3.151 +
3.152 + operator Edge() const {
3.153 + if (out == INVALID && in == INVALID) return INVALID;
3.154 + return out != INVALID ? forward(out) : backward(in);
3.155 + }
3.156 +
3.157 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.158 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.159 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.160 + };
3.161 +
3.162 + class InEdgeIt {
3.163 + Parent::OutEdgeIt out;
3.164 + Parent::InEdgeIt in;
3.165 + public:
3.166 + InEdgeIt() {}
3.167 + InEdgeIt(const SymListGraph& g, Edge e) {
3.168 + if ((e.id & 1) == 0) {
3.169 + out = Parent::OutEdgeIt(g, SymEdge(e));
3.170 + in = Parent::InEdgeIt(g, g.tail(e));
3.171 + } else {
3.172 + out = Parent::OutEdgeIt(INVALID);
3.173 + in = Parent::InEdgeIt(g, SymEdge(e));
3.174 + }
3.175 + }
3.176 + InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
3.177 +
3.178 + InEdgeIt(const SymListGraph& g, const Node v)
3.179 + : out(g, v), in(g, v) {}
3.180 +
3.181 + InEdgeIt &operator++() {
3.182 + if (out != INVALID) {
3.183 + ++out;
3.184 + } else {
3.185 + ++in;
3.186 + }
3.187 + return *this;
3.188 + }
3.189 +
3.190 + operator Edge() const {
3.191 + if (out == INVALID && in == INVALID) return INVALID;
3.192 + return out != INVALID ? backward(out) : forward(in);
3.193 + }
3.194 +
3.195 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.196 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.197 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.198 + };
3.199 +
3.200 + class SymEdgeIt : public Parent::EdgeIt {
3.201 +
3.202 + public:
3.203 + SymEdgeIt() {}
3.204 +
3.205 + SymEdgeIt(const SymListGraph& g)
3.206 + : SymListGraph::Parent::EdgeIt(g) {}
3.207 +
3.208 + SymEdgeIt(const SymListGraph& g, SymEdge e)
3.209 + : SymListGraph::Parent::EdgeIt(g, e) {}
3.210 +
3.211 + SymEdgeIt(Invalid i)
3.212 + : SymListGraph::Parent::EdgeIt(INVALID) {}
3.213 +
3.214 + SymEdgeIt& operator++() {
3.215 + SymListGraph::Parent::EdgeIt::operator++();
3.216 + return *this;
3.217 + }
3.218 +
3.219 + operator SymEdge() const {
3.220 + return SymEdge
3.221 + (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
3.222 + }
3.223 + bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
3.224 + bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
3.225 + bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
3.226 + };
3.227 +
3.228 + class EdgeIt {
3.229 + SymEdgeIt it;
3.230 + bool fw;
3.231 + public:
3.232 + EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
3.233 + EdgeIt (Invalid i) : it(i) { }
3.234 + EdgeIt(const SymListGraph& g, Edge e)
3.235 + : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
3.236 + EdgeIt() { }
3.237 + EdgeIt& operator++() {
3.238 + fw = !fw;
3.239 + if (fw) ++it;
3.240 + return *this;
3.241 + }
3.242 + operator Edge() const {
3.243 + if (it == INVALID) return INVALID;
3.244 + return fw ? forward(it) : backward(it);
3.245 + }
3.246 + bool operator==(const Edge i) const {return Edge(*this) == i;}
3.247 + bool operator!=(const Edge i) const {return Edge(*this) != i;}
3.248 + bool operator<(const Edge i) const {return Edge(*this) < i;}
3.249 +
3.250 + };
3.251 +
3.252 + ///Number of nodes.
3.253 + int nodeNum() const { return Parent::nodeNum(); }
3.254 + ///Number of edges.
3.255 + int edgeNum() const { return 2*Parent::edgeNum(); }
3.256 + ///Number of symmetric edges.
3.257 + int symEdgeNum() const { return Parent::edgeNum(); }
3.258 +
3.259 + ///Set the expected maximum number of edges.
3.260 +
3.261 + ///With this function, it is possible to set the expected number of edges.
3.262 + ///The use of this fasten the building of the graph and makes
3.263 + ///it possible to avoid the superfluous memory allocation.
3.264 + void reserveSymEdge(int n) { Parent::reserveEdge(n); };
3.265 +
3.266 + /// Maximum node ID.
3.267 +
3.268 + /// Maximum node ID.
3.269 + ///\sa id(Node)
3.270 + int maxNodeId() const { return Parent::maxNodeId(); }
3.271 + /// Maximum edge ID.
3.272 +
3.273 + /// Maximum edge ID.
3.274 + ///\sa id(Edge)
3.275 + int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
3.276 + /// Maximum symmetric edge ID.
3.277 +
3.278 + /// Maximum symmetric edge ID.
3.279 + ///\sa id(SymEdge)
3.280 + int maxSymEdgeId() const { return Parent::maxEdgeId(); }
3.281 +
3.282 +
3.283 + Node tail(Edge e) const {
3.284 + return (e.id & 1) == 0 ?
3.285 + Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
3.286 + }
3.287 +
3.288 + Node head(Edge e) const {
3.289 + return (e.id & 1) == 0 ?
3.290 + Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
3.291 + }
3.292 +
3.293 + Node tail(SymEdge e) const {
3.294 + return Parent::tail(e);
3.295 + }
3.296 +
3.297 + Node head(SymEdge e) const {
3.298 + return Parent::head(e);
3.299 + }
3.300 +
3.301 + NodeIt& first(NodeIt& v) const {
3.302 + v=NodeIt(*this); return v; }
3.303 + EdgeIt& first(EdgeIt& e) const {
3.304 + e=EdgeIt(*this); return e; }
3.305 + SymEdgeIt& first(SymEdgeIt& e) const {
3.306 + e=SymEdgeIt(*this); return e; }
3.307 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.308 + e=OutEdgeIt(*this,v); return e; }
3.309 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.310 + e=InEdgeIt(*this,v); return e; }
3.311 +
3.312 + /// Node ID.
3.313 +
3.314 + /// The ID of a valid Node is a nonnegative integer not greater than
3.315 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
3.316 + /// and the greatest node ID can be actually less then \ref maxNodeId().
3.317 + ///
3.318 + /// The ID of the \ref INVALID node is -1.
3.319 + ///\return The ID of the node \c v.
3.320 + static int id(Node v) { return Parent::id(v); }
3.321 + /// Edge ID.
3.322 +
3.323 + /// The ID of a valid Edge is a nonnegative integer not greater than
3.324 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
3.325 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
3.326 + ///
3.327 + /// The ID of the \ref INVALID edge is -1.
3.328 + ///\return The ID of the edge \c e.
3.329 + static int id(Edge e) { return e.id; }
3.330 +
3.331 + /// The ID of a valid SymEdge is a nonnegative integer not greater than
3.332 + /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
3.333 + /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
3.334 + ///
3.335 + /// The ID of the \ref INVALID symmetric edge is -1.
3.336 + ///\return The ID of the edge \c e.
3.337 + static int id(SymEdge e) { return Parent::id(e); }
3.338 +
3.339 + /// Adds a new node to the graph.
3.340 +
3.341 + /// \warning It adds the new node to the front of the list.
3.342 + /// (i.e. the lastly added node becomes the first.)
3.343 + Node addNode() {
3.344 + return Parent::addNode();
3.345 + }
3.346 +
3.347 + SymEdge addEdge(Node u, Node v) {
3.348 + SymEdge se = Parent::addEdge(u, v);
3.349 + edge_maps.add(forward(se));
3.350 + edge_maps.add(backward(se));
3.351 + return se;
3.352 + }
3.353 +
3.354 + /// Finds an edge between two nodes.
3.355 +
3.356 + /// Finds an edge from node \c u to node \c v.
3.357 + ///
3.358 + /// If \c prev is \ref INVALID (this is the default value), then
3.359 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.360 + /// the next edge from \c u to \c v after \c prev.
3.361 + /// \return The found edge or INVALID if there is no such an edge.
3.362 + Edge findEdge(Node u, Node v, Edge prev = INVALID)
3.363 + {
3.364 + if (prev == INVALID || id(prev) & 1 == 0) {
3.365 + SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
3.366 + if (se != INVALID) return forward(se);
3.367 + } else {
3.368 + SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
3.369 + if (se != INVALID) return backward(se);
3.370 + }
3.371 + return INVALID;
3.372 + }
3.373 +
3.374 +// /// Finds an symmetric edge between two nodes.
3.375 +
3.376 +// /// Finds an symmetric edge from node \c u to node \c v.
3.377 +// ///
3.378 +// /// If \c prev is \ref INVALID (this is the default value), then
3.379 +// /// It finds the first edge from \c u to \c v. Otherwise it looks for
3.380 +// /// the next edge from \c u to \c v after \c prev.
3.381 +// /// \return The found edge or INVALID if there is no such an edge.
3.382 +
3.383 +// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
3.384 +// {
3.385 +// if (prev == INVALID || id(prev) & 1 == 0) {
3.386 +// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
3.387 +// if (se != INVALID) return se;
3.388 +// } else {
3.389 +// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
3.390 +// if (se != INVALID) return se;
3.391 +// }
3.392 +// return INVALID;
3.393 +// }
3.394 +
3.395 + public:
3.396 +
3.397 + void erase(Node n) {
3.398 + for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
3.399 + edge_maps.erase(it);
3.400 + edge_maps.erase(opposite(it));
3.401 + }
3.402 + Parent::erase(n);
3.403 + }
3.404 +
3.405 + void erase(SymEdge e) {
3.406 + edge_maps.erase(forward(e));
3.407 + edge_maps.erase(backward(e));
3.408 + Parent::erase(e);
3.409 + };
3.410 +
3.411 + void clear() {
3.412 + edge_maps.clear();
3.413 + Parent::clear();
3.414 + }
3.415 +
3.416 + static Edge opposite(Edge e) {
3.417 + return Edge(id(e) ^ 1);
3.418 + }
3.419 +
3.420 + static Edge forward(SymEdge e) {
3.421 + return Edge(id(e) << 1);
3.422 + }
3.423 +
3.424 + static Edge backward(SymEdge e) {
3.425 + return Edge((id(e) << 1) | 1);
3.426 + }
3.427 +
3.428 };
3.429
3.430 -
3.431 ///A graph class containing only nodes.
3.432
3.433 ///This class implements a graph structure without edges.
4.1 --- a/src/lemon/map_bits.h Mon Oct 04 16:03:25 2004 +0000
4.2 +++ b/src/lemon/map_bits.h Mon Oct 04 17:13:21 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/lemon/map_defines.h Mon Oct 04 16:03:25 2004 +0000
5.2 +++ b/src/lemon/map_defines.h Mon Oct 04 17:13:21 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/lemon/map_registry.h Mon Oct 04 16:03:25 2004 +0000
6.2 +++ b/src/lemon/map_registry.h Mon Oct 04 17:13:21 2004 +0000
6.3 @@ -27,24 +27,35 @@
6.4
6.5 namespace lemon {
6.6
6.7 -/// \addtogroup graphmapfactory
6.8 -/// @{
6.9 + /// \addtogroup graphmapfactory
6.10 + /// @{
6.11
6.12 -/**
6.13 - * Registry class to register edge or node maps into the graph. The
6.14 - * registry helps you to implement an observer pattern. If you add
6.15 - * or erase an edge or node you must notify all the maps about the
6.16 - * event.
6.17 -*/
6.18 + /// Map registry for graph maps.
6.19 +
6.20 + /**
6.21 + * Registry class to register edge or node maps into the graph. The
6.22 + * registry helps you to implement an observer pattern. If you add
6.23 + * or erase an edge or node you must notify all the maps about the
6.24 + * event.
6.25 + *
6.26 + * \param G The graph type to register maps.
6.27 + * \param K The key type of the maps registered into the registry.
6.28 + * \param KIt The key iterator type iterates on the keys.
6.29 + *
6.30 + * \author Balazs Dezso
6.31 + */
6.32 +
6.33 template <typename G, typename K, typename KIt>
6.34 class MapRegistry {
6.35 public:
6.36 typedef G Graph;
6.37 typedef K KeyType;
6.38 typedef KIt KeyIt;
6.39 +
6.40 + /// MapBase is the base class of the dynamic maps.
6.41
6.42 /**
6.43 - * MapBase is the base class of the registered maps.
6.44 + * MapBase is the base class of the dynamic maps.
6.45 * It defines the core modification operations on the maps and
6.46 * implements some helper functions.
6.47 */
6.48 @@ -58,22 +69,30 @@
6.49
6.50 friend class MapRegistry<G, K, KIt>;
6.51
6.52 + /// Default constructor.
6.53 +
6.54 /**
6.55 * Default constructor for MapBase.
6.56 */
6.57
6.58 MapBase() : graph(0), registry(0) {}
6.59 +
6.60 + /// Constructor to register map into a graph registry.
6.61
6.62 /**
6.63 - * Simple constructor to register into a graph registry.
6.64 + * Simple constructor to register dynamic map into a graph registry.
6.65 */
6.66
6.67 MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
6.68 r.attach(*this);
6.69 }
6.70
6.71 + /// Copy constructor.
6.72 +
6.73 /**
6.74 * Copy constructor to register into the registry.
6.75 + * If the copiable map is registered into a registry
6.76 + * the construated map will be registered to the same registry.
6.77 */
6.78
6.79 MapBase(const MapBase& copy) : graph(copy.graph), registry(0) {
6.80 @@ -81,9 +100,13 @@
6.81 copy.registry->attach(*this);
6.82 }
6.83 }
6.84 +
6.85 + /// Assign operator.
6.86
6.87 /**
6.88 - * Assign operator.
6.89 + * Assign operator. This member detach first the map
6.90 + * from the current registry and then it attach to the
6.91 + * copiable map's registry if it exists.
6.92 */
6.93 const MapBase& operator=(const MapBase& copy) {
6.94 if (registry) {
6.95 @@ -96,9 +119,11 @@
6.96 return *this;
6.97 }
6.98
6.99 + /// Destructor
6.100
6.101 /**
6.102 - * Destructor.
6.103 + * This member detach the map from the its registry if the
6.104 + * registry exists.
6.105 */
6.106
6.107 virtual ~MapBase() {
6.108 @@ -107,6 +132,8 @@
6.109 }
6.110 }
6.111
6.112 + /// The graph of the map.
6.113 +
6.114 /*
6.115 * Returns the graph that the map belongs to.
6.116 */
6.117 @@ -121,9 +148,14 @@
6.118 int registry_index;
6.119
6.120 protected:
6.121 +
6.122 + /// Helper function to implement constructors in the subclasses.
6.123
6.124 /**
6.125 - Helper function to implement constructors in the subclasses.
6.126 + * Helper function to implement constructors in the subclasses.
6.127 + * It adds all of the nodes or edges to the map via the
6.128 + * \ref MapRegistry::MapBase::add add
6.129 + * member function.
6.130 */
6.131
6.132 virtual void init() {
6.133 @@ -132,8 +164,14 @@
6.134 }
6.135 }
6.136
6.137 +
6.138 + /// Helper function to implement destructors in the subclasses.
6.139 +
6.140 /**
6.141 - Helper function to implement the destructor in the subclasses.
6.142 + * Helper function to implement destructors in the subclasses.
6.143 + * It erases all of the nodes or edges of the map via the
6.144 + * \ref MapRegistry::MapBase::erase erase
6.145 + * member function. It can be used by the clear function also.
6.146 */
6.147
6.148 virtual void destroy() {
6.149 @@ -141,16 +179,22 @@
6.150 erase(it);
6.151 }
6.152 }
6.153 +
6.154 + /// The member function to add new node or edge to the map.
6.155
6.156 /**
6.157 The add member function should be overloaded in the subclasses.
6.158 - \e Add extends the map with the new node.
6.159 + \e Add extends the map with the new node or edge.
6.160 */
6.161
6.162 virtual void add(const KeyType&) = 0;
6.163 +
6.164 +
6.165 + /// The member function to erase a node or edge from the map.
6.166 +
6.167 /**
6.168 The erase member function should be overloaded in the subclasses.
6.169 - \e Erase removes the node from the map.
6.170 + \e Erase removes the node or edge from the map.
6.171 */
6.172
6.173 virtual void erase(const KeyType&) = 0;
6.174 @@ -161,9 +205,13 @@
6.175 */
6.176
6.177 virtual void clear() = 0;
6.178 +
6.179 + /// Exception class to throw at unsupported operation.
6.180
6.181 /**
6.182 - Exception class to throw at unsupported operation.
6.183 + * Exception class to throw at unsupported operation.
6.184 + * If the map does not support erasing or adding new
6.185 + * node or key it must be throwed.
6.186 */
6.187
6.188 class NotSupportedOperationException {};
6.189 @@ -172,50 +220,58 @@
6.190
6.191 protected:
6.192
6.193 - /**
6.194 - * The container type of the maps.
6.195 - */
6.196 +
6.197 typedef std::vector<MapBase*> Container;
6.198
6.199 - /**
6.200 - * The container of the registered maps.
6.201 - */
6.202 Container container;
6.203
6.204
6.205 public:
6.206 +
6.207 + /// Default constructor.
6.208
6.209 /**
6.210 - * Default Constructor of the MapRegistry. It creates an empty registry.
6.211 + * Default constructor of the \e MapRegistry.
6.212 + * It creates an empty registry.
6.213 */
6.214 MapRegistry() {}
6.215 +
6.216 + /// Copy Constructor of the MapRegistry.
6.217
6.218 /**
6.219 - * Copy Constructor of the MapRegistry. The new registry does not steal
6.220 - * the maps from the right value. The new registry will be an empty.
6.221 + * Copy constructor of the \e MapRegistry.
6.222 + * The new registry does not steal
6.223 + * the maps from the copiable registry.
6.224 + * The new registry will be empty.
6.225 */
6.226 MapRegistry(const MapRegistry&) {}
6.227 +
6.228 + /// Assign operator.
6.229
6.230 /**
6.231 - * Assign operator. The left value does not steal the maps
6.232 - * from the right value. The left value will be an empty registry.
6.233 + * Assign operator. This registry does not steal the maps
6.234 + * from the copiable registry. This registry will be an empty registry.
6.235 + * This operator will be called when a graph is assigned.
6.236 */
6.237 MapRegistry& operator=(const MapRegistry&) {
6.238 typename Container::iterator it;
6.239 for (it = container.begin(); it != container.end(); ++it) {
6.240 - (*it)->destroy();
6.241 + (*it)->clear();
6.242 (*it)->graph = 0;
6.243 (*it)->registry = 0;
6.244 }
6.245 }
6.246 +
6.247 + /// Destructor.
6.248
6.249 /**
6.250 - * Destructor of the MapRegistry.
6.251 + * Destructor of the MapRegistry. It makes empty the attached map
6.252 + * first then detachs them.
6.253 */
6.254 ~MapRegistry() {
6.255 typename Container::iterator it;
6.256 for (it = container.begin(); it != container.end(); ++it) {
6.257 - (*it)->destroy();
6.258 + (*it)->clear();
6.259 (*it)->registry = 0;
6.260 (*it)->graph = 0;
6.261 }
6.262 @@ -223,9 +279,11 @@
6.263
6.264
6.265 public:
6.266 +
6.267 + /// Attachs a map to the \e MapRegistry.
6.268
6.269 /**
6.270 - * Attach a map into thr registry. If the map has been attached
6.271 + * Attachs a map into thr registry. If the map has been attached
6.272 * into an other registry it is detached from that automaticly.
6.273 */
6.274 void attach(MapBase& map) {
6.275 @@ -236,9 +294,11 @@
6.276 map.registry = this;
6.277 map.registry_index = container.size()-1;
6.278 }
6.279 +
6.280 + /// Detachs a map from the \e MapRegistry.
6.281
6.282 /**
6.283 - * Detach the map from the registry.
6.284 + * Detachs a map from the \e MapRegistry.
6.285 */
6.286 void detach(MapBase& map) {
6.287 container.back()->registry_index = map.registry_index;
6.288 @@ -248,29 +308,41 @@
6.289 map.graph = 0;
6.290 }
6.291
6.292 + /// Notify all the registered maps about a Key added.
6.293
6.294 /**
6.295 * Notify all the registered maps about a Key added.
6.296 + * This member should be called whenever a node or edge
6.297 + * is added to the graph.
6.298 */
6.299 - void add(KeyType& key) {
6.300 + void add(const KeyType& key) {
6.301 typename Container::iterator it;
6.302 for (it = container.begin(); it != container.end(); ++it) {
6.303 (*it)->add(key);
6.304 }
6.305 }
6.306 +
6.307 + /// Notify all the registered maps about a Key erased.
6.308
6.309 /**
6.310 * Notify all the registered maps about a Key erased.
6.311 + * This member should be called whenever a node or edge
6.312 + * is erased from the graph.
6.313 */
6.314 - void erase(KeyType& key) {
6.315 + void erase(const KeyType& key) {
6.316 typename Container::iterator it;
6.317 for (it = container.begin(); it != container.end(); ++it) {
6.318 (*it)->erase(key);
6.319 }
6.320 }
6.321
6.322 +
6.323 + /// Notify all the registered maps about all the Keys are erased.
6.324 +
6.325 /**
6.326 * Notify all the registered maps about the map should be cleared.
6.327 + * This member should be called whenever all of the nodes or edges
6.328 + * are erased from the graph.
6.329 */
6.330 void clear() {
6.331 typename Container::iterator it;
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/lemon/skeletons/sym_graph.h Mon Oct 04 17:13:21 2004 +0000
7.3 @@ -0,0 +1,653 @@
7.4 +/* -*- C++ -*-
7.5 + * src/lemon/skeletons/graph.h - Part of LEMON, 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 LEMON_SKELETON_SYM_GRAPH_H
7.21 +#define LEMON_SKELETON_SYM_GRAPH_H
7.22 +
7.23 +///\ingroup skeletons
7.24 +///\file
7.25 +///\brief Declaration of SymGraph.
7.26 +
7.27 +#include <lemon/invalid.h>
7.28 +#include <lemon/skeletons/graph.h>
7.29 +#include <lemon/skeletons/maps.h>
7.30 +
7.31 +namespace lemon {
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 lemon::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 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 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 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 + ///\e
7.496 +
7.497 + ///\todo Should it be in the concept?
7.498 + ///
7.499 + int nodeNum() const { return 0; }
7.500 + ///\e
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 + ///\e
7.531 + NodeMap(const StaticSymGraph&) { }
7.532 + ///\e
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 + ///\e
7.555 + EdgeMap(const StaticSymGraph&) { }
7.556 + ///\e
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 + ///\e
7.579 + SymEdgeMap(const StaticSymGraph&) { }
7.580 + ///\e
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 lemon
7.653 +
7.654 +
7.655 +
7.656 +#endif // LEMON_SKELETON_GRAPH_H
8.1 --- a/src/lemon/smart_graph.h Mon Oct 04 16:03:25 2004 +0000
8.2 +++ b/src/lemon/smart_graph.h Mon Oct 04 17:13:21 2004 +0000
8.3 @@ -26,8 +26,8 @@
8.4
8.5 #include <lemon/invalid.h>
8.6
8.7 +
8.8 #include <lemon/array_map.h>
8.9 -#include <lemon/sym_map.h>
8.10
8.11 #include <lemon/map_registry.h>
8.12
8.13 @@ -298,6 +298,381 @@
8.14
8.15 };
8.16
8.17 +
8.18 +
8.19 + class SymSmartGraph : public SmartGraph {
8.20 + typedef SmartGraph Parent;
8.21 + public:
8.22 +
8.23 + typedef SymSmartGraph Graph;
8.24 +
8.25 + typedef SmartGraph::Node Node;
8.26 + typedef SmartGraph::NodeIt NodeIt;
8.27 +
8.28 + class SymEdge;
8.29 + class SymEdgeIt;
8.30 +
8.31 + class Edge;
8.32 + class EdgeIt;
8.33 + class OutEdgeIt;
8.34 + class InEdgeIt;
8.35 +
8.36 + template <typename Value>
8.37 + class NodeMap : public Parent::NodeMap<Value> {
8.38 + public:
8.39 + NodeMap(const SymSmartGraph& g)
8.40 + : SymSmartGraph::Parent::NodeMap<Value>(g) {}
8.41 + NodeMap(const SymSmartGraph& g, Value v)
8.42 + : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
8.43 + template<typename TT>
8.44 + NodeMap(const NodeMap<TT>& copy)
8.45 + : SymSmartGraph::Parent::NodeMap<Value>(copy) { }
8.46 + };
8.47 +
8.48 + template <typename Value>
8.49 + class SymEdgeMap : public Parent::EdgeMap<Value> {
8.50 + public:
8.51 + typedef SymEdge KeyType;
8.52 +
8.53 + SymEdgeMap(const SymSmartGraph& g)
8.54 + : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
8.55 + SymEdgeMap(const SymSmartGraph& g, Value v)
8.56 + : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
8.57 + template<typename TT>
8.58 + SymEdgeMap(const SymEdgeMap<TT>& copy)
8.59 + : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
8.60 +
8.61 + };
8.62 +
8.63 + // Create edge map registry.
8.64 + CREATE_EDGE_MAP_REGISTRY;
8.65 + // Create edge maps.
8.66 + CREATE_EDGE_MAP(ArrayMap);
8.67 +
8.68 + class Edge {
8.69 + friend class SymSmartGraph;
8.70 + friend class SymSmartGraph::EdgeIt;
8.71 + friend class SymSmartGraph::OutEdgeIt;
8.72 + friend class SymSmartGraph::InEdgeIt;
8.73 +
8.74 + protected:
8.75 + int id;
8.76 +
8.77 + Edge(int pid) { id = pid; }
8.78 +
8.79 + public:
8.80 + /// An Edge with id \c n.
8.81 +
8.82 + Edge() { }
8.83 + Edge (Invalid) { id = -1; }
8.84 +
8.85 + operator SymEdge(){ return SymEdge(id >> 1);}
8.86 +
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 + bool operator<(const Edge i) const {return id < i.id;}
8.90 + // ///Validity check
8.91 + // operator bool() { return n!=-1; }
8.92 + };
8.93 +
8.94 + class SymEdge : public SmartGraph::Edge {
8.95 + friend class SymSmartGraph;
8.96 + friend class SymSmartGraph::Edge;
8.97 + typedef SmartGraph::Edge Parent;
8.98 +
8.99 + protected:
8.100 + SymEdge(int pid) : Parent(pid) {}
8.101 + public:
8.102 +
8.103 + SymEdge() { }
8.104 + SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
8.105 + SymEdge (Invalid) : Parent(INVALID) {}
8.106 +
8.107 + };
8.108 +
8.109 + class OutEdgeIt {
8.110 + Parent::OutEdgeIt out;
8.111 + Parent::InEdgeIt in;
8.112 + public:
8.113 + OutEdgeIt() {}
8.114 + OutEdgeIt(const SymSmartGraph& g, Edge e) {
8.115 + if ((e.id & 1) == 0) {
8.116 + out = Parent::OutEdgeIt(g, SymEdge(e));
8.117 + in = Parent::InEdgeIt(g, g.tail(e));
8.118 + } else {
8.119 + out = Parent::OutEdgeIt(INVALID);
8.120 + in = Parent::InEdgeIt(g, SymEdge(e));
8.121 + }
8.122 + }
8.123 + OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
8.124 +
8.125 + OutEdgeIt(const SymSmartGraph& g, const Node v)
8.126 + : out(g, v), in(g, v) {}
8.127 + OutEdgeIt &operator++() {
8.128 + if (out != INVALID) {
8.129 + ++out;
8.130 + } else {
8.131 + ++in;
8.132 + }
8.133 + return *this;
8.134 + }
8.135 +
8.136 + operator Edge() const {
8.137 + if (out == INVALID && in == INVALID) return INVALID;
8.138 + return out != INVALID ? forward(out) : backward(in);
8.139 + }
8.140 +
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 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.144 + };
8.145 +
8.146 + class InEdgeIt {
8.147 + Parent::OutEdgeIt out;
8.148 + Parent::InEdgeIt in;
8.149 + public:
8.150 + InEdgeIt() {}
8.151 + InEdgeIt(const SymSmartGraph& g, Edge e) {
8.152 + if ((e.id & 1) == 0) {
8.153 + out = Parent::OutEdgeIt(g, SymEdge(e));
8.154 + in = Parent::InEdgeIt(g, g.tail(e));
8.155 + } else {
8.156 + out = Parent::OutEdgeIt(INVALID);
8.157 + in = Parent::InEdgeIt(g, SymEdge(e));
8.158 + }
8.159 + }
8.160 + InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
8.161 +
8.162 + InEdgeIt(const SymSmartGraph& g, const Node v)
8.163 + : out(g, v), in(g, v) {}
8.164 +
8.165 + InEdgeIt &operator++() {
8.166 + if (out != INVALID) {
8.167 + ++out;
8.168 + } else {
8.169 + ++in;
8.170 + }
8.171 + return *this;
8.172 + }
8.173 +
8.174 + operator Edge() const {
8.175 + if (out == INVALID && in == INVALID) return INVALID;
8.176 + return out != INVALID ? backward(out) : forward(in);
8.177 + }
8.178 +
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 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.182 + };
8.183 +
8.184 + class SymEdgeIt : public Parent::EdgeIt {
8.185 +
8.186 + public:
8.187 + SymEdgeIt() {}
8.188 +
8.189 + SymEdgeIt(const SymSmartGraph& g)
8.190 + : SymSmartGraph::Parent::EdgeIt(g) {}
8.191 +
8.192 + SymEdgeIt(const SymSmartGraph& g, SymEdge e)
8.193 + : SymSmartGraph::Parent::EdgeIt(g, e) {}
8.194 +
8.195 + SymEdgeIt(Invalid i)
8.196 + : SymSmartGraph::Parent::EdgeIt(INVALID) {}
8.197 +
8.198 + SymEdgeIt& operator++() {
8.199 + SymSmartGraph::Parent::EdgeIt::operator++();
8.200 + return *this;
8.201 + }
8.202 +
8.203 + operator SymEdge() const {
8.204 + return SymEdge
8.205 + (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
8.206 + }
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 + bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
8.210 + };
8.211 +
8.212 + class EdgeIt {
8.213 + SymEdgeIt it;
8.214 + bool fw;
8.215 + public:
8.216 + EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
8.217 + EdgeIt (Invalid i) : it(i) { }
8.218 + EdgeIt(const SymSmartGraph& g, Edge e)
8.219 + : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
8.220 + EdgeIt() { }
8.221 + EdgeIt& operator++() {
8.222 + fw = !fw;
8.223 + if (fw) ++it;
8.224 + return *this;
8.225 + }
8.226 + operator Edge() const {
8.227 + if (it == INVALID) return INVALID;
8.228 + return fw ? forward(it) : backward(it);
8.229 + }
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 + bool operator<(const Edge i) const {return Edge(*this) < i;}
8.233 +
8.234 + };
8.235 +
8.236 + ///Number of nodes.
8.237 + int nodeNum() const { return Parent::nodeNum(); }
8.238 + ///Number of edges.
8.239 + int edgeNum() const { return 2*Parent::edgeNum(); }
8.240 + ///Number of symmetric edges.
8.241 + int symEdgeNum() const { return Parent::edgeNum(); }
8.242 +
8.243 + /// Maximum node ID.
8.244 +
8.245 + /// Maximum node ID.
8.246 + ///\sa id(Node)
8.247 + int maxNodeId() const { return Parent::maxNodeId(); }
8.248 + /// Maximum edge ID.
8.249 +
8.250 + /// Maximum edge ID.
8.251 + ///\sa id(Edge)
8.252 + int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
8.253 + /// Maximum symmetric edge ID.
8.254 +
8.255 + /// Maximum symmetric edge ID.
8.256 + ///\sa id(SymEdge)
8.257 + int maxSymEdgeId() const { return Parent::maxEdgeId(); }
8.258 +
8.259 +
8.260 + Node tail(Edge e) const {
8.261 + return (e.id & 1) == 0 ?
8.262 + Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
8.263 + }
8.264 +
8.265 + Node head(Edge e) const {
8.266 + return (e.id & 1) == 0 ?
8.267 + Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
8.268 + }
8.269 +
8.270 + Node tail(SymEdge e) const {
8.271 + return Parent::tail(e);
8.272 + }
8.273 +
8.274 + Node head(SymEdge e) const {
8.275 + return Parent::head(e);
8.276 + }
8.277 +
8.278 + NodeIt& first(NodeIt& v) const {
8.279 + v=NodeIt(*this); return v; }
8.280 + EdgeIt& first(EdgeIt& e) const {
8.281 + e=EdgeIt(*this); return e; }
8.282 + SymEdgeIt& first(SymEdgeIt& e) const {
8.283 + e=SymEdgeIt(*this); return e; }
8.284 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
8.285 + e=OutEdgeIt(*this,v); return e; }
8.286 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
8.287 + e=InEdgeIt(*this,v); return e; }
8.288 +
8.289 + /// Node ID.
8.290 +
8.291 + /// The ID of a valid Node is a nonnegative integer not greater than
8.292 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
8.293 + /// and the greatest node ID can be actually less then \ref maxNodeId().
8.294 + ///
8.295 + /// The ID of the \ref INVALID node is -1.
8.296 + ///\return The ID of the node \c v.
8.297 + static int id(Node v) { return Parent::id(v); }
8.298 + /// Edge ID.
8.299 +
8.300 + /// The ID of a valid Edge is a nonnegative integer not greater than
8.301 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
8.302 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
8.303 + ///
8.304 + /// The ID of the \ref INVALID edge is -1.
8.305 + ///\return The ID of the edge \c e.
8.306 + static int id(Edge e) { return e.id; }
8.307 +
8.308 + /// The ID of a valid SymEdge is a nonnegative integer not greater than
8.309 + /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
8.310 + /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
8.311 + ///
8.312 + /// The ID of the \ref INVALID symmetric edge is -1.
8.313 + ///\return The ID of the edge \c e.
8.314 + static int id(SymEdge e) { return Parent::id(e); }
8.315 +
8.316 + /// Adds a new node to the graph.
8.317 +
8.318 + /// \warning It adds the new node to the front of the list.
8.319 + /// (i.e. the lastly added node becomes the first.)
8.320 + Node addNode() {
8.321 + return Parent::addNode();
8.322 + }
8.323 +
8.324 + SymEdge addEdge(Node u, Node v) {
8.325 + SymEdge se = Parent::addEdge(u, v);
8.326 + edge_maps.add(forward(se));
8.327 + edge_maps.add(backward(se));
8.328 + return se;
8.329 + }
8.330 +
8.331 + /// Finds an edge between two nodes.
8.332 +
8.333 + /// Finds an edge from node \c u to node \c v.
8.334 + ///
8.335 + /// If \c prev is \ref INVALID (this is the default value), then
8.336 + /// It finds the first edge from \c u to \c v. Otherwise it looks for
8.337 + /// the next edge from \c u to \c v after \c prev.
8.338 + /// \return The found edge or INVALID if there is no such an edge.
8.339 + Edge findEdge(Node u, Node v, Edge prev = INVALID)
8.340 + {
8.341 + if (prev == INVALID || id(prev) & 1 == 0) {
8.342 + SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
8.343 + if (se != INVALID) return forward(se);
8.344 + } else {
8.345 + SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
8.346 + if (se != INVALID) return backward(se);
8.347 + }
8.348 + return INVALID;
8.349 + }
8.350 +
8.351 +// /// Finds an symmetric edge between two nodes.
8.352 +
8.353 +// /// Finds an symmetric edge from node \c u to node \c v.
8.354 +// ///
8.355 +// /// If \c prev is \ref INVALID (this is the default value), then
8.356 +// /// It finds the first edge from \c u to \c v. Otherwise it looks for
8.357 +// /// the next edge from \c u to \c v after \c prev.
8.358 +// /// \return The found edge or INVALID if there is no such an edge.
8.359 +
8.360 +// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
8.361 +// {
8.362 +// if (prev == INVALID || id(prev) & 1 == 0) {
8.363 +// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
8.364 +// if (se != INVALID) return se;
8.365 +// } else {
8.366 +// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
8.367 +// if (se != INVALID) return se;
8.368 +// }
8.369 +// return INVALID;
8.370 +// }
8.371 +
8.372 + public:
8.373 +
8.374 + void clear() {
8.375 + edge_maps.clear();
8.376 + Parent::clear();
8.377 + }
8.378 +
8.379 + static Edge opposite(Edge e) {
8.380 + return Edge(id(e) ^ 1);
8.381 + }
8.382 +
8.383 + static Edge forward(SymEdge e) {
8.384 + return Edge(id(e) << 1);
8.385 + }
8.386 +
8.387 + static Edge backward(SymEdge e) {
8.388 + return Edge((id(e) << 1) | 1);
8.389 + }
8.390 +
8.391 + };
8.392 ///Graph for bidirectional edges.
8.393
8.394 ///The purpose of this graph structure is to handle graphs
8.395 @@ -318,7 +693,7 @@
8.396 ///it is not possible to delete edges or nodes from the graph.
8.397 //\sa SmartGraph.
8.398
8.399 - class SymSmartGraph : public SmartGraph
8.400 + /* class SymSmartGraph : public SmartGraph
8.401 {
8.402 public:
8.403 typedef SymSmartGraph Graph;
8.404 @@ -353,7 +728,7 @@
8.405 }
8.406
8.407
8.408 - };
8.409 + };*/
8.410
8.411 /// @}
8.412 } //namespace lemon
9.1 --- a/src/lemon/sym_map.h Mon Oct 04 16:03:25 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/lemon/sym_map.h - Part of LEMON, 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 LEMON_SYM_MAP_H
9.21 -#define LEMON_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 lemon {
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/lemon/vector_map.h Mon Oct 04 16:03:25 2004 +0000
10.2 +++ b/src/lemon/vector_map.h Mon Oct 04 17:13:21 2004 +0000
10.3 @@ -31,18 +31,16 @@
10.4 /// \addtogroup graphmaps
10.5 /// @{
10.6
10.7 - /** The ArrayMap template class is graph map structure what
10.8 + /** The VectorMap template class is graph map structure what
10.9 * automatically updates the map when a key is added to or erased from
10.10 * the map. This map factory uses the allocators to implement
10.11 * the container functionality. This map factory
10.12 * uses the std::vector to implement the container function.
10.13 *
10.14 - * The template parameter is the MapRegistry that the maps
10.15 - * will belong to and the ValueType.
10.16 + * \param MapRegistry The MapRegistry that the maps will belong to.
10.17 + * \param Value The value type of the map.
10.18 *
10.19 - * \todo It should use a faster initialization using the maxNodeId() or
10.20 - * maxEdgeId() function of the graph instead of iterating through each
10.21 - * edge/node.
10.22 + * \author Balazs Dezso
10.23 */
10.24
10.25 template <typename MapRegistry, typename Value>
10.26 @@ -84,17 +82,27 @@
10.27 /// The pointer type of the map;
10.28 typedef typename Container::const_pointer ConstPointerType;
10.29
10.30 - /** Graph and Registry initialized map constructor.
10.31 + /// Constructor to attach the new map into a registry.
10.32 +
10.33 + /** Constructor to attach the new map into a registry.
10.34 + * It adds all the nodes or edges of the graph to the map.
10.35 */
10.36 VectorMap(const Graph& g, MapRegistry& r)
10.37 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
10.38
10.39 - /** Constructor to use default value to initialize the map.
10.40 + /// Constructor uses given value to initialize the map.
10.41 +
10.42 + /** Constructor uses given value to initialize the map.
10.43 + * It adds all the nodes or edges of the graph to the map.
10.44 */
10.45 VectorMap(const Graph& g, MapRegistry& r, const Value& v)
10.46 : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
10.47
10.48 + /// Assign operator to copy a map of an other map type.
10.49 +
10.50 /** Assign operator to copy a map of an other map type.
10.51 + * This map's value type must be assignable by the other
10.52 + * map type's value type.
10.53 */
10.54 template <typename TT>
10.55 VectorMap(const VectorMap<MapRegistry, TT>& c)
10.56 @@ -105,7 +113,11 @@
10.57 }
10.58 }
10.59
10.60 + /// Assign operator to copy a map of an other map type.
10.61 +
10.62 /** Assign operator to copy a map of an other map type.
10.63 + * This map's value type must be assignable by the other
10.64 + * map type's value type.
10.65 */
10.66 template <typename TT>
10.67 VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
10.68 @@ -119,6 +131,9 @@
10.69 }
10.70 return *this;
10.71 }
10.72 +
10.73 + /// The subcript operator.
10.74 +
10.75 /**
10.76 * The subscript operator. The map can be subscripted by the
10.77 * actual keys of the graph.
10.78 @@ -128,6 +143,8 @@
10.79 return container[id];
10.80 }
10.81
10.82 + /// The const subcript operator.
10.83 +
10.84 /**
10.85 * The const subscript operator. The map can be subscripted by the
10.86 * actual keys of the graph.
10.87 @@ -137,6 +154,8 @@
10.88 return container[id];
10.89 }
10.90
10.91 + ///Setter function of the map.
10.92 +
10.93 /** Setter function of the map. Equivalent with map[key] = val.
10.94 * This is a compatibility feature with the not dereferable maps.
10.95 */
10.96 @@ -144,8 +163,11 @@
10.97 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
10.98 container[id] = val;
10.99 }
10.100 + /// Adds a new key to the map.
10.101
10.102 - /** Add a new key to the map. It called by the map registry.
10.103 + /** Adds a new key to the map. It called by the map registry
10.104 + * and it overrides the \ref MapRegistry::MapBase MapBase's
10.105 + * add() member function.
10.106 */
10.107 void add(const KeyType& key) {
10.108 int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
10.109 @@ -153,13 +175,22 @@
10.110 container.resize(id + 1);
10.111 }
10.112 }
10.113 +
10.114 + /// Erases a key from the map.
10.115
10.116 - /** Erase a key from the map. It called by the map registry.
10.117 + /** Erase a key from the map. It called by the map registry
10.118 + * and it overrides the \ref MapRegistry::MapBase MapBase's
10.119 + * erase() member function.
10.120 */
10.121 void erase(const KeyType& key) {}
10.122
10.123 - /** Clear the data structure.
10.124 + /// Makes empty the map.
10.125 +
10.126 + /** Makes empty the map. It called by the map registry
10.127 + * and it overrides the \ref MapRegistry::MapBase MapBase's
10.128 + * clear() member function.
10.129 */
10.130 +
10.131 void clear() {
10.132 container.clear();
10.133 }
11.1 --- a/src/test/Makefile.am Mon Oct 04 16:03:25 2004 +0000
11.2 +++ b/src/test/Makefile.am Mon Oct 04 17:13:21 2004 +0000
11.3 @@ -9,6 +9,7 @@
11.4 dfs_test \
11.5 dijkstra_test \
11.6 graph_test \
11.7 + sym_graph_test \
11.8 graph_wrapper_test \
11.9 kruskal_test \
11.10 min_cost_flow_test \
11.11 @@ -28,6 +29,7 @@
11.12 dfs_test_SOURCES = dfs_test.cc
11.13 dijkstra_test_SOURCES = dijkstra_test.cc
11.14 graph_test_SOURCES = graph_test.cc
11.15 +sym_graph_test_SOURCES = sym_graph_test.cc
11.16 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
11.17 kruskal_test_SOURCES = kruskal_test.cc
11.18 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
12.1 --- a/src/test/graph_test.cc Mon Oct 04 16:03:25 2004 +0000
12.2 +++ b/src/test/graph_test.cc Mon Oct 04 17:13:21 2004 +0000
12.3 @@ -63,7 +63,6 @@
12.4 for(NodeIt n(G);n!=INVALID;++n) {
12.5 checkGraphInEdgeList(G,n,3);
12.6 checkGraphOutEdgeList(G,n,3);
12.7 - ++n;
12.8 }
12.9 }
12.10
12.11 @@ -82,8 +81,8 @@
12.12 template void lemon::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
12.13
12.14 //Compile SymSmartGraph
12.15 -template void lemon::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
12.16 -template void lemon::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
12.17 +//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
12.18 +//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
12.19
12.20 //Compile ListGraph
12.21 template void lemon::checkCompileGraph<ListGraph>(ListGraph &);
12.22 @@ -92,9 +91,9 @@
12.23
12.24
12.25 //Compile SymListGraph
12.26 -template void lemon::checkCompileGraph<SymListGraph>(SymListGraph &);
12.27 -template void lemon::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
12.28 -template void lemon::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
12.29 +//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
12.30 +//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
12.31 +//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
12.32
12.33 //Compile FullGraph
12.34 template void lemon::checkCompileStaticGraph<FullGraph>(FullGraph &);
12.35 @@ -131,14 +130,14 @@
12.36 checkPetersen(G);
12.37 }
12.38 {
12.39 - SymSmartGraph G;
12.40 - addPetersen(G);
12.41 - checkPetersen(G);
12.42 + // SymSmartGraph G;
12.43 + // addPetersen(G);
12.44 + // checkPetersen(G);
12.45 }
12.46 {
12.47 - SymListGraph G;
12.48 - addPetersen(G);
12.49 - checkPetersen(G);
12.50 + // SymListGraph G;
12.51 + // addPetersen(G);
12.52 + // checkPetersen(G);
12.53 }
12.54
12.55 ///\file
13.1 --- a/src/test/graph_test.h Mon Oct 04 16:03:25 2004 +0000
13.2 +++ b/src/test/graph_test.h Mon Oct 04 17:13:21 2004 +0000
13.3 @@ -298,6 +298,7 @@
13.4 typename Graph::OutEdgeIt e(G,n);
13.5 for(int i=0;i<nn;i++) {
13.6 check(e!=INVALID,"Wrong OutEdge list linking.");
13.7 + check(n==G.tail(e), "Wrong OutEdge list linking.");
13.8 ++e;
13.9 }
13.10 check(e==INVALID,"Wrong OutEdge list linking.");
13.11 @@ -310,6 +311,7 @@
13.12 typename Graph::InEdgeIt e(G,n);
13.13 for(int i=0;i<nn;i++) {
13.14 check(e!=INVALID,"Wrong InEdge list linking.");
13.15 + check(n==G.head(e), "Wrong InEdge list linking.");
13.16 ++e;
13.17 }
13.18 check(e==INVALID,"Wrong InEdge list linking.");
14.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
14.2 +++ b/src/test/sym_graph_test.cc Mon Oct 04 17:13:21 2004 +0000
14.3 @@ -0,0 +1,96 @@
14.4 +/* -*- C++ -*-
14.5 + * src/test/sym_graph_test.cc - Part of LEMON, a generic C++ optimization library
14.6 + *
14.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
14.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
14.9 + *
14.10 + * Permission to use, modify and distribute this software is granted
14.11 + * provided that this copyright notice appears in all copies. For
14.12 + * precise terms see the accompanying LICENSE file.
14.13 + *
14.14 + * This software is provided "AS IS" with no warranty of any kind,
14.15 + * express or implied, and with no claim as to its suitability for any
14.16 + * purpose.
14.17 + *
14.18 + */
14.19 +
14.20 +#include<iostream>
14.21 +
14.22 +#include<lemon/skeletons/sym_graph.h>
14.23 +
14.24 +#include<lemon/list_graph.h>
14.25 +#include<lemon/smart_graph.h>
14.26 +#include<lemon/full_graph.h>
14.27 +
14.28 +#include"test_tools.h"
14.29 +#include"graph_test.h"
14.30 +#include"sym_graph_test.h"
14.31 +
14.32 +/**
14.33 +\file
14.34 +This test makes consistency checks of list graph structures.
14.35 +
14.36 +G.addNode(), G.addEdge(), G.tail(), G.head()
14.37 +
14.38 +\todo Checks for empty graphs and isolated points.
14.39 +conversion.
14.40 +*/
14.41 +
14.42 +using namespace lemon;
14.43 +
14.44 +template<class Graph> void checkPetersen(Graph &G)
14.45 +{
14.46 + typedef typename Graph::NodeIt NodeIt;
14.47 +
14.48 +
14.49 + checkGraphNodeList(G,10);
14.50 + checkGraphEdgeList(G,30);
14.51 + checkGraphSymEdgeList(G,15);
14.52 +
14.53 + for(NodeIt n(G);n!=INVALID;++n) {
14.54 + checkGraphInEdgeList(G,n,3);
14.55 + checkGraphOutEdgeList(G,n,3);
14.56 + }
14.57 +}
14.58 +
14.59 +//Compile Graph
14.60 +template void lemon::checkCompileStaticSymGraph<skeleton::StaticSymGraph>
14.61 +(skeleton::StaticSymGraph &);
14.62 +
14.63 +template void lemon::checkCompileSymGraph<skeleton::ExtendableSymGraph>
14.64 +(skeleton::ExtendableSymGraph &);
14.65 +
14.66 +template void lemon::checkCompileErasableSymGraph<skeleton::ErasableSymGraph>
14.67 +(skeleton::ErasableSymGraph &);
14.68 +
14.69 +
14.70 +//Compile SymSmartGraph
14.71 +template void lemon::checkCompileSymGraph<SymSmartGraph>(SymSmartGraph &);
14.72 +template void lemon::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
14.73 +
14.74 +//Compile SymListGraph
14.75 +template void lemon::checkCompileSymGraph<SymListGraph>(SymListGraph &);
14.76 +template void lemon::checkCompileErasableSymGraph<SymListGraph>(SymListGraph &);
14.77 +template void lemon::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
14.78 +
14.79 +int main()
14.80 +{
14.81 + {
14.82 + SymSmartGraph G;
14.83 + addSymPetersen(G);
14.84 + checkPetersen(G);
14.85 + }
14.86 + {
14.87 + SymListGraph G;
14.88 + addSymPetersen(G);
14.89 + checkPetersen(G);
14.90 + }
14.91 +
14.92 + ///\file
14.93 + ///\todo map tests.
14.94 + ///\todo copy constr tests.
14.95 +
14.96 + std::cout << __FILE__ ": All tests passed.\n";
14.97 +
14.98 + return 0;
14.99 +}
15.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
15.2 +++ b/src/test/sym_graph_test.h Mon Oct 04 17:13:21 2004 +0000
15.3 @@ -0,0 +1,179 @@
15.4 +/* -*- C++ -*-
15.5 + * src/test/sym_graph_test.h - Part of LEMON, a generic C++ optimization library
15.6 + *
15.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
15.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
15.9 + *
15.10 + * Permission to use, modify and distribute this software is granted
15.11 + * provided that this copyright notice appears in all copies. For
15.12 + * precise terms see the accompanying LICENSE file.
15.13 + *
15.14 + * This software is provided "AS IS" with no warranty of any kind,
15.15 + * express or implied, and with no claim as to its suitability for any
15.16 + * purpose.
15.17 + *
15.18 + */
15.19 +#ifndef LEMON_TEST_SYM_GRAPH_TEST_H
15.20 +#define LEMON_TEST_SYM_GRAPH_TEST_H
15.21 +
15.22 +
15.23 +#include "graph_test.h"
15.24 +#include "test_tools.h"
15.25 +
15.26 +//! \ingroup misc
15.27 +//! \file
15.28 +//! \brief Some utility to test symmetric graph classes.
15.29 +namespace lemon {
15.30 +
15.31 + template<class Graph> void checkCompileStaticSymGraph(Graph &G)
15.32 + {
15.33 + typedef typename Graph::Node Node;
15.34 + typedef typename Graph::NodeIt NodeIt;
15.35 + typedef typename Graph::SymEdge SymEdge;
15.36 + typedef typename Graph::SymEdgeIt SymEdgeIt;
15.37 + typedef typename Graph::Edge Edge;
15.38 + typedef typename Graph::EdgeIt EdgeIt;
15.39 + typedef typename Graph::InEdgeIt InEdgeIt;
15.40 + typedef typename Graph::OutEdgeIt OutEdgeIt;
15.41 +
15.42 + checkCompileStaticGraph(G);
15.43 +
15.44 + {
15.45 + SymEdge i; SymEdge j(i); SymEdge k(INVALID);
15.46 + i=j;
15.47 + bool b; b=true;
15.48 + b=(i==INVALID); b=(i!=INVALID);
15.49 + b=(i==j); b=(i!=j); b=(i<j);
15.50 + Edge e;
15.51 + e = G.forward(i);
15.52 + e = G.backward(i);
15.53 + }
15.54 + {
15.55 + SymEdgeIt i; SymEdgeIt j(i); SymEdgeIt k(INVALID); SymEdgeIt l(G);
15.56 + i=j;
15.57 + j=G.first(i);
15.58 + j=++i;
15.59 + bool b; b=true;
15.60 + b=(i==INVALID); b=(i!=INVALID);
15.61 + SymEdge n(i);
15.62 + n=i;
15.63 + b=(i==j); b=(i!=j); b=(i<j);
15.64 + //SymEdge ->SymEdgeIt conversion
15.65 + SymEdgeIt ni(G,n);
15.66 + }
15.67 + {
15.68 + Edge i, j;
15.69 + j = G.opposite(i);
15.70 + }
15.71 + {
15.72 + Node n;
15.73 + SymEdge se;
15.74 + se=INVALID;
15.75 + n=G.tail(se);
15.76 + n=G.head(se);
15.77 + }
15.78 + // id tests
15.79 + { SymEdge n; int i=G.id(n); i=i; }
15.80 + //SymEdgeMap tests
15.81 + {
15.82 + SymEdge k;
15.83 + typename Graph::template SymEdgeMap<int> m(G);
15.84 + typename Graph::template SymEdgeMap<int> const &cm = m; //Const map
15.85 + //Inicialize with default value
15.86 + typename Graph::template SymEdgeMap<int> mdef(G,12);
15.87 + typename Graph::template SymEdgeMap<int> mm(cm); //Copy
15.88 + typename Graph::template SymEdgeMap<double> dm(cm); //Copy from another type
15.89 + int v;
15.90 + v=m[k]; m[k]=v; m.set(k,v);
15.91 + v=cm[k];
15.92 +
15.93 + m=cm;
15.94 + dm=cm; //Copy from another type
15.95 + {
15.96 + //Check the typedef's
15.97 + typename Graph::template SymEdgeMap<int>::ValueType val;
15.98 + val = 1;
15.99 + typename Graph::template SymEdgeMap<int>::KeyType key;
15.100 + key = typename Graph::SymEdgeIt(G);
15.101 + }
15.102 + }
15.103 + { //bool SymEdgeMap
15.104 + SymEdge k;
15.105 + typename Graph::template SymEdgeMap<bool> m(G);
15.106 + typename Graph::template SymEdgeMap<bool> const &cm = m; //Const map
15.107 + //Inicialize with default value
15.108 + typename Graph::template SymEdgeMap<bool> mdef(G,12);
15.109 + typename Graph::template SymEdgeMap<bool> mm(cm); //Copy
15.110 + typename Graph::template SymEdgeMap<int> dm(cm); //Copy from another type
15.111 + bool v;
15.112 + v=m[k]; m[k]=v; m.set(k,v);
15.113 + v=cm[k];
15.114 +
15.115 + m=cm;
15.116 + dm=cm; //Copy from another type
15.117 + m=dm; //Copy to another type
15.118 + {
15.119 + //Check the typedef's
15.120 + typename Graph::template SymEdgeMap<bool>::ValueType val;
15.121 + val=true;
15.122 + typename Graph::template SymEdgeMap<bool>::KeyType key;
15.123 + key= typename Graph::SymEdgeIt(G);
15.124 + }
15.125 + }
15.126 + }
15.127 +
15.128 + template<class Graph> void checkCompileSymGraph(Graph &G)
15.129 + {
15.130 + checkCompileStaticSymGraph(G);
15.131 +
15.132 + typedef typename Graph::Node Node;
15.133 + typedef typename Graph::NodeIt NodeIt;
15.134 + typedef typename Graph::SymEdge SymEdge;
15.135 + typedef typename Graph::SymEdgeIt SymEdgeIt;
15.136 + typedef typename Graph::Edge Edge;
15.137 + typedef typename Graph::EdgeIt EdgeIt;
15.138 + typedef typename Graph::InEdgeIt InEdgeIt;
15.139 + typedef typename Graph::OutEdgeIt OutEdgeIt;
15.140 +
15.141 + Node n,m;
15.142 + n=G.addNode();
15.143 + m=G.addNode();
15.144 + SymEdge e;
15.145 + e = G.addEdge(n,m);
15.146 +
15.147 + // G.clear();
15.148 + }
15.149 +
15.150 + template<class Graph> void checkCompileSymGraphEraseSymEdge(Graph &G)
15.151 + {
15.152 + typename Graph::SymEdge n;
15.153 + G.erase(n);
15.154 + }
15.155 +
15.156 + template<class Graph> void checkCompileErasableSymGraph(Graph &G)
15.157 + {
15.158 + checkCompileSymGraph(G);
15.159 + checkCompileGraphEraseNode(G);
15.160 + checkCompileSymGraphEraseSymEdge(G);
15.161 + }
15.162 +
15.163 + template<class Graph> void checkGraphSymEdgeList(Graph &G, int nn)
15.164 + {
15.165 + typedef typename Graph::SymEdgeIt SymEdgeIt;
15.166 +
15.167 + SymEdgeIt e(G);
15.168 + for(int i=0;i<nn;i++) {
15.169 + check(e!=INVALID,"Wrong SymEdge list linking.");
15.170 + ++e;
15.171 + }
15.172 + check(e==INVALID,"Wrong SymEdge list linking.");
15.173 + }
15.174 +
15.175 + ///\file
15.176 + ///\todo Check head(), tail() as well;
15.177 +
15.178 +
15.179 +} //namespace lemon
15.180 +
15.181 +
15.182 +#endif
16.1 --- a/src/test/test_tools.h Mon Oct 04 16:03:25 2004 +0000
16.2 +++ b/src/test/test_tools.h Mon Oct 04 17:13:21 2004 +0000
16.3 @@ -67,7 +67,7 @@
16.4 ///Adds a Petersen graph to \c G.
16.5
16.6 ///Adds a Petersen graph to \c G.
16.7 -///\return The nodes end edges og the generated graph.
16.8 +///\return The nodes and edges of the generated graph.
16.9
16.10 template<typename Graph>
16.11 PetStruct<Graph> addPetersen(Graph &G,int num=5)
16.12 @@ -87,6 +87,45 @@
16.13 return n;
16.14 }
16.15
16.16 +///Structure returned by \ref addSymPetersen().
16.17
16.18 +///Structure returned by \ref addSymPetersen().
16.19 +///
16.20 +template<class Graph> struct SymPetStruct
16.21 +{
16.22 + ///Vector containing the outer nodes.
16.23 + std::vector<typename Graph::Node> outer;
16.24 + ///Vector containing the inner nodes.
16.25 + std::vector<typename Graph::Node> inner;
16.26 + ///Vector containing the edges of the inner circle.
16.27 + std::vector<typename Graph::SymEdge> incir;
16.28 + ///Vector containing the edges of the outer circle.
16.29 + std::vector<typename Graph::SymEdge> outcir;
16.30 + ///Vector containing the chord edges.
16.31 + std::vector<typename Graph::SymEdge> chords;
16.32 +};
16.33 +
16.34 +///Adds a Petersen graph to the symmetric \c G.
16.35 +
16.36 +///Adds a Petersen graph to the symmetric \c G.
16.37 +///\return The nodes and edges of the generated graph.
16.38 +
16.39 +template<typename Graph>
16.40 +SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5)
16.41 +{
16.42 + SymPetStruct<Graph> n;
16.43 +
16.44 + for(int i=0;i<num;i++) {
16.45 + n.outer.push_back(G.addNode());
16.46 + n.inner.push_back(G.addNode());
16.47 + }
16.48 +
16.49 + for(int i=0;i<num;i++) {
16.50 + n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
16.51 + n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
16.52 + n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
16.53 + }
16.54 + return n;
16.55 +}
16.56
16.57 #endif