1837 typedef True UndirectedTag; |
1837 typedef True UndirectedTag; |
1838 |
1838 |
1839 typedef typename Digraph::Arc Edge; |
1839 typedef typename Digraph::Arc Edge; |
1840 typedef typename Digraph::Node Node; |
1840 typedef typename Digraph::Node Node; |
1841 |
1841 |
1842 class Arc : public Edge { |
1842 class Arc { |
1843 friend class UndirectorBase; |
1843 friend class UndirectorBase; |
1844 protected: |
1844 protected: |
|
1845 Edge _edge; |
1845 bool _forward; |
1846 bool _forward; |
1846 |
1847 |
1847 Arc(const Edge& edge, bool forward) : |
1848 Arc(const Edge& edge, bool forward) |
1848 Edge(edge), _forward(forward) {} |
1849 : _edge(edge), _forward(forward) {} |
1849 |
1850 |
1850 public: |
1851 public: |
1851 Arc() {} |
1852 Arc() {} |
1852 |
1853 |
1853 Arc(Invalid) : Edge(INVALID), _forward(true) {} |
1854 Arc(Invalid) : _edge(INVALID), _forward(true) {} |
|
1855 |
|
1856 operator const Edge&() const { return _edge; } |
1854 |
1857 |
1855 bool operator==(const Arc &other) const { |
1858 bool operator==(const Arc &other) const { |
1856 return _forward == other._forward && |
1859 return _forward == other._forward && _edge == other._edge; |
1857 static_cast<const Edge&>(*this) == static_cast<const Edge&>(other); |
|
1858 } |
1860 } |
1859 bool operator!=(const Arc &other) const { |
1861 bool operator!=(const Arc &other) const { |
1860 return _forward != other._forward || |
1862 return _forward != other._forward || _edge != other._edge; |
1861 static_cast<const Edge&>(*this) != static_cast<const Edge&>(other); |
|
1862 } |
1863 } |
1863 bool operator<(const Arc &other) const { |
1864 bool operator<(const Arc &other) const { |
1864 return _forward < other._forward || |
1865 return _forward < other._forward || |
1865 (_forward == other._forward && |
1866 (_forward == other._forward && _edge < other._edge); |
1866 static_cast<const Edge&>(*this) < static_cast<const Edge&>(other)); |
|
1867 } |
1867 } |
1868 }; |
1868 }; |
1869 |
1869 |
1870 void first(Node& n) const { |
1870 void first(Node& n) const { |
1871 _digraph->first(n); |
1871 _digraph->first(n); |
1896 void next(Edge& e) const { |
1896 void next(Edge& e) const { |
1897 _digraph->next(e); |
1897 _digraph->next(e); |
1898 } |
1898 } |
1899 |
1899 |
1900 void firstOut(Arc& a, const Node& n) const { |
1900 void firstOut(Arc& a, const Node& n) const { |
1901 _digraph->firstIn(a, n); |
1901 _digraph->firstIn(a._edge, n); |
1902 if( static_cast<const Edge&>(a) != INVALID ) { |
1902 if (a._edge != INVALID ) { |
1903 a._forward = false; |
1903 a._forward = false; |
1904 } else { |
1904 } else { |
1905 _digraph->firstOut(a, n); |
1905 _digraph->firstOut(a._edge, n); |
1906 a._forward = true; |
1906 a._forward = true; |
1907 } |
1907 } |
1908 } |
1908 } |
1909 void nextOut(Arc &a) const { |
1909 void nextOut(Arc &a) const { |
1910 if (!a._forward) { |
1910 if (!a._forward) { |
1911 Node n = _digraph->target(a); |
1911 Node n = _digraph->target(a._edge); |
1912 _digraph->nextIn(a); |
1912 _digraph->nextIn(a._edge); |
1913 if (static_cast<const Edge&>(a) == INVALID ) { |
1913 if (a._edge == INVALID) { |
1914 _digraph->firstOut(a, n); |
1914 _digraph->firstOut(a._edge, n); |
1915 a._forward = true; |
1915 a._forward = true; |
1916 } |
1916 } |
1917 } |
1917 } |
1918 else { |
1918 else { |
1919 _digraph->nextOut(a); |
1919 _digraph->nextOut(a._edge); |
1920 } |
1920 } |
1921 } |
1921 } |
1922 |
1922 |
1923 void firstIn(Arc &a, const Node &n) const { |
1923 void firstIn(Arc &a, const Node &n) const { |
1924 _digraph->firstOut(a, n); |
1924 _digraph->firstOut(a._edge, n); |
1925 if (static_cast<const Edge&>(a) != INVALID ) { |
1925 if (a._edge != INVALID ) { |
1926 a._forward = false; |
1926 a._forward = false; |
1927 } else { |
1927 } else { |
1928 _digraph->firstIn(a, n); |
1928 _digraph->firstIn(a._edge, n); |
1929 a._forward = true; |
1929 a._forward = true; |
1930 } |
1930 } |
1931 } |
1931 } |
1932 void nextIn(Arc &a) const { |
1932 void nextIn(Arc &a) const { |
1933 if (!a._forward) { |
1933 if (!a._forward) { |
1934 Node n = _digraph->source(a); |
1934 Node n = _digraph->source(a._edge); |
1935 _digraph->nextOut(a); |
1935 _digraph->nextOut(a._edge); |
1936 if( static_cast<const Edge&>(a) == INVALID ) { |
1936 if (a._edge == INVALID ) { |
1937 _digraph->firstIn(a, n); |
1937 _digraph->firstIn(a._edge, n); |
1938 a._forward = true; |
1938 a._forward = true; |
1939 } |
1939 } |
1940 } |
1940 } |
1941 else { |
1941 else { |
1942 _digraph->nextIn(a); |
1942 _digraph->nextIn(a._edge); |
1943 } |
1943 } |
1944 } |
1944 } |
1945 |
1945 |
1946 void firstInc(Edge &e, bool &d, const Node &n) const { |
1946 void firstInc(Edge &e, bool &d, const Node &n) const { |
1947 d = true; |
1947 d = true; |
1970 Node v(const Edge& e) const { |
1970 Node v(const Edge& e) const { |
1971 return _digraph->target(e); |
1971 return _digraph->target(e); |
1972 } |
1972 } |
1973 |
1973 |
1974 Node source(const Arc &a) const { |
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 Node target(const Arc &a) const { |
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 static Arc direct(const Edge &e, bool d) { |
1982 static Arc direct(const Edge &e, bool d) { |
1983 return Arc(e, d); |
1983 return Arc(e, d); |
1984 } |
|
1985 Arc direct(const Edge &e, const Node& n) const { |
|
1986 return Arc(e, _digraph->source(e) == n); |
|
1987 } |
1984 } |
1988 |
1985 |
1989 static bool direction(const Arc &a) { return a._forward; } |
1986 static bool direction(const Arc &a) { return a._forward; } |
1990 |
1987 |
1991 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } |
1988 Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); } |