COIN-OR::LEMON - Graph Library

Changeset 2235:48801095a410 in lemon-0.x


Ignore:
Timestamp:
10/12/06 12:53:25 (13 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2978
Message:

EdgeLookUp? and AllEdgeLookUp? added.

Files:
3 added
2 edited

Legend:

Unmodified
Added
Removed
  • benchmark/Makefile.am

    r2119 r2235  
    11EXTRA_DIST += \
    22        benchmark/Makefile
     3        benchmark/edge_lookup_test
    34
    45noinst_HEADERS += benchmark/bench_tools.h
     
    1213        benchmark/bfs-bench \
    1314        benchmark/radix_sort-bench \
    14         benchmark/swap_bipartite_bench
     15        benchmark/swap_bipartite_bench \
     16        benchmark/edge_lookup
    1517
    1618endif WANT_BENCHMARK
     
    2527
    2628benchmark_swap_bipartite_bench_SOURCES = benchmark/swap_bipartite_bench.cc
     29
     30benchmark_edge_lookup_SOURCES = benchmark/edge_lookup.cc
  • lemon/graph_utils.h

    r2201 r2235  
    2424#include <map>
    2525#include <cmath>
     26#include <algorithm>
    2627
    2728#include <lemon/bits/invalid.h>
     
    375376  ///\endcode
    376377  ///
     378  ///\sa EdgeLookUp
     379  ///\se AllEdgeLookup
    377380  ///\sa ConEdgeIt
    378381  template <typename Graph>
     
    396399  ///
    397400  ///\sa findEdge()
     401  ///\sa EdgeLookUp
     402  ///\se AllEdgeLookup
    398403  ///
    399404  /// \author Balazs Dezso
     
    18391844
    18401845
     1846  ///Fast edge look up between given endpoints.
     1847 
     1848  ///\ingroup gutils
     1849  ///Using this class, you can find an edge in a graph from a given
     1850  ///source to a given target in time <em>O(log d)</em>,
     1851  ///where <em>d</em> is the out-degree of the source node.
     1852  ///
     1853  ///It is not possible to find \e all parallel edges between two nodes.
     1854  ///Use \ref AllEdgeLookUp for this purpose.
     1855  ///
     1856  ///\warning This class is static, so you should refresh() (or at least
     1857  ///refresh(Node)) this data structure
     1858  ///whenever the graph changes. This is a time consuming (superlinearly
     1859  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
     1860  ///
     1861  ///\param G The type of the underlying graph.
     1862  ///
     1863  ///\sa AllEdgeLookUp 
     1864  template<class G>
     1865  class EdgeLookUp
     1866  {
     1867  public:
     1868    GRAPH_TYPEDEFS(typename G)
     1869    typedef G Graph;
     1870
     1871  protected:
     1872    const Graph &_g;
     1873    typename Graph::template NodeMap<Edge> _head;
     1874    typename Graph::template EdgeMap<Edge> _left;
     1875    typename Graph::template EdgeMap<Edge> _right;
     1876   
     1877    class EdgeLess {
     1878      const Graph &g;
     1879    public:
     1880      EdgeLess(const Graph &_g) : g(_g) {}
     1881      bool operator()(Edge a,Edge b) const
     1882      {
     1883        return g.target(a)<g.target(b);
     1884      }
     1885    };
     1886   
     1887  public:
     1888   
     1889    ///Constructor
     1890
     1891    ///Constructor.
     1892    ///
     1893    ///It builds up the search database, which remains valid until the graph
     1894    ///changes.
     1895    EdgeLookUp(const Graph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
     1896   
     1897  private:
     1898    Edge refresh_rec(std::vector<Edge> &v,int a,int b)
     1899    {
     1900      int m=(a+b)/2;
     1901      Edge me=v[m];
     1902      _left[me] = a<m?refresh_rec(v,a,m-1):INVALID;
     1903      _right[me] = m<b?refresh_rec(v,m+1,b):INVALID;
     1904      return me;
     1905    }
     1906  public:
     1907    ///Refresh the data structure at a node.
     1908
     1909    ///Build up the search database of node \c n.
     1910    ///
     1911    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
     1912    ///the number of the outgoing edges of \c n.
     1913    void refresh(Node n)
     1914    {
     1915      std::vector<Edge> v;
     1916      for(OutEdgeIt e(_g,n);e!=INVALID;++e) v.push_back(e);
     1917      if(v.size()) {
     1918        std::sort(v.begin(),v.end(),EdgeLess(_g));
     1919        _head[n]=refresh_rec(v,0,v.size()-1);
     1920      }
     1921      else _head[n]=INVALID;
     1922    }
     1923    ///Refresh the full data structure.
     1924
     1925    ///Build up the full search database. In fact, it simply calls
     1926    ///\ref refresh(Node) "refresh(n)" for each node \c n.
     1927    ///
     1928    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
     1929    ///the number of the edges of \c n and <em>D</em> is the maximum
     1930    ///out-degree of the graph.
     1931
     1932    void refresh()
     1933    {
     1934      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
     1935    }
     1936   
     1937    ///Find an edge between two nodes.
     1938   
     1939    ///Find an edge between two nodes in time <em>O(</em>log<em>d)</em>, where
     1940    /// <em>d</em> is the number of outgoing edges of \c s.
     1941    ///\param s The source node
     1942    ///\param t The target node
     1943    ///\return An edge from \c s to \c t if there exists,
     1944    ///\ref INVALID otherwise.
     1945    ///
     1946    ///\warning If you change the graph, refresh() must be called before using
     1947    ///this operator. If you change the outgoing edges of
     1948    ///a single node \c n, then
     1949    ///\ref refresh(Node) "refresh(n)" is enough.
     1950    ///
     1951    Edge operator()(Node s, Node t) const
     1952    {
     1953      Edge e;
     1954      for(e=_head[s];
     1955          e!=INVALID&&_g.target(e)!=t;
     1956          e = t < _g.target(e)?_left[e]:_right[e]) ;
     1957      return e;
     1958    }
     1959
     1960  };
     1961
     1962  ///Fast look up of all edges between given endpoints.
     1963 
     1964  ///\ingroup gutils
     1965  ///This class is the same as \ref EdgeLookUp, with the addition
     1966  ///that it makes it possible to find all edges between given endpoints.
     1967  ///
     1968  ///\warning This class is static, so you should refresh() (or at least
     1969  ///refresh(Node)) this data structure
     1970  ///whenever the graph changes. This is a time consuming (superlinearly
     1971  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of edges).
     1972  ///
     1973  ///\param G The type of the underlying graph.
     1974  ///
     1975  ///\sa EdgeLookUp 
     1976  template<class G>
     1977  class AllEdgeLookUp : public EdgeLookUp<G>
     1978  {
     1979    using EdgeLookUp<G>::_g;
     1980    using EdgeLookUp<G>::_right;
     1981    using EdgeLookUp<G>::_left;
     1982    using EdgeLookUp<G>::_head;
     1983
     1984    GRAPH_TYPEDEFS(typename G)
     1985    typedef G Graph;
     1986   
     1987    typename Graph::template EdgeMap<Edge> _next;
     1988   
     1989    Edge refreshNext(Edge head,Edge next=INVALID)
     1990    {
     1991      if(head==INVALID) return next;
     1992      else {
     1993        next=refreshNext(_right[head],next);
     1994//      _next[head]=next;
     1995        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
     1996          ? next : INVALID;
     1997        return refreshNext(_left[head],head);
     1998      }
     1999    }
     2000   
     2001    void refreshNext()
     2002    {
     2003      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
     2004    }
     2005   
     2006  public:
     2007    ///Constructor
     2008
     2009    ///Constructor.
     2010    ///
     2011    ///It builds up the search database, which remains valid until the graph
     2012    ///changes.
     2013    AllEdgeLookUp(const Graph &g) : EdgeLookUp<G>(g), _next(g) {refreshNext();}
     2014
     2015    ///Refresh the data structure at a node.
     2016
     2017    ///Build up the search database of node \c n.
     2018    ///
     2019    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
     2020    ///the number of the outgoing edges of \c n.
     2021   
     2022    void refresh(Node n)
     2023    {
     2024      EdgeLookUp<G>::refresh(n);
     2025      refreshNext(_head[n]);
     2026    }
     2027   
     2028    ///Refresh the full data structure.
     2029
     2030    ///Build up the full search database. In fact, it simply calls
     2031    ///\ref refresh(Node) "refresh(n)" for each node \c n.
     2032    ///
     2033    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
     2034    ///the number of the edges of \c n and <em>D</em> is the maximum
     2035    ///out-degree of the graph.
     2036
     2037    void refresh()
     2038    {
     2039      for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
     2040    }
     2041   
     2042    ///Find an edge between two nodes.
     2043   
     2044    ///Find an edge between two nodes.
     2045    ///\param s The source node
     2046    ///\param t The target node
     2047    ///\param prev The previous edge between \c s and \c t. It it is INVALID or
     2048    ///not given, the operator finds the first appropriate edge.
     2049    ///\return An edge from \c s to \c t after \prev or
     2050    ///\ref INVALID if there is no more.
     2051    ///
     2052    ///For example, you can count the number of edges from \c u to \c v in the
     2053    ///following way.
     2054    ///\code
     2055    ///AllEdgeLookUp<ListGraph> ae(g);
     2056    ///...
     2057    ///int n=0;
     2058    ///for(Edge e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
     2059    ///\endcode
     2060    ///
     2061    ///Finding the first edge take <em>O(</em>log<em>d)</em> time, where
     2062    /// <em>d</em> is the number of outgoing edges of \c s. Then, the
     2063    ///consecutive edges are found in constant time.
     2064    ///
     2065    ///\warning If you change the graph, refresh() must be called before using
     2066    ///this operator. If you change the outgoing edges of
     2067    ///a single node \c n, then
     2068    ///\ref refresh(Node) "refresh(n)" is enough.
     2069    ///
     2070#ifdef DOXYGEN
     2071    Edge operator()(Node s, Node t, Edge prev=INVALID) const {}
     2072#else
     2073    using EdgeLookUp<G>::operator() ;
     2074    Edge operator()(Node s, Node t, Edge prev) const
     2075    {
     2076      return prev==INVALID?(*this)(s,t):_next[prev];
     2077    }
     2078#endif
     2079     
     2080  };
     2081
    18412082  /// @}
    18422083
Note: See TracChangeset for help on using the changeset viewer.