Changeset 1720:578d8b2b76c6 in lemon-0.x

Timestamp:

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

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Matrixmaps moved to own file

Location:

lemon

Files:

• concept/matrix_maps.h (added)
• graph_utils.h (modified) (12 diffs)
• matrix_maps.h (added)

lemon/graph_utils.h

@@ -26 +26 @@
 #include <lemon/utility.h>
 #include <lemon/maps.h>
+#include <lemon/traits.h>
 #include <lemon/bits/alteration_notifier.h>
 
@@ -401 +402 @@
   }
 
-
   /// \brief Class to copy a graph.
   ///
@@ -515 +515 @@
       return edgeRefMap;
     }
+
+    void run() {}
 
   private:
@@ -543 +545 @@
   }
 
-  template <typename _Graph, typename _Item>
-  class ItemSetTraits {};
-  
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Node> {
-  public:
-    
-    typedef _Graph Graph;
-
-    typedef typename Graph::Node Item;
-    typedef typename Graph::NodeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template NodeMap<_Value> {
-    public:
-      typedef typename Graph::template NodeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-        : Parent(_graph, _value) {}
+  /// \brief Class to copy an undirected graph.
+  ///
+  /// Class to copy an undirected graph to an other graph (duplicate a graph).
+  /// The simplest way of using it is through the \c copyUndirGraph() function.
+  template <typename Target, typename Source>
+  class UndirGraphCopy {
+  public: 
+    typedef typename Source::Node Node;
+    typedef typename Source::NodeIt NodeIt;
+    typedef typename Source::Edge Edge;
+    typedef typename Source::EdgeIt EdgeIt;
+    typedef typename Source::UndirEdge UndirEdge;
+    typedef typename Source::UndirEdgeIt UndirEdgeIt;
+
+    typedef typename Source::
+    template NodeMap<typename Target::Node> NodeRefMap;
+    
+    typedef typename Source::
+    template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
+
+  private:
+
+    struct EdgeRefMap {
+      EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
+      typedef typename Source::Edge Key;
+      typedef typename Target::Edge Value;
+
+      Value operator[](const Key& key) {
+        return gc.target.direct(gc.undirEdgeRef[key], 
+                                gc.target.direction(key));
+      }
+      
+      UndirGraphCopy& gc;
     };
-
+    
+  public:
+
+    /// \brief Constructor for the UndirGraphCopy.
+    ///
+    /// It copies the content of the \c _source graph into the
+    /// \c _target graph. It creates also two references, one beetween
+    /// the two nodeset and one beetween the two edgesets.
+    UndirGraphCopy(Target& _target, const Source& _source) 
+      : source(_source), target(_target), 
+        nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
+      for (NodeIt it(source); it != INVALID; ++it) {
+        nodeRefMap[it] = target.addNode();
+      }
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+        undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)], 
+                                        nodeRefMap[source.target(it)]);
+      }
+    }
+
+    /// \brief Copies the node references into the given map.
+    ///
+    /// Copies the node references into the given map.
+    template <typename NodeRef>
+    const UndirGraphCopy& nodeRef(NodeRef& map) const {
+      for (NodeIt it(source); it != INVALID; ++it) {
+        map.set(it, nodeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the node references into the given map.
+    ///
+    /// Reverse and copies the node references into the given map.
+    template <typename NodeRef>
+    const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
+      for (NodeIt it(source); it != INVALID; ++it) {
+        map.set(nodeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Copies the edge references into the given map.
+    ///
+    /// Copies the edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& edgeRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+        map.set(edgeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the undirected edge references into the 
+    /// given map.
+    ///
+    /// Reverse and copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+        map.set(it, edgeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Copies the undirected edge references into the given map.
+    ///
+    /// Copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+        map.set(it, undirEdgeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the undirected edge references into the 
+    /// given map.
+    ///
+    /// Reverse and copies the undirected edge references into the given map.
+    template <typename EdgeRef>
+    const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
+      for (UndirEdgeIt it(source); it != INVALID; ++it) {
+        map.set(undirEdgeRefMap[it], it);
+      }
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's node type,
+    /// and the copied map's key type is the source graph's node
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& nodeMap(TargetMap& tMap, 
+                                  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's edge type,
+    /// and the copied map's key type is the source graph's edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& edgeMap(TargetMap& tMap, 
+                                  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
+      return *this;
+    }
+
+    /// \brief Make copy of the given map.
+    ///
+    /// Makes copy of the given map for the newly created graph. 
+    /// The new map's key type is the target graph's edge type,
+    /// and the copied map's key type is the source graph's edge
+    /// type.  
+    template <typename TargetMap, typename SourceMap>
+    const UndirGraphCopy& undirEdgeMap(TargetMap& tMap, 
+                                  const SourceMap& sMap) const {
+      copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
+      return *this;
+    }
+
+    /// \brief Gives back the stored node references.
+    ///
+    /// Gives back the stored node references.
+    const NodeRefMap& nodeRef() const {
+      return nodeRefMap;
+    }
+
+    /// \brief Gives back the stored edge references.
+    ///
+    /// Gives back the stored edge references.
+    const EdgeRefMap& edgeRef() const {
+      return edgeRefMap;
+    }
+
+    /// \brief Gives back the stored undir edge references.
+    ///
+    /// Gives back the stored undir edge references.
+    const UndirEdgeRefMap& undirEdgeRef() const {
+      return undirEdgeRefMap;
+    }
+
+    void run() {}
+
+  private:
+    
+    const Source& source;
+    Target& target;
+
+    NodeRefMap nodeRefMap;
+    EdgeRefMap edgeRefMap;
+    UndirEdgeRefMap undirEdgeRefMap;
   };
 
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::Edge> {
-  public:
-    
-    typedef _Graph Graph;
-
-    typedef typename Graph::Edge Item;
-    typedef typename Graph::EdgeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template EdgeMap<_Value> {
-    public:
-      typedef typename Graph::template EdgeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-        : Parent(_graph, _value) {}
-    };
-
-  };
-
-  template <typename _Graph>
-  class ItemSetTraits<_Graph, typename _Graph::UndirEdge> {
-  public:
-    
-    typedef _Graph Graph;
-
-    typedef typename Graph::UndirEdge Item;
-    typedef typename Graph::UndirEdgeIt ItemIt;
-
-    template <typename _Value>
-    class Map : public Graph::template UndirEdgeMap<_Value> {
-    public:
-      typedef typename Graph::template UndirEdgeMap<_Value> Parent; 
-      typedef typename Parent::Value Value;
-
-      Map(const Graph& _graph) : Parent(_graph) {}
-      Map(const Graph& _graph, const Value& _value) 
-        : Parent(_graph, _value) {}
-    };
-
-  };
+  /// \brief Copy a graph to an other graph.
+  ///
+  /// Copy a graph to an other graph.
+  /// The usage of the function:
+  /// 
+  /// \code
+  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
+  /// \endcode
+  /// 
+  /// After the copy the \c nr map will contain the mapping from the
+  /// source graph's nodes to the target graph's nodes and the \c ecr will
+  /// contain the mapping from the target graph's edges to the source's
+  /// edges.
+  template <typename Target, typename Source>
+  UndirGraphCopy<Target, Source> 
+  copyUndirGraph(Target& target, const Source& source) {
+    return UndirGraphCopy<Target, Source>(target, source);
+  }
+
 
   /// @}
@@ -616 +763 @@
   /// \addtogroup graph_maps
   /// @{
-
-  template <typename Map, typename Enable = void>
-  struct ReferenceMapTraits {
-    typedef typename Map::Value Value;
-    typedef typename Map::Value& Reference;
-    typedef const typename Map::Value& ConstReference;
-    typedef typename Map::Value* Pointer;
-    typedef const typename Map::Value* ConstPointer;
-  };
-
-  template <typename Map>
-  struct ReferenceMapTraits<
-    Map, 
-    typename enable_if<typename Map::FullTypeTag, void>::type
-  > {
-    typedef typename Map::Value Value;
-    typedef typename Map::Reference Reference;
-    typedef typename Map::ConstReference ConstReference;
-    typedef typename Map::Pointer Pointer;
-    typedef typename Map::ConstPointer ConstPointer;
-  };
 
   /// Provides an immutable and unique id for each item in the graph.
@@ -755 +881 @@
     ///
     /// It gives back the value associated with the key.
-    const Value operator[](const Key& key) const {
+    Value operator[](const Key& key) const {
       return Map::operator[](key);
     }
@@ -1193 +1319 @@
   }
 
-  /// \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:
-
-    static int index(int i, int j) {
-      if (i < j) {
-        return j * j + i;
-      } else {
-        return i * i + i + j;
-      }
-    }
-
-    static int size(int s) {
-      return s * s;
-    }
-
-    void add(const Node& node) {
-      if (size(graph.id(node) + 1) >= (int)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.
   ///
@@ -1427 +1325 @@
   /// in constant time. On the other hand, the values are updated automatically
   /// whenever the graph changes.
-  ///
-  /// \warning Besides addNode() and addEdge(), a graph structure may provide
-  /// alternative ways to mogify the graph. The correct behavior of InDegMap
-  /// is not guarantied if these additional featureas are used. For example
-  /// the funstions \ref ListGraph::changeSource() "changeSource()",
-  /// \ref ListGraph::changeTarget() "changeTarget()" and
-  /// \ref ListGraph::reverseEdge() "reverseEdge()"
-  /// of \ref ListGraph will \e not update the degree values correctly.
   ///
   /// \sa OutDegMap
@@ -1502 +1392 @@
     }
 
+    virtual void signalChange(const Edge& edge) {
+      erase(edge);
+    }
+
+    virtual void commitChange(const Edge& edge) {
+      add(edge);
+    }
 
     virtual void build() {
@@ -1526 +1423 @@
   /// in constant time. On the other hand, the values are updated automatically
   /// whenever the graph changes.
-  ///
-  /// \warning Besides addNode() and addEdge(), a graph structure may provide
-  /// alternative ways to mogify the graph. The correct behavior of OutDegMap
-  /// is not guarantied if these additional featureas are used. For example
-  /// the funstions \ref ListGraph::changeSource() "changeSource()",
-  /// \ref ListGraph::changeTarget() "changeTarget()" and
-  /// \ref ListGraph::reverseEdge() "reverseEdge()"
-  /// of \ref ListGraph will \e not update the degree values correctly.
   ///
   /// \sa InDegMap
@@ -1601 +1490 @@
     }
 
+    virtual void signalChange(const Edge& edge) {
+      erase(edge);
+    }
+
+    virtual void commitChange(const Edge& edge) {
+      add(edge);
+    }
+
 
     virtual void build() {
@@ -1619 +1516 @@
   };
 
-  // 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;
-  };
-
 
   /// @}