Changeset 1695:e6f99fe1723f in lemon-0.x for lemon/graph_utils.h

Timestamp:

10/03/05 12:14:49 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2221

Message:

Potential difference map
NodeMatrixMap? -- Matrix over the nodes
Indicators for common tags

File:

• lemon/graph_utils.h (modified) (3 diffs)

lemon/graph_utils.h

@@ -21 +21 @@
 #include <vector>
 #include <map>
+#include <cmath>
 
 #include <lemon/invalid.h>
@@ -1061 +1062 @@
   }
 
-  template <typename _Graph>
-  class DegMapBase {
-  public:
-    
+  /// \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))];
+    }
+    
+    /// \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;
   };
 
@@ -1271 +1528 @@
   };
 
+  // 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;
+  };
+
+
   /// @}