1.1 --- a/lemon/Makefile.am Wed Nov 05 14:44:37 2008 +0000
1.2 +++ b/lemon/Makefile.am Thu Nov 06 14:40:32 2008 +0000
1.3 @@ -31,6 +31,7 @@
1.4 lemon/full_graph.h \
1.5 lemon/graph_to_eps.h \
1.6 lemon/grid_graph.h \
1.7 + lemon/hypercube_graph.h \
1.8 lemon/kruskal.h \
1.9 lemon/lgf_reader.h \
1.10 lemon/lgf_writer.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/hypercube_graph.h Thu Nov 06 14:40:32 2008 +0000
2.3 @@ -0,0 +1,439 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef HYPERCUBE_GRAPH_H
2.23 +#define HYPERCUBE_GRAPH_H
2.24 +
2.25 +#include <vector>
2.26 +#include <lemon/core.h>
2.27 +#include <lemon/assert.h>
2.28 +#include <lemon/bits/graph_extender.h>
2.29 +
2.30 +///\ingroup graphs
2.31 +///\file
2.32 +///\brief HypercubeGraph class.
2.33 +
2.34 +namespace lemon {
2.35 +
2.36 + class HypercubeGraphBase {
2.37 +
2.38 + public:
2.39 +
2.40 + typedef HypercubeGraphBase Graph;
2.41 +
2.42 + class Node;
2.43 + class Edge;
2.44 + class Arc;
2.45 +
2.46 + public:
2.47 +
2.48 + HypercubeGraphBase() {}
2.49 +
2.50 + protected:
2.51 +
2.52 + void construct(int dim) {
2.53 + LEMON_ASSERT(dim >= 1, "The number of dimensions must be at least 1.");
2.54 + _dim = dim;
2.55 + _node_num = 1 << dim;
2.56 + _edge_num = dim * (1 << dim-1);
2.57 + }
2.58 +
2.59 + public:
2.60 +
2.61 + typedef True NodeNumTag;
2.62 + typedef True EdgeNumTag;
2.63 + typedef True ArcNumTag;
2.64 +
2.65 + int nodeNum() const { return _node_num; }
2.66 + int edgeNum() const { return _edge_num; }
2.67 + int arcNum() const { return 2 * _edge_num; }
2.68 +
2.69 + int maxNodeId() const { return _node_num - 1; }
2.70 + int maxEdgeId() const { return _edge_num - 1; }
2.71 + int maxArcId() const { return 2 * _edge_num - 1; }
2.72 +
2.73 + static Node nodeFromId(int id) { return Node(id); }
2.74 + static Edge edgeFromId(int id) { return Edge(id); }
2.75 + static Arc arcFromId(int id) { return Arc(id); }
2.76 +
2.77 + static int id(Node node) { return node._id; }
2.78 + static int id(Edge edge) { return edge._id; }
2.79 + static int id(Arc arc) { return arc._id; }
2.80 +
2.81 + Node u(Edge edge) const {
2.82 + int base = edge._id & ((1 << _dim-1) - 1);
2.83 + int k = edge._id >> _dim-1;
2.84 + return ((base >> k) << k+1) | (base & ((1 << k) - 1));
2.85 + }
2.86 +
2.87 + Node v(Edge edge) const {
2.88 + int base = edge._id & ((1 << _dim-1) - 1);
2.89 + int k = edge._id >> _dim-1;
2.90 + return ((base >> k) << k+1) | (base & ((1 << k) - 1)) | (1 << k);
2.91 + }
2.92 +
2.93 + Node source(Arc arc) const {
2.94 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
2.95 + }
2.96 +
2.97 + Node target(Arc arc) const {
2.98 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
2.99 + }
2.100 +
2.101 + typedef True FindEdgeTag;
2.102 + typedef True FindArcTag;
2.103 +
2.104 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
2.105 + if (prev != INVALID) return INVALID;
2.106 + int d = u._id ^ v._id;
2.107 + int k = 0;
2.108 + if (d == 0) return INVALID;
2.109 + for ( ; (d & 1) == 0; d >>= 1) ++k;
2.110 + if (d >> 1 != 0) return INVALID;
2.111 + return (k << _dim-1) | ((u._id >> k+1) << k) | (u._id & ((1 << k) - 1));
2.112 + }
2.113 +
2.114 + Arc findArc(Node u, Node v, Arc prev = INVALID) const {
2.115 + Edge edge = findEdge(u, v, prev);
2.116 + if (edge == INVALID) return INVALID;
2.117 + int k = edge._id >> _dim-1;
2.118 + return ((u._id >> k) & 1) == 1 ? edge._id << 1 : (edge._id << 1) | 1;
2.119 + }
2.120 +
2.121 + class Node {
2.122 + friend class HypercubeGraphBase;
2.123 +
2.124 + protected:
2.125 + int _id;
2.126 + Node(int id) : _id(id) {}
2.127 + public:
2.128 + Node() {}
2.129 + Node (Invalid) : _id(-1) {}
2.130 + bool operator==(const Node node) const {return _id == node._id;}
2.131 + bool operator!=(const Node node) const {return _id != node._id;}
2.132 + bool operator<(const Node node) const {return _id < node._id;}
2.133 + };
2.134 +
2.135 + class Edge {
2.136 + friend class HypercubeGraphBase;
2.137 + friend class Arc;
2.138 +
2.139 + protected:
2.140 + int _id;
2.141 +
2.142 + Edge(int id) : _id(id) {}
2.143 +
2.144 + public:
2.145 + Edge() {}
2.146 + Edge (Invalid) : _id(-1) {}
2.147 + bool operator==(const Edge edge) const {return _id == edge._id;}
2.148 + bool operator!=(const Edge edge) const {return _id != edge._id;}
2.149 + bool operator<(const Edge edge) const {return _id < edge._id;}
2.150 + };
2.151 +
2.152 + class Arc {
2.153 + friend class HypercubeGraphBase;
2.154 +
2.155 + protected:
2.156 + int _id;
2.157 +
2.158 + Arc(int id) : _id(id) {}
2.159 +
2.160 + public:
2.161 + Arc() {}
2.162 + Arc (Invalid) : _id(-1) {}
2.163 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
2.164 + bool operator==(const Arc arc) const {return _id == arc._id;}
2.165 + bool operator!=(const Arc arc) const {return _id != arc._id;}
2.166 + bool operator<(const Arc arc) const {return _id < arc._id;}
2.167 + };
2.168 +
2.169 + void first(Node& node) const {
2.170 + node._id = _node_num - 1;
2.171 + }
2.172 +
2.173 + static void next(Node& node) {
2.174 + --node._id;
2.175 + }
2.176 +
2.177 + void first(Edge& edge) const {
2.178 + edge._id = _edge_num - 1;
2.179 + }
2.180 +
2.181 + static void next(Edge& edge) {
2.182 + --edge._id;
2.183 + }
2.184 +
2.185 + void first(Arc& arc) const {
2.186 + arc._id = 2 * _edge_num - 1;
2.187 + }
2.188 +
2.189 + static void next(Arc& arc) {
2.190 + --arc._id;
2.191 + }
2.192 +
2.193 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
2.194 + edge._id = node._id >> 1;
2.195 + dir = (node._id & 1) == 0;
2.196 + }
2.197 +
2.198 + void nextInc(Edge& edge, bool& dir) const {
2.199 + Node n = dir ? u(edge) : v(edge);
2.200 + int k = (edge._id >> _dim-1) + 1;
2.201 + if (k < _dim) {
2.202 + edge._id = (k << _dim-1) |
2.203 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
2.204 + dir = ((n._id >> k) & 1) == 0;
2.205 + } else {
2.206 + edge._id = -1;
2.207 + dir = true;
2.208 + }
2.209 + }
2.210 +
2.211 + void firstOut(Arc& arc, const Node& node) const {
2.212 + arc._id = ((node._id >> 1) << 1) | (~node._id & 1);
2.213 + }
2.214 +
2.215 + void nextOut(Arc& arc) const {
2.216 + Node n = (arc._id & 1) == 1 ? u(arc) : v(arc);
2.217 + int k = (arc._id >> _dim) + 1;
2.218 + if (k < _dim) {
2.219 + arc._id = (k << _dim-1) |
2.220 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
2.221 + arc._id = (arc._id << 1) | (~(n._id >> k) & 1);
2.222 + } else {
2.223 + arc._id = -1;
2.224 + }
2.225 + }
2.226 +
2.227 + void firstIn(Arc& arc, const Node& node) const {
2.228 + arc._id = ((node._id >> 1) << 1) | (node._id & 1);
2.229 + }
2.230 +
2.231 + void nextIn(Arc& arc) const {
2.232 + Node n = (arc._id & 1) == 1 ? v(arc) : u(arc);
2.233 + int k = (arc._id >> _dim) + 1;
2.234 + if (k < _dim) {
2.235 + arc._id = (k << _dim-1) |
2.236 + ((n._id >> k+1) << k) | (n._id & ((1 << k) - 1));
2.237 + arc._id = (arc._id << 1) | ((n._id >> k) & 1);
2.238 + } else {
2.239 + arc._id = -1;
2.240 + }
2.241 + }
2.242 +
2.243 + static bool direction(Arc arc) {
2.244 + return (arc._id & 1) == 1;
2.245 + }
2.246 +
2.247 + static Arc direct(Edge edge, bool dir) {
2.248 + return Arc((edge._id << 1) | (dir ? 1 : 0));
2.249 + }
2.250 +
2.251 + int dimension() const {
2.252 + return _dim;
2.253 + }
2.254 +
2.255 + bool projection(Node node, int n) const {
2.256 + return static_cast<bool>(node._id & (1 << n));
2.257 + }
2.258 +
2.259 + int dimension(Edge edge) const {
2.260 + return edge._id >> _dim-1;
2.261 + }
2.262 +
2.263 + int dimension(Arc arc) const {
2.264 + return arc._id >> _dim;
2.265 + }
2.266 +
2.267 + int index(Node node) const {
2.268 + return node._id;
2.269 + }
2.270 +
2.271 + Node operator()(int ix) const {
2.272 + return Node(ix);
2.273 + }
2.274 +
2.275 + private:
2.276 + int _dim;
2.277 + int _node_num, _edge_num;
2.278 + };
2.279 +
2.280 +
2.281 + typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
2.282 +
2.283 + /// \ingroup graphs
2.284 + ///
2.285 + /// \brief Hypercube graph class
2.286 + ///
2.287 + /// This class implements a special graph type. The nodes of the graph
2.288 + /// are indiced with integers with at most \c dim binary digits.
2.289 + /// Two nodes are connected in the graph if and only if their indices
2.290 + /// differ only on one position in the binary form.
2.291 + ///
2.292 + /// \note The type of the indices is chosen to \c int for efficiency
2.293 + /// reasons. Thus the maximum dimension of this implementation is 26
2.294 + /// (assuming that the size of \c int is 32 bit).
2.295 + ///
2.296 + /// This graph type is fully conform to the \ref concepts::Graph
2.297 + /// "Graph" concept, and it also has an important extra feature
2.298 + /// that its maps are real \ref concepts::ReferenceMap
2.299 + /// "reference map"s.
2.300 + class HypercubeGraph : public ExtendedHypercubeGraphBase {
2.301 + public:
2.302 +
2.303 + typedef ExtendedHypercubeGraphBase Parent;
2.304 +
2.305 + /// \brief Constructs a hypercube graph with \c dim dimensions.
2.306 + ///
2.307 + /// Constructs a hypercube graph with \c dim dimensions.
2.308 + HypercubeGraph(int dim) { construct(dim); }
2.309 +
2.310 + /// \brief The number of dimensions.
2.311 + ///
2.312 + /// Gives back the number of dimensions.
2.313 + int dimension() const {
2.314 + return Parent::dimension();
2.315 + }
2.316 +
2.317 + /// \brief Returns \c true if the n'th bit of the node is one.
2.318 + ///
2.319 + /// Returns \c true if the n'th bit of the node is one.
2.320 + bool projection(Node node, int n) const {
2.321 + return Parent::projection(node, n);
2.322 + }
2.323 +
2.324 + /// \brief The dimension id of an edge.
2.325 + ///
2.326 + /// Gives back the dimension id of the given edge.
2.327 + /// It is in the [0..dim-1] range.
2.328 + int dimension(Edge edge) const {
2.329 + return Parent::dimension(edge);
2.330 + }
2.331 +
2.332 + /// \brief The dimension id of an arc.
2.333 + ///
2.334 + /// Gives back the dimension id of the given arc.
2.335 + /// It is in the [0..dim-1] range.
2.336 + int dimension(Arc arc) const {
2.337 + return Parent::dimension(arc);
2.338 + }
2.339 +
2.340 + /// \brief The index of a node.
2.341 + ///
2.342 + /// Gives back the index of the given node.
2.343 + /// The lower bits of the integer describes the node.
2.344 + int index(Node node) const {
2.345 + return Parent::index(node);
2.346 + }
2.347 +
2.348 + /// \brief Gives back a node by its index.
2.349 + ///
2.350 + /// Gives back a node by its index.
2.351 + Node operator()(int ix) const {
2.352 + return Parent::operator()(ix);
2.353 + }
2.354 +
2.355 + /// \brief Number of nodes.
2.356 + int nodeNum() const { return Parent::nodeNum(); }
2.357 + /// \brief Number of edges.
2.358 + int edgeNum() const { return Parent::edgeNum(); }
2.359 + /// \brief Number of arcs.
2.360 + int arcNum() const { return Parent::arcNum(); }
2.361 +
2.362 + /// \brief Linear combination map.
2.363 + ///
2.364 + /// This map makes possible to give back a linear combination
2.365 + /// for each node. It works like the \c std::accumulate function,
2.366 + /// so it accumulates the \c bf binary function with the \c fv first
2.367 + /// value. The map accumulates only on that positions (dimensions)
2.368 + /// where the index of the node is one. The values that have to be
2.369 + /// accumulated should be given by the \c begin and \c end iterators
2.370 + /// and the length of this range should be equal to the dimension
2.371 + /// number of the graph.
2.372 + ///
2.373 + ///\code
2.374 + /// const int DIM = 3;
2.375 + /// HypercubeGraph graph(DIM);
2.376 + /// dim2::Point<double> base[DIM];
2.377 + /// for (int k = 0; k < DIM; ++k) {
2.378 + /// base[k].x = rnd();
2.379 + /// base[k].y = rnd();
2.380 + /// }
2.381 + /// HypercubeGraph::HyperMap<dim2::Point<double> >
2.382 + /// pos(graph, base, base + DIM, dim2::Point<double>(0.0, 0.0));
2.383 + ///\endcode
2.384 + ///
2.385 + /// \see HypercubeGraph
2.386 + template <typename T, typename BF = std::plus<T> >
2.387 + class HyperMap {
2.388 + public:
2.389 +
2.390 + /// \brief The key type of the map
2.391 + typedef Node Key;
2.392 + /// \brief The value type of the map
2.393 + typedef T Value;
2.394 +
2.395 + /// \brief Constructor for HyperMap.
2.396 + ///
2.397 + /// Construct a HyperMap for the given graph. The values that have
2.398 + /// to be accumulated should be given by the \c begin and \c end
2.399 + /// iterators and the length of this range should be equal to the
2.400 + /// dimension number of the graph.
2.401 + ///
2.402 + /// This map accumulates the \c bf binary function with the \c fv
2.403 + /// first value on that positions (dimensions) where the index of
2.404 + /// the node is one.
2.405 + template <typename It>
2.406 + HyperMap(const Graph& graph, It begin, It end,
2.407 + T fv = 0, const BF& bf = BF())
2.408 + : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf)
2.409 + {
2.410 + LEMON_ASSERT(_values.size() == graph.dimension(),
2.411 + "Wrong size of range");
2.412 + }
2.413 +
2.414 + /// \brief The partial accumulated value.
2.415 + ///
2.416 + /// Gives back the partial accumulated value.
2.417 + Value operator[](const Key& k) const {
2.418 + Value val = _first_value;
2.419 + int id = _graph.index(k);
2.420 + int n = 0;
2.421 + while (id != 0) {
2.422 + if (id & 1) {
2.423 + val = _bin_func(val, _values[n]);
2.424 + }
2.425 + id >>= 1;
2.426 + ++n;
2.427 + }
2.428 + return val;
2.429 + }
2.430 +
2.431 + private:
2.432 + const Graph& _graph;
2.433 + std::vector<T> _values;
2.434 + T _first_value;
2.435 + BF _bin_func;
2.436 + };
2.437 +
2.438 + };
2.439 +
2.440 +}
2.441 +
2.442 +#endif
3.1 --- a/test/digraph_test.cc Wed Nov 05 14:44:37 2008 +0000
3.2 +++ b/test/digraph_test.cc Thu Nov 06 14:40:32 2008 +0000
3.3 @@ -20,7 +20,6 @@
3.4 #include <lemon/list_graph.h>
3.5 #include <lemon/smart_graph.h>
3.6 #include <lemon/full_graph.h>
3.7 -//#include <lemon/hypercube_graph.h>
3.8
3.9 #include "test_tools.h"
3.10 #include "graph_test.h"
3.11 @@ -112,7 +111,6 @@
3.12
3.13 }
3.14
3.15 -
3.16 void checkConcepts() {
3.17 { // Checking digraph components
3.18 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
3.19 @@ -145,9 +143,6 @@
3.20 { // Checking FullDigraph
3.21 checkConcept<Digraph, FullDigraph>();
3.22 }
3.23 -// { // Checking HyperCubeDigraph
3.24 -// checkConcept<Digraph, HyperCubeDigraph>();
3.25 -// }
3.26 }
3.27
3.28 template <typename Digraph>
4.1 --- a/test/graph_test.cc Wed Nov 05 14:44:37 2008 +0000
4.2 +++ b/test/graph_test.cc Thu Nov 06 14:40:32 2008 +0000
4.3 @@ -21,6 +21,7 @@
4.4 #include <lemon/smart_graph.h>
4.5 #include <lemon/full_graph.h>
4.6 #include <lemon/grid_graph.h>
4.7 +#include <lemon/hypercube_graph.h>
4.8
4.9 #include "test_tools.h"
4.10 #include "graph_test.h"
4.11 @@ -104,9 +105,9 @@
4.12 checkGraphEdgeList(G, num * (num - 1) / 2);
4.13
4.14 for (NodeIt n(G); n != INVALID; ++n) {
4.15 - checkGraphOutArcList(G, n, num - 1);
4.16 - checkGraphInArcList(G, n, num - 1);
4.17 - checkGraphIncEdgeList(G, n, num - 1);
4.18 + checkGraphOutArcList(G, n, num - 1);
4.19 + checkGraphInArcList(G, n, num - 1);
4.20 + checkGraphIncEdgeList(G, n, num - 1);
4.21 }
4.22
4.23 checkGraphConArcList(G, num * (num - 1));
4.24 @@ -121,7 +122,7 @@
4.25 checkGraphArcMap(G);
4.26 checkGraphEdgeMap(G);
4.27
4.28 -
4.29 +
4.30 for (int i = 0; i < G.nodeNum(); ++i) {
4.31 check(G.index(G(i)) == i, "Wrong index");
4.32 }
4.33 @@ -177,6 +178,9 @@
4.34 { // Checking GridGraph
4.35 checkConcept<Graph, GridGraph>();
4.36 }
4.37 + { // Checking HypercubeGraph
4.38 + checkConcept<Graph, HypercubeGraph>();
4.39 + }
4.40 }
4.41
4.42 template <typename Graph>
4.43 @@ -312,6 +316,54 @@
4.44
4.45 }
4.46
4.47 +void checkHypercubeGraph(int dim) {
4.48 + GRAPH_TYPEDEFS(HypercubeGraph);
4.49 +
4.50 + HypercubeGraph G(dim);
4.51 + checkGraphNodeList(G, 1 << dim);
4.52 + checkGraphEdgeList(G, dim * (1 << dim-1));
4.53 + checkGraphArcList(G, dim * (1 << dim));
4.54 +
4.55 + Node n = G.nodeFromId(dim);
4.56 +
4.57 + for (NodeIt n(G); n != INVALID; ++n) {
4.58 + checkGraphIncEdgeList(G, n, dim);
4.59 + for (IncEdgeIt e(G, n); e != INVALID; ++e) {
4.60 + check( (G.u(e) == n &&
4.61 + G.id(G.v(e)) == G.id(n) ^ (1 << G.dimension(e))) ||
4.62 + (G.v(e) == n &&
4.63 + G.id(G.u(e)) == G.id(n) ^ (1 << G.dimension(e))),
4.64 + "Wrong edge or wrong dimension");
4.65 + }
4.66 +
4.67 + checkGraphOutArcList(G, n, dim);
4.68 + for (OutArcIt a(G, n); a != INVALID; ++a) {
4.69 + check(G.source(a) == n &&
4.70 + G.id(G.target(a)) == G.id(n) ^ (1 << G.dimension(a)),
4.71 + "Wrong arc or wrong dimension");
4.72 + }
4.73 +
4.74 + checkGraphInArcList(G, n, dim);
4.75 + for (InArcIt a(G, n); a != INVALID; ++a) {
4.76 + check(G.target(a) == n &&
4.77 + G.id(G.source(a)) == G.id(n) ^ (1 << G.dimension(a)),
4.78 + "Wrong arc or wrong dimension");
4.79 + }
4.80 + }
4.81 +
4.82 + checkGraphConArcList(G, (1 << dim) * dim);
4.83 + checkGraphConEdgeList(G, dim * (1 << dim-1));
4.84 +
4.85 + checkArcDirections(G);
4.86 +
4.87 + checkNodeIds(G);
4.88 + checkArcIds(G);
4.89 + checkEdgeIds(G);
4.90 + checkGraphNodeMap(G);
4.91 + checkGraphArcMap(G);
4.92 + checkGraphEdgeMap(G);
4.93 +}
4.94 +
4.95 void checkGraphs() {
4.96 { // Checking ListGraph
4.97 checkGraph<ListGraph>();
4.98 @@ -321,7 +373,7 @@
4.99 checkGraph<SmartGraph>();
4.100 checkGraphValidity<SmartGraph>();
4.101 }
4.102 - { // Checking FullGraph
4.103 + { // Checking FullGraph
4.104 checkFullGraph(7);
4.105 checkFullGraph(8);
4.106 }
4.107 @@ -332,6 +384,12 @@
4.108 checkGridGraph(0, 0);
4.109 checkGridGraph(1, 1);
4.110 }
4.111 + { // Checking HypercubeGraph
4.112 + checkHypercubeGraph(1);
4.113 + checkHypercubeGraph(2);
4.114 + checkHypercubeGraph(3);
4.115 + checkHypercubeGraph(4);
4.116 + }
4.117 }
4.118
4.119 int main() {
5.1 --- a/tools/lemon-0.x-to-1.x.sh Wed Nov 05 14:44:37 2008 +0000
5.2 +++ b/tools/lemon-0.x-to-1.x.sh Thu Nov 06 14:40:32 2008 +0000
5.3 @@ -81,6 +81,7 @@
5.4 -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
5.5 -e "s/\<copyGraph\>/graphCopy/g"\
5.6 -e "s/\<copyDigraph\>/digraphCopy/g"\
5.7 + -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
5.8 -e "s/\<IntegerMap\>/RangeMap/g"\
5.9 -e "s/\<integerMap\>/rangeMap/g"\
5.10 -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\