Changeset 1531:a3b20dd847b5 in lemon-0.x for lemon/graph_utils.h

Timestamp:

07/04/05 15:10:34 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

New graph copy interface

File:

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

lemon/graph_utils.h

@@ -144 +144 @@
   }
 
+  /// \brief Function to count the number of the out-edges from node \c n.
+  ///
+  /// This function counts the number of the out-edges from node \c n
+  /// in the graph.  
+  template <typename Graph>
+  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
+    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
+  }
+
+  /// \brief Function to count the number of the in-edges to node \c n.
+  ///
+  /// This function counts the number of the in-edges to node \c n
+  /// in the graph.  
+  template <typename Graph>
+  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
+    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
+  }
+
+
   /// Finds an edge between two nodes of a graph.
 
@@ -174 +193 @@
     return e;
   }
-  
-  /// \brief Function to count the number of the out-edges from node \c n.
-  ///
-  /// This function counts the number of the out-edges from node \c n
-  /// in the graph.  
-  template <typename Graph>
-  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
-    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
-  }
-
-  /// \brief Function to count the number of the in-edges to node \c n.
-  ///
-  /// This function counts the number of the in-edges to node \c n
-  /// in the graph.  
-  template <typename Graph>
-  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
-    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
-  }
-
-  // graph copy
-
-  template <
-    typename DestinationGraph, 
-    typename SourceGraph, 
-    typename NodeBijection>
-  void copyNodes(DestinationGraph& _d, const SourceGraph& _s, 
-                 NodeBijection& _nb) {    
-    for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
-      _nb[it] = _d.addNode();
-    }
-  }
-
-  template <
-    typename DestinationGraph, 
-    typename SourceGraph, 
-    typename NodeBijection,
-    typename EdgeBijection>
-  void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
-                 const NodeBijection& _nb, EdgeBijection& _eb) {    
-    for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
-      _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
-    }
-  }
-
-  template <
-    typename DestinationGraph, 
-    typename SourceGraph, 
-    typename NodeBijection,
-    typename EdgeBijection>
-  void copyGraph(DestinationGraph& _d, const SourceGraph& _s, 
-                 NodeBijection& _nb, EdgeBijection& _eb) {
-    nodeCopy(_d, _s, _nb);
-    edgeCopy(_d, _s, _nb, _eb);
-  }
- 
-  template <
-    typename _DestinationGraph, 
-    typename _SourceGraph, 
-    typename _NodeBijection 
-    =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
-    typename _EdgeBijection 
-    = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
-  >
+
+  /// \brief Copy the source map to the target map.
+  ///
+  /// Copy the \c source map to the \c target map. It uses the given iterator
+  /// to iterate on the data structure and it use the \c ref mapping to
+  /// convert the source's keys to the target's keys.
+  template <typename Target, typename Source, 
+            typename ItemIt, typename Ref>          
+  void copyMap(Target& target, const Source& source, 
+               ItemIt it, const Ref& ref) {
+    for (; it != INVALID; ++it) {
+      target[ref[it]] = source[it];
+    }
+  }
+
+  /// \brief Copy the source map to the target map.
+  ///
+  /// Copy the \c source map to the \c target map. It uses the given iterator
+  /// to iterate on the data structure.
+  template <typename Target, typename Source, 
+            typename ItemIt>        
+  void copyMap(Target& target, const Source& source, ItemIt it) {
+    for (; it != INVALID; ++it) {
+      target[it] = source[it];
+    }
+  }
+
+
+  /// \brief Class to copy a graph to an other graph.
+  ///
+  /// Class to copy a graph to an other graph. It can be used easier
+  /// with the \c copyGraph() function.
+  template <typename Target, typename Source>
   class GraphCopy {
-  public:
-    
-    typedef _DestinationGraph DestinationGraph;
-    typedef _SourceGraph SourceGraph;
-
-    typedef _NodeBijection NodeBijection;
-    typedef _EdgeBijection EdgeBijection;
-    
-  protected:          
-    
-    NodeBijection node_bijection;
-    EdgeBijection edge_bijection;     
-
-  public:
-     
-    GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
-      copyGraph(_d, _s, node_bijection, edge_bijection);
-    }
-    
-    const NodeBijection& getNodeBijection() const {
-      return node_bijection;
-    }
-
-    const EdgeBijection& getEdgeBijection() const {
-      return edge_bijection;
-    }
-     
-  };
-
+  public: 
+    typedef typename Source::Node Node;
+    typedef typename Source::NodeIt NodeIt;
+    typedef typename Source::Edge Edge;
+    typedef typename Source::EdgeIt EdgeIt;
+
+    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
+    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
+
+    /// \brief Constructor for the GraphCopy.
+    ///
+    /// 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.
+    GraphCopy(Target& _target, const Source& _source) 
+      : source(_source), target(_target), 
+        nodeRefMap(_source), edgeRefMap(_source) {
+      for (NodeIt it(source); it != INVALID; ++it) {
+        nodeRefMap[it] = target.addNode();
+      }
+      for (EdgeIt it(source); it != INVALID; ++it) {
+        edgeRefMap[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 GraphCopy& 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 GraphCopy& 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 GraphCopy& edgeRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+        map.set(it, edgeRefMap[it]);
+      }
+      return *this;
+    }
+
+    /// \brief Reverse and copies the edge references into the given map.
+    ///
+    /// Reverse and copies the edge references into the given map.
+    template <typename EdgeRef>
+    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
+      for (EdgeIt it(source); it != INVALID; ++it) {
+        map.set(edgeRefMap[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 GraphCopy& 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 GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
+      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
+      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;
+    }
+
+  private:
+    
+    const Source& source;
+    Target& target;
+
+    NodeRefMap nodeRefMap;
+    EdgeRefMap edgeRefMap;
+  };
+
+  /// \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 edge to the source's
+  /// edges.
+  template <typename Target, typename Source>
+  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
+    return GraphCopy<Target, Source>(target, source);
+  }
 
   template <typename _Graph, typename _Item>