# HG changeset patch
# User deba
# Date 1128334489 0
# Node ID e6f99fe1723fd594923665eac4ec07bbed9dc402
# Parent  6d81e6f7a88d1c1f18aaa0f83958bd3a20d5d9b7
Potential difference map
NodeMatrixMap -- Matrix over the nodes
Indicators for common tags

diff -r 6d81e6f7a88d -r e6f99fe1723f lemon/graph_utils.h
--- a/lemon/graph_utils.h	Mon Oct 03 10:11:29 2005 +0000
+++ b/lemon/graph_utils.h	Mon Oct 03 10:14:49 2005 +0000
@@ -20,6 +20,7 @@
 #include <iterator>
 #include <vector>
 #include <map>
+#include <cmath>
 
 #include <lemon/invalid.h>
 #include <lemon/utility.h>
@@ -1060,16 +1061,272 @@
     return BackwardMap<Graph>(graph);
   }
 
-  template <typename _Graph>
-  class DegMapBase {
+  /// \brief Potential difference map
+  ///
+  /// 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))];
+    }
     
-    typedef _Graph Graph;
+    /// \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.
@@ -1270,6 +1527,48 @@
     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
diff -r 6d81e6f7a88d -r e6f99fe1723f lemon/maps.h
--- a/lemon/maps.h	Mon Oct 03 10:11:29 2005 +0000
+++ b/lemon/maps.h	Mon Oct 03 10:14:49 2005 +0000
@@ -17,7 +17,6 @@
 #ifndef LEMON_MAPS_H
 #define LEMON_MAPS_H
 
-#include <lemon/graph_utils.h>
 #include <lemon/utility.h>