Changeset 2235:48801095a410 in lemon-0.x
- Timestamp:
- 10/12/06 12:53:25 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2978
- Files:
-
- 3 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
benchmark/Makefile.am
r2119 r2235 1 1 EXTRA_DIST += \ 2 2 benchmark/Makefile 3 benchmark/edge_lookup_test 3 4 4 5 noinst_HEADERS += benchmark/bench_tools.h … … 12 13 benchmark/bfs-bench \ 13 14 benchmark/radix_sort-bench \ 14 benchmark/swap_bipartite_bench 15 benchmark/swap_bipartite_bench \ 16 benchmark/edge_lookup 15 17 16 18 endif WANT_BENCHMARK … … 25 27 26 28 benchmark_swap_bipartite_bench_SOURCES = benchmark/swap_bipartite_bench.cc 29 30 benchmark_edge_lookup_SOURCES = benchmark/edge_lookup.cc -
lemon/graph_utils.h
r2201 r2235 24 24 #include <map> 25 25 #include <cmath> 26 #include <algorithm> 26 27 27 28 #include <lemon/bits/invalid.h> … … 375 376 ///\endcode 376 377 /// 378 ///\sa EdgeLookUp 379 ///\se AllEdgeLookup 377 380 ///\sa ConEdgeIt 378 381 template <typename Graph> … … 396 399 /// 397 400 ///\sa findEdge() 401 ///\sa EdgeLookUp 402 ///\se AllEdgeLookup 398 403 /// 399 404 /// \author Balazs Dezso … … 1839 1844 1840 1845 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 1841 2082 /// @} 1842 2083
Note: See TracChangeset
for help on using the changeset viewer.