1.1 --- a/lemon/graph_utils.h Mon Oct 03 10:11:29 2005 +0000
1.2 +++ b/lemon/graph_utils.h Mon Oct 03 10:14:49 2005 +0000
1.3 @@ -20,6 +20,7 @@
1.4 #include <iterator>
1.5 #include <vector>
1.6 #include <map>
1.7 +#include <cmath>
1.8
1.9 #include <lemon/invalid.h>
1.10 #include <lemon/utility.h>
1.11 @@ -1060,16 +1061,272 @@
1.12 return BackwardMap<Graph>(graph);
1.13 }
1.14
1.15 - template <typename _Graph>
1.16 - class DegMapBase {
1.17 + /// \brief Potential difference map
1.18 + ///
1.19 + /// If there is an potential map on the nodes then we
1.20 + /// can get an edge map as we get the substraction of the
1.21 + /// values of the target and source.
1.22 + template <typename Graph, typename NodeMap>
1.23 + class PotentialDifferenceMap {
1.24 public:
1.25 + typedef typename Graph::Edge Key;
1.26 + typedef typename NodeMap::Value Value;
1.27 +
1.28 + /// \brief Constructor
1.29 + ///
1.30 + /// Contructor of the map
1.31 + PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
1.32 + : graph(_graph), potential(_potential) {}
1.33 +
1.34 + /// \brief Const subscription operator
1.35 + ///
1.36 + /// Const subscription operator
1.37 + Value operator[](const Key& edge) const {
1.38 + return potential[graph.target(edge)] - potential[graph.source(edge)];
1.39 + }
1.40 +
1.41 + private:
1.42 + const Graph& graph;
1.43 + const NodeMap& potential;
1.44 + };
1.45 +
1.46 + /// \brief Just returns a PotentialDifferenceMap
1.47 + ///
1.48 + /// Just returns a PotentialDifferenceMap
1.49 + /// \relates PotentialDifferenceMap
1.50 + template <typename Graph, typename NodeMap>
1.51 + PotentialDifferenceMap<Graph, NodeMap>
1.52 + potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
1.53 + return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
1.54 + }
1.55 +
1.56 + /// \brief Container for store values for each ordered pair of nodes
1.57 + ///
1.58 + /// Container for store values for each ordered pair of nodes.
1.59 + template <typename _Graph, typename _Value>
1.60 + class NodeMatrixMap
1.61 + : protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
1.62 + public:
1.63 + typedef _Graph Graph;
1.64 + typedef typename Graph::Node Node;
1.65 + typedef Node Key;
1.66 + typedef _Value Value;
1.67 +
1.68 + /// \brief Creates a node matrix for the given graph
1.69 + ///
1.70 + /// Creates a node matrix for the given graph.
1.71 + NodeMatrixMap(const Graph& _graph)
1.72 + : graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
1.73 +
1.74 + /// \brief Creates a node matrix for the given graph
1.75 + ///
1.76 + /// Creates a node matrix for the given graph and assigns each
1.77 + /// initial value to the given parameter.
1.78 + NodeMatrixMap(const Graph& _graph, const Value& _val)
1.79 + : graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
1.80 +
1.81 + /// \brief Gives back the value assigned to the \c left - \c right
1.82 + /// ordered pair.
1.83 + ///
1.84 + /// Gives back the value assigned to the \c left - \c right ordered pair.
1.85 + const Value& operator()(const Node& left, const Node& right) const {
1.86 + return values[index(graph.id(left), graph.id(right))];
1.87 + }
1.88
1.89 - typedef _Graph Graph;
1.90 + /// \brief Gives back the value assigned to the \c left - \c right
1.91 + /// ordered pair.
1.92 + ///
1.93 + /// Gives back the value assigned to the \c left - \c right ordered pair.
1.94 + Value& operator()(const Node& left, const Node& right) {
1.95 + return values[index(graph.id(left), graph.id(right))];
1.96 + }
1.97 +
1.98 + /// \brief Setter function for the matrix map.
1.99 + ///
1.100 + /// Setter function for the matrix map.
1.101 + void set(const Node& left, const Node& right, const Value& val) {
1.102 + values[index(graph.id(left), graph.id(right))] = val;
1.103 + }
1.104 +
1.105 + /// \brief Map for the coloumn view of the matrix
1.106 + ///
1.107 + /// Map for the coloumn view of the matrix.
1.108 + class ColMap : public MapBase<Node, Value> {
1.109 + friend class NodeMatrixMap;
1.110 + private:
1.111 + ColMap(NodeMatrixMap& _matrix, Node _col)
1.112 + : matrix(_matrix), col(_col) {}
1.113 +
1.114 + public:
1.115 + /// \brief Subscription operator
1.116 + ///
1.117 + /// Subscription operator.
1.118 + Value& operator[](Node row) {
1.119 + return matrix(col, row);
1.120 + }
1.121 +
1.122 + /// \brief Setter function
1.123 + ///
1.124 + /// Setter function.
1.125 + void set(Node row, const Value& val) {
1.126 + matrix.set(col, row, val);
1.127 + }
1.128 +
1.129 + /// \brief Subscription operator
1.130 + ///
1.131 + /// Subscription operator.
1.132 + const Value& operator[](Node row) const {
1.133 + return matrix(col, row);
1.134 + }
1.135 +
1.136 + private:
1.137 + NodeMatrixMap& matrix;
1.138 + Node col;
1.139 + };
1.140 +
1.141 + /// \brief Map for the const coloumn view of the matrix
1.142 + ///
1.143 + /// Map for the const coloumn view of the matrix.
1.144 + class ConstColMap : public MapBase<Node, Value> {
1.145 + friend class NodeMatrixMap;
1.146 + private:
1.147 + ConstColMap(const NodeMatrixMap& _matrix, Node _col)
1.148 + : matrix(_matrix), col(_col) {}
1.149 +
1.150 + public:
1.151 + /// \brief Subscription operator
1.152 + ///
1.153 + /// Subscription operator.
1.154 + const Value& operator[](Node row) const {
1.155 + return matrix(col, row);
1.156 + }
1.157 +
1.158 + private:
1.159 + const NodeMatrixMap& matrix;
1.160 + Node col;
1.161 + };
1.162 +
1.163 + /// \brief Map for the row view of the matrix
1.164 + ///
1.165 + /// Map for the row view of the matrix.
1.166 + class RowMap : public MapBase<Node, Value> {
1.167 + public:
1.168 + friend class NodeMatrixMap;
1.169 + private:
1.170 + RowMap(NodeMatrixMap& _matrix, Node _row)
1.171 + : matrix(_matrix), row(_row) {}
1.172 +
1.173 + public:
1.174 + /// \brief Subscription operator
1.175 + ///
1.176 + /// Subscription operator.
1.177 + Value& operator[](Node col) {
1.178 + return matrix(col, row);
1.179 + }
1.180 +
1.181 + /// \brief Setter function
1.182 + ///
1.183 + /// Setter function.
1.184 + void set(Node col, const Value& val) {
1.185 + matrix.set(col, row, val);
1.186 + }
1.187 +
1.188 + /// \brief Subscription operator
1.189 + ///
1.190 + /// Subscription operator.
1.191 + const Value& operator[](Node col) const {
1.192 + return matrix(col, row);
1.193 + }
1.194 +
1.195 + private:
1.196 + NodeMatrixMap& matrix;
1.197 + Node row;
1.198 + };
1.199 +
1.200 + /// \brief Map for the const row view of the matrix
1.201 + ///
1.202 + /// Map for the row const view of the matrix.
1.203 + class ConstRowMap : public MapBase<Node, Value> {
1.204 + public:
1.205 + friend class NodeMatrixMap;
1.206 + private:
1.207 + ConstRowMap(const NodeMatrixMap& _matrix, Node _row)
1.208 + : matrix(_matrix), row(_row) {}
1.209 +
1.210 + public:
1.211 + /// \brief Subscription operator
1.212 + ///
1.213 + /// Subscription operator.
1.214 + const Value& operator[](Node col) const {
1.215 + return matrix(col, row);
1.216 + }
1.217 +
1.218 + private:
1.219 + const NodeMatrixMap& matrix;
1.220 + Node row;
1.221 + };
1.222 +
1.223 + /// \brief Gives back the column view for the given node
1.224 + ///
1.225 + /// Gives back the column view for the given node
1.226 + ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
1.227 + /// \brief Gives back the column view for the given node
1.228 + ///
1.229 + /// Gives back the column view for the given node
1.230 + ColMap operator[](Node col) { return ColMap(*this, col); }
1.231 +
1.232 + /// \brief Gives back the column view for the given node
1.233 + ///
1.234 + /// Gives back the column view for the given node
1.235 + ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
1.236 + /// \brief Gives back the column view for the given node
1.237 + ///
1.238 + /// Gives back the column view for the given node
1.239 + ColMap colMap(Node col) { return ColMap(*this, col); }
1.240 +
1.241 + /// \brief Gives back the row view for the given node
1.242 + ///
1.243 + /// Gives back the row view for the given node
1.244 + ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
1.245 + /// \brief Gives back the row view for the given node
1.246 + ///
1.247 + /// Gives back the row view for the given node
1.248 + RowMap rowMap(Node row) { return RowMap(*this, row); }
1.249
1.250 protected:
1.251
1.252 - typedef typename Graph::template NodeMap<int> IntNodeMap;
1.253 + static int index(int i, int j) {
1.254 + int m = i > j ? i : j;
1.255 + if (i < j) {
1.256 + return m * m + i;
1.257 + } else {
1.258 + return m * m + m + j;
1.259 + }
1.260 + }
1.261 +
1.262 + static int size(int s) {
1.263 + return s * s;
1.264 + }
1.265 +
1.266 + void add(const Node& node) {
1.267 + if (size(graph.id(node) + 1) > values.size()) {
1.268 + values.resize(size(graph.id(node) + 1));
1.269 + }
1.270 + }
1.271 +
1.272 + void erase(const Node&) {}
1.273 +
1.274 + void build() {
1.275 + values.resize(size(graph.maxId(Node()) + 1));
1.276 + }
1.277 +
1.278 + void clear() {
1.279 + values.clear();
1.280 + }
1.281
1.282 + private:
1.283 + const Graph& graph;
1.284 + std::vector<Value> values;
1.285 };
1.286
1.287 /// \brief Map of the node in-degrees.
1.288 @@ -1270,6 +1527,48 @@
1.289 AutoNodeMap deg;
1.290 };
1.291
1.292 + // Indicators for the tags
1.293 +
1.294 + template <typename Graph, typename Enable = void>
1.295 + struct NodeNumTagIndicator {
1.296 + static const bool value = false;
1.297 + };
1.298 +
1.299 + template <typename Graph>
1.300 + struct NodeNumTagIndicator<
1.301 + Graph,
1.302 + typename enable_if<typename Graph::NodeNumTag, void>::type
1.303 + > {
1.304 + static const bool value = true;
1.305 + };
1.306 +
1.307 + template <typename Graph, typename Enable = void>
1.308 + struct EdgeNumTagIndicator {
1.309 + static const bool value = false;
1.310 + };
1.311 +
1.312 + template <typename Graph>
1.313 + struct EdgeNumTagIndicator<
1.314 + Graph,
1.315 + typename enable_if<typename Graph::EdgeNumTag, void>::type
1.316 + > {
1.317 + static const bool value = true;
1.318 + };
1.319 +
1.320 + template <typename Graph, typename Enable = void>
1.321 + struct FindEdgeTagIndicator {
1.322 + static const bool value = false;
1.323 + };
1.324 +
1.325 + template <typename Graph>
1.326 + struct FindEdgeTagIndicator<
1.327 + Graph,
1.328 + typename enable_if<typename Graph::FindEdgeTag, void>::type
1.329 + > {
1.330 + static const bool value = true;
1.331 + };
1.332 +
1.333 +
1.334 /// @}
1.335
1.336 } //END OF NAMESPACE LEMON
2.1 --- a/lemon/maps.h Mon Oct 03 10:11:29 2005 +0000
2.2 +++ b/lemon/maps.h Mon Oct 03 10:14:49 2005 +0000
2.3 @@ -17,7 +17,6 @@
2.4 #ifndef LEMON_MAPS_H
2.5 #define LEMON_MAPS_H
2.6
2.7 -#include <lemon/graph_utils.h>
2.8 #include <lemon/utility.h>
2.9
2.10