Rewritten countItems and findEdges
authordeba
Thu, 30 Mar 2006 08:38:41 +0000
changeset 2020332245399dc6
parent 2019 e70c1f6849bc
child 2021 11455e986b95
Rewritten countItems and findEdges
lemon/graph_utils.h
     1.1 --- a/lemon/graph_utils.h	Mon Mar 27 16:25:14 2006 +0000
     1.2 +++ b/lemon/graph_utils.h	Thu Mar 30 08:38:41 2006 +0000
     1.3 @@ -102,8 +102,9 @@
     1.4    /// The complexity of the function is O(n) because
     1.5    /// it iterates on all of the items.
     1.6  
     1.7 -  template <typename Graph, typename ItemIt>
     1.8 +  template <typename Graph, typename Item>
     1.9    inline int countItems(const Graph& g) {
    1.10 +    typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
    1.11      int num = 0;
    1.12      for (ItemIt it(g); it != INVALID; ++it) {
    1.13        ++num;
    1.14 @@ -113,15 +114,24 @@
    1.15  
    1.16    // Node counting:
    1.17  
    1.18 -  template <typename Graph>
    1.19 -  inline typename enable_if<typename Graph::NodeNumTag, int>::type
    1.20 -  _countNodes(const Graph &g) {
    1.21 -    return g.nodeNum();
    1.22 -  }
    1.23 +  namespace _graph_utils_bits {
    1.24 +    
    1.25 +    template <typename Graph, typename Enable = void>
    1.26 +    struct CountNodesSelector {
    1.27 +      static int count(const Graph &g) {
    1.28 +        return countItems<Graph, typename Graph::Node>(g);
    1.29 +      }
    1.30 +    };
    1.31  
    1.32 -  template <typename Graph>
    1.33 -  inline int _countNodes(Wrap<Graph> w) {
    1.34 -    return countItems<Graph, typename Graph::NodeIt>(w.value);
    1.35 +    template <typename Graph>
    1.36 +    struct CountNodesSelector<
    1.37 +      Graph, typename 
    1.38 +      enable_if<typename Graph::NodeNumTag, void>::type> 
    1.39 +    {
    1.40 +      static int count(const Graph &g) {
    1.41 +        return g.nodeNum();
    1.42 +      }
    1.43 +    };    
    1.44    }
    1.45  
    1.46    /// \brief Function to count the nodes in the graph.
    1.47 @@ -134,20 +144,30 @@
    1.48  
    1.49    template <typename Graph>
    1.50    inline int countNodes(const Graph& g) {
    1.51 -    return _countNodes<Graph>(g);
    1.52 +    return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
    1.53    }
    1.54  
    1.55 +
    1.56    // Edge counting:
    1.57  
    1.58 -  template <typename Graph>
    1.59 -  inline typename enable_if<typename Graph::EdgeNumTag, int>::type
    1.60 -  _countEdges(const Graph &g) {
    1.61 -    return g.edgeNum();
    1.62 -  }
    1.63 +  namespace _graph_utils_bits {
    1.64 +    
    1.65 +    template <typename Graph, typename Enable = void>
    1.66 +    struct CountEdgesSelector {
    1.67 +      static int count(const Graph &g) {
    1.68 +        return countItems<Graph, typename Graph::Edge>(g);
    1.69 +      }
    1.70 +    };
    1.71  
    1.72 -  template <typename Graph>
    1.73 -  inline int _countEdges(Wrap<Graph> w) {
    1.74 -    return countItems<Graph, typename Graph::EdgeIt>(w.value);
    1.75 +    template <typename Graph>
    1.76 +    struct CountEdgesSelector<
    1.77 +      Graph, 
    1.78 +      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
    1.79 +    {
    1.80 +      static int count(const Graph &g) {
    1.81 +        return g.edgeNum();
    1.82 +      }
    1.83 +    };    
    1.84    }
    1.85  
    1.86    /// \brief Function to count the edges in the graph.
    1.87 @@ -158,21 +178,28 @@
    1.88  
    1.89    template <typename Graph>
    1.90    inline int countEdges(const Graph& g) {
    1.91 -    return _countEdges<Graph>(g);
    1.92 +    return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
    1.93    }
    1.94  
    1.95    // Undirected edge counting:
    1.96 +  namespace _graph_utils_bits {
    1.97 +    
    1.98 +    template <typename Graph, typename Enable = void>
    1.99 +    struct CountUEdgesSelector {
   1.100 +      static int count(const Graph &g) {
   1.101 +        return countItems<Graph, typename Graph::UEdge>(g);
   1.102 +      }
   1.103 +    };
   1.104  
   1.105 -  template <typename Graph>
   1.106 -  inline
   1.107 -  typename enable_if<typename Graph::EdgeNumTag, int>::type
   1.108 -  _countUEdges(const Graph &g) {
   1.109 -    return g.uEdgeNum();
   1.110 -  }
   1.111 -
   1.112 -  template <typename Graph>
   1.113 -  inline int _countUEdges(Wrap<Graph> w) {
   1.114 -    return countItems<Graph, typename Graph::UEdgeIt>(w.value);
   1.115 +    template <typename Graph>
   1.116 +    struct CountUEdgesSelector<
   1.117 +      Graph, 
   1.118 +      typename enable_if<typename Graph::EdgeNumTag, void>::type> 
   1.119 +    {
   1.120 +      static int count(const Graph &g) {
   1.121 +        return g.uEdgeNum();
   1.122 +      }
   1.123 +    };    
   1.124    }
   1.125  
   1.126    /// \brief Function to count the undirected edges in the graph.
   1.127 @@ -183,11 +210,11 @@
   1.128  
   1.129    template <typename Graph>
   1.130    inline int countUEdges(const Graph& g) {
   1.131 -    return _countUEdges<Graph>(g);
   1.132 +    return _graph_utils_bits::CountUEdgesSelector<Graph>::count(g);
   1.133 +
   1.134    }
   1.135  
   1.136  
   1.137 -
   1.138    template <typename Graph, typename DegIt>
   1.139    inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
   1.140      int num = 0;
   1.141 @@ -224,32 +251,36 @@
   1.142      return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
   1.143    }
   1.144  
   1.145 +  namespace _graph_utils_bits {
   1.146 +    
   1.147 +    template <typename Graph, typename Enable = void>
   1.148 +    struct FindEdgeSelector {
   1.149 +      typedef typename Graph::Node Node;
   1.150 +      typedef typename Graph::Edge Edge;
   1.151 +      static Edge find(const Graph &g, Node u, Node v, Edge e) {
   1.152 +        if (e == INVALID) {
   1.153 +          g.firstOut(e, u);
   1.154 +        } else {
   1.155 +          g.nextOut(e);
   1.156 +        }
   1.157 +        while (e != INVALID && g.target(e) != v) {
   1.158 +          g.nextOut(e);
   1.159 +        }
   1.160 +        return e;
   1.161 +      }
   1.162 +    };
   1.163  
   1.164 -  template <typename Graph>
   1.165 -  inline
   1.166 -  typename enable_if<typename Graph::FindEdgeTag, typename Graph::Edge>::type 
   1.167 -  _findEdge(const Graph &g,
   1.168 -	    typename Graph::Node u, typename Graph::Node v,
   1.169 -	    typename Graph::Edge prev = INVALID) {
   1.170 -    return g.findEdge(u, v, prev);
   1.171 -  }
   1.172 -
   1.173 -  template <typename Graph>
   1.174 -  inline typename Graph::Edge 
   1.175 -  _findEdge(Wrap<Graph> w,
   1.176 -	    typename Graph::Node u, 
   1.177 -	    typename Graph::Node v,
   1.178 -	    typename Graph::Edge prev = INVALID) {
   1.179 -    const Graph& g = w.value;
   1.180 -    if (prev == INVALID) {
   1.181 -      typename Graph::OutEdgeIt e(g, u);
   1.182 -      while (e != INVALID && g.target(e) != v) ++e;
   1.183 -      return e;
   1.184 -    } else {
   1.185 -      typename Graph::OutEdgeIt e(g, prev); ++e;
   1.186 -      while (e != INVALID && g.target(e) != v) ++e;
   1.187 -      return e;
   1.188 -    }
   1.189 +    template <typename Graph>
   1.190 +    struct FindEdgeSelector<
   1.191 +      Graph, 
   1.192 +      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
   1.193 +    {
   1.194 +      typedef typename Graph::Node Node;
   1.195 +      typedef typename Graph::Edge Edge;
   1.196 +      static Edge find(const Graph &g, Node u, Node v, Edge prev) {
   1.197 +        return g.findEdge(u, v, prev);
   1.198 +      }
   1.199 +    };    
   1.200    }
   1.201  
   1.202    /// \brief Finds an edge between two nodes of a graph.
   1.203 @@ -267,14 +298,12 @@
   1.204    ///   ...
   1.205    /// }
   1.206    ///\endcode
   1.207 -  // /// \todo We may want to use the "GraphBase" 
   1.208 -  // /// interface here...
   1.209    template <typename Graph>
   1.210    inline typename Graph::Edge findEdge(const Graph &g,
   1.211  				       typename Graph::Node u, 
   1.212  				       typename Graph::Node v,
   1.213  				       typename Graph::Edge prev = INVALID) {
   1.214 -    return _findEdge<Graph>(g, u, v, prev);
   1.215 +    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, prev);
   1.216    }
   1.217  
   1.218    /// \brief Iterator for iterating on edges connected the same nodes.
   1.219 @@ -325,38 +354,57 @@
   1.220      const Graph& graph;
   1.221    };
   1.222  
   1.223 -  template <typename Graph>
   1.224 -  inline
   1.225 -  typename enable_if<
   1.226 -    typename Graph::FindEdgeTag, 
   1.227 -    typename Graph::UEdge>::type 
   1.228 -  _findUEdge(const Graph &g,
   1.229 -	    typename Graph::Node u, typename Graph::Node v,
   1.230 -	    typename Graph::UEdge prev = INVALID) {
   1.231 -    return g.findUEdge(u, v, prev);
   1.232 -  }
   1.233 +  namespace _graph_utils_bits {
   1.234 +    
   1.235 +    template <typename Graph, typename Enable = void>
   1.236 +    struct FindUEdgeSelector {
   1.237 +      typedef typename Graph::Node Node;
   1.238 +      typedef typename Graph::UEdge UEdge;
   1.239 +      static UEdge find(const Graph &g, Node u, Node v, UEdge e) {
   1.240 +        bool b;
   1.241 +        if (u != v) {
   1.242 +          if (e == INVALID) {
   1.243 +            g.firstInc(e, u, b);
   1.244 +          } else {
   1.245 +            b = g.source(e) == u;
   1.246 +            g.nextInc(e, b);
   1.247 +          }
   1.248 +          while (e != INVALID && g.target(e) != v) {
   1.249 +            g.nextInc(e, b);
   1.250 +          }
   1.251 +        } else {
   1.252 +          if (e == INVALID) {
   1.253 +            g.firstInc(e, u, b);
   1.254 +          } else {
   1.255 +            b = true;
   1.256 +            g.nextInc(e, b);
   1.257 +          }
   1.258 +          while (e != INVALID && (!b || g.target(e) != v)) {
   1.259 +            g.nextInc(e, b);
   1.260 +          }
   1.261 +        }
   1.262 +        return e;
   1.263 +      }
   1.264 +    };
   1.265  
   1.266 -  template <typename Graph>
   1.267 -  inline typename Graph::UEdge 
   1.268 -  _findUEdge(Wrap<Graph> w,
   1.269 -	    typename Graph::Node u, 
   1.270 -	    typename Graph::Node v,
   1.271 -	    typename Graph::UEdge prev = INVALID) {
   1.272 -    const Graph& g = w.value;
   1.273 -    if (prev == INVALID) {
   1.274 -      typename Graph::OutEdgeIt e(g, u);
   1.275 -      while (e != INVALID && g.target(e) != v) ++e;
   1.276 -      return e;
   1.277 -    } else {
   1.278 -      typename Graph::OutEdgeIt e(g, g.direct(prev, u)); ++e;
   1.279 -      while (e != INVALID && g.target(e) != v) ++e;
   1.280 -      return e;
   1.281 -    }
   1.282 +    template <typename Graph>
   1.283 +    struct FindUEdgeSelector<
   1.284 +      Graph, 
   1.285 +      typename enable_if<typename Graph::FindEdgeTag, void>::type> 
   1.286 +    {
   1.287 +      typedef typename Graph::Node Node;
   1.288 +      typedef typename Graph::UEdge UEdge;
   1.289 +      static UEdge find(const Graph &g, Node u, Node v, UEdge prev) {
   1.290 +        return g.findUEdge(u, v, prev);
   1.291 +      }
   1.292 +    };    
   1.293    }
   1.294  
   1.295    /// \brief Finds an uedge between two nodes of a graph.
   1.296    ///
   1.297    /// Finds an uedge from node \c u to node \c v in graph \c g.
   1.298 +  /// If the node \c u and node \c v is equal then each loop edge
   1.299 +  /// will be enumerated.
   1.300    ///
   1.301    /// If \c prev is \ref INVALID (this is the default value), then
   1.302    /// it finds the first edge from \c u to \c v. Otherwise it looks for
   1.303 @@ -370,15 +418,12 @@
   1.304    ///   ...
   1.305    /// }
   1.306    ///\endcode
   1.307 -  // /// \todo We may want to use the "GraphBase" 
   1.308 -  // /// interface here...
   1.309    template <typename Graph>
   1.310 -  inline typename Graph::UEdge 
   1.311 -  findUEdge(const Graph &g,
   1.312 -		typename Graph::Node u, 
   1.313 -		typename Graph::Node v,
   1.314 -		typename Graph::UEdge prev = INVALID) {
   1.315 -    return _findUEdge<Graph>(g, u, v, prev);
   1.316 +  inline typename Graph::UEdge findEdge(const Graph &g,
   1.317 +                                        typename Graph::Node u, 
   1.318 +                                        typename Graph::Node v,
   1.319 +                                        typename Graph::UEdge prev = INVALID) {
   1.320 +    return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev);
   1.321    }
   1.322  
   1.323    /// \brief Iterator for iterating on uedges connected the same nodes.