1.1 --- a/demo/grid_graph_demo.cc Fri Sep 30 13:13:42 2005 +0000
1.2 +++ b/demo/grid_graph_demo.cc Fri Sep 30 13:15:28 2005 +0000
1.3 @@ -41,28 +41,21 @@
1.4 std::cout << "The length of shortest path: " <<
1.5 bfs.run(start, stop) << std::endl;
1.6
1.7 - GridGraph::NodeMap<xy<double> > coord(graph);
1.8 - for (int i = 0; i < graph.width(); ++i) {
1.9 - for (int j = 0; j < graph.height(); ++j) {
1.10 - coord[graph(i, j)] = xy<double>( i * 10.0, j * 10.0);
1.11 - }
1.12 - }
1.13 -
1.14 - FilteredGraph::EdgeMap<Color> color(filtered, Color(0.0, 0.0, 0.0));
1.15 + FilteredGraph::EdgeMap<bool> path(filtered, false);
1.16
1.17 for (GridGraph::Node node = stop;
1.18 node != start; node = bfs.predNode(node)) {
1.19 - color[bfs.pred(node)] = Color(1.0, 0.0, 0.0);
1.20 + path[bfs.pred(node)] = true;
1.21 }
1.22
1.23 graphToEps(filtered, "grid_graph.eps").scaleToA4().
1.24 title("Grid graph").
1.25 copyright("(C) 2005 LEMON Project").
1.26 - coords(coord).
1.27 + coords(scaleMap(indexMap(graph), 10)).
1.28 enableParallel().
1.29 - nodeScale(.45).
1.30 + nodeScale(0.5).
1.31 drawArrows().
1.32 - edgeColors(color).
1.33 + edgeColors(composeMap(ColorSet(), path)).
1.34 run();
1.35
1.36 std::cout << "The shortest path is written to grid_graph.eps" << std::endl;
2.1 --- a/lemon/Makefile.am Fri Sep 30 13:13:42 2005 +0000
2.2 +++ b/lemon/Makefile.am Fri Sep 30 13:15:28 2005 +0000
2.3 @@ -34,6 +34,7 @@
2.4 graph_adaptor.h \
2.5 graph_utils.h \
2.6 graph_to_eps.h \
2.7 + hypercube_graph.h \
2.8 invalid.h \
2.9 iterable_maps.h \
2.10 kruskal.h \
3.1 --- a/lemon/grid_graph.h Fri Sep 30 13:13:42 2005 +0000
3.2 +++ b/lemon/grid_graph.h Fri Sep 30 13:15:28 2005 +0000
3.3 @@ -27,8 +27,21 @@
3.4
3.5 #include <lemon/bits/undir_graph_extender.h>
3.6
3.7 +#include <lemon/xy.h>
3.8 +
3.9 +///\ingroup graphs
3.10 +///\file
3.11 +///\brief GridGraph class.
3.12 +
3.13 namespace lemon {
3.14
3.15 + /// \brief Base graph for GridGraph.
3.16 + ///
3.17 + /// Base graph for grid graph. It describes some member functions
3.18 + /// which can be used in the GridGraph.
3.19 + ///
3.20 + /// \warning Always use the GridGraph instead of this.
3.21 + /// \see GridGraph
3.22 class GridGraphBase {
3.23
3.24 public:
3.25 @@ -356,9 +369,91 @@
3.26 /// "Undirected Graph" concept.
3.27 ///
3.28 /// \author Balazs Dezso
3.29 + /// \see GridGraphBase
3.30 class GridGraph : public ExtendedGridGraphBase {
3.31 public:
3.32 -
3.33 +
3.34 + /// \brief Map to get the indices of the nodes as xy<int>.
3.35 + ///
3.36 + /// Map to get the indices of the nodes as xy<int>.
3.37 + class IndexMap {
3.38 + public:
3.39 + typedef True NeedCopy;
3.40 + /// \brief The key type of the map
3.41 + typedef GridGraph::Node Key;
3.42 + /// \brief The value type of the map
3.43 + typedef xy<int> Value;
3.44 +
3.45 + /// \brief Constructor
3.46 + ///
3.47 + /// Constructor
3.48 + IndexMap(const GridGraph& _graph) : graph(_graph) {}
3.49 +
3.50 + /// \brief The subscript operator
3.51 + ///
3.52 + /// The subscript operator.
3.53 + Value operator[](Key key) const {
3.54 + return xy<int>(graph.row(key), graph.col(key));
3.55 + }
3.56 +
3.57 + private:
3.58 + const GridGraph& graph;
3.59 + };
3.60 +
3.61 + /// \brief Map to get the row of the nodes.
3.62 + ///
3.63 + /// Map to get the row of the nodes.
3.64 + class RowMap {
3.65 + public:
3.66 + typedef True NeedCopy;
3.67 + /// \brief The key type of the map
3.68 + typedef GridGraph::Node Key;
3.69 + /// \brief The value type of the map
3.70 + typedef int Value;
3.71 +
3.72 + /// \brief Constructor
3.73 + ///
3.74 + /// Constructor
3.75 + RowMap(const GridGraph& _graph) : graph(_graph) {}
3.76 +
3.77 + /// \brief The subscript operator
3.78 + ///
3.79 + /// The subscript operator.
3.80 + Value operator[](Key key) const {
3.81 + return graph.row(key);
3.82 + }
3.83 +
3.84 + private:
3.85 + const GridGraph& graph;
3.86 + };
3.87 +
3.88 + /// \brief Map to get the column of the nodes.
3.89 + ///
3.90 + /// Map to get the column of the nodes.
3.91 + class ColMap {
3.92 + public:
3.93 + typedef True NeedCopy;
3.94 + /// \brief The key type of the map
3.95 + typedef GridGraph::Node Key;
3.96 + /// \brief The value type of the map
3.97 + typedef int Value;
3.98 +
3.99 + /// \brief Constructor
3.100 + ///
3.101 + /// Constructor
3.102 + ColMap(const GridGraph& _graph) : graph(_graph) {}
3.103 +
3.104 + /// \brief The subscript operator
3.105 + ///
3.106 + /// The subscript operator.
3.107 + Value operator[](Key key) const {
3.108 + return graph.col(key);
3.109 + }
3.110 +
3.111 + private:
3.112 + const GridGraph& graph;
3.113 + };
3.114 +
3.115 GridGraph(int n, int m) { construct(n, m); }
3.116
3.117 /// \brief Gives back the edge goes down from the node.
3.118 @@ -398,5 +493,26 @@
3.119 }
3.120
3.121 };
3.122 +
3.123 + /// \brief Index map of the grid graph
3.124 + ///
3.125 + /// Just returns an IndexMap for the grid graph.
3.126 + GridGraph::IndexMap indexMap(const GridGraph& graph) {
3.127 + return GridGraph::IndexMap(graph);
3.128 + }
3.129 +
3.130 + /// \brief Row map of the grid graph
3.131 + ///
3.132 + /// Just returns an RowMap for the grid graph.
3.133 + GridGraph::RowMap rowMap(const GridGraph& graph) {
3.134 + return GridGraph::RowMap(graph);
3.135 + }
3.136 +
3.137 + /// \brief Coloumn map of the grid graph
3.138 + ///
3.139 + /// Just returns an ColMap for the grid graph.
3.140 + GridGraph::ColMap colMap(const GridGraph& graph) {
3.141 + return GridGraph::ColMap(graph);
3.142 + }
3.143 }
3.144 #endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/hypercube_graph.h Fri Sep 30 13:15:28 2005 +0000
4.3 @@ -0,0 +1,339 @@
4.4 +/* -*- C++ -*-
4.5 + * lemon/hypercube_graph.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef HYPERCUBE_GRAPH_H
4.21 +#define HYPERCUBE_GRAPH_H
4.22 +
4.23 +#include <iostream>
4.24 +#include <vector>
4.25 +#include <lemon/invalid.h>
4.26 +#include <lemon/utility.h>
4.27 +
4.28 +#include <lemon/bits/iterable_graph_extender.h>
4.29 +#include <lemon/bits/alteration_notifier.h>
4.30 +#include <lemon/bits/default_map.h>
4.31 +
4.32 +///\ingroup graphs
4.33 +///\file
4.34 +///\brief HyperCubeGraph class.
4.35 +
4.36 +namespace lemon {
4.37 +
4.38 + /// \brief Base graph for HyperGraph.
4.39 + ///
4.40 + /// Base graph for hyper-cube graph. It describes some member functions
4.41 + /// which can be used in the HyperCubeGraph.
4.42 + ///
4.43 + /// \warning Always use the HyperCubeGraph instead of this.
4.44 + /// \see HyperCubeGraph
4.45 + class HyperCubeGraphBase {
4.46 +
4.47 + public:
4.48 +
4.49 + typedef HyperCubeGraphBase Graph;
4.50 +
4.51 + class Node;
4.52 + class Edge;
4.53 +
4.54 + public:
4.55 +
4.56 + HyperCubeGraphBase() {}
4.57 +
4.58 + protected:
4.59 +
4.60 + /// \brief Creates a hypercube graph with the given size.
4.61 + ///
4.62 + /// Creates a hypercube graph with the given size.
4.63 + void construct(int dim) {
4.64 + _dim = dim;
4.65 + _nodeNum = 1 << dim;
4.66 + }
4.67 +
4.68 + public:
4.69 +
4.70 +
4.71 + typedef True NodeNumTag;
4.72 + typedef True EdgeNumTag;
4.73 +
4.74 + ///Number of nodes.
4.75 + int nodeNum() const { return _nodeNum; }
4.76 + ///Number of edges.
4.77 + int edgeNum() const { return _nodeNum * _dim; }
4.78 +
4.79 + /// Maximum node ID.
4.80 +
4.81 + /// Maximum node ID.
4.82 + ///\sa id(Node)
4.83 + int maxId(Node = INVALID) const { return nodeNum() - 1; }
4.84 + /// Maximum edge ID.
4.85 +
4.86 + /// Maximum edge ID.
4.87 + ///\sa id(Edge)
4.88 + int maxId(Edge = INVALID) const { return edgeNum() - 1; }
4.89 +
4.90 + /// \brief Gives back the source node of an edge.
4.91 + ///
4.92 + /// Gives back the source node of an edge.
4.93 + Node source(Edge e) const {
4.94 + return e.id / _dim;
4.95 + }
4.96 +
4.97 + /// \brief Gives back the target node of an edge.
4.98 + ///
4.99 + /// Gives back the target node of an edge.
4.100 + Node target(Edge e) const {
4.101 + return (e.id / _dim) ^ ( 1 << (e.id % _dim));
4.102 + }
4.103 +
4.104 + /// Node ID.
4.105 +
4.106 + /// The ID of a valid Node is a nonnegative integer not greater than
4.107 + /// \ref maxNodeId(). The range of the ID's is not surely continuous
4.108 + /// and the greatest node ID can be actually less then \ref maxNodeId().
4.109 + ///
4.110 + /// The ID of the \ref INVALID node is -1.
4.111 + ///\return The ID of the node \c v.
4.112 +
4.113 + static int id(Node v) { return v.id; }
4.114 + /// Edge ID.
4.115 +
4.116 + /// The ID of a valid Edge is a nonnegative integer not greater than
4.117 + /// \ref maxEdgeId(). The range of the ID's is not surely continuous
4.118 + /// and the greatest edge ID can be actually less then \ref maxEdgeId().
4.119 + ///
4.120 + /// The ID of the \ref INVALID edge is -1.
4.121 + ///\return The ID of the edge \c e.
4.122 + static int id(Edge e) { return e.id; }
4.123 +
4.124 + static Node fromId(int id, Node) { return Node(id);}
4.125 +
4.126 + static Edge fromId(int id, Edge) { return Edge(id);}
4.127 +
4.128 + class Node {
4.129 + friend class HyperCubeGraphBase;
4.130 +
4.131 + protected:
4.132 + int id;
4.133 + Node(int _id) { id = _id;}
4.134 + public:
4.135 + Node() {}
4.136 + Node (Invalid) { id = -1; }
4.137 + bool operator==(const Node node) const {return id == node.id;}
4.138 + bool operator!=(const Node node) const {return id != node.id;}
4.139 + bool operator<(const Node node) const {return id < node.id;}
4.140 + };
4.141 +
4.142 + class Edge {
4.143 + friend class HyperCubeGraphBase;
4.144 +
4.145 + protected:
4.146 + int id;
4.147 +
4.148 + Edge(int _id) : id(_id) {}
4.149 +
4.150 + public:
4.151 + Edge() { }
4.152 + Edge (Invalid) { id = -1; }
4.153 + bool operator==(const Edge edge) const {return id == edge.id;}
4.154 + bool operator!=(const Edge edge) const {return id != edge.id;}
4.155 + bool operator<(const Edge edge) const {return id < edge.id;}
4.156 + };
4.157 +
4.158 + void first(Node& node) const {
4.159 + node.id = nodeNum() - 1;
4.160 + }
4.161 +
4.162 + static void next(Node& node) {
4.163 + --node.id;
4.164 + }
4.165 +
4.166 + void first(Edge& edge) const {
4.167 + edge.id = edgeNum() - 1;
4.168 + }
4.169 +
4.170 + static void next(Edge& edge) {
4.171 + --edge.id;
4.172 + }
4.173 +
4.174 + void firstOut(Edge& edge, const Node& node) const {
4.175 + edge.id = node.id * _dim;
4.176 + }
4.177 +
4.178 + void nextOut(Edge& edge) const {
4.179 + ++edge.id;
4.180 + if (edge.id % _dim == 0) edge.id = -1;
4.181 + }
4.182 +
4.183 + void firstIn(Edge& edge, const Node& node) const {
4.184 + edge.id = (node.id ^ 1) * _dim;
4.185 + }
4.186 +
4.187 + void nextIn(Edge& edge) const {
4.188 + int cnt = edge.id % _dim;
4.189 + if ((cnt + 1) % _dim == 0) {
4.190 + edge.id = -1;
4.191 + } else {
4.192 + edge.id = ((edge.id / _dim) ^ ((1 << cnt) * 3)) * _dim + cnt + 1;
4.193 + }
4.194 + }
4.195 +
4.196 + /// \brief Gives back the number of the dimensions.
4.197 + ///
4.198 + /// Gives back the number of the dimensions.
4.199 + int dimension() const {
4.200 + return _dim;
4.201 + }
4.202 +
4.203 + /// \brief Returns true if the n'th bit of the node is one.
4.204 + ///
4.205 + /// Returns true if the n'th bit of the node is one.
4.206 + bool projection(Node node, int n) const {
4.207 + return (bool)(node.id & (1 << n));
4.208 + }
4.209 +
4.210 + /// \brief The dimension id of the edge.
4.211 + ///
4.212 + /// It returns the dimension id of the edge. It can
4.213 + /// be in the ${0, 1, dim-1}$ intervall.
4.214 + int dimension(Edge edge) const {
4.215 + return edge.id % _dim;
4.216 + }
4.217 +
4.218 + /// \brief Gives back the index of the node.
4.219 + ///
4.220 + /// Gives back the index of the node. The lower bits of the
4.221 + /// integer describe the node.
4.222 + int index(Node node) const {
4.223 + return node.id;
4.224 + }
4.225 +
4.226 + /// \brief Gives back the node by its index.
4.227 + ///
4.228 + /// Gives back the node by its index.
4.229 + Node node(int index) const {
4.230 + return Node(index);
4.231 + }
4.232 +
4.233 + private:
4.234 + int _dim, _nodeNum;
4.235 + };
4.236 +
4.237 +
4.238 + typedef MappableGraphExtender<
4.239 + IterableGraphExtender<
4.240 + AlterableGraphExtender<
4.241 + HyperCubeGraphBase > > > ExtendedHyperCubeGraphBase;
4.242 +
4.243 + /// \ingroup graphs
4.244 + ///
4.245 + /// \brief HyperCube graph class
4.246 + ///
4.247 + /// This class implements a special graph type. The nodes of the
4.248 + /// graph can be indiced with integers with at most \c dim binary length.
4.249 + /// Two nodes are connected in the graph if the indices differ only
4.250 + /// on one position in the binary form.
4.251 + ///
4.252 + /// \note The type of the \c ids is chosen to \c int because efficiency
4.253 + /// reasons. This way the maximal dimension of this implementation
4.254 + /// is 26.
4.255 + ///
4.256 + /// The graph type is fully conform to the \ref concept::StaticGraph
4.257 + /// concept but it does not conform to the \ref concept::UndirGraph.
4.258 + ///
4.259 + /// \see HyperCubeGraphBase
4.260 + /// \author Balazs Dezso
4.261 + class HyperCubeGraph : public ExtendedHyperCubeGraphBase {
4.262 + public:
4.263 +
4.264 + /// \brief Construct a graph with \c dim dimension.
4.265 + ///
4.266 + /// Construct a graph with \c dim dimension.
4.267 + HyperCubeGraph(int dim) { construct(dim); }
4.268 +
4.269 + /// \brief Linear combination map.
4.270 + ///
4.271 + /// It makes possible to give back a linear combination
4.272 + /// for each node. This function works like the \c std::accumulate
4.273 + /// so it accumulates the \c bf binary function with the \c fv
4.274 + /// first value. The map accumulates only on that dimensions where
4.275 + /// the node's index is one. The accumulated values should be
4.276 + /// given by the \c begin and \c end iterators and this range's length
4.277 + /// should be the dimension number of the graph.
4.278 + ///
4.279 + /// \code
4.280 + /// const int DIM = 3;
4.281 + /// HyperCubeGraph graph(DIM);
4.282 + /// xy<double> base[DIM];
4.283 + /// for (int k = 0; k < DIM; ++k) {
4.284 + /// base[k].x = rand() / (RAND_MAX + 1.0);
4.285 + /// base[k].y = rand() / (RAND_MAX + 1.0);
4.286 + /// }
4.287 + /// HyperCubeGraph::HyperMap<xy<double> >
4.288 + /// pos(graph, base, base + DIM, xy<double>(0.0, 0.0));
4.289 + /// \endcode
4.290 + ///
4.291 + /// \see HyperCubeGraph
4.292 + template <typename T, typename BF = std::plus<T> >
4.293 + class HyperMap {
4.294 + public:
4.295 +
4.296 + typedef Node Key;
4.297 + typedef T Value;
4.298 +
4.299 +
4.300 + /// \brief Constructor for HyperMap.
4.301 + ///
4.302 + /// Construct a HyperMap for the given graph. The accumulated values
4.303 + /// should be given by the \c begin and \c end iterators and this
4.304 + /// range's length should be the dimension number of the graph.
4.305 + ///
4.306 + /// This function accumulates the \c bf binary function with
4.307 + /// the \c fv first value. The map accumulates only on that dimensions
4.308 + /// where the node's index is one.
4.309 + template <typename It>
4.310 + HyperMap(const Graph& graph, It begin, It end,
4.311 + T fv = 0.0, const BF& bf = BF())
4.312 + : _graph(graph), _values(begin, end), _first_value(fv), _bin_func(bf) {
4.313 + if (_values.size() != graph.dimension()) {}
4.314 + }
4.315 +
4.316 + /// \brief Gives back the partial accumulated value.
4.317 + ///
4.318 + /// Gives back the partial accumulated value.
4.319 + Value operator[](Key k) const {
4.320 + Value val = _first_value;
4.321 + int id = _graph.index(k);
4.322 + int n = 0;
4.323 + while (id != 0) {
4.324 + if (id & 1) {
4.325 + val = _bin_func(_values[n], _first_value);
4.326 + }
4.327 + id >>= 1;
4.328 + ++n;
4.329 + }
4.330 + return val;
4.331 + }
4.332 +
4.333 + private:
4.334 + const Graph& _graph;
4.335 + std::vector<T> _values;
4.336 + T _first_value;
4.337 + BF _bin_func;
4.338 + };
4.339 + };
4.340 +}
4.341 +#endif
4.342 +