COIN-OR::LEMON - Graph Library

Changeset 1909:2d806130e700 in lemon-0.x for lemon/graph_utils.h


Ignore:
Timestamp:
01/26/06 16:42:13 (14 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
Message:

Undir -> U transition

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_utils.h

    r1875 r1909  
    7272  ///This \c \#define creates the same convenience typedefs as defined by
    7373  ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
    74   ///\c UndirEdge, \c UndirEdgeIt, \c IncEdgeIt,
    75   ///\c BoolUndirEdgeMap, \c IntUndirEdgeMap,  \c DoubleUndirEdgeMap. 
     74  ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
     75  ///\c BoolUEdgeMap, \c IntUEdgeMap,  \c DoubleUEdgeMap. 
    7676  ///
    7777  ///\note If \c G it a template parameter, it should be used in this way.
     
    8484#define UNDIRGRAPH_TYPEDEFS(Graph)                              \
    8585  GRAPH_TYPEDEFS(Graph)                                         \
    86     typedef Graph:: UndirEdge   UndirEdge;                      \
    87     typedef Graph:: UndirEdgeIt UndirEdgeIt;                    \
     86    typedef Graph:: UEdge   UEdge;                      \
     87    typedef Graph:: UEdgeIt UEdgeIt;                    \
    8888    typedef Graph:: IncEdgeIt   IncEdgeIt;                     
    89 //     typedef Graph::template UndirEdgeMap<bool> BoolUndirEdgeMap;     
    90 //     typedef Graph::template UndirEdgeMap<int> IntUndirEdgeMap;
    91 //     typedef Graph::template UndirEdgeMap<double> DoubleUndirEdgeMap;
     89//     typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;     
     90//     typedef Graph::template UEdgeMap<int> IntUEdgeMap;
     91//     typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
    9292 
    9393
     
    163163  inline
    164164  typename enable_if<typename Graph::EdgeNumTag, int>::type
    165   _countUndirEdges(const Graph &g) {
    166     return g.undirEdgeNum();
    167   }
    168 
    169   template <typename Graph>
    170   inline int _countUndirEdges(Wrap<Graph> w) {
    171     return countItems<Graph, typename Graph::UndirEdgeIt>(w.value);
     165  _countUEdges(const Graph &g) {
     166    return g.uEdgeNum();
     167  }
     168
     169  template <typename Graph>
     170  inline int _countUEdges(Wrap<Graph> w) {
     171    return countItems<Graph, typename Graph::UEdgeIt>(w.value);
    172172  }
    173173
     
    179179
    180180  template <typename Graph>
    181   inline int countUndirEdges(const Graph& g) {
    182     return _countUndirEdges<Graph>(g);
     181  inline int countUEdges(const Graph& g) {
     182    return _countUEdges<Graph>(g);
    183183  }
    184184
     
    326326  typename enable_if<
    327327    typename Graph::FindEdgeTag,
    328     typename Graph::UndirEdge>::type
    329   _findUndirEdge(const Graph &g,
     328    typename Graph::UEdge>::type
     329  _findUEdge(const Graph &g,
    330330            typename Graph::Node u, typename Graph::Node v,
    331             typename Graph::UndirEdge prev = INVALID) {
    332     return g.findUndirEdge(u, v, prev);
    333   }
    334 
    335   template <typename Graph>
    336   inline typename Graph::UndirEdge
    337   _findUndirEdge(Wrap<Graph> w,
     331            typename Graph::UEdge prev = INVALID) {
     332    return g.findUEdge(u, v, prev);
     333  }
     334
     335  template <typename Graph>
     336  inline typename Graph::UEdge
     337  _findUEdge(Wrap<Graph> w,
    338338            typename Graph::Node u,
    339339            typename Graph::Node v,
    340             typename Graph::UndirEdge prev = INVALID) {
     340            typename Graph::UEdge prev = INVALID) {
    341341    const Graph& g = w.value;
    342342    if (prev == INVALID) {
     
    351351  }
    352352
    353   /// \brief Finds an undir edge between two nodes of a graph.
    354   ///
    355   /// Finds an undir edge from node \c u to node \c v in graph \c g.
     353  /// \brief Finds an uedge between two nodes of a graph.
     354  ///
     355  /// Finds an uedge from node \c u to node \c v in graph \c g.
    356356  ///
    357357  /// If \c prev is \ref INVALID (this is the default value), then
     
    362362  /// Thus you can iterate through each edge from \c u to \c v as it follows.
    363363  /// \code
    364   /// for(UndirEdge e = findUndirEdge(g,u,v); e != INVALID;
    365   ///     e = findUndirEdge(g,u,v,e)) {
     364  /// for(UEdge e = findUEdge(g,u,v); e != INVALID;
     365  ///     e = findUEdge(g,u,v,e)) {
    366366  ///   ...
    367367  /// }
     
    370370  // /// interface here...
    371371  template <typename Graph>
    372   inline typename Graph::UndirEdge
    373   findUndirEdge(const Graph &g,
     372  inline typename Graph::UEdge
     373  findUEdge(const Graph &g,
    374374                typename Graph::Node u,
    375375                typename Graph::Node v,
    376                 typename Graph::UndirEdge prev = INVALID) {
    377     return _findUndirEdge<Graph>(g, u, v, prev);
    378   }
    379 
    380   /// \brief Iterator for iterating on undir edges connected the same nodes.
    381   ///
    382   /// Iterator for iterating on undir edges connected the same nodes. It is
    383   /// higher level interface for the findUndirEdge() function. You can
     376                typename Graph::UEdge prev = INVALID) {
     377    return _findUEdge<Graph>(g, u, v, prev);
     378  }
     379
     380  /// \brief Iterator for iterating on uedges connected the same nodes.
     381  ///
     382  /// Iterator for iterating on uedges connected the same nodes. It is
     383  /// higher level interface for the findUEdge() function. You can
    384384  /// use it the following way:
    385385  /// \code
    386   /// for (ConUndirEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
     386  /// for (ConUEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
    387387  ///   ...
    388388  /// }
     
    391391  /// \author Balazs Dezso
    392392  template <typename _Graph>
    393   class ConUndirEdgeIt : public _Graph::UndirEdge {
     393  class ConUEdgeIt : public _Graph::UEdge {
    394394  public:
    395395
    396396    typedef _Graph Graph;
    397     typedef typename Graph::UndirEdge Parent;
    398 
    399     typedef typename Graph::UndirEdge UndirEdge;
     397    typedef typename Graph::UEdge Parent;
     398
     399    typedef typename Graph::UEdge UEdge;
    400400    typedef typename Graph::Node Node;
    401401
    402402    /// \brief Constructor.
    403403    ///
    404     /// Construct a new ConUndirEdgeIt iterating on the edges which
     404    /// Construct a new ConUEdgeIt iterating on the edges which
    405405    /// connects the \c u and \c v node.
    406     ConUndirEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
    407       Parent::operator=(findUndirEdge(graph, u, v));
     406    ConUEdgeIt(const Graph& g, Node u, Node v) : graph(g) {
     407      Parent::operator=(findUEdge(graph, u, v));
    408408    }
    409409
    410410    /// \brief Constructor.
    411411    ///
    412     /// Construct a new ConUndirEdgeIt which continues the iterating from
     412    /// Construct a new ConUEdgeIt which continues the iterating from
    413413    /// the \c e edge.
    414     ConUndirEdgeIt(const Graph& g, UndirEdge e) : Parent(e), graph(g) {}
     414    ConUEdgeIt(const Graph& g, UEdge e) : Parent(e), graph(g) {}
    415415   
    416416    /// \brief Increment operator.
    417417    ///
    418418    /// It increments the iterator and gives back the next edge.
    419     ConUndirEdgeIt& operator++() {
    420       Parent::operator=(findUndirEdge(graph, graph.source(*this),
     419    ConUEdgeIt& operator++() {
     420      Parent::operator=(findUEdge(graph, graph.source(*this),
    421421                                      graph.target(*this), *this));
    422422      return *this;
     
    597597  ///
    598598  /// Class to copy an undirected graph to an other graph (duplicate a graph).
    599   /// The simplest way of using it is through the \c copyUndirGraph() function.
     599  /// The simplest way of using it is through the \c copyUGraph() function.
    600600  template <typename Target, typename Source>
    601   class UndirGraphCopy {
     601  class UGraphCopy {
    602602  public:
    603603    typedef typename Source::Node Node;
     
    605605    typedef typename Source::Edge Edge;
    606606    typedef typename Source::EdgeIt EdgeIt;
    607     typedef typename Source::UndirEdge UndirEdge;
    608     typedef typename Source::UndirEdgeIt UndirEdgeIt;
     607    typedef typename Source::UEdge UEdge;
     608    typedef typename Source::UEdgeIt UEdgeIt;
    609609
    610610    typedef typename Source::
     
    612612   
    613613    typedef typename Source::
    614     template UndirEdgeMap<typename Target::UndirEdge> UndirEdgeRefMap;
     614    template UEdgeMap<typename Target::UEdge> UEdgeRefMap;
    615615
    616616  private:
    617617
    618618    struct EdgeRefMap {
    619       EdgeRefMap(UndirGraphCopy& _gc) : gc(_gc) {}
     619      EdgeRefMap(UGraphCopy& _gc) : gc(_gc) {}
    620620      typedef typename Source::Edge Key;
    621621      typedef typename Target::Edge Value;
    622622
    623623      Value operator[](const Key& key) {
    624         return gc.target.direct(gc.undirEdgeRef[key],
     624        return gc.target.direct(gc.uEdgeRef[key],
    625625                                gc.target.direction(key));
    626626      }
    627627     
    628       UndirGraphCopy& gc;
     628      UGraphCopy& gc;
    629629    };
    630630   
    631631  public:
    632632
    633     /// \brief Constructor for the UndirGraphCopy.
     633    /// \brief Constructor for the UGraphCopy.
    634634    ///
    635635    /// It copies the content of the \c _source graph into the
    636636    /// \c _target graph. It creates also two references, one beetween
    637637    /// the two nodeset and one beetween the two edgesets.
    638     UndirGraphCopy(Target& _target, const Source& _source)
     638    UGraphCopy(Target& _target, const Source& _source)
    639639      : source(_source), target(_target),
    640         nodeRefMap(_source), edgeRefMap(*this), undirEdgeRefMap(_source) {
     640        nodeRefMap(_source), edgeRefMap(*this), uEdgeRefMap(_source) {
    641641      for (NodeIt it(source); it != INVALID; ++it) {
    642642        nodeRefMap[it] = target.addNode();
    643643      }
    644       for (UndirEdgeIt it(source); it != INVALID; ++it) {
    645         undirEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
     644      for (UEdgeIt it(source); it != INVALID; ++it) {
     645        uEdgeRefMap[it] = target.addEdge(nodeRefMap[source.source(it)],
    646646                                        nodeRefMap[source.target(it)]);
    647647      }
     
    652652    /// Copies the node references into the given map.
    653653    template <typename NodeRef>
    654     const UndirGraphCopy& nodeRef(NodeRef& map) const {
     654    const UGraphCopy& nodeRef(NodeRef& map) const {
    655655      for (NodeIt it(source); it != INVALID; ++it) {
    656656        map.set(it, nodeRefMap[it]);
     
    663663    /// Reverse and copies the node references into the given map.
    664664    template <typename NodeRef>
    665     const UndirGraphCopy& nodeCrossRef(NodeRef& map) const {
     665    const UGraphCopy& nodeCrossRef(NodeRef& map) const {
    666666      for (NodeIt it(source); it != INVALID; ++it) {
    667667        map.set(nodeRefMap[it], it);
     
    674674    /// Copies the edge references into the given map.
    675675    template <typename EdgeRef>
    676     const UndirGraphCopy& edgeRef(EdgeRef& map) const {
     676    const UGraphCopy& edgeRef(EdgeRef& map) const {
    677677      for (EdgeIt it(source); it != INVALID; ++it) {
    678678        map.set(edgeRefMap[it], it);
     
    686686    /// Reverse and copies the undirected edge references into the given map.
    687687    template <typename EdgeRef>
    688     const UndirGraphCopy& edgeCrossRef(EdgeRef& map) const {
     688    const UGraphCopy& edgeCrossRef(EdgeRef& map) const {
    689689      for (EdgeIt it(source); it != INVALID; ++it) {
    690690        map.set(it, edgeRefMap[it]);
     
    697697    /// Copies the undirected edge references into the given map.
    698698    template <typename EdgeRef>
    699     const UndirGraphCopy& undirEdgeRef(EdgeRef& map) const {
    700       for (UndirEdgeIt it(source); it != INVALID; ++it) {
    701         map.set(it, undirEdgeRefMap[it]);
     699    const UGraphCopy& uEdgeRef(EdgeRef& map) const {
     700      for (UEdgeIt it(source); it != INVALID; ++it) {
     701        map.set(it, uEdgeRefMap[it]);
    702702      }
    703703      return *this;
     
    709709    /// Reverse and copies the undirected edge references into the given map.
    710710    template <typename EdgeRef>
    711     const UndirGraphCopy& undirEdgeCrossRef(EdgeRef& map) const {
    712       for (UndirEdgeIt it(source); it != INVALID; ++it) {
    713         map.set(undirEdgeRefMap[it], it);
     711    const UGraphCopy& uEdgeCrossRef(EdgeRef& map) const {
     712      for (UEdgeIt it(source); it != INVALID; ++it) {
     713        map.set(uEdgeRefMap[it], it);
    714714      }
    715715      return *this;
     
    723723    /// type. 
    724724    template <typename TargetMap, typename SourceMap>
    725     const UndirGraphCopy& nodeMap(TargetMap& tMap,
     725    const UGraphCopy& nodeMap(TargetMap& tMap,
    726726                                  const SourceMap& sMap) const {
    727727      copyMap(tMap, sMap, NodeIt(source), nodeRefMap);
     
    736736    /// type. 
    737737    template <typename TargetMap, typename SourceMap>
    738     const UndirGraphCopy& edgeMap(TargetMap& tMap,
     738    const UGraphCopy& edgeMap(TargetMap& tMap,
    739739                                  const SourceMap& sMap) const {
    740740      copyMap(tMap, sMap, EdgeIt(source), edgeRefMap);
     
    749749    /// type. 
    750750    template <typename TargetMap, typename SourceMap>
    751     const UndirGraphCopy& undirEdgeMap(TargetMap& tMap,
     751    const UGraphCopy& uEdgeMap(TargetMap& tMap,
    752752                                  const SourceMap& sMap) const {
    753       copyMap(tMap, sMap, UndirEdgeIt(source), undirEdgeRefMap);
     753      copyMap(tMap, sMap, UEdgeIt(source), uEdgeRefMap);
    754754      return *this;
    755755    }
     
    769769    }
    770770
    771     /// \brief Gives back the stored undir edge references.
    772     ///
    773     /// Gives back the stored undir edge references.
    774     const UndirEdgeRefMap& undirEdgeRef() const {
    775       return undirEdgeRefMap;
     771    /// \brief Gives back the stored uedge references.
     772    ///
     773    /// Gives back the stored uedge references.
     774    const UEdgeRefMap& uEdgeRef() const {
     775      return uEdgeRefMap;
    776776    }
    777777
     
    785785    NodeRefMap nodeRefMap;
    786786    EdgeRefMap edgeRefMap;
    787     UndirEdgeRefMap undirEdgeRefMap;
     787    UEdgeRefMap uEdgeRefMap;
    788788  };
    789789
     
    802802  /// edges.
    803803  template <typename Target, typename Source>
    804   UndirGraphCopy<Target, Source>
    805   copyUndirGraph(Target& target, const Source& source) {
    806     return UndirGraphCopy<Target, Source>(target, source);
     804  UGraphCopy<Target, Source>
     805  copyUGraph(Target& target, const Source& source) {
     806    return UGraphCopy<Target, Source>(target, source);
    807807  }
    808808
     
    906906    typedef _Graph Graph;
    907907
    908     /// The key type of InvertableMap (Node, Edge, UndirEdge).
     908    /// The key type of InvertableMap (Node, Edge, UEdge).
    909909    typedef typename _Map::Key Key;
    910910    /// The value type of the InvertableMap.
     
    10371037  /// \param _Graph The graph class the \c DescriptorMap belongs to.
    10381038  /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
    1039   /// UndirEdge.
     1039  /// UEdge.
    10401040#ifndef DOXYGEN
    10411041  /// \param _Map A ReadWriteMap mapping from the item type to integer.
     
    10561056    typedef _Graph Graph;
    10571057
    1058     /// The key type of DescriptorMap (Node, Edge, UndirEdge).
     1058    /// The key type of DescriptorMap (Node, Edge, UEdge).
    10591059    typedef typename _Map::Key Key;
    10601060    /// The value type of DescriptorMap.
     
    12971297
    12981298    typedef typename Graph::Edge Value;
    1299     typedef typename Graph::UndirEdge Key;
     1299    typedef typename Graph::UEdge Key;
    13001300
    13011301    /// \brief Constructor
     
    13361336
    13371337    typedef typename Graph::Edge Value;
    1338     typedef typename Graph::UndirEdge Key;
     1338    typedef typename Graph::UEdge Key;
    13391339
    13401340    /// \brief Constructor
Note: See TracChangeset for help on using the changeset viewer.