1.1 --- a/src/hugo/Makefile.am Wed Sep 29 10:35:35 2004 +0000
1.2 +++ b/src/hugo/Makefile.am Wed Sep 29 14:02:14 2004 +0000
1.3 @@ -18,11 +18,12 @@
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 @@ -30,6 +31,5 @@
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 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/hugo/attic/tight_edge_filter_map.h Wed Sep 29 14:02:14 2004 +0000
2.3 @@ -0,0 +1,63 @@
2.4 +/* -*- C++ -*-
2.5 + * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
2.21 +#define HUGO_TIGHT_EDGE_FILTER_MAP_H
2.22 +
2.23 +#include <hugo/maps.h>
2.24 +
2.25 +// /// \file
2.26 +// /// \brief Maximum flow algorithms.
2.27 +// /// \ingroup galgs
2.28 +
2.29 +namespace hugo {
2.30 +
2.31 + /// \brief A map for filtering the edge-set to those edges
2.32 + /// which are tight w.r.t. some node_potential map and
2.33 + /// edge_distance map.
2.34 + ///
2.35 + /// A node-map node_potential is said to be a potential w.r.t.
2.36 + /// an edge-map edge_distance
2.37 + /// if and only if for each edge e, node_potential[g.head(e)]
2.38 + /// <= edge_distance[e]+node_potential[g.tail(e)]
2.39 + /// (or the reverse inequality holds for each edge).
2.40 + /// An edge is said to be tight if this inequality holds with equality,
2.41 + /// and the map returns true exactly for those edges.
2.42 + /// To avoid rounding errors, it is recommended to use this class with exact
2.43 + /// types, e.g. with int.
2.44 + template<typename Graph,
2.45 + typename NodePotentialMap, typename EdgeDistanceMap>
2.46 + class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
2.47 + protected:
2.48 + const Graph* g;
2.49 + NodePotentialMap* node_potential;
2.50 + EdgeDistanceMap* edge_distance;
2.51 + public:
2.52 + TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
2.53 + EdgeDistanceMap& _edge_distance) :
2.54 + g(&_g), node_potential(&_node_potential),
2.55 + edge_distance(&_edge_distance) { }
2.56 + bool operator[](const typename Graph::Edge& e) const {
2.57 + return ((*node_potential)[g->head(e)] ==
2.58 + (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
2.59 + }
2.60 + };
2.61 +
2.62 +} //namespace hugo
2.63 +
2.64 +#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
2.65 +
2.66 +
3.1 --- a/src/hugo/default_map.h Wed Sep 29 10:35:35 2004 +0000
3.2 +++ b/src/hugo/default_map.h Wed Sep 29 14:02:14 2004 +0000
3.3 @@ -59,9 +59,12 @@
3.4 : Parent(static_cast<const Parent&>(copy)) {} \
3.5 template <typename TT> \
3.6 DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
3.7 - : Parent(*copy.getGraph()) { \
3.8 + : { \
3.9 + Parent::MapBase::operator= \
3.10 + (static_cast<const typename Parent::MapBase&>(copy)); \
3.11 if (Parent::getGraph()) { \
3.12 for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
3.13 + Parent::add(it); \
3.14 Parent::operator[](it) = copy[it]; \
3.15 } \
3.16 } \
4.1 --- a/src/hugo/list_graph.h Wed Sep 29 10:35:35 2004 +0000
4.2 +++ b/src/hugo/list_graph.h Wed Sep 29 14:02:14 2004 +0000
4.3 @@ -29,6 +29,8 @@
4.4 #include <hugo/map_registry.h>
4.5 #include <hugo/array_map.h>
4.6
4.7 +#include <hugo/sym_map.h>
4.8 +
4.9 #include <hugo/map_defines.h>
4.10
4.11
4.12 @@ -102,7 +104,6 @@
4.13 first_free_node(_g.first_free_node), edges(_g.edges),
4.14 first_free_edge(_g.first_free_edge) {}
4.15
4.16 - /// \bug In the vector can be hole if a node is erased from the graph.
4.17 ///Number of nodes.
4.18 int nodeNum() const { return nodes.size(); }
4.19 ///Number of edges.
4.20 @@ -437,7 +438,7 @@
4.21 ///
4.22 ///\todo this date structure need some reconsiderations. Maybe it
4.23 ///should be implemented independently from ListGraph.
4.24 - /*
4.25 +
4.26 class SymListGraph : public ListGraph
4.27 {
4.28 public:
4.29 @@ -482,402 +483,8 @@
4.30 ListGraph::erase(f);
4.31 ListGraph::erase(e);
4.32 }
4.33 - };*/
4.34 + };
4.35
4.36 - class SymListGraph : public ListGraph {
4.37 - typedef ListGraph Parent;
4.38 - public:
4.39 -
4.40 - typedef SymListGraph Graph;
4.41 -
4.42 - typedef ListGraph::Node Node;
4.43 - typedef ListGraph::NodeIt NodeIt;
4.44 -
4.45 - class SymEdge;
4.46 - class SymEdgeIt;
4.47 -
4.48 - class Edge;
4.49 - class EdgeIt;
4.50 - class OutEdgeIt;
4.51 - class InEdgeIt;
4.52 -
4.53 - template <typename Value>
4.54 - class NodeMap : public Parent::NodeMap<Value> {
4.55 - public:
4.56 - NodeMap(const SymListGraph& g)
4.57 - : SymListGraph::Parent::NodeMap<Value>(g) {}
4.58 - NodeMap(const SymListGraph& g, Value v)
4.59 - : SymListGraph::Parent::NodeMap<Value>(g, v) {}
4.60 - template<typename TT>
4.61 - NodeMap(const NodeMap<TT>& copy)
4.62 - : SymListGraph::Parent::NodeMap<Value>(copy) { }
4.63 - };
4.64 -
4.65 - template <typename Value>
4.66 - class SymEdgeMap : public Parent::EdgeMap<Value> {
4.67 - public:
4.68 - typedef SymEdge KeyType;
4.69 -
4.70 - SymEdgeMap(const SymListGraph& g)
4.71 - : SymListGraph::Parent::EdgeMap<Value>(g) {}
4.72 - SymEdgeMap(const SymListGraph& g, Value v)
4.73 - : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
4.74 - template<typename TT>
4.75 - SymEdgeMap(const SymEdgeMap<TT>& copy)
4.76 - : SymListGraph::Parent::EdgeMap<Value>(copy) { }
4.77 -
4.78 - };
4.79 -
4.80 - // Create edge map registry.
4.81 - CREATE_EDGE_MAP_REGISTRY;
4.82 - // Create edge maps.
4.83 - CREATE_EDGE_MAP(ArrayMap);
4.84 -
4.85 - class Edge {
4.86 - friend class SymListGraph;
4.87 - friend class SymListGraph::EdgeIt;
4.88 - friend class SymListGraph::OutEdgeIt;
4.89 - friend class SymListGraph::InEdgeIt;
4.90 -
4.91 - protected:
4.92 - int id;
4.93 -
4.94 - Edge(int pid) { id = pid; }
4.95 -
4.96 - public:
4.97 - /// An Edge with id \c n.
4.98 -
4.99 - Edge() { }
4.100 - Edge (Invalid) { id = -1; }
4.101 -
4.102 - operator SymEdge(){ return SymEdge(id >> 1);}
4.103 -
4.104 - bool operator==(const Edge i) const {return id == i.id;}
4.105 - bool operator!=(const Edge i) const {return id != i.id;}
4.106 - bool operator<(const Edge i) const {return id < i.id;}
4.107 - // ///Validity check
4.108 - // operator bool() { return n!=-1; }
4.109 - };
4.110 -
4.111 - class SymEdge : public ListGraph::Edge {
4.112 - friend class SymListGraph;
4.113 - friend class SymListGraph::Edge;
4.114 - typedef ListGraph::Edge Parent;
4.115 -
4.116 - protected:
4.117 - SymEdge(int pid) : Parent(pid) {}
4.118 - public:
4.119 -
4.120 - SymEdge() { }
4.121 - SymEdge(const ListGraph::Edge& i) : Parent(i) {}
4.122 - SymEdge (Invalid) : Parent(INVALID) {}
4.123 -
4.124 - };
4.125 -
4.126 - class OutEdgeIt {
4.127 - Parent::OutEdgeIt out;
4.128 - Parent::InEdgeIt in;
4.129 - public:
4.130 - OutEdgeIt() {}
4.131 - OutEdgeIt(const SymListGraph& g, Edge e) {
4.132 - if ((e.id & 1) == 0) {
4.133 - out = Parent::OutEdgeIt(g, SymEdge(e));
4.134 - in = Parent::InEdgeIt(g, g.tail(e));
4.135 - } else {
4.136 - out = Parent::OutEdgeIt(INVALID);
4.137 - in = Parent::InEdgeIt(g, SymEdge(e));
4.138 - }
4.139 - }
4.140 - OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
4.141 -
4.142 - OutEdgeIt(const SymListGraph& g, const Node v)
4.143 - : out(g, v), in(g, v) {}
4.144 - OutEdgeIt &operator++() {
4.145 - if (out != INVALID) {
4.146 - ++out;
4.147 - } else {
4.148 - ++in;
4.149 - }
4.150 - return *this;
4.151 - }
4.152 -
4.153 - operator Edge() const {
4.154 - if (out == INVALID && in == INVALID) return INVALID;
4.155 - return out != INVALID ? forward(out) : backward(in);
4.156 - }
4.157 -
4.158 - bool operator==(const Edge i) const {return Edge(*this) == i;}
4.159 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
4.160 - bool operator<(const Edge i) const {return Edge(*this) < i;}
4.161 - };
4.162 -
4.163 - class InEdgeIt {
4.164 - Parent::OutEdgeIt out;
4.165 - Parent::InEdgeIt in;
4.166 - public:
4.167 - InEdgeIt() {}
4.168 - InEdgeIt(const SymListGraph& g, Edge e) {
4.169 - if ((e.id & 1) == 0) {
4.170 - out = Parent::OutEdgeIt(g, SymEdge(e));
4.171 - in = Parent::InEdgeIt(g, g.tail(e));
4.172 - } else {
4.173 - out = Parent::OutEdgeIt(INVALID);
4.174 - in = Parent::InEdgeIt(g, SymEdge(e));
4.175 - }
4.176 - }
4.177 - InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
4.178 -
4.179 - InEdgeIt(const SymListGraph& g, const Node v)
4.180 - : out(g, v), in(g, v) {}
4.181 -
4.182 - InEdgeIt &operator++() {
4.183 - if (out != INVALID) {
4.184 - ++out;
4.185 - } else {
4.186 - ++in;
4.187 - }
4.188 - return *this;
4.189 - }
4.190 -
4.191 - operator Edge() const {
4.192 - if (out == INVALID && in == INVALID) return INVALID;
4.193 - return out != INVALID ? backward(out) : forward(in);
4.194 - }
4.195 -
4.196 - bool operator==(const Edge i) const {return Edge(*this) == i;}
4.197 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
4.198 - bool operator<(const Edge i) const {return Edge(*this) < i;}
4.199 - };
4.200 -
4.201 - class SymEdgeIt : public Parent::EdgeIt {
4.202 -
4.203 - public:
4.204 - SymEdgeIt() {}
4.205 -
4.206 - SymEdgeIt(const SymListGraph& g)
4.207 - : SymListGraph::Parent::EdgeIt(g) {}
4.208 -
4.209 - SymEdgeIt(const SymListGraph& g, SymEdge e)
4.210 - : SymListGraph::Parent::EdgeIt(g, e) {}
4.211 -
4.212 - SymEdgeIt(Invalid i)
4.213 - : SymListGraph::Parent::EdgeIt(INVALID) {}
4.214 -
4.215 - SymEdgeIt& operator++() {
4.216 - SymListGraph::Parent::EdgeIt::operator++();
4.217 - return *this;
4.218 - }
4.219 -
4.220 - operator SymEdge() const {
4.221 - return SymEdge
4.222 - (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
4.223 - }
4.224 - bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
4.225 - bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
4.226 - bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
4.227 - };
4.228 -
4.229 - class EdgeIt {
4.230 - SymEdgeIt it;
4.231 - bool fw;
4.232 - public:
4.233 - EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
4.234 - EdgeIt (Invalid i) : it(i) { }
4.235 - EdgeIt(const SymListGraph& g, Edge e)
4.236 - : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
4.237 - EdgeIt() { }
4.238 - EdgeIt& operator++() {
4.239 - fw = !fw;
4.240 - if (fw) ++it;
4.241 - return *this;
4.242 - }
4.243 - operator Edge() const {
4.244 - if (it == INVALID) return INVALID;
4.245 - return fw ? forward(it) : backward(it);
4.246 - }
4.247 - bool operator==(const Edge i) const {return Edge(*this) == i;}
4.248 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
4.249 - bool operator<(const Edge i) const {return Edge(*this) < i;}
4.250 -
4.251 - };
4.252 -
4.253 - ///Number of nodes.
4.254 - int nodeNum() const { return Parent::nodeNum(); }
4.255 - ///Number of edges.
4.256 - int edgeNum() const { return 2*Parent::edgeNum(); }
4.257 - ///Number of symmetric edges.
4.258 - int symEdgeNum() const { return Parent::edgeNum(); }
4.259 -
4.260 - ///Set the expected maximum number of edges.
4.261 -
4.262 - ///With this function, it is possible to set the expected number of edges.
4.263 - ///The use of this fasten the building of the graph and makes
4.264 - ///it possible to avoid the superfluous memory allocation.
4.265 - void reserveSymEdge(int n) { Parent::reserveEdge(n); };
4.266 -
4.267 - /// Maximum node ID.
4.268 -
4.269 - /// Maximum node ID.
4.270 - ///\sa id(Node)
4.271 - int maxNodeId() const { return Parent::maxNodeId(); }
4.272 - /// Maximum edge ID.
4.273 -
4.274 - /// Maximum edge ID.
4.275 - ///\sa id(Edge)
4.276 - int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
4.277 - /// Maximum symmetric edge ID.
4.278 -
4.279 - /// Maximum symmetric edge ID.
4.280 - ///\sa id(SymEdge)
4.281 - int maxSymEdgeId() const { return Parent::maxEdgeId(); }
4.282 -
4.283 -
4.284 - Node tail(Edge e) const {
4.285 - return (e.id & 1) == 0 ?
4.286 - Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
4.287 - }
4.288 -
4.289 - Node head(Edge e) const {
4.290 - return (e.id & 1) == 0 ?
4.291 - Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
4.292 - }
4.293 -
4.294 - Node tail(SymEdge e) const {
4.295 - return Parent::tail(e);
4.296 - }
4.297 -
4.298 - Node head(SymEdge e) const {
4.299 - return Parent::head(e);
4.300 - }
4.301 -
4.302 - NodeIt& first(NodeIt& v) const {
4.303 - v=NodeIt(*this); return v; }
4.304 - EdgeIt& first(EdgeIt& e) const {
4.305 - e=EdgeIt(*this); return e; }
4.306 - SymEdgeIt& first(SymEdgeIt& e) const {
4.307 - e=SymEdgeIt(*this); return e; }
4.308 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
4.309 - e=OutEdgeIt(*this,v); return e; }
4.310 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
4.311 - e=InEdgeIt(*this,v); return e; }
4.312 -
4.313 - /// Node ID.
4.314 -
4.315 - /// The ID of a valid Node is a nonnegative integer not greater than
4.316 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
4.317 - /// and the greatest node ID can be actually less then \ref maxNodeId().
4.318 - ///
4.319 - /// The ID of the \ref INVALID node is -1.
4.320 - ///\return The ID of the node \c v.
4.321 - static int id(Node v) { return Parent::id(v); }
4.322 - /// Edge ID.
4.323 -
4.324 - /// The ID of a valid Edge is a nonnegative integer not greater than
4.325 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
4.326 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
4.327 - ///
4.328 - /// The ID of the \ref INVALID edge is -1.
4.329 - ///\return The ID of the edge \c e.
4.330 - static int id(Edge e) { return e.id; }
4.331 -
4.332 - /// The ID of a valid SymEdge is a nonnegative integer not greater than
4.333 - /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
4.334 - /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
4.335 - ///
4.336 - /// The ID of the \ref INVALID symmetric edge is -1.
4.337 - ///\return The ID of the edge \c e.
4.338 - static int id(SymEdge e) { return Parent::id(e); }
4.339 -
4.340 - /// Adds a new node to the graph.
4.341 -
4.342 - /// \warning It adds the new node to the front of the list.
4.343 - /// (i.e. the lastly added node becomes the first.)
4.344 - Node addNode() {
4.345 - return Parent::addNode();
4.346 - }
4.347 -
4.348 - SymEdge addEdge(Node u, Node v) {
4.349 - SymEdge se = Parent::addEdge(u, v);
4.350 - edge_maps.add(forward(se));
4.351 - edge_maps.add(backward(se));
4.352 - return se;
4.353 - }
4.354 -
4.355 - /// Finds an edge between two nodes.
4.356 -
4.357 - /// Finds an edge from node \c u to node \c v.
4.358 - ///
4.359 - /// If \c prev is \ref INVALID (this is the default value), then
4.360 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
4.361 - /// the next edge from \c u to \c v after \c prev.
4.362 - /// \return The found edge or INVALID if there is no such an edge.
4.363 - Edge findEdge(Node u, Node v, Edge prev = INVALID)
4.364 - {
4.365 - if (prev == INVALID || id(prev) & 1 == 0) {
4.366 - SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
4.367 - if (se != INVALID) return forward(se);
4.368 - } else {
4.369 - SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
4.370 - if (se != INVALID) return backward(se);
4.371 - }
4.372 - return INVALID;
4.373 - }
4.374 -
4.375 -// /// Finds an symmetric edge between two nodes.
4.376 -
4.377 -// /// Finds an symmetric edge from node \c u to node \c v.
4.378 -// ///
4.379 -// /// If \c prev is \ref INVALID (this is the default value), then
4.380 -// /// It finds the first edge from \c u to \c v. Otherwise it looks for
4.381 -// /// the next edge from \c u to \c v after \c prev.
4.382 -// /// \return The found edge or INVALID if there is no such an edge.
4.383 -
4.384 -// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
4.385 -// {
4.386 -// if (prev == INVALID || id(prev) & 1 == 0) {
4.387 -// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
4.388 -// if (se != INVALID) return se;
4.389 -// } else {
4.390 -// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
4.391 -// if (se != INVALID) return se;
4.392 -// }
4.393 -// return INVALID;
4.394 -// }
4.395 -
4.396 - public:
4.397 -
4.398 - void erase(Node n) {
4.399 - for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
4.400 - edge_maps.erase(it);
4.401 - edge_maps.erase(opposite(it));
4.402 - }
4.403 - Parent::erase(n);
4.404 - }
4.405 -
4.406 - void erase(SymEdge e) {
4.407 - edge_maps.erase(forward(e));
4.408 - edge_maps.erase(backward(e));
4.409 - Parent::erase(e);
4.410 - };
4.411 -
4.412 - void clear() {
4.413 - edge_maps.clear();
4.414 - Parent::clear();
4.415 - }
4.416 -
4.417 - static Edge opposite(Edge e) {
4.418 - return Edge(id(e) ^ 1);
4.419 - }
4.420 -
4.421 - static Edge forward(SymEdge e) {
4.422 - return Edge(id(e) << 1);
4.423 - }
4.424 -
4.425 - static Edge backward(SymEdge e) {
4.426 - return Edge((id(e) << 1) | 1);
4.427 - }
4.428 -
4.429 - };
4.430
4.431 ///A graph class containing only nodes.
4.432
5.1 --- a/src/hugo/map_bits.h Wed Sep 29 10:35:35 2004 +0000
5.2 +++ b/src/hugo/map_bits.h Wed Sep 29 14:02:14 2004 +0000
5.3 @@ -54,10 +54,10 @@
5.4 template <typename Graph>
5.5 struct KeyInfo<Graph, typename Graph::SymEdgeIt> {
5.6 static int maxId(const Graph& graph) {
5.7 - return graph.maxSymEdgeId();
5.8 + return graph.maxEdgeId() >> 1;
5.9 }
5.10 - static int id(const Graph& graph, const typename Graph::SymEdge& edge) {
5.11 - return graph.id(edge);
5.12 + static int id(const Graph& graph, const typename Graph::Edge& edge) {
5.13 + return graph.id(edge) >> 1;
5.14 }
5.15 };
5.16
6.1 --- a/src/hugo/map_defines.h Wed Sep 29 10:35:35 2004 +0000
6.2 +++ b/src/hugo/map_defines.h Wed Sep 29 14:02:14 2004 +0000
6.3 @@ -114,7 +114,8 @@
6.4 /** This macro creates MapRegistry for Symmetric Edge Maps.
6.5 */
6.6 #define CREATE_SYM_EDGE_MAP_REGISTRY \
6.7 -typedef MapRegistry<Graph, SymEdge, SymEdgeIt> SymEdgeMapRegistry; \
6.8 +typedef SymEdgeIt<Graph, Edge, EdgeIt> SymEdgeIt; \
6.9 +typedef MapRegistry<Graph, Edge, SymEdgeIt> SymEdgeMapRegistry; \
6.10 mutable SymEdgeMapRegistry sym_edge_maps;
6.11
6.12
6.13 @@ -126,9 +127,9 @@
6.14 */
6.15 #define CREATE_SYM_EDGE_MAP(DynMap) \
6.16 template <typename Value> \
6.17 -class SymEdgeMap : public DynMap<SymEdgeMapRegistry, Value> { \
6.18 +class SymEdgeMap : public SymMap<DynMap, SymEdgeMapRegistry, Value> { \
6.19 public: \
6.20 -typedef DynMap<SymEdgeMapRegistry, Value> Parent; \
6.21 +typedef SymMap<DynMap, SymEdgeMapRegistry, Value> Parent; \
6.22 \
6.23 SymEdgeMap(const typename Parent::Graph& g) \
6.24 : Parent(g, g.sym_edge_maps) {} \
7.1 --- a/src/hugo/map_registry.h Wed Sep 29 10:35:35 2004 +0000
7.2 +++ b/src/hugo/map_registry.h Wed Sep 29 14:02:14 2004 +0000
7.3 @@ -252,7 +252,7 @@
7.4 /**
7.5 * Notify all the registered maps about a Key added.
7.6 */
7.7 - void add(const KeyType& key) {
7.8 + void add(KeyType& key) {
7.9 typename Container::iterator it;
7.10 for (it = container.begin(); it != container.end(); ++it) {
7.11 (*it)->add(key);
7.12 @@ -262,7 +262,7 @@
7.13 /**
7.14 * Notify all the registered maps about a Key erased.
7.15 */
7.16 - void erase(const KeyType& key) {
7.17 + void erase(KeyType& key) {
7.18 typename Container::iterator it;
7.19 for (it = container.begin(); it != container.end(); ++it) {
7.20 (*it)->erase(key);
8.1 --- a/src/hugo/skeletons/sym_graph.h Wed Sep 29 10:35:35 2004 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,653 +0,0 @@
8.4 -/* -*- C++ -*-
8.5 - * src/hugo/skeletons/graph.h - Part of HUGOlib, a generic C++ optimization library
8.6 - *
8.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
8.9 - *
8.10 - * Permission to use, modify and distribute this software is granted
8.11 - * provided that this copyright notice appears in all copies. For
8.12 - * precise terms see the accompanying LICENSE file.
8.13 - *
8.14 - * This software is provided "AS IS" with no warranty of any kind,
8.15 - * express or implied, and with no claim as to its suitability for any
8.16 - * purpose.
8.17 - *
8.18 - */
8.19 -
8.20 -#ifndef HUGO_SKELETON_SYM_GRAPH_H
8.21 -#define HUGO_SKELETON_SYM_GRAPH_H
8.22 -
8.23 -///\ingroup skeletons
8.24 -///\file
8.25 -///\brief Declaration of SymGraph.
8.26 -
8.27 -#include <hugo/invalid.h>
8.28 -#include <hugo/skeletons/graph.h>
8.29 -#include <hugo/skeletons/maps.h>
8.30 -
8.31 -namespace hugo {
8.32 - namespace skeleton {
8.33 -
8.34 - /// \addtogroup skeletons
8.35 - /// @{
8.36 -
8.37 - /// An empty static graph class.
8.38 -
8.39 - /// This class provides all the common features of a symmetric
8.40 - /// graph structure, however completely without implementations and
8.41 - /// real data structures behind the interface.
8.42 - /// All graph algorithms should compile with this class, but it will not
8.43 - /// run properly, of course.
8.44 - ///
8.45 - /// It can be used for checking the interface compatibility,
8.46 - /// or it can serve as a skeleton of a new symmetric graph structure.
8.47 - ///
8.48 - /// Also, you will find here the full documentation of a certain graph
8.49 - /// feature, the documentation of a real symmetric graph imlementation
8.50 - /// like @ref SymListGraph or
8.51 - /// @ref hugo::SymSmartGraph will just refer to this structure.
8.52 - class StaticSymGraph
8.53 - {
8.54 - public:
8.55 - /// Defalult constructor.
8.56 -
8.57 - /// Defalult constructor.
8.58 - ///
8.59 - StaticSymGraph() { }
8.60 - ///Copy consructor.
8.61 -
8.62 -// ///\todo It is not clear, what we expect from a copy constructor.
8.63 -// ///E.g. How to assign the nodes/edges to each other? What about maps?
8.64 -// StaticGraph(const StaticGraph& g) { }
8.65 -
8.66 - /// The base type of node iterators,
8.67 - /// or in other words, the trivial node iterator.
8.68 -
8.69 - /// This is the base type of each node iterator,
8.70 - /// thus each kind of node iterator converts to this.
8.71 - /// More precisely each kind of node iterator should be inherited
8.72 - /// from the trivial node iterator.
8.73 - class Node {
8.74 - public:
8.75 - /// Default constructor
8.76 -
8.77 - /// @warning The default constructor sets the iterator
8.78 - /// to an undefined value.
8.79 - Node() { }
8.80 - /// Copy constructor.
8.81 -
8.82 - /// Copy constructor.
8.83 - ///
8.84 - Node(const Node&) { }
8.85 -
8.86 - /// Invalid constructor \& conversion.
8.87 -
8.88 - /// This constructor initializes the iterator to be invalid.
8.89 - /// \sa Invalid for more details.
8.90 - Node(Invalid) { }
8.91 - /// Equality operator
8.92 -
8.93 - /// Two iterators are equal if and only if they point to the
8.94 - /// same object or both are invalid.
8.95 - bool operator==(Node) const { return true; }
8.96 -
8.97 - /// Inequality operator
8.98 -
8.99 - /// \sa operator==(Node n)
8.100 - ///
8.101 - bool operator!=(Node) const { return true; }
8.102 -
8.103 - ///Comparison operator.
8.104 -
8.105 - ///This is a strict ordering between the nodes.
8.106 - ///
8.107 - ///This ordering can be different from the order in which NodeIt
8.108 - ///goes through the nodes.
8.109 - ///\todo Possibly we don't need it.
8.110 - bool operator<(Node) const { return true; }
8.111 - };
8.112 -
8.113 - /// This iterator goes through each node.
8.114 -
8.115 - /// This iterator goes through each node.
8.116 - /// Its usage is quite simple, for example you can count the number
8.117 - /// of nodes in graph \c g of type \c Graph like this:
8.118 - /// \code
8.119 - /// int count=0;
8.120 - /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
8.121 - /// \endcode
8.122 - class NodeIt : public Node {
8.123 - public:
8.124 - /// Default constructor
8.125 -
8.126 - /// @warning The default constructor sets the iterator
8.127 - /// to an undefined value.
8.128 - NodeIt() { }
8.129 - /// Copy constructor.
8.130 -
8.131 - /// Copy constructor.
8.132 - ///
8.133 - NodeIt(const NodeIt&) { }
8.134 - /// Invalid constructor \& conversion.
8.135 -
8.136 - /// Initialize the iterator to be invalid.
8.137 - /// \sa Invalid for more details.
8.138 - NodeIt(Invalid) { }
8.139 - /// Sets the iterator to the first node.
8.140 -
8.141 - /// Sets the iterator to the first node of \c g.
8.142 - ///
8.143 - NodeIt(const StaticSymGraph& g) { }
8.144 - /// Node -> NodeIt conversion.
8.145 -
8.146 - /// Sets the iterator to the node of \c g pointed by the trivial
8.147 - /// iterator n.
8.148 - /// This feature necessitates that each time we
8.149 - /// iterate the edge-set, the iteration order is the same.
8.150 - NodeIt(const StaticSymGraph& g, const Node& n) { }
8.151 - /// Next node.
8.152 -
8.153 - /// Assign the iterator to the next node.
8.154 - ///
8.155 - NodeIt& operator++() { return *this; }
8.156 - };
8.157 -
8.158 -
8.159 - /// The base type of the symmetric edge iterators.
8.160 -
8.161 - /// The base type of the symmetric edge iterators.
8.162 - ///
8.163 - class SymEdge {
8.164 - public:
8.165 - /// Default constructor
8.166 -
8.167 - /// @warning The default constructor sets the iterator
8.168 - /// to an undefined value.
8.169 - SymEdge() { }
8.170 - /// Copy constructor.
8.171 -
8.172 - /// Copy constructor.
8.173 - ///
8.174 - SymEdge(const SymEdge&) { }
8.175 - /// Initialize the iterator to be invalid.
8.176 -
8.177 - /// Initialize the iterator to be invalid.
8.178 - ///
8.179 - SymEdge(Invalid) { }
8.180 - /// Equality operator
8.181 -
8.182 - /// Two iterators are equal if and only if they point to the
8.183 - /// same object or both are invalid.
8.184 - bool operator==(SymEdge) const { return true; }
8.185 - /// Inequality operator
8.186 -
8.187 - /// \sa operator==(Node n)
8.188 - ///
8.189 - bool operator!=(SymEdge) const { return true; }
8.190 - ///Comparison operator.
8.191 -
8.192 - ///This is a strict ordering between the nodes.
8.193 - ///
8.194 - ///This ordering can be different from the order in which NodeIt
8.195 - ///goes through the nodes.
8.196 - ///\todo Possibly we don't need it.
8.197 - bool operator<(SymEdge) const { return true; }
8.198 - };
8.199 -
8.200 -
8.201 - /// The base type of the edge iterators.
8.202 -
8.203 - /// The base type of the edge iterators.
8.204 - ///
8.205 - class Edge : public SymEdge {
8.206 - public:
8.207 - /// Default constructor
8.208 -
8.209 - /// @warning The default constructor sets the iterator
8.210 - /// to an undefined value.
8.211 - Edge() { }
8.212 - /// Copy constructor.
8.213 -
8.214 - /// Copy constructor.
8.215 - ///
8.216 - Edge(const Edge&) { }
8.217 - /// Initialize the iterator to be invalid.
8.218 -
8.219 - /// Initialize the iterator to be invalid.
8.220 - ///
8.221 - Edge(Invalid) { }
8.222 - /// Equality operator
8.223 -
8.224 - /// Two iterators are equal if and only if they point to the
8.225 - /// same object or both are invalid.
8.226 - bool operator==(Edge) const { return true; }
8.227 - /// Inequality operator
8.228 -
8.229 - /// \sa operator==(Node n)
8.230 - ///
8.231 - bool operator!=(Edge) const { return true; }
8.232 - ///Comparison operator.
8.233 -
8.234 - ///This is a strict ordering between the nodes.
8.235 - ///
8.236 - ///This ordering can be different from the order in which NodeIt
8.237 - ///goes through the nodes.
8.238 - ///\todo Possibly we don't need it.
8.239 - bool operator<(Edge) const { return true; }
8.240 - };
8.241 -
8.242 - /// This iterator goes trough the outgoing edges of a node.
8.243 -
8.244 - /// This iterator goes trough the \e outgoing edges of a certain node
8.245 - /// of a graph.
8.246 - /// Its usage is quite simple, for example you can count the number
8.247 - /// of outgoing edges of a node \c n
8.248 - /// in graph \c g of type \c Graph as follows.
8.249 - /// \code
8.250 - /// int count=0;
8.251 - /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
8.252 - /// \endcode
8.253 -
8.254 - class OutEdgeIt : public Edge {
8.255 - public:
8.256 - /// Default constructor
8.257 -
8.258 - /// @warning The default constructor sets the iterator
8.259 - /// to an undefined value.
8.260 - OutEdgeIt() { }
8.261 - /// Copy constructor.
8.262 -
8.263 - /// Copy constructor.
8.264 - ///
8.265 - OutEdgeIt(const OutEdgeIt&) { }
8.266 - /// Initialize the iterator to be invalid.
8.267 -
8.268 - /// Initialize the iterator to be invalid.
8.269 - ///
8.270 - OutEdgeIt(Invalid) { }
8.271 - /// This constructor sets the iterator to first outgoing edge.
8.272 -
8.273 - /// This constructor set the iterator to the first outgoing edge of
8.274 - /// node
8.275 - ///@param n the node
8.276 - ///@param g the graph
8.277 - OutEdgeIt(const StaticSymGraph& g, const Node& n) { }
8.278 - /// Edge -> OutEdgeIt conversion
8.279 -
8.280 - /// Sets the iterator to the value of the trivial iterator \c e.
8.281 - /// This feature necessitates that each time we
8.282 - /// iterate the edge-set, the iteration order is the same.
8.283 - OutEdgeIt(const StaticSymGraph& g, const Edge& e) { }
8.284 - ///Next outgoing edge
8.285 -
8.286 - /// Assign the iterator to the next
8.287 - /// outgoing edge of the corresponding node.
8.288 - OutEdgeIt& operator++() { return *this; }
8.289 - };
8.290 -
8.291 - /// This iterator goes trough the incoming edges of a node.
8.292 -
8.293 - /// This iterator goes trough the \e incoming edges of a certain node
8.294 - /// of a graph.
8.295 - /// Its usage is quite simple, for example you can count the number
8.296 - /// of outgoing edges of a node \c n
8.297 - /// in graph \c g of type \c Graph as follows.
8.298 - /// \code
8.299 - /// int count=0;
8.300 - /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
8.301 - /// \endcode
8.302 -
8.303 - class InEdgeIt : public Edge {
8.304 - public:
8.305 - /// Default constructor
8.306 -
8.307 - /// @warning The default constructor sets the iterator
8.308 - /// to an undefined value.
8.309 - InEdgeIt() { }
8.310 - /// Copy constructor.
8.311 -
8.312 - /// Copy constructor.
8.313 - ///
8.314 - InEdgeIt(const InEdgeIt&) { }
8.315 - /// Initialize the iterator to be invalid.
8.316 -
8.317 - /// Initialize the iterator to be invalid.
8.318 - ///
8.319 - InEdgeIt(Invalid) { }
8.320 - /// This constructor sets the iterator to first incoming edge.
8.321 -
8.322 - /// This constructor set the iterator to the first incoming edge of
8.323 - /// node
8.324 - ///@param n the node
8.325 - ///@param g the graph
8.326 - InEdgeIt(const StaticSymGraph& g, const Node& n) { }
8.327 - /// Edge -> InEdgeIt conversion
8.328 -
8.329 - /// Sets the iterator to the value of the trivial iterator \c e.
8.330 - /// This feature necessitates that each time we
8.331 - /// iterate the edge-set, the iteration order is the same.
8.332 - InEdgeIt(const StaticSymGraph& g, const Edge& n) { }
8.333 - /// Next incoming edge
8.334 -
8.335 - /// Assign the iterator to the next inedge of the corresponding node.
8.336 - ///
8.337 - InEdgeIt& operator++() { return *this; }
8.338 - };
8.339 - /// This iterator goes through each symmetric edge.
8.340 -
8.341 - /// This iterator goes through each symmetric edge of a graph.
8.342 - /// Its usage is quite simple, for example you can count the number
8.343 - /// of symmetric edges in a graph \c g of type \c Graph as follows:
8.344 - /// \code
8.345 - /// int count=0;
8.346 - /// for(Graph::SymEdgeIt e(g); e!=INVALID; ++e) ++count;
8.347 - /// \endcode
8.348 - class SymEdgeIt : public SymEdge {
8.349 - public:
8.350 - /// Default constructor
8.351 -
8.352 - /// @warning The default constructor sets the iterator
8.353 - /// to an undefined value.
8.354 - SymEdgeIt() { }
8.355 - /// Copy constructor.
8.356 -
8.357 - /// Copy constructor.
8.358 - ///
8.359 - SymEdgeIt(const SymEdgeIt&) { }
8.360 - /// Initialize the iterator to be invalid.
8.361 -
8.362 - /// Initialize the iterator to be invalid.
8.363 - ///
8.364 - SymEdgeIt(Invalid) { }
8.365 - /// This constructor sets the iterator to first edge.
8.366 -
8.367 - /// This constructor set the iterator to the first edge of
8.368 - /// node
8.369 - ///@param g the graph
8.370 - SymEdgeIt(const StaticSymGraph& g) { }
8.371 - /// Edge -> EdgeIt conversion
8.372 -
8.373 - /// Sets the iterator to the value of the trivial iterator \c e.
8.374 - /// This feature necessitates that each time we
8.375 - /// iterate the edge-set, the iteration order is the same.
8.376 - SymEdgeIt(const StaticSymGraph&, const SymEdge&) { }
8.377 - ///Next edge
8.378 -
8.379 - /// Assign the iterator to the next
8.380 - /// edge of the corresponding node.
8.381 - SymEdgeIt& operator++() { return *this; }
8.382 - };
8.383 - /// This iterator goes through each edge.
8.384 -
8.385 - /// This iterator goes through each edge of a graph.
8.386 - /// Its usage is quite simple, for example you can count the number
8.387 - /// of edges in a graph \c g of type \c Graph as follows:
8.388 - /// \code
8.389 - /// int count=0;
8.390 - /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
8.391 - /// \endcode
8.392 - class EdgeIt : public Edge {
8.393 - public:
8.394 - /// Default constructor
8.395 -
8.396 - /// @warning The default constructor sets the iterator
8.397 - /// to an undefined value.
8.398 - EdgeIt() { }
8.399 - /// Copy constructor.
8.400 -
8.401 - /// Copy constructor.
8.402 - ///
8.403 - EdgeIt(const EdgeIt&) { }
8.404 - /// Initialize the iterator to be invalid.
8.405 -
8.406 - /// Initialize the iterator to be invalid.
8.407 - ///
8.408 - EdgeIt(Invalid) { }
8.409 - /// This constructor sets the iterator to first edge.
8.410 -
8.411 - /// This constructor set the iterator to the first edge of
8.412 - /// node
8.413 - ///@param g the graph
8.414 - EdgeIt(const StaticSymGraph& g) { }
8.415 - /// Edge -> EdgeIt conversion
8.416 -
8.417 - /// Sets the iterator to the value of the trivial iterator \c e.
8.418 - /// This feature necessitates that each time we
8.419 - /// iterate the edge-set, the iteration order is the same.
8.420 - EdgeIt(const StaticSymGraph&, const Edge&) { }
8.421 - ///Next edge
8.422 -
8.423 - /// Assign the iterator to the next
8.424 - /// edge of the corresponding node.
8.425 - EdgeIt& operator++() { return *this; }
8.426 - };
8.427 -
8.428 - /// First node of the graph.
8.429 -
8.430 - /// \retval i the first node.
8.431 - /// \return the first node.
8.432 - ///
8.433 - NodeIt& first(NodeIt& i) const { return i; }
8.434 -
8.435 - /// The first incoming edge.
8.436 -
8.437 - /// The first incoming edge.
8.438 - ///
8.439 - InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
8.440 - /// The first outgoing edge.
8.441 -
8.442 - /// The first outgoing edge.
8.443 - ///
8.444 - OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
8.445 - /// The first edge of the Graph.
8.446 -
8.447 - /// The first edge of the Graph.
8.448 - ///
8.449 - EdgeIt& first(EdgeIt& i) const { return i; }
8.450 - /// The first symmetric edge of the Graph.
8.451 -
8.452 - /// The first symmetric edge of the Graph.
8.453 - ///
8.454 - SymEdgeIt& first(SymEdgeIt& i) const { return i; }
8.455 -
8.456 - ///Gives back the head node of an edge.
8.457 -
8.458 - ///Gives back the head node of an edge.
8.459 - ///
8.460 - Node head(Edge) const { return INVALID; }
8.461 - ///Gives back the tail node of an edge.
8.462 -
8.463 - ///Gives back the tail node of an edge.
8.464 - ///
8.465 - Node tail(Edge) const { return INVALID; }
8.466 -
8.467 - ///Gives back the first node of an symmetric edge.
8.468 -
8.469 - ///Gives back the first node of an symmetric edge.
8.470 - ///
8.471 - Node head(SymEdge) const { return INVALID; }
8.472 - ///Gives back the second node of an symmetric edge.
8.473 -
8.474 - ///Gives back the second node of an symmetric edge.
8.475 - ///
8.476 - Node tail(SymEdge) const { return INVALID; }
8.477 - ///Gives back the \e id of a node.
8.478 -
8.479 - ///\warning Not all graph structures provide this feature.
8.480 - ///
8.481 - ///\todo Should each graph provide \c id?
8.482 - int id(const Node&) const { return 0; }
8.483 - ///Gives back the \e id of an edge.
8.484 -
8.485 - ///\warning Not all graph structures provide this feature.
8.486 - ///
8.487 - ///\todo Should each graph provide \c id?
8.488 - int id(const Edge&) const { return 0; }
8.489 -
8.490 - ///\warning Not all graph structures provide this feature.
8.491 - ///
8.492 - ///\todo Should each graph provide \c id?
8.493 - int id(const SymEdge&) const { return 0; }
8.494 -
8.495 - ///\e
8.496 -
8.497 - ///\todo Should it be in the concept?
8.498 - ///
8.499 - int nodeNum() const { return 0; }
8.500 - ///\e
8.501 -
8.502 - ///\todo Should it be in the concept?
8.503 - ///
8.504 - int edgeNum() const { return 0; }
8.505 -
8.506 - ///\todo Should it be in the concept?
8.507 - ///
8.508 - int symEdgeNum() const { return 0; }
8.509 -
8.510 -
8.511 - /// Gives back the forward directed edge of the symmetric edge.
8.512 - Edge forward(SymEdge) const {return INVALID;}
8.513 -
8.514 - /// Gives back the backward directed edge of the symmetric edge.
8.515 - Edge backward(SymEdge) const {return INVALID;};
8.516 -
8.517 - /// Gives back the opposite of the edge.
8.518 - Edge opposite(Edge) const {return INVALID;}
8.519 -
8.520 - ///Reference map of the nodes to type \c T.
8.521 - /// \ingroup skeletons
8.522 - ///Reference map of the nodes to type \c T.
8.523 - /// \sa Reference
8.524 - /// \warning Making maps that can handle bool type (NodeMap<bool>)
8.525 - /// needs some extra attention!
8.526 - template<class T> class NodeMap : public ReferenceMap< Node, T >
8.527 - {
8.528 - public:
8.529 -
8.530 - ///\e
8.531 - NodeMap(const StaticSymGraph&) { }
8.532 - ///\e
8.533 - NodeMap(const StaticSymGraph&, T) { }
8.534 -
8.535 - ///Copy constructor
8.536 - template<typename TT> NodeMap(const NodeMap<TT>&) { }
8.537 - ///Assignment operator
8.538 - template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
8.539 - { return *this; }
8.540 - };
8.541 -
8.542 - ///Reference map of the edges to type \c T.
8.543 -
8.544 - /// \ingroup skeletons
8.545 - ///Reference map of the edges to type \c T.
8.546 - /// \sa Reference
8.547 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
8.548 - /// needs some extra attention!
8.549 - template<class T> class EdgeMap
8.550 - : public ReferenceMap<Edge,T>
8.551 - {
8.552 - public:
8.553 -
8.554 - ///\e
8.555 - EdgeMap(const StaticSymGraph&) { }
8.556 - ///\e
8.557 - EdgeMap(const StaticSymGraph&, T) { }
8.558 -
8.559 - ///Copy constructor
8.560 - template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
8.561 - ///Assignment operator
8.562 - template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
8.563 - { return *this; }
8.564 - };
8.565 -
8.566 - ///Reference map of the edges to type \c T.
8.567 -
8.568 - /// \ingroup skeletons
8.569 - ///Reference map of the symmetric edges to type \c T.
8.570 - /// \sa Reference
8.571 - /// \warning Making maps that can handle bool type (EdgeMap<bool>)
8.572 - /// needs some extra attention!
8.573 - template<class T> class SymEdgeMap
8.574 - : public ReferenceMap<SymEdge,T>
8.575 - {
8.576 - public:
8.577 -
8.578 - ///\e
8.579 - SymEdgeMap(const StaticSymGraph&) { }
8.580 - ///\e
8.581 - SymEdgeMap(const StaticSymGraph&, T) { }
8.582 -
8.583 - ///Copy constructor
8.584 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT>&) { }
8.585 - ///Assignment operator
8.586 - template<typename TT> SymEdgeMap &operator=(const SymEdgeMap<TT>&)
8.587 - { return *this; }
8.588 - };
8.589 - };
8.590 -
8.591 -
8.592 -
8.593 - /// An empty non-static graph class.
8.594 -
8.595 - /// This class provides everything that \ref StaticGraph
8.596 - /// with additional functionality which enables to build a
8.597 - /// graph from scratch.
8.598 - class ExtendableSymGraph : public StaticSymGraph
8.599 - {
8.600 - public:
8.601 - /// Defalult constructor.
8.602 -
8.603 - /// Defalult constructor.
8.604 - ///
8.605 - ExtendableSymGraph() { }
8.606 - ///Add a new node to the graph.
8.607 -
8.608 - /// \return the new node.
8.609 - ///
8.610 - Node addNode() { return INVALID; }
8.611 - ///Add a new edge to the graph.
8.612 -
8.613 - ///Add a new symmetric edge to the graph with tail node \c t
8.614 - ///and head node \c h.
8.615 - ///\return the new edge.
8.616 - SymEdge addEdge(Node h, Node t) { return INVALID; }
8.617 -
8.618 - /// Resets the graph.
8.619 -
8.620 - /// This function deletes all edges and nodes of the graph.
8.621 - /// It also frees the memory allocated to store them.
8.622 - /// \todo It might belong to \ref ErasableGraph.
8.623 - void clear() { }
8.624 - };
8.625 -
8.626 - /// An empty erasable graph class.
8.627 -
8.628 - /// This class is an extension of \ref ExtendableGraph. It also makes it
8.629 - /// possible to erase edges or nodes.
8.630 - class ErasableSymGraph : public ExtendableSymGraph
8.631 - {
8.632 - public:
8.633 - /// Defalult constructor.
8.634 -
8.635 - /// Defalult constructor.
8.636 - ///
8.637 - ErasableSymGraph() { }
8.638 - /// Deletes a node.
8.639 -
8.640 - /// Deletes node \c n node.
8.641 - ///
8.642 - void erase(Node n) { }
8.643 - /// Deletes an edge.
8.644 -
8.645 - /// Deletes edge \c e edge.
8.646 - ///
8.647 - void erase(SymEdge e) { }
8.648 - };
8.649 -
8.650 - // @}
8.651 - } //namespace skeleton
8.652 -} //namespace hugo
8.653 -
8.654 -
8.655 -
8.656 -#endif // HUGO_SKELETON_GRAPH_H
9.1 --- a/src/hugo/smart_graph.h Wed Sep 29 10:35:35 2004 +0000
9.2 +++ b/src/hugo/smart_graph.h Wed Sep 29 14:02:14 2004 +0000
9.3 @@ -27,6 +27,8 @@
9.4 #include <hugo/invalid.h>
9.5
9.6 #include <hugo/array_map.h>
9.7 +#include <hugo/sym_map.h>
9.8 +
9.9 #include <hugo/map_registry.h>
9.10
9.11 #include <hugo/map_defines.h>
9.12 @@ -296,381 +298,6 @@
9.13
9.14 };
9.15
9.16 -
9.17 -
9.18 - class SymSmartGraph : public SmartGraph {
9.19 - typedef SmartGraph Parent;
9.20 - public:
9.21 -
9.22 - typedef SymSmartGraph Graph;
9.23 -
9.24 - typedef SmartGraph::Node Node;
9.25 - typedef SmartGraph::NodeIt NodeIt;
9.26 -
9.27 - class SymEdge;
9.28 - class SymEdgeIt;
9.29 -
9.30 - class Edge;
9.31 - class EdgeIt;
9.32 - class OutEdgeIt;
9.33 - class InEdgeIt;
9.34 -
9.35 - template <typename Value>
9.36 - class NodeMap : public Parent::NodeMap<Value> {
9.37 - public:
9.38 - NodeMap(const SymSmartGraph& g)
9.39 - : SymSmartGraph::Parent::NodeMap<Value>(g) {}
9.40 - NodeMap(const SymSmartGraph& g, Value v)
9.41 - : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
9.42 - template<typename TT>
9.43 - NodeMap(const NodeMap<TT>& copy)
9.44 - : SymSmartGraph::Parent::NodeMap<Value>(copy) { }
9.45 - };
9.46 -
9.47 - template <typename Value>
9.48 - class SymEdgeMap : public Parent::EdgeMap<Value> {
9.49 - public:
9.50 - typedef SymEdge KeyType;
9.51 -
9.52 - SymEdgeMap(const SymSmartGraph& g)
9.53 - : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
9.54 - SymEdgeMap(const SymSmartGraph& g, Value v)
9.55 - : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
9.56 - template<typename TT>
9.57 - SymEdgeMap(const SymEdgeMap<TT>& copy)
9.58 - : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
9.59 -
9.60 - };
9.61 -
9.62 - // Create edge map registry.
9.63 - CREATE_EDGE_MAP_REGISTRY;
9.64 - // Create edge maps.
9.65 - CREATE_EDGE_MAP(ArrayMap);
9.66 -
9.67 - class Edge {
9.68 - friend class SymSmartGraph;
9.69 - friend class SymSmartGraph::EdgeIt;
9.70 - friend class SymSmartGraph::OutEdgeIt;
9.71 - friend class SymSmartGraph::InEdgeIt;
9.72 -
9.73 - protected:
9.74 - int id;
9.75 -
9.76 - Edge(int pid) { id = pid; }
9.77 -
9.78 - public:
9.79 - /// An Edge with id \c n.
9.80 -
9.81 - Edge() { }
9.82 - Edge (Invalid) { id = -1; }
9.83 -
9.84 - operator SymEdge(){ return SymEdge(id >> 1);}
9.85 -
9.86 - bool operator==(const Edge i) const {return id == i.id;}
9.87 - bool operator!=(const Edge i) const {return id != i.id;}
9.88 - bool operator<(const Edge i) const {return id < i.id;}
9.89 - // ///Validity check
9.90 - // operator bool() { return n!=-1; }
9.91 - };
9.92 -
9.93 - class SymEdge : public SmartGraph::Edge {
9.94 - friend class SymSmartGraph;
9.95 - friend class SymSmartGraph::Edge;
9.96 - typedef SmartGraph::Edge Parent;
9.97 -
9.98 - protected:
9.99 - SymEdge(int pid) : Parent(pid) {}
9.100 - public:
9.101 -
9.102 - SymEdge() { }
9.103 - SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
9.104 - SymEdge (Invalid) : Parent(INVALID) {}
9.105 -
9.106 - };
9.107 -
9.108 - class OutEdgeIt {
9.109 - Parent::OutEdgeIt out;
9.110 - Parent::InEdgeIt in;
9.111 - public:
9.112 - OutEdgeIt() {}
9.113 - OutEdgeIt(const SymSmartGraph& g, Edge e) {
9.114 - if ((e.id & 1) == 0) {
9.115 - out = Parent::OutEdgeIt(g, SymEdge(e));
9.116 - in = Parent::InEdgeIt(g, g.tail(e));
9.117 - } else {
9.118 - out = Parent::OutEdgeIt(INVALID);
9.119 - in = Parent::InEdgeIt(g, SymEdge(e));
9.120 - }
9.121 - }
9.122 - OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
9.123 -
9.124 - OutEdgeIt(const SymSmartGraph& g, const Node v)
9.125 - : out(g, v), in(g, v) {}
9.126 - OutEdgeIt &operator++() {
9.127 - if (out != INVALID) {
9.128 - ++out;
9.129 - } else {
9.130 - ++in;
9.131 - }
9.132 - return *this;
9.133 - }
9.134 -
9.135 - operator Edge() const {
9.136 - if (out == INVALID && in == INVALID) return INVALID;
9.137 - return out != INVALID ? forward(out) : backward(in);
9.138 - }
9.139 -
9.140 - bool operator==(const Edge i) const {return Edge(*this) == i;}
9.141 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
9.142 - bool operator<(const Edge i) const {return Edge(*this) < i;}
9.143 - };
9.144 -
9.145 - class InEdgeIt {
9.146 - Parent::OutEdgeIt out;
9.147 - Parent::InEdgeIt in;
9.148 - public:
9.149 - InEdgeIt() {}
9.150 - InEdgeIt(const SymSmartGraph& g, Edge e) {
9.151 - if ((e.id & 1) == 0) {
9.152 - out = Parent::OutEdgeIt(g, SymEdge(e));
9.153 - in = Parent::InEdgeIt(g, g.tail(e));
9.154 - } else {
9.155 - out = Parent::OutEdgeIt(INVALID);
9.156 - in = Parent::InEdgeIt(g, SymEdge(e));
9.157 - }
9.158 - }
9.159 - InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
9.160 -
9.161 - InEdgeIt(const SymSmartGraph& g, const Node v)
9.162 - : out(g, v), in(g, v) {}
9.163 -
9.164 - InEdgeIt &operator++() {
9.165 - if (out != INVALID) {
9.166 - ++out;
9.167 - } else {
9.168 - ++in;
9.169 - }
9.170 - return *this;
9.171 - }
9.172 -
9.173 - operator Edge() const {
9.174 - if (out == INVALID && in == INVALID) return INVALID;
9.175 - return out != INVALID ? backward(out) : forward(in);
9.176 - }
9.177 -
9.178 - bool operator==(const Edge i) const {return Edge(*this) == i;}
9.179 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
9.180 - bool operator<(const Edge i) const {return Edge(*this) < i;}
9.181 - };
9.182 -
9.183 - class SymEdgeIt : public Parent::EdgeIt {
9.184 -
9.185 - public:
9.186 - SymEdgeIt() {}
9.187 -
9.188 - SymEdgeIt(const SymSmartGraph& g)
9.189 - : SymSmartGraph::Parent::EdgeIt(g) {}
9.190 -
9.191 - SymEdgeIt(const SymSmartGraph& g, SymEdge e)
9.192 - : SymSmartGraph::Parent::EdgeIt(g, e) {}
9.193 -
9.194 - SymEdgeIt(Invalid i)
9.195 - : SymSmartGraph::Parent::EdgeIt(INVALID) {}
9.196 -
9.197 - SymEdgeIt& operator++() {
9.198 - SymSmartGraph::Parent::EdgeIt::operator++();
9.199 - return *this;
9.200 - }
9.201 -
9.202 - operator SymEdge() const {
9.203 - return SymEdge
9.204 - (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
9.205 - }
9.206 - bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
9.207 - bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
9.208 - bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
9.209 - };
9.210 -
9.211 - class EdgeIt {
9.212 - SymEdgeIt it;
9.213 - bool fw;
9.214 - public:
9.215 - EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
9.216 - EdgeIt (Invalid i) : it(i) { }
9.217 - EdgeIt(const SymSmartGraph& g, Edge e)
9.218 - : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
9.219 - EdgeIt() { }
9.220 - EdgeIt& operator++() {
9.221 - fw = !fw;
9.222 - if (fw) ++it;
9.223 - return *this;
9.224 - }
9.225 - operator Edge() const {
9.226 - if (it == INVALID) return INVALID;
9.227 - return fw ? forward(it) : backward(it);
9.228 - }
9.229 - bool operator==(const Edge i) const {return Edge(*this) == i;}
9.230 - bool operator!=(const Edge i) const {return Edge(*this) != i;}
9.231 - bool operator<(const Edge i) const {return Edge(*this) < i;}
9.232 -
9.233 - };
9.234 -
9.235 - ///Number of nodes.
9.236 - int nodeNum() const { return Parent::nodeNum(); }
9.237 - ///Number of edges.
9.238 - int edgeNum() const { return 2*Parent::edgeNum(); }
9.239 - ///Number of symmetric edges.
9.240 - int symEdgeNum() const { return Parent::edgeNum(); }
9.241 -
9.242 - /// Maximum node ID.
9.243 -
9.244 - /// Maximum node ID.
9.245 - ///\sa id(Node)
9.246 - int maxNodeId() const { return Parent::maxNodeId(); }
9.247 - /// Maximum edge ID.
9.248 -
9.249 - /// Maximum edge ID.
9.250 - ///\sa id(Edge)
9.251 - int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
9.252 - /// Maximum symmetric edge ID.
9.253 -
9.254 - /// Maximum symmetric edge ID.
9.255 - ///\sa id(SymEdge)
9.256 - int maxSymEdgeId() const { return Parent::maxEdgeId(); }
9.257 -
9.258 -
9.259 - Node tail(Edge e) const {
9.260 - return (e.id & 1) == 0 ?
9.261 - Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
9.262 - }
9.263 -
9.264 - Node head(Edge e) const {
9.265 - return (e.id & 1) == 0 ?
9.266 - Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
9.267 - }
9.268 -
9.269 - Node tail(SymEdge e) const {
9.270 - return Parent::tail(e);
9.271 - }
9.272 -
9.273 - Node head(SymEdge e) const {
9.274 - return Parent::head(e);
9.275 - }
9.276 -
9.277 - NodeIt& first(NodeIt& v) const {
9.278 - v=NodeIt(*this); return v; }
9.279 - EdgeIt& first(EdgeIt& e) const {
9.280 - e=EdgeIt(*this); return e; }
9.281 - SymEdgeIt& first(SymEdgeIt& e) const {
9.282 - e=SymEdgeIt(*this); return e; }
9.283 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
9.284 - e=OutEdgeIt(*this,v); return e; }
9.285 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
9.286 - e=InEdgeIt(*this,v); return e; }
9.287 -
9.288 - /// Node ID.
9.289 -
9.290 - /// The ID of a valid Node is a nonnegative integer not greater than
9.291 - /// \ref maxNodeId(). The range of the ID's is not surely continuous
9.292 - /// and the greatest node ID can be actually less then \ref maxNodeId().
9.293 - ///
9.294 - /// The ID of the \ref INVALID node is -1.
9.295 - ///\return The ID of the node \c v.
9.296 - static int id(Node v) { return Parent::id(v); }
9.297 - /// Edge ID.
9.298 -
9.299 - /// The ID of a valid Edge is a nonnegative integer not greater than
9.300 - /// \ref maxEdgeId(). The range of the ID's is not surely continuous
9.301 - /// and the greatest edge ID can be actually less then \ref maxEdgeId().
9.302 - ///
9.303 - /// The ID of the \ref INVALID edge is -1.
9.304 - ///\return The ID of the edge \c e.
9.305 - static int id(Edge e) { return e.id; }
9.306 -
9.307 - /// The ID of a valid SymEdge is a nonnegative integer not greater than
9.308 - /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
9.309 - /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
9.310 - ///
9.311 - /// The ID of the \ref INVALID symmetric edge is -1.
9.312 - ///\return The ID of the edge \c e.
9.313 - static int id(SymEdge e) { return Parent::id(e); }
9.314 -
9.315 - /// Adds a new node to the graph.
9.316 -
9.317 - /// \warning It adds the new node to the front of the list.
9.318 - /// (i.e. the lastly added node becomes the first.)
9.319 - Node addNode() {
9.320 - return Parent::addNode();
9.321 - }
9.322 -
9.323 - SymEdge addEdge(Node u, Node v) {
9.324 - SymEdge se = Parent::addEdge(u, v);
9.325 - edge_maps.add(forward(se));
9.326 - edge_maps.add(backward(se));
9.327 - return se;
9.328 - }
9.329 -
9.330 - /// Finds an edge between two nodes.
9.331 -
9.332 - /// Finds an edge from node \c u to node \c v.
9.333 - ///
9.334 - /// If \c prev is \ref INVALID (this is the default value), then
9.335 - /// It finds the first edge from \c u to \c v. Otherwise it looks for
9.336 - /// the next edge from \c u to \c v after \c prev.
9.337 - /// \return The found edge or INVALID if there is no such an edge.
9.338 - Edge findEdge(Node u, Node v, Edge prev = INVALID)
9.339 - {
9.340 - if (prev == INVALID || id(prev) & 1 == 0) {
9.341 - SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
9.342 - if (se != INVALID) return forward(se);
9.343 - } else {
9.344 - SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
9.345 - if (se != INVALID) return backward(se);
9.346 - }
9.347 - return INVALID;
9.348 - }
9.349 -
9.350 -// /// Finds an symmetric edge between two nodes.
9.351 -
9.352 -// /// Finds an symmetric edge from node \c u to node \c v.
9.353 -// ///
9.354 -// /// If \c prev is \ref INVALID (this is the default value), then
9.355 -// /// It finds the first edge from \c u to \c v. Otherwise it looks for
9.356 -// /// the next edge from \c u to \c v after \c prev.
9.357 -// /// \return The found edge or INVALID if there is no such an edge.
9.358 -
9.359 -// SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
9.360 -// {
9.361 -// if (prev == INVALID || id(prev) & 1 == 0) {
9.362 -// SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
9.363 -// if (se != INVALID) return se;
9.364 -// } else {
9.365 -// SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
9.366 -// if (se != INVALID) return se;
9.367 -// }
9.368 -// return INVALID;
9.369 -// }
9.370 -
9.371 - public:
9.372 -
9.373 - void clear() {
9.374 - edge_maps.clear();
9.375 - Parent::clear();
9.376 - }
9.377 -
9.378 - static Edge opposite(Edge e) {
9.379 - return Edge(id(e) ^ 1);
9.380 - }
9.381 -
9.382 - static Edge forward(SymEdge e) {
9.383 - return Edge(id(e) << 1);
9.384 - }
9.385 -
9.386 - static Edge backward(SymEdge e) {
9.387 - return Edge((id(e) << 1) | 1);
9.388 - }
9.389 -
9.390 - };
9.391 ///Graph for bidirectional edges.
9.392
9.393 ///The purpose of this graph structure is to handle graphs
9.394 @@ -691,7 +318,7 @@
9.395 ///it is not possible to delete edges or nodes from the graph.
9.396 //\sa SmartGraph.
9.397
9.398 - /* class SymSmartGraph : public SmartGraph
9.399 + class SymSmartGraph : public SmartGraph
9.400 {
9.401 public:
9.402 typedef SymSmartGraph Graph;
9.403 @@ -726,7 +353,7 @@
9.404 }
9.405
9.406
9.407 - };*/
9.408 + };
9.409
9.410 /// @}
9.411 } //namespace hugo
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/src/hugo/sym_map.h Wed Sep 29 14:02:14 2004 +0000
10.3 @@ -0,0 +1,144 @@
10.4 +/* -*- C++ -*-
10.5 + * src/hugo/sym_map.h - Part of HUGOlib, a generic C++ optimization library
10.6 + *
10.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
10.9 + *
10.10 + * Permission to use, modify and distribute this software is granted
10.11 + * provided that this copyright notice appears in all copies. For
10.12 + * precise terms see the accompanying LICENSE file.
10.13 + *
10.14 + * This software is provided "AS IS" with no warranty of any kind,
10.15 + * express or implied, and with no claim as to its suitability for any
10.16 + * purpose.
10.17 + *
10.18 + */
10.19 +
10.20 +#ifndef HUGO_SYM_MAP_H
10.21 +#define HUGO_SYM_MAP_H
10.22 +
10.23 +///\ingroup graphmaps
10.24 +///\file
10.25 +///\brief Graph maps that construates and destruates
10.26 +///their elements dynamically.
10.27 +
10.28 +namespace hugo {
10.29 +
10.30 +/// \addtogroup graphmaps
10.31 +/// @{
10.32 +
10.33 + /** The SymEdgeIt is wrapper class for the EdgeIt. It can be used to
10.34 + * iterate on the symmetric maps when all of the edge - reverse edge pair
10.35 + * has different parity.
10.36 + */
10.37 +
10.38 +
10.39 + template <typename Graph, typename Edge, typename EdgeIt>
10.40 + class SymEdgeIt : public EdgeIt {
10.41 + public:
10.42 +
10.43 + /** Default constructor.
10.44 + */
10.45 + SymEdgeIt()
10.46 + : EdgeIt() {}
10.47 +
10.48 + /** Graph initialized constructor.
10.49 + */
10.50 + SymEdgeIt(const Graph& graph)
10.51 + : EdgeIt(graph) {
10.52 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
10.53 + EdgeIt::operator++();
10.54 + }
10.55 + }
10.56 +
10.57 + /** Creating invelid SymEdgeIt.
10.58 + */
10.59 + SymEdgeIt(Invalid invalid)
10.60 + : EdgeIt(invalid) {}
10.61 +
10.62 + /** SymEdgeIt from the given Edge.
10.63 + */
10.64 + SymEdgeIt(const Graph& graph, const Edge& edge)
10.65 + : EdgeIt(graph, edge) {
10.66 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
10.67 + EdgeIt::operator++();
10.68 + }
10.69 + }
10.70 +
10.71 + /** Increase operator.
10.72 + */
10.73 + SymEdgeIt& operator++() {
10.74 + EdgeIt::operator++();
10.75 + while ( (EdgeIt::n & 1) && EdgeIt::n != -1) {
10.76 + EdgeIt::operator++();
10.77 + }
10.78 + return *this;
10.79 + }
10.80 + };
10.81 +
10.82 + /** The SymMap template class is graph map structure what
10.83 + * wraps an other map structure to use as symmetric map structure.
10.84 + *
10.85 + * The template parameter is the MapRegistry that the maps
10.86 + * will belong to and the ValueType.
10.87 + */
10.88 + template <template <typename, typename> class DynMap,
10.89 + typename MapRegistry, typename Value>
10.90 + class SymMap : public DynMap<MapRegistry, Value>{
10.91 +
10.92 + private:
10.93 +
10.94 + typedef DynMap<MapRegistry, Value> MapImpl;
10.95 +
10.96 + public:
10.97 +
10.98 + /// The graph type of the maps.
10.99 + typedef typename MapRegistry::Graph Graph;
10.100 +
10.101 + typedef typename MapImpl::KeyType KeyType;
10.102 +
10.103 + public:
10.104 +
10.105 +
10.106 + /** Graph and Registry initialized map constructor.
10.107 + */
10.108 + SymMap(const Graph& g, MapRegistry& r) : MapImpl(g, r) {}
10.109 +
10.110 + /** Constructor to use default value to initialize the map.
10.111 + */
10.112 + SymMap(const Graph& g, MapRegistry& r, const Value& v)
10.113 + : MapImpl(g, r, v) {}
10.114 +
10.115 + /** Constructor to copy a map of the same map type.
10.116 + */
10.117 + SymMap(const SymMap& copy)
10.118 + : MapImpl(static_cast<const MapImpl&>(copy)) {}
10.119 +
10.120 + /** Assign operator to copy a map of the same map type.
10.121 + */
10.122 + SymMap& operator=(const SymMap& copy) {
10.123 + MapImpl::operator=(static_cast<const MapImpl&>(copy));
10.124 + return *this;
10.125 + }
10.126 +
10.127 + /** Add a new key to the map. It called by the map registry.
10.128 + */
10.129 + void add(const KeyType& key) {
10.130 + int id = MapImpl::getGraph()->id(key);
10.131 + if (id & 1) return;
10.132 + MapImpl::add(key);
10.133 + }
10.134 +
10.135 + /** Erase a key from the map. It called by the map registry.
10.136 + */
10.137 + void erase(const KeyType& key) {
10.138 + int id = MapImpl::getGraph()->id(key);
10.139 + if (id & 1) return;
10.140 + MapImpl::add(key);
10.141 + }
10.142 + };
10.143 +
10.144 + /// @}
10.145 +}
10.146 +
10.147 +#endif
11.1 --- a/src/hugo/tight_edge_filter_map.h Wed Sep 29 10:35:35 2004 +0000
11.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
11.3 @@ -1,63 +0,0 @@
11.4 -/* -*- C++ -*-
11.5 - * src/hugo/tight_edge_filter_map.h - Part of HUGOlib, a generic C++ optimization library
11.6 - *
11.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
11.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
11.9 - *
11.10 - * Permission to use, modify and distribute this software is granted
11.11 - * provided that this copyright notice appears in all copies. For
11.12 - * precise terms see the accompanying LICENSE file.
11.13 - *
11.14 - * This software is provided "AS IS" with no warranty of any kind,
11.15 - * express or implied, and with no claim as to its suitability for any
11.16 - * purpose.
11.17 - *
11.18 - */
11.19 -
11.20 -#ifndef HUGO_TIGHT_EDGE_FILTER_MAP_H
11.21 -#define HUGO_TIGHT_EDGE_FILTER_MAP_H
11.22 -
11.23 -#include <hugo/maps.h>
11.24 -
11.25 -// /// \file
11.26 -// /// \brief Maximum flow algorithms.
11.27 -// /// \ingroup galgs
11.28 -
11.29 -namespace hugo {
11.30 -
11.31 - /// \brief A map for filtering the edge-set to those edges
11.32 - /// which are tight w.r.t. some node_potential map and
11.33 - /// edge_distance map.
11.34 - ///
11.35 - /// A node-map node_potential is said to be a potential w.r.t.
11.36 - /// an edge-map edge_distance
11.37 - /// if and only if for each edge e, node_potential[g.head(e)]
11.38 - /// <= edge_distance[e]+node_potential[g.tail(e)]
11.39 - /// (or the reverse inequality holds for each edge).
11.40 - /// An edge is said to be tight if this inequality holds with equality,
11.41 - /// and the map returns true exactly for those edges.
11.42 - /// To avoid rounding errors, it is recommended to use this class with exact
11.43 - /// types, e.g. with int.
11.44 - template<typename Graph,
11.45 - typename NodePotentialMap, typename EdgeDistanceMap>
11.46 - class TightEdgeFilterMap : public MapBase<typename Graph::Edge, bool> {
11.47 - protected:
11.48 - const Graph* g;
11.49 - NodePotentialMap* node_potential;
11.50 - EdgeDistanceMap* edge_distance;
11.51 - public:
11.52 - TightEdgeFilterMap(Graph& _g, NodePotentialMap& _node_potential,
11.53 - EdgeDistanceMap& _edge_distance) :
11.54 - g(&_g), node_potential(&_node_potential),
11.55 - edge_distance(&_edge_distance) { }
11.56 - bool operator[](const typename Graph::Edge& e) const {
11.57 - return ((*node_potential)[g->head(e)] ==
11.58 - (*edge_distance)[e]+(*node_potential)[g->tail(e)]);
11.59 - }
11.60 - };
11.61 -
11.62 -} //namespace hugo
11.63 -
11.64 -#endif //HUGO_TIGHT_EDGE_FILTER_MAP_H
11.65 -
11.66 -
12.1 --- a/src/test/Makefile.am Wed Sep 29 10:35:35 2004 +0000
12.2 +++ b/src/test/Makefile.am Wed Sep 29 14:02:14 2004 +0000
12.3 @@ -9,7 +9,6 @@
12.4 dfs_test \
12.5 dijkstra_test \
12.6 graph_test \
12.7 - sym_graph_test \
12.8 graph_wrapper_test \
12.9 kruskal_test \
12.10 min_cost_flow_test \
12.11 @@ -29,7 +28,6 @@
12.12 dfs_test_SOURCES = dfs_test.cc
12.13 dijkstra_test_SOURCES = dijkstra_test.cc
12.14 graph_test_SOURCES = graph_test.cc
12.15 -sym_graph_test_SOURCES = sym_graph_test.cc
12.16 graph_wrapper_test_SOURCES = graph_wrapper_test.cc
12.17 kruskal_test_SOURCES = kruskal_test.cc
12.18 min_cost_flow_test_SOURCES = min_cost_flow_test.cc
13.1 --- a/src/test/graph_test.cc Wed Sep 29 10:35:35 2004 +0000
13.2 +++ b/src/test/graph_test.cc Wed Sep 29 14:02:14 2004 +0000
13.3 @@ -63,6 +63,7 @@
13.4 for(NodeIt n(G);n!=INVALID;++n) {
13.5 checkGraphInEdgeList(G,n,3);
13.6 checkGraphOutEdgeList(G,n,3);
13.7 + ++n;
13.8 }
13.9 }
13.10
13.11 @@ -81,8 +82,8 @@
13.12 template void hugo::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
13.13
13.14 //Compile SymSmartGraph
13.15 -//template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
13.16 -//template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
13.17 +template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
13.18 +template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
13.19
13.20 //Compile ListGraph
13.21 template void hugo::checkCompileGraph<ListGraph>(ListGraph &);
13.22 @@ -91,9 +92,9 @@
13.23
13.24
13.25 //Compile SymListGraph
13.26 -//template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
13.27 -//template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
13.28 -//template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
13.29 +template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
13.30 +template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
13.31 +template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
13.32
13.33 //Compile FullGraph
13.34 template void hugo::checkCompileStaticGraph<FullGraph>(FullGraph &);
13.35 @@ -130,14 +131,14 @@
13.36 checkPetersen(G);
13.37 }
13.38 {
13.39 - // SymSmartGraph G;
13.40 - // addPetersen(G);
13.41 - // checkPetersen(G);
13.42 + SymSmartGraph G;
13.43 + addPetersen(G);
13.44 + checkPetersen(G);
13.45 }
13.46 {
13.47 - // SymListGraph G;
13.48 - // addPetersen(G);
13.49 - // checkPetersen(G);
13.50 + SymListGraph G;
13.51 + addPetersen(G);
13.52 + checkPetersen(G);
13.53 }
13.54
13.55 ///\file
14.1 --- a/src/test/graph_test.h Wed Sep 29 10:35:35 2004 +0000
14.2 +++ b/src/test/graph_test.h Wed Sep 29 14:02:14 2004 +0000
14.3 @@ -298,7 +298,6 @@
14.4 typename Graph::OutEdgeIt e(G,n);
14.5 for(int i=0;i<nn;i++) {
14.6 check(e!=INVALID,"Wrong OutEdge list linking.");
14.7 - check(n==G.tail(e), "Wrong OutEdge list linking.");
14.8 ++e;
14.9 }
14.10 check(e==INVALID,"Wrong OutEdge list linking.");
14.11 @@ -311,7 +310,6 @@
14.12 typename Graph::InEdgeIt e(G,n);
14.13 for(int i=0;i<nn;i++) {
14.14 check(e!=INVALID,"Wrong InEdge list linking.");
14.15 - check(n==G.head(e), "Wrong InEdge list linking.");
14.16 ++e;
14.17 }
14.18 check(e==INVALID,"Wrong InEdge list linking.");
15.1 --- a/src/test/sym_graph_test.cc Wed Sep 29 10:35:35 2004 +0000
15.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
15.3 @@ -1,96 +0,0 @@
15.4 -/* -*- C++ -*-
15.5 - * src/test/sym_graph_test.cc - Part of HUGOlib, 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 -
15.20 -#include<iostream>
15.21 -
15.22 -#include<hugo/skeletons/sym_graph.h>
15.23 -
15.24 -#include<hugo/list_graph.h>
15.25 -#include<hugo/smart_graph.h>
15.26 -#include<hugo/full_graph.h>
15.27 -
15.28 -#include"test_tools.h"
15.29 -#include"graph_test.h"
15.30 -#include"sym_graph_test.h"
15.31 -
15.32 -/**
15.33 -\file
15.34 -This test makes consistency checks of list graph structures.
15.35 -
15.36 -G.addNode(), G.addEdge(), G.tail(), G.head()
15.37 -
15.38 -\todo Checks for empty graphs and isolated points.
15.39 -conversion.
15.40 -*/
15.41 -
15.42 -using namespace hugo;
15.43 -
15.44 -template<class Graph> void checkPetersen(Graph &G)
15.45 -{
15.46 - typedef typename Graph::NodeIt NodeIt;
15.47 -
15.48 -
15.49 - checkGraphNodeList(G,10);
15.50 - checkGraphEdgeList(G,30);
15.51 - checkGraphSymEdgeList(G,15);
15.52 -
15.53 - for(NodeIt n(G);n!=INVALID;++n) {
15.54 - checkGraphInEdgeList(G,n,3);
15.55 - checkGraphOutEdgeList(G,n,3);
15.56 - }
15.57 -}
15.58 -
15.59 -//Compile Graph
15.60 -template void hugo::checkCompileStaticSymGraph<skeleton::StaticSymGraph>
15.61 -(skeleton::StaticSymGraph &);
15.62 -
15.63 -template void hugo::checkCompileSymGraph<skeleton::ExtendableSymGraph>
15.64 -(skeleton::ExtendableSymGraph &);
15.65 -
15.66 -template void hugo::checkCompileErasableSymGraph<skeleton::ErasableSymGraph>
15.67 -(skeleton::ErasableSymGraph &);
15.68 -
15.69 -
15.70 -//Compile SymSmartGraph
15.71 -template void hugo::checkCompileSymGraph<SymSmartGraph>(SymSmartGraph &);
15.72 -template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
15.73 -
15.74 -//Compile SymListGraph
15.75 -template void hugo::checkCompileSymGraph<SymListGraph>(SymListGraph &);
15.76 -template void hugo::checkCompileErasableSymGraph<SymListGraph>(SymListGraph &);
15.77 -template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
15.78 -
15.79 -int main()
15.80 -{
15.81 - {
15.82 - SymSmartGraph G;
15.83 - addSymPetersen(G);
15.84 - checkPetersen(G);
15.85 - }
15.86 - {
15.87 - SymListGraph G;
15.88 - addSymPetersen(G);
15.89 - checkPetersen(G);
15.90 - }
15.91 -
15.92 - ///\file
15.93 - ///\todo map tests.
15.94 - ///\todo copy constr tests.
15.95 -
15.96 - std::cout << __FILE__ ": All tests passed.\n";
15.97 -
15.98 - return 0;
15.99 -}
16.1 --- a/src/test/sym_graph_test.h Wed Sep 29 10:35:35 2004 +0000
16.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
16.3 @@ -1,179 +0,0 @@
16.4 -/* -*- C++ -*-
16.5 - * src/test/sym_graph_test.h - Part of HUGOlib, a generic C++ optimization library
16.6 - *
16.7 - * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
16.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
16.9 - *
16.10 - * Permission to use, modify and distribute this software is granted
16.11 - * provided that this copyright notice appears in all copies. For
16.12 - * precise terms see the accompanying LICENSE file.
16.13 - *
16.14 - * This software is provided "AS IS" with no warranty of any kind,
16.15 - * express or implied, and with no claim as to its suitability for any
16.16 - * purpose.
16.17 - *
16.18 - */
16.19 -#ifndef HUGO_TEST_SYM_GRAPH_TEST_H
16.20 -#define HUGO_TEST_SYM_GRAPH_TEST_H
16.21 -
16.22 -
16.23 -#include "graph_test.h"
16.24 -#include "test_tools.h"
16.25 -
16.26 -//! \ingroup misc
16.27 -//! \file
16.28 -//! \brief Some utility to test symmetric graph classes.
16.29 -namespace hugo {
16.30 -
16.31 - template<class Graph> void checkCompileStaticSymGraph(Graph &G)
16.32 - {
16.33 - typedef typename Graph::Node Node;
16.34 - typedef typename Graph::NodeIt NodeIt;
16.35 - typedef typename Graph::SymEdge SymEdge;
16.36 - typedef typename Graph::SymEdgeIt SymEdgeIt;
16.37 - typedef typename Graph::Edge Edge;
16.38 - typedef typename Graph::EdgeIt EdgeIt;
16.39 - typedef typename Graph::InEdgeIt InEdgeIt;
16.40 - typedef typename Graph::OutEdgeIt OutEdgeIt;
16.41 -
16.42 - checkCompileStaticGraph(G);
16.43 -
16.44 - {
16.45 - SymEdge i; SymEdge j(i); SymEdge k(INVALID);
16.46 - i=j;
16.47 - bool b; b=true;
16.48 - b=(i==INVALID); b=(i!=INVALID);
16.49 - b=(i==j); b=(i!=j); b=(i<j);
16.50 - Edge e;
16.51 - e = G.forward(i);
16.52 - e = G.backward(i);
16.53 - }
16.54 - {
16.55 - SymEdgeIt i; SymEdgeIt j(i); SymEdgeIt k(INVALID); SymEdgeIt l(G);
16.56 - i=j;
16.57 - j=G.first(i);
16.58 - j=++i;
16.59 - bool b; b=true;
16.60 - b=(i==INVALID); b=(i!=INVALID);
16.61 - SymEdge n(i);
16.62 - n=i;
16.63 - b=(i==j); b=(i!=j); b=(i<j);
16.64 - //SymEdge ->SymEdgeIt conversion
16.65 - SymEdgeIt ni(G,n);
16.66 - }
16.67 - {
16.68 - Edge i, j;
16.69 - j = G.opposite(i);
16.70 - }
16.71 - {
16.72 - Node n;
16.73 - SymEdge se;
16.74 - se=INVALID;
16.75 - n=G.tail(se);
16.76 - n=G.head(se);
16.77 - }
16.78 - // id tests
16.79 - { SymEdge n; int i=G.id(n); i=i; }
16.80 - //SymEdgeMap tests
16.81 - {
16.82 - SymEdge k;
16.83 - typename Graph::template SymEdgeMap<int> m(G);
16.84 - typename Graph::template SymEdgeMap<int> const &cm = m; //Const map
16.85 - //Inicialize with default value
16.86 - typename Graph::template SymEdgeMap<int> mdef(G,12);
16.87 - typename Graph::template SymEdgeMap<int> mm(cm); //Copy
16.88 - typename Graph::template SymEdgeMap<double> dm(cm); //Copy from another type
16.89 - int v;
16.90 - v=m[k]; m[k]=v; m.set(k,v);
16.91 - v=cm[k];
16.92 -
16.93 - m=cm;
16.94 - dm=cm; //Copy from another type
16.95 - {
16.96 - //Check the typedef's
16.97 - typename Graph::template SymEdgeMap<int>::ValueType val;
16.98 - val = 1;
16.99 - typename Graph::template SymEdgeMap<int>::KeyType key;
16.100 - key = typename Graph::SymEdgeIt(G);
16.101 - }
16.102 - }
16.103 - { //bool SymEdgeMap
16.104 - SymEdge k;
16.105 - typename Graph::template SymEdgeMap<bool> m(G);
16.106 - typename Graph::template SymEdgeMap<bool> const &cm = m; //Const map
16.107 - //Inicialize with default value
16.108 - typename Graph::template SymEdgeMap<bool> mdef(G,12);
16.109 - typename Graph::template SymEdgeMap<bool> mm(cm); //Copy
16.110 - typename Graph::template SymEdgeMap<int> dm(cm); //Copy from another type
16.111 - bool v;
16.112 - v=m[k]; m[k]=v; m.set(k,v);
16.113 - v=cm[k];
16.114 -
16.115 - m=cm;
16.116 - dm=cm; //Copy from another type
16.117 - m=dm; //Copy to another type
16.118 - {
16.119 - //Check the typedef's
16.120 - typename Graph::template SymEdgeMap<bool>::ValueType val;
16.121 - val=true;
16.122 - typename Graph::template SymEdgeMap<bool>::KeyType key;
16.123 - key= typename Graph::SymEdgeIt(G);
16.124 - }
16.125 - }
16.126 - }
16.127 -
16.128 - template<class Graph> void checkCompileSymGraph(Graph &G)
16.129 - {
16.130 - checkCompileStaticSymGraph(G);
16.131 -
16.132 - typedef typename Graph::Node Node;
16.133 - typedef typename Graph::NodeIt NodeIt;
16.134 - typedef typename Graph::SymEdge SymEdge;
16.135 - typedef typename Graph::SymEdgeIt SymEdgeIt;
16.136 - typedef typename Graph::Edge Edge;
16.137 - typedef typename Graph::EdgeIt EdgeIt;
16.138 - typedef typename Graph::InEdgeIt InEdgeIt;
16.139 - typedef typename Graph::OutEdgeIt OutEdgeIt;
16.140 -
16.141 - Node n,m;
16.142 - n=G.addNode();
16.143 - m=G.addNode();
16.144 - SymEdge e;
16.145 - e = G.addEdge(n,m);
16.146 -
16.147 - // G.clear();
16.148 - }
16.149 -
16.150 - template<class Graph> void checkCompileSymGraphEraseSymEdge(Graph &G)
16.151 - {
16.152 - typename Graph::SymEdge n;
16.153 - G.erase(n);
16.154 - }
16.155 -
16.156 - template<class Graph> void checkCompileErasableSymGraph(Graph &G)
16.157 - {
16.158 - checkCompileSymGraph(G);
16.159 - checkCompileGraphEraseNode(G);
16.160 - checkCompileSymGraphEraseSymEdge(G);
16.161 - }
16.162 -
16.163 - template<class Graph> void checkGraphSymEdgeList(Graph &G, int nn)
16.164 - {
16.165 - typedef typename Graph::SymEdgeIt SymEdgeIt;
16.166 -
16.167 - SymEdgeIt e(G);
16.168 - for(int i=0;i<nn;i++) {
16.169 - check(e!=INVALID,"Wrong SymEdge list linking.");
16.170 - ++e;
16.171 - }
16.172 - check(e==INVALID,"Wrong SymEdge list linking.");
16.173 - }
16.174 -
16.175 - ///\file
16.176 - ///\todo Check head(), tail() as well;
16.177 -
16.178 -
16.179 -} //namespace hugo
16.180 -
16.181 -
16.182 -#endif
17.1 --- a/src/test/test_tools.h Wed Sep 29 10:35:35 2004 +0000
17.2 +++ b/src/test/test_tools.h Wed Sep 29 14:02:14 2004 +0000
17.3 @@ -67,7 +67,7 @@
17.4 ///Adds a Petersen graph to \c G.
17.5
17.6 ///Adds a Petersen graph to \c G.
17.7 -///\return The nodes and edges of the generated graph.
17.8 +///\return The nodes end edges og the generated graph.
17.9
17.10 template<typename Graph>
17.11 PetStruct<Graph> addPetersen(Graph &G,int num=5)
17.12 @@ -87,45 +87,6 @@
17.13 return n;
17.14 }
17.15
17.16 -///Structure returned by \ref addSymPetersen().
17.17
17.18 -///Structure returned by \ref addSymPetersen().
17.19 -///
17.20 -template<class Graph> struct SymPetStruct
17.21 -{
17.22 - ///Vector containing the outer nodes.
17.23 - std::vector<typename Graph::Node> outer;
17.24 - ///Vector containing the inner nodes.
17.25 - std::vector<typename Graph::Node> inner;
17.26 - ///Vector containing the edges of the inner circle.
17.27 - std::vector<typename Graph::SymEdge> incir;
17.28 - ///Vector containing the edges of the outer circle.
17.29 - std::vector<typename Graph::SymEdge> outcir;
17.30 - ///Vector containing the chord edges.
17.31 - std::vector<typename Graph::SymEdge> chords;
17.32 -};
17.33 -
17.34 -///Adds a Petersen graph to the symmetric \c G.
17.35 -
17.36 -///Adds a Petersen graph to the symmetric \c G.
17.37 -///\return The nodes and edges of the generated graph.
17.38 -
17.39 -template<typename Graph>
17.40 -SymPetStruct<Graph> addSymPetersen(Graph &G,int num=5)
17.41 -{
17.42 - SymPetStruct<Graph> n;
17.43 -
17.44 - for(int i=0;i<num;i++) {
17.45 - n.outer.push_back(G.addNode());
17.46 - n.inner.push_back(G.addNode());
17.47 - }
17.48 -
17.49 - for(int i=0;i<num;i++) {
17.50 - n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
17.51 - n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
17.52 - n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
17.53 - }
17.54 - return n;
17.55 -}
17.56
17.57 #endif