r703:cb38ccedd2c1
Thu, 07 May 2009 10:46:49
[Not Reviewed]
0 comments (0 inline)
0
1
0
30
33
| ... | ... |
@@ -1794,242 +1794,239 @@ |
| 1794 | 1794 |
/// This function returns the status of the given edge. |
| 1795 | 1795 |
/// It is \c true if the given edge is enabled (i.e. not hidden). |
| 1796 | 1796 |
bool status(const Edge& e) const { return Parent::status(e); }
|
| 1797 | 1797 |
|
| 1798 | 1798 |
/// \brief Disables the given edge |
| 1799 | 1799 |
/// |
| 1800 | 1800 |
/// This function disables the given edge in the subgraph, |
| 1801 | 1801 |
/// so the iteration jumps over it. |
| 1802 | 1802 |
/// It is the same as \ref status() "status(e, false)". |
| 1803 | 1803 |
void disable(const Edge& e) const { Parent::status(e, false); }
|
| 1804 | 1804 |
|
| 1805 | 1805 |
/// \brief Enables the given edge |
| 1806 | 1806 |
/// |
| 1807 | 1807 |
/// This function enables the given edge in the subgraph. |
| 1808 | 1808 |
/// It is the same as \ref status() "status(e, true)". |
| 1809 | 1809 |
void enable(const Edge& e) const { Parent::status(e, true); }
|
| 1810 | 1810 |
|
| 1811 | 1811 |
}; |
| 1812 | 1812 |
|
| 1813 | 1813 |
/// \brief Returns a read-only FilterEdges adaptor |
| 1814 | 1814 |
/// |
| 1815 | 1815 |
/// This function just returns a read-only \ref FilterEdges adaptor. |
| 1816 | 1816 |
/// \ingroup graph_adaptors |
| 1817 | 1817 |
/// \relates FilterEdges |
| 1818 | 1818 |
template<typename GR, typename EF> |
| 1819 | 1819 |
FilterEdges<const GR, EF> |
| 1820 | 1820 |
filterEdges(const GR& graph, EF& edge_filter) {
|
| 1821 | 1821 |
return FilterEdges<const GR, EF>(graph, edge_filter); |
| 1822 | 1822 |
} |
| 1823 | 1823 |
|
| 1824 | 1824 |
template<typename GR, typename EF> |
| 1825 | 1825 |
FilterEdges<const GR, const EF> |
| 1826 | 1826 |
filterEdges(const GR& graph, const EF& edge_filter) {
|
| 1827 | 1827 |
return FilterEdges<const GR, const EF>(graph, edge_filter); |
| 1828 | 1828 |
} |
| 1829 | 1829 |
|
| 1830 | 1830 |
|
| 1831 | 1831 |
template <typename DGR> |
| 1832 | 1832 |
class UndirectorBase {
|
| 1833 | 1833 |
public: |
| 1834 | 1834 |
typedef DGR Digraph; |
| 1835 | 1835 |
typedef UndirectorBase Adaptor; |
| 1836 | 1836 |
|
| 1837 | 1837 |
typedef True UndirectedTag; |
| 1838 | 1838 |
|
| 1839 | 1839 |
typedef typename Digraph::Arc Edge; |
| 1840 | 1840 |
typedef typename Digraph::Node Node; |
| 1841 | 1841 |
|
| 1842 |
class Arc |
|
| 1842 |
class Arc {
|
|
| 1843 | 1843 |
friend class UndirectorBase; |
| 1844 | 1844 |
protected: |
| 1845 |
Edge _edge; |
|
| 1845 | 1846 |
bool _forward; |
| 1846 | 1847 |
|
| 1847 |
Arc(const Edge& edge, bool forward) : |
|
| 1848 |
Edge(edge), _forward(forward) {}
|
|
| 1848 |
Arc(const Edge& edge, bool forward) |
|
| 1849 |
: _edge(edge), _forward(forward) {}
|
|
| 1849 | 1850 |
|
| 1850 | 1851 |
public: |
| 1851 | 1852 |
Arc() {}
|
| 1852 | 1853 |
|
| 1853 |
Arc(Invalid) : |
|
| 1854 |
Arc(Invalid) : _edge(INVALID), _forward(true) {}
|
|
| 1855 |
|
|
| 1856 |
operator const Edge&() const { return _edge; }
|
|
| 1854 | 1857 |
|
| 1855 | 1858 |
bool operator==(const Arc &other) const {
|
| 1856 |
return _forward == other._forward && |
|
| 1857 |
static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); |
|
| 1859 |
return _forward == other._forward && _edge == other._edge; |
|
| 1858 | 1860 |
} |
| 1859 | 1861 |
bool operator!=(const Arc &other) const {
|
| 1860 |
return _forward != other._forward || |
|
| 1861 |
static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); |
|
| 1862 |
return _forward != other._forward || _edge != other._edge; |
|
| 1862 | 1863 |
} |
| 1863 | 1864 |
bool operator<(const Arc &other) const {
|
| 1864 | 1865 |
return _forward < other._forward || |
| 1865 |
(_forward == other._forward && |
|
| 1866 |
static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); |
|
| 1866 |
(_forward == other._forward && _edge < other._edge); |
|
| 1867 | 1867 |
} |
| 1868 | 1868 |
}; |
| 1869 | 1869 |
|
| 1870 | 1870 |
void first(Node& n) const {
|
| 1871 | 1871 |
_digraph->first(n); |
| 1872 | 1872 |
} |
| 1873 | 1873 |
|
| 1874 | 1874 |
void next(Node& n) const {
|
| 1875 | 1875 |
_digraph->next(n); |
| 1876 | 1876 |
} |
| 1877 | 1877 |
|
| 1878 | 1878 |
void first(Arc& a) const {
|
| 1879 |
_digraph->first(a); |
|
| 1879 |
_digraph->first(a._edge); |
|
| 1880 | 1880 |
a._forward = true; |
| 1881 | 1881 |
} |
| 1882 | 1882 |
|
| 1883 | 1883 |
void next(Arc& a) const {
|
| 1884 | 1884 |
if (a._forward) {
|
| 1885 | 1885 |
a._forward = false; |
| 1886 | 1886 |
} else {
|
| 1887 |
_digraph->next(a); |
|
| 1887 |
_digraph->next(a._edge); |
|
| 1888 | 1888 |
a._forward = true; |
| 1889 | 1889 |
} |
| 1890 | 1890 |
} |
| 1891 | 1891 |
|
| 1892 | 1892 |
void first(Edge& e) const {
|
| 1893 | 1893 |
_digraph->first(e); |
| 1894 | 1894 |
} |
| 1895 | 1895 |
|
| 1896 | 1896 |
void next(Edge& e) const {
|
| 1897 | 1897 |
_digraph->next(e); |
| 1898 | 1898 |
} |
| 1899 | 1899 |
|
| 1900 | 1900 |
void firstOut(Arc& a, const Node& n) const {
|
| 1901 |
_digraph->firstIn(a, n); |
|
| 1902 |
if( static_cast<const Edge&>(a) != INVALID ) {
|
|
| 1901 |
_digraph->firstIn(a._edge, n); |
|
| 1902 |
if (a._edge != INVALID ) {
|
|
| 1903 | 1903 |
a._forward = false; |
| 1904 | 1904 |
} else {
|
| 1905 |
_digraph->firstOut(a, n); |
|
| 1905 |
_digraph->firstOut(a._edge, n); |
|
| 1906 | 1906 |
a._forward = true; |
| 1907 | 1907 |
} |
| 1908 | 1908 |
} |
| 1909 | 1909 |
void nextOut(Arc &a) const {
|
| 1910 | 1910 |
if (!a._forward) {
|
| 1911 |
Node n = _digraph->target(a); |
|
| 1912 |
_digraph->nextIn(a); |
|
| 1913 |
if (static_cast<const Edge&>(a) == INVALID ) {
|
|
| 1914 |
_digraph->firstOut(a, n); |
|
| 1911 |
Node n = _digraph->target(a._edge); |
|
| 1912 |
_digraph->nextIn(a._edge); |
|
| 1913 |
if (a._edge == INVALID) {
|
|
| 1914 |
_digraph->firstOut(a._edge, n); |
|
| 1915 | 1915 |
a._forward = true; |
| 1916 | 1916 |
} |
| 1917 | 1917 |
} |
| 1918 | 1918 |
else {
|
| 1919 |
_digraph->nextOut(a); |
|
| 1919 |
_digraph->nextOut(a._edge); |
|
| 1920 | 1920 |
} |
| 1921 | 1921 |
} |
| 1922 | 1922 |
|
| 1923 | 1923 |
void firstIn(Arc &a, const Node &n) const {
|
| 1924 |
_digraph->firstOut(a, n); |
|
| 1925 |
if (static_cast<const Edge&>(a) != INVALID ) {
|
|
| 1924 |
_digraph->firstOut(a._edge, n); |
|
| 1925 |
if (a._edge != INVALID ) {
|
|
| 1926 | 1926 |
a._forward = false; |
| 1927 | 1927 |
} else {
|
| 1928 |
_digraph->firstIn(a, n); |
|
| 1928 |
_digraph->firstIn(a._edge, n); |
|
| 1929 | 1929 |
a._forward = true; |
| 1930 | 1930 |
} |
| 1931 | 1931 |
} |
| 1932 | 1932 |
void nextIn(Arc &a) const {
|
| 1933 | 1933 |
if (!a._forward) {
|
| 1934 |
Node n = _digraph->source(a); |
|
| 1935 |
_digraph->nextOut(a); |
|
| 1936 |
if( static_cast<const Edge&>(a) == INVALID ) {
|
|
| 1937 |
_digraph->firstIn(a, n); |
|
| 1934 |
Node n = _digraph->source(a._edge); |
|
| 1935 |
_digraph->nextOut(a._edge); |
|
| 1936 |
if (a._edge == INVALID ) {
|
|
| 1937 |
_digraph->firstIn(a._edge, n); |
|
| 1938 | 1938 |
a._forward = true; |
| 1939 | 1939 |
} |
| 1940 | 1940 |
} |
| 1941 | 1941 |
else {
|
| 1942 |
_digraph->nextIn(a); |
|
| 1942 |
_digraph->nextIn(a._edge); |
|
| 1943 | 1943 |
} |
| 1944 | 1944 |
} |
| 1945 | 1945 |
|
| 1946 | 1946 |
void firstInc(Edge &e, bool &d, const Node &n) const {
|
| 1947 | 1947 |
d = true; |
| 1948 | 1948 |
_digraph->firstOut(e, n); |
| 1949 | 1949 |
if (e != INVALID) return; |
| 1950 | 1950 |
d = false; |
| 1951 | 1951 |
_digraph->firstIn(e, n); |
| 1952 | 1952 |
} |
| 1953 | 1953 |
|
| 1954 | 1954 |
void nextInc(Edge &e, bool &d) const {
|
| 1955 | 1955 |
if (d) {
|
| 1956 | 1956 |
Node s = _digraph->source(e); |
| 1957 | 1957 |
_digraph->nextOut(e); |
| 1958 | 1958 |
if (e != INVALID) return; |
| 1959 | 1959 |
d = false; |
| 1960 | 1960 |
_digraph->firstIn(e, s); |
| 1961 | 1961 |
} else {
|
| 1962 | 1962 |
_digraph->nextIn(e); |
| 1963 | 1963 |
} |
| 1964 | 1964 |
} |
| 1965 | 1965 |
|
| 1966 | 1966 |
Node u(const Edge& e) const {
|
| 1967 | 1967 |
return _digraph->source(e); |
| 1968 | 1968 |
} |
| 1969 | 1969 |
|
| 1970 | 1970 |
Node v(const Edge& e) const {
|
| 1971 | 1971 |
return _digraph->target(e); |
| 1972 | 1972 |
} |
| 1973 | 1973 |
|
| 1974 | 1974 |
Node source(const Arc &a) const {
|
| 1975 |
return a._forward ? _digraph->source(a) : _digraph->target(a); |
|
| 1975 |
return a._forward ? _digraph->source(a._edge) : _digraph->target(a._edge); |
|
| 1976 | 1976 |
} |
| 1977 | 1977 |
|
| 1978 | 1978 |
Node target(const Arc &a) const {
|
| 1979 |
return a._forward ? _digraph->target(a) : _digraph->source(a); |
|
| 1979 |
return a._forward ? _digraph->target(a._edge) : _digraph->source(a._edge); |
|
| 1980 | 1980 |
} |
| 1981 | 1981 |
|
| 1982 | 1982 |
static Arc direct(const Edge &e, bool d) {
|
| 1983 | 1983 |
return Arc(e, d); |
| 1984 | 1984 |
} |
| 1985 |
Arc direct(const Edge &e, const Node& n) const {
|
|
| 1986 |
return Arc(e, _digraph->source(e) == n); |
|
| 1987 |
} |
|
| 1988 | 1985 |
|
| 1989 | 1986 |
static bool direction(const Arc &a) { return a._forward; }
|
| 1990 | 1987 |
|
| 1991 | 1988 |
Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
|
| 1992 | 1989 |
Arc arcFromId(int ix) const {
|
| 1993 | 1990 |
return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1)); |
| 1994 | 1991 |
} |
| 1995 | 1992 |
Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
|
| 1996 | 1993 |
|
| 1997 | 1994 |
int id(const Node &n) const { return _digraph->id(n); }
|
| 1998 | 1995 |
int id(const Arc &a) const {
|
| 1999 | 1996 |
return (_digraph->id(a) << 1) | (a._forward ? 1 : 0); |
| 2000 | 1997 |
} |
| 2001 | 1998 |
int id(const Edge &e) const { return _digraph->id(e); }
|
| 2002 | 1999 |
|
| 2003 | 2000 |
int maxNodeId() const { return _digraph->maxNodeId(); }
|
| 2004 | 2001 |
int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
|
| 2005 | 2002 |
int maxEdgeId() const { return _digraph->maxArcId(); }
|
| 2006 | 2003 |
|
| 2007 | 2004 |
Node addNode() { return _digraph->addNode(); }
|
| 2008 | 2005 |
Edge addEdge(const Node& u, const Node& v) {
|
| 2009 | 2006 |
return _digraph->addArc(u, v); |
| 2010 | 2007 |
} |
| 2011 | 2008 |
|
| 2012 | 2009 |
void erase(const Node& i) { _digraph->erase(i); }
|
| 2013 | 2010 |
void erase(const Edge& i) { _digraph->erase(i); }
|
| 2014 | 2011 |
|
| 2015 | 2012 |
void clear() { _digraph->clear(); }
|
| 2016 | 2013 |
|
| 2017 | 2014 |
typedef NodeNumTagIndicator<Digraph> NodeNumTag; |
| 2018 | 2015 |
int nodeNum() const { return _digraph->nodeNum(); }
|
| 2019 | 2016 |
|
| 2020 | 2017 |
typedef ArcNumTagIndicator<Digraph> ArcNumTag; |
| 2021 | 2018 |
int arcNum() const { return 2 * _digraph->arcNum(); }
|
| 2022 | 2019 |
|
| 2023 | 2020 |
typedef ArcNumTag EdgeNumTag; |
| 2024 | 2021 |
int edgeNum() const { return _digraph->arcNum(); }
|
| 2025 | 2022 |
|
| 2026 | 2023 |
typedef FindArcTagIndicator<Digraph> FindArcTag; |
| 2027 | 2024 |
Arc findArc(Node s, Node t, Arc p = INVALID) const {
|
| 2028 | 2025 |
if (p == INVALID) {
|
| 2029 | 2026 |
Edge arc = _digraph->findArc(s, t); |
| 2030 | 2027 |
if (arc != INVALID) return direct(arc, true); |
| 2031 | 2028 |
arc = _digraph->findArc(t, s); |
| 2032 | 2029 |
if (arc != INVALID) return direct(arc, false); |
| 2033 | 2030 |
} else if (direction(p)) {
|
| 2034 | 2031 |
Edge arc = _digraph->findArc(s, t, p); |
| 2035 | 2032 |
if (arc != INVALID) return direct(arc, true); |
0 comments (0 inline)