COIN-OR::LEMON - Graph Library

Changeset 1531:a3b20dd847b5 in lemon-0.x


Ignore:
Timestamp:
07/04/05 15:10:34 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2022
Message:

New graph copy interface

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1526 r1531  
    144144  }
    145145
     146  /// \brief Function to count the number of the out-edges from node \c n.
     147  ///
     148  /// This function counts the number of the out-edges from node \c n
     149  /// in the graph. 
     150  template <typename Graph>
     151  inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
     152    return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
     153  }
     154
     155  /// \brief Function to count the number of the in-edges to node \c n.
     156  ///
     157  /// This function counts the number of the in-edges to node \c n
     158  /// in the graph. 
     159  template <typename Graph>
     160  inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
     161    return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
     162  }
     163
     164
    146165  /// Finds an edge between two nodes of a graph.
    147166
     
    174193    return e;
    175194  }
    176  
    177   /// \brief Function to count the number of the out-edges from node \c n.
    178   ///
    179   /// This function counts the number of the out-edges from node \c n
    180   /// in the graph. 
    181   template <typename Graph>
    182   inline int countOutEdges(const Graph& _g,  const typename Graph::Node& _n) {
    183     return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n);
    184   }
    185 
    186   /// \brief Function to count the number of the in-edges to node \c n.
    187   ///
    188   /// This function counts the number of the in-edges to node \c n
    189   /// in the graph. 
    190   template <typename Graph>
    191   inline int countInEdges(const Graph& _g,  const typename Graph::Node& _n) {
    192     return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n);
    193   }
    194 
    195   // graph copy
    196 
    197   template <
    198     typename DestinationGraph,
    199     typename SourceGraph,
    200     typename NodeBijection>
    201   void copyNodes(DestinationGraph& _d, const SourceGraph& _s,
    202                  NodeBijection& _nb) {   
    203     for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) {
    204       _nb[it] = _d.addNode();
    205     }
    206   }
    207 
    208   template <
    209     typename DestinationGraph,
    210     typename SourceGraph,
    211     typename NodeBijection,
    212     typename EdgeBijection>
    213   void copyEdges(DestinationGraph& _d, const SourceGraph& _s,
    214                  const NodeBijection& _nb, EdgeBijection& _eb) {   
    215     for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) {
    216       _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]);
    217     }
    218   }
    219 
    220   template <
    221     typename DestinationGraph,
    222     typename SourceGraph,
    223     typename NodeBijection,
    224     typename EdgeBijection>
    225   void copyGraph(DestinationGraph& _d, const SourceGraph& _s,
    226                  NodeBijection& _nb, EdgeBijection& _eb) {
    227     nodeCopy(_d, _s, _nb);
    228     edgeCopy(_d, _s, _nb, _eb);
    229   }
    230  
    231   template <
    232     typename _DestinationGraph,
    233     typename _SourceGraph,
    234     typename _NodeBijection
    235     =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>,
    236     typename _EdgeBijection
    237     = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge>
    238   >
     195
     196  /// \brief Copy the source map to the target map.
     197  ///
     198  /// Copy the \c source map to the \c target map. It uses the given iterator
     199  /// to iterate on the data structure and it use the \c ref mapping to
     200  /// convert the source's keys to the target's keys.
     201  template <typename Target, typename Source,
     202            typename ItemIt, typename Ref>         
     203  void copyMap(Target& target, const Source& source,
     204               ItemIt it, const Ref& ref) {
     205    for (; it != INVALID; ++it) {
     206      target[ref[it]] = source[it];
     207    }
     208  }
     209
     210  /// \brief Copy the source map to the target map.
     211  ///
     212  /// Copy the \c source map to the \c target map. It uses the given iterator
     213  /// to iterate on the data structure.
     214  template <typename Target, typename Source,
     215            typename ItemIt>       
     216  void copyMap(Target& target, const Source& source, ItemIt it) {
     217    for (; it != INVALID; ++it) {
     218      target[it] = source[it];
     219    }
     220  }
     221
     222
     223  /// \brief Class to copy a graph to an other graph.
     224  ///
     225  /// Class to copy a graph to an other graph. It can be used easier
     226  /// with the \c copyGraph() function.
     227  template <typename Target, typename Source>
    239228  class GraphCopy {
    240   public:
    241    
    242     typedef _DestinationGraph DestinationGraph;
    243     typedef _SourceGraph SourceGraph;
    244 
    245     typedef _NodeBijection NodeBijection;
    246     typedef _EdgeBijection EdgeBijection;
    247    
    248   protected:         
    249    
    250     NodeBijection node_bijection;
    251     EdgeBijection edge_bijection;     
    252 
    253   public:
    254      
    255     GraphCopy(DestinationGraph& _d, const SourceGraph& _s) {
    256       copyGraph(_d, _s, node_bijection, edge_bijection);
    257     }
    258    
    259     const NodeBijection& getNodeBijection() const {
    260       return node_bijection;
    261     }
    262 
    263     const EdgeBijection& getEdgeBijection() const {
    264       return edge_bijection;
    265     }
    266      
    267   };
    268 
     229  public:
     230    typedef typename Source::Node Node;
     231    typedef typename Source::NodeIt NodeIt;
     232    typedef typename Source::Edge Edge;
     233    typedef typename Source::EdgeIt EdgeIt;
     234
     235    typedef typename Source::template NodeMap<typename Target::Node>NodeRefMap;
     236    typedef typename Source::template EdgeMap<typename Target::Edge>EdgeRefMap;
     237
     238    /// \brief Constructor for the GraphCopy.
     239    ///
     240    /// It copies the content of the \c _source graph into the
     241    /// \c _target graph. It creates also two references, one beetween
     242    /// the two nodeset and one beetween the two edgesets.
     243    GraphCopy(Target& _target, const Source& _source)
     244      : source(_source), target(_target),
     245        nodeRefMap(_source), edgeRefMap(_source) {
     246      for (NodeIt it(source); it != INVALID; ++it) {
     247        nodeRefMap[it] = target.addNode();
     248      }
     249      for (EdgeIt it(source); it != INVALID; ++it) {
     250        edgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
     251                                        nodeRefMap[source.target(it)]);
     252      }
     253    }
     254
     255    /// \brief Copies the node references into the given map.
     256    ///
     257    /// Copies the node references into the given map.
     258    template <typename NodeRef>
     259    const GraphCopy& nodeRef(NodeRef& map) const {
     260      for (NodeIt it(source); it != INVALID; ++it) {
     261        map.set(it, nodeRefMap[it]);
     262      }
     263      return *this;
     264    }
     265
     266    /// \brief Reverse and copies the node references into the given map.
     267    ///
     268    /// Reverse and copies the node references into the given map.
     269    template <typename NodeRef>
     270    const GraphCopy& nodeCrossRef(NodeRef& map) const {
     271      for (NodeIt it(source); it != INVALID; ++it) {
     272        map.set(nodeRefMap[it], it);
     273      }
     274      return *this;
     275    }
     276
     277    /// \brief Copies the edge references into the given map.
     278    ///
     279    /// Copies the edge references into the given map.
     280    template <typename EdgeRef>
     281    const GraphCopy& edgeRef(EdgeRef& map) const {
     282      for (EdgeIt it(source); it != INVALID; ++it) {
     283        map.set(it, edgeRefMap[it]);
     284      }
     285      return *this;
     286    }
     287
     288    /// \brief Reverse and copies the edge references into the given map.
     289    ///
     290    /// Reverse and copies the edge references into the given map.
     291    template <typename EdgeRef>
     292    const GraphCopy& edgeCrossRef(EdgeRef& map) const {
     293      for (EdgeIt it(source); it != INVALID; ++it) {
     294        map.set(edgeRefMap[it], it);
     295      }
     296      return *this;
     297    }
     298
     299    /// \brief Make copy of the given map.
     300    ///
     301    /// Makes copy of the given map for the newly created graph.
     302    /// The new map's key type is the target graph's node type,
     303    /// and the copied map's key type is the source graph's node
     304    /// type. 
     305    template <typename TargetMap, typename SourceMap>
     306    const GraphCopy& nodeMap(TargetMap& tMap, const SourceMap& sMap) const {
     307      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
     308      return *this;
     309    }
     310
     311    /// \brief Make copy of the given map.
     312    ///
     313    /// Makes copy of the given map for the newly created graph.
     314    /// The new map's key type is the target graph's edge type,
     315    /// and the copied map's key type is the source graph's edge
     316    /// type. 
     317    template <typename TargetMap, typename SourceMap>
     318    const GraphCopy& edgeMap(TargetMap& tMap, const SourceMap& sMap) const {
     319      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
     320      return *this;
     321    }
     322
     323    /// \brief Gives back the stored node references.
     324    ///
     325    /// Gives back the stored node references.
     326    const NodeRefMap& nodeRef() const {
     327      return nodeRefMap;
     328    }
     329
     330    /// \brief Gives back the stored edge references.
     331    ///
     332    /// Gives back the stored edge references.
     333    const EdgeRefMap& edgeRef() const {
     334      return edgeRefMap;
     335    }
     336
     337  private:
     338   
     339    const Source& source;
     340    Target& target;
     341
     342    NodeRefMap nodeRefMap;
     343    EdgeRefMap edgeRefMap;
     344  };
     345
     346  /// \brief Copy a graph to an other graph.
     347  ///
     348  /// Copy a graph to an other graph.
     349  /// The usage of the function:
     350  ///
     351  /// \code
     352  /// copyGraph(trg, src).nodeRef(nr).edgeCrossRef(ecr);
     353  /// \endcode
     354  ///
     355  /// After the copy the \c nr map will contain the mapping from the
     356  /// source graph's nodes to the target graph's nodes and the \c ecr will
     357  /// contain the mapping from the target graph's edge to the source's
     358  /// edges.
     359  template <typename Target, typename Source>
     360  GraphCopy<Target, Source> copyGraph(Target& target, const Source& source) {
     361    return GraphCopy<Target, Source>(target, source);
     362  }
    269363
    270364  template <typename _Graph, typename _Item>
  • lemon/maps.h

    r1456 r1531  
    207207  /// @{
    208208
     209  /// \brief Identity mapping.
     210  ///
     211  /// This mapping gives back the given key as value without any
     212  /// modification.
     213  template <typename T>
     214  class IdentityMap {
     215  public:
     216    typedef T Key;
     217    typedef T Value;
     218
     219    const Value& operator[](const Key& t) const {
     220      return t;
     221    }
     222  };
    209223
    210224  ///Convert the \c Value of a maps to another type.
Note: See TracChangeset for help on using the changeset viewer.