lemon-0.x: comparison lemon/graph

equal deleted inserted replaced

-:6234c4fa5df9
+:1ef52a3eb8ab
 #define LEMON_GRAPH_UTILS_H
 #include <iterator>
 #include <vector>
 #include <map>
+#include <cmath>
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
 #include <lemon/maps.h>
 #include <lemon/bits/alteration_notifier.h>
 template <typename Graph>
 inline BackwardMap<Graph> backwardMap(const Graph& graph) {
 return BackwardMap<Graph>(graph);
 }
-template <typename _Graph>
+/// \brief Potential difference map
-class DegMapBase {
+///
-public:
+/// If there is an potential map on the nodes then we
+/// can get an edge map as we get the substraction of the
+/// values of the target and source.
+template <typename Graph, typename NodeMap>
+class PotentialDifferenceMap {
+public:
+typedef typename Graph::Edge Key;
+typedef typename NodeMap::Value Value;
+/// \brief Constructor
+///
+/// Contructor of the map
+PotentialDifferenceMap(const Graph& _graph, const NodeMap& _potential)
+: graph(_graph), potential(_potential) {}
+/// \brief Const subscription operator
+///
+/// Const subscription operator
+Value operator[](const Key& edge) const {
+return potential[graph.target(edge)] - potential[graph.source(edge)];
+}
+private:
+const Graph& graph;
+const NodeMap& potential;
+};
+/// \brief Just returns a PotentialDifferenceMap
+///
+/// Just returns a PotentialDifferenceMap
+/// \relates PotentialDifferenceMap
+template <typename Graph, typename NodeMap>
+PotentialDifferenceMap<Graph, NodeMap>
+potentialDifferenceMap(const Graph& graph, const NodeMap& potential) {
+return PotentialDifferenceMap<Graph, NodeMap>(graph, potential);
+}
+/// \brief Container for store values for each ordered pair of nodes
+///
+/// Container for store values for each ordered pair of nodes.
+template <typename _Graph, typename _Value>
+class NodeMatrixMap
+: protected AlterationNotifier<typename _Graph::Node>::ObserverBase {
+public:
 typedef _Graph Graph;
+typedef typename Graph::Node Node;
+typedef Node Key;
+typedef _Value Value;
+/// \brief Creates a node matrix for the given graph
+///
+/// Creates a node matrix for the given graph.
+NodeMatrixMap(const Graph& _graph)
+: graph(_graph), values(size(_graph.maxId(Node()) + 1)) {}
+/// \brief Creates a node matrix for the given graph
+///
+/// Creates a node matrix for the given graph and assigns each
+/// initial value to the given parameter.
+NodeMatrixMap(const Graph& _graph, const Value& _val)
+: graph(_graph), values(size(_graph.maxId(Node()) + 1), _val) {}
+/// \brief Gives back the value assigned to the \c left - \c right
+/// ordered pair.
+///
+/// Gives back the value assigned to the \c left - \c right ordered pair.
+const Value& operator()(const Node& left, const Node& right) const {
+return values[index(graph.id(left), graph.id(right))];
+}
+/// \brief Gives back the value assigned to the \c left - \c right
+/// ordered pair.
+///
+/// Gives back the value assigned to the \c left - \c right ordered pair.
+Value& operator()(const Node& left, const Node& right) {
+return values[index(graph.id(left), graph.id(right))];
+}
+/// \brief Setter function for the matrix map.
+///
+/// Setter function for the matrix map.
+void set(const Node& left, const Node& right, const Value& val) {
+values[index(graph.id(left), graph.id(right))] = val;
+}
+/// \brief Map for the coloumn view of the matrix
+///
+/// Map for the coloumn view of the matrix.
+class ColMap : public MapBase<Node, Value> {
+friend class NodeMatrixMap;
+private:
+ColMap(NodeMatrixMap& _matrix, Node _col)
+	: matrix(_matrix), col(_col) {}
+public:
+/// \brief Subscription operator
+///
+/// Subscription operator.
+Value& operator[](Node row) {
+	return matrix(col, row);
+}
+/// \brief Setter function
+///
+/// Setter function.
+void set(Node row, const Value& val) {
+	matrix.set(col, row, val);
+}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+const Value& operator[](Node row) const {
+	return matrix(col, row);
+}
+private:
+NodeMatrixMap& matrix;
+Node col;
+};
+/// \brief Map for the const coloumn view of the matrix
+///
+/// Map for the const coloumn view of the matrix.
+class ConstColMap : public MapBase<Node, Value> {
+friend class NodeMatrixMap;
+private:
+ConstColMap(const NodeMatrixMap& _matrix, Node _col)
+	: matrix(_matrix), col(_col) {}
+public:
+/// \brief Subscription operator
+///
+/// Subscription operator.
+const Value& operator[](Node row) const {
+	return matrix(col, row);
+}
+private:
+const NodeMatrixMap& matrix;
+Node col;
+};
+/// \brief Map for the row view of the matrix
+///
+/// Map for the row view of the matrix.
+class RowMap : public MapBase<Node, Value> {
+public:
+friend class NodeMatrixMap;
+private:
+RowMap(NodeMatrixMap& _matrix, Node _row)
+	: matrix(_matrix), row(_row) {}
+public:
+/// \brief Subscription operator
+///
+/// Subscription operator.
+Value& operator[](Node col) {
+	return matrix(col, row);
+}
+/// \brief Setter function
+///
+/// Setter function.
+void set(Node col, const Value& val) {
+	matrix.set(col, row, val);
+}
+/// \brief Subscription operator
+///
+/// Subscription operator.
+const Value& operator[](Node col) const {
+	return matrix(col, row);
+}
+private:
+NodeMatrixMap& matrix;
+Node row;
+};
+/// \brief Map for the const row view of the matrix
+///
+/// Map for the row const view of the matrix.
+class ConstRowMap : public MapBase<Node, Value> {
+public:
+friend class NodeMatrixMap;
+private:
+ConstRowMap(const NodeMatrixMap& _matrix, Node _row)
+	: matrix(_matrix), row(_row) {}
+public:
+/// \brief Subscription operator
+///
+/// Subscription operator.
+const Value& operator[](Node col) const {
+	return matrix(col, row);
+}
+private:
+const NodeMatrixMap& matrix;
+Node row;
+};
+/// \brief Gives back the column view for the given node
+///
+/// Gives back the column view for the given node
+ConstColMap operator[](Node col) const { return ConstColMap(*this, col); }
+/// \brief Gives back the column view for the given node
+///
+/// Gives back the column view for the given node
+ColMap operator[](Node col) { return ColMap(*this, col); }
+/// \brief Gives back the column view for the given node
+///
+/// Gives back the column view for the given node
+ConstColMap colMap(Node col) const { return ConstColMap(*this, col); }
+/// \brief Gives back the column view for the given node
+///
+/// Gives back the column view for the given node
+ColMap colMap(Node col) { return ColMap(*this, col); }
+/// \brief Gives back the row view for the given node
+///
+/// Gives back the row view for the given node
+ConstRowMap rowMap(Node row) const { return ConstRowMap(*this, row); }
+/// \brief Gives back the row view for the given node
+///
+/// Gives back the row view for the given node
+RowMap rowMap(Node row) { return RowMap(*this, row); }
 protected:
-typedef typename Graph::template NodeMap<int> IntNodeMap;
+static int index(int i, int j) {
+int m = i > j ? i : j;
+if (i < j) {
+	return m * m + i;
+} else {
+	return m * m + m + j;
+}
+}
+static int size(int s) {
+return s * s;
+}
+void add(const Node& node) {
+if (size(graph.id(node) + 1) > values.size()) {
+	values.resize(size(graph.id(node) + 1));
+}
+}
+void erase(const Node&) {}
+void build() {
+values.resize(size(graph.maxId(Node()) + 1));
+}
+void clear() {
+values.clear();
+}
+private:
+const Graph& graph;
+std::vector<Value> values;
 };
 /// \brief Map of the node in-degrees.
 ///
 /// This map returns the in-degree of a node. Once it is constructed,
 const _Graph& graph;
 AutoNodeMap deg;
 };
+// Indicators for the tags
+template <typename Graph, typename Enable = void>
+struct NodeNumTagIndicator {
+static const bool value = false;
+};
+template <typename Graph>
+struct NodeNumTagIndicator<
+Graph,
+typename enable_if<typename Graph::NodeNumTag, void>::type
+> {
+static const bool value = true;
+};
+template <typename Graph, typename Enable = void>
+struct EdgeNumTagIndicator {
+static const bool value = false;
+};
+template <typename Graph>
+struct EdgeNumTagIndicator<
+Graph,
+typename enable_if<typename Graph::EdgeNumTag, void>::type
+> {
+static const bool value = true;
+};
+template <typename Graph, typename Enable = void>
+struct FindEdgeTagIndicator {
+static const bool value = false;
+};
+template <typename Graph>
+struct FindEdgeTagIndicator<
+Graph,
+typename enable_if<typename Graph::FindEdgeTag, void>::type
+> {
+static const bool value = true;
+};
 /// @}
 } //END OF NAMESPACE LEMON
 #endif

changeset 1702	44d495c659b5
parent 1679	e825655c24a4
child 1704	467d7927a901