91 |
91 |
92 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; |
92 typedef EdgeNumTagIndicator<Graph> EdgeNumTag; |
93 int edgeNum() const { return graph->edgeNum(); } |
93 int edgeNum() const { return graph->edgeNum(); } |
94 |
94 |
95 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
95 typedef FindEdgeTagIndicator<Graph> FindEdgeTag; |
96 Edge findEdge(const Node& source, const Node& target, |
96 Edge findEdge(const Node& u, const Node& v, |
97 const Edge& prev = INVALID) { |
97 const Edge& prev = INVALID) { |
98 return graph->findEdge(source, target, prev); |
98 return graph->findEdge(u, v, prev); |
99 } |
99 } |
100 |
100 |
101 Node addNode() const { |
101 Node addNode() const { |
102 return Node(graph->addNode()); |
102 return Node(graph->addNode()); |
103 } |
103 } |
104 |
104 |
105 Edge addEdge(const Node& source, const Node& target) const { |
105 Edge addEdge(const Node& u, const Node& v) const { |
106 return Edge(graph->addEdge(source, target)); |
106 return Edge(graph->addEdge(u, v)); |
107 } |
107 } |
108 |
108 |
109 void erase(const Node& i) const { graph->erase(i); } |
109 void erase(const Node& i) const { graph->erase(i); } |
110 void erase(const Edge& i) const { graph->erase(i); } |
110 void erase(const Edge& i) const { graph->erase(i); } |
111 |
111 |
112 void clear() const { graph->clear(); } |
112 void clear() const { graph->clear(); } |
113 |
113 |
114 int id(const Node& v) const { return graph->id(v); } |
114 int id(const Node& v) const { return graph->id(v); } |
115 int id(const Edge& e) const { return graph->id(e); } |
115 int id(const Edge& e) const { return graph->id(e); } |
116 |
116 |
117 Node fromNodeId(int id) const { |
117 Node fromNodeId(int ix) const { |
118 return graph->fromNodeId(id); |
118 return graph->fromNodeId(ix); |
119 } |
119 } |
120 |
120 |
121 Edge fromEdgeId(int id) const { |
121 Edge fromEdgeId(int ix) const { |
122 return graph->fromEdgeId(id); |
122 return graph->fromEdgeId(ix); |
123 } |
123 } |
124 |
124 |
125 int maxNodeId() const { |
125 int maxNodeId() const { |
126 return graph->maxNodeId(); |
126 return graph->maxNodeId(); |
127 } |
127 } |
1819 operator GraphEdge() const { return item.first(); } |
1819 operator GraphEdge() const { return item.first(); } |
1820 operator GraphNode() const { return item.second(); } |
1820 operator GraphNode() const { return item.second(); } |
1821 |
1821 |
1822 }; |
1822 }; |
1823 |
1823 |
1824 void first(Node& node) const { |
1824 void first(Node& n) const { |
1825 Parent::first(node); |
1825 Parent::first(n); |
1826 node.in_node = true; |
1826 n.in_node = true; |
1827 } |
1827 } |
1828 |
1828 |
1829 void next(Node& node) const { |
1829 void next(Node& n) const { |
1830 if (node.in_node) { |
1830 if (n.in_node) { |
1831 node.in_node = false; |
1831 n.in_node = false; |
1832 } else { |
1832 } else { |
1833 node.in_node = true; |
1833 n.in_node = true; |
1834 Parent::next(node); |
1834 Parent::next(n); |
1835 } |
1835 } |
1836 } |
1836 } |
1837 |
1837 |
1838 void first(Edge& edge) const { |
1838 void first(Edge& e) const { |
1839 edge.item.setSecond(); |
1839 e.item.setSecond(); |
1840 Parent::first(edge.item.second()); |
1840 Parent::first(e.item.second()); |
1841 if (edge.item.second() == INVALID) { |
1841 if (e.item.second() == INVALID) { |
1842 edge.item.setFirst(); |
1842 e.item.setFirst(); |
1843 Parent::first(edge.item.first()); |
1843 Parent::first(e.item.first()); |
1844 } |
1844 } |
1845 } |
1845 } |
1846 |
1846 |
1847 void next(Edge& edge) const { |
1847 void next(Edge& e) const { |
1848 if (edge.item.secondState()) { |
1848 if (e.item.secondState()) { |
1849 Parent::next(edge.item.second()); |
1849 Parent::next(e.item.second()); |
1850 if (edge.item.second() == INVALID) { |
1850 if (e.item.second() == INVALID) { |
1851 edge.item.setFirst(); |
1851 e.item.setFirst(); |
1852 Parent::first(edge.item.first()); |
1852 Parent::first(e.item.first()); |
1853 } |
1853 } |
1854 } else { |
1854 } else { |
1855 Parent::next(edge.item.first()); |
1855 Parent::next(e.item.first()); |
1856 } |
1856 } |
1857 } |
1857 } |
1858 |
1858 |
1859 void firstOut(Edge& edge, const Node& node) const { |
1859 void firstOut(Edge& e, const Node& n) const { |
1860 if (node.in_node) { |
1860 if (n.in_node) { |
1861 edge.item.setSecond(node); |
1861 e.item.setSecond(n); |
1862 } else { |
1862 } else { |
1863 edge.item.setFirst(); |
1863 e.item.setFirst(); |
1864 Parent::firstOut(edge.item.first(), node); |
1864 Parent::firstOut(e.item.first(), n); |
1865 } |
1865 } |
1866 } |
1866 } |
1867 |
1867 |
1868 void nextOut(Edge& edge) const { |
1868 void nextOut(Edge& e) const { |
1869 if (!edge.item.firstState()) { |
1869 if (!e.item.firstState()) { |
1870 edge.item.setFirst(INVALID); |
1870 e.item.setFirst(INVALID); |
1871 } else { |
1871 } else { |
1872 Parent::nextOut(edge.item.first()); |
1872 Parent::nextOut(e.item.first()); |
1873 } |
1873 } |
1874 } |
1874 } |
1875 |
1875 |
1876 void firstIn(Edge& edge, const Node& node) const { |
1876 void firstIn(Edge& e, const Node& n) const { |
1877 if (!node.in_node) { |
1877 if (!n.in_node) { |
1878 edge.item.setSecond(node); |
1878 e.item.setSecond(n); |
1879 } else { |
1879 } else { |
1880 edge.item.setFirst(); |
1880 e.item.setFirst(); |
1881 Parent::firstIn(edge.item.first(), node); |
1881 Parent::firstIn(e.item.first(), n); |
1882 } |
1882 } |
1883 } |
1883 } |
1884 |
1884 |
1885 void nextIn(Edge& edge) const { |
1885 void nextIn(Edge& e) const { |
1886 if (!edge.item.firstState()) { |
1886 if (!e.item.firstState()) { |
1887 edge.item.setFirst(INVALID); |
1887 e.item.setFirst(INVALID); |
1888 } else { |
1888 } else { |
1889 Parent::nextIn(edge.item.first()); |
1889 Parent::nextIn(e.item.first()); |
1890 } |
1890 } |
1891 } |
1891 } |
1892 |
1892 |
1893 Node source(const Edge& edge) const { |
1893 Node source(const Edge& e) const { |
1894 if (edge.item.firstState()) { |
1894 if (e.item.firstState()) { |
1895 return Node(Parent::source(edge.item.first()), false); |
1895 return Node(Parent::source(e.item.first()), false); |
1896 } else { |
1896 } else { |
1897 return Node(edge.item.second(), true); |
1897 return Node(e.item.second(), true); |
1898 } |
1898 } |
1899 } |
1899 } |
1900 |
1900 |
1901 Node target(const Edge& edge) const { |
1901 Node target(const Edge& e) const { |
1902 if (edge.item.firstState()) { |
1902 if (e.item.firstState()) { |
1903 return Node(Parent::target(edge.item.first()), true); |
1903 return Node(Parent::target(e.item.first()), true); |
1904 } else { |
1904 } else { |
1905 return Node(edge.item.second(), false); |
1905 return Node(e.item.second(), false); |
1906 } |
1906 } |
1907 } |
1907 } |
1908 |
1908 |
1909 int id(const Node& node) const { |
1909 int id(const Node& n) const { |
1910 return (Parent::id(node) << 1) | (node.in_node ? 0 : 1); |
1910 return (Parent::id(n) << 1) | (n.in_node ? 0 : 1); |
1911 } |
1911 } |
1912 Node nodeFromId(int id) const { |
1912 Node nodeFromId(int ix) const { |
1913 return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0); |
1913 return Node(Parent::nodeFromId(ix >> 1), (ix & 1) == 0); |
1914 } |
1914 } |
1915 int maxNodeId() const { |
1915 int maxNodeId() const { |
1916 return 2 * Parent::maxNodeId() + 1; |
1916 return 2 * Parent::maxNodeId() + 1; |
1917 } |
1917 } |
1918 |
1918 |
1919 int id(const Edge& edge) const { |
1919 int id(const Edge& e) const { |
1920 if (edge.item.firstState()) { |
1920 if (e.item.firstState()) { |
1921 return Parent::id(edge.item.first()) << 1; |
1921 return Parent::id(e.item.first()) << 1; |
1922 } else { |
1922 } else { |
1923 return (Parent::id(edge.item.second()) << 1) | 1; |
1923 return (Parent::id(e.item.second()) << 1) | 1; |
1924 } |
1924 } |
1925 } |
1925 } |
1926 Edge edgeFromId(int id) const { |
1926 Edge edgeFromId(int ix) const { |
1927 if ((id & 1) == 0) { |
1927 if ((ix & 1) == 0) { |
1928 return Edge(Parent::edgeFromId(id >> 1)); |
1928 return Edge(Parent::edgeFromId(ix >> 1)); |
1929 } else { |
1929 } else { |
1930 return Edge(Parent::nodeFromId(id >> 1)); |
1930 return Edge(Parent::nodeFromId(ix >> 1)); |
1931 } |
1931 } |
1932 } |
1932 } |
1933 int maxEdgeId() const { |
1933 int maxEdgeId() const { |
1934 return std::max(Parent::maxNodeId() << 1, |
1934 return std::max(Parent::maxNodeId() << 1, |
1935 (Parent::maxEdgeId() << 1) | 1); |
1935 (Parent::maxEdgeId() << 1) | 1); |
1936 } |
1936 } |
1937 |
1937 |
1938 /// \brief Returns true when the node is in-node. |
1938 /// \brief Returns true when the node is in-node. |
1939 /// |
1939 /// |
1940 /// Returns true when the node is in-node. |
1940 /// Returns true when the node is in-node. |
1941 static bool inNode(const Node& node) { |
1941 static bool inNode(const Node& n) { |
1942 return node.in_node; |
1942 return n.in_node; |
1943 } |
1943 } |
1944 |
1944 |
1945 /// \brief Returns true when the node is out-node. |
1945 /// \brief Returns true when the node is out-node. |
1946 /// |
1946 /// |
1947 /// Returns true when the node is out-node. |
1947 /// Returns true when the node is out-node. |
1948 static bool outNode(const Node& node) { |
1948 static bool outNode(const Node& n) { |
1949 return !node.in_node; |
1949 return !n.in_node; |
1950 } |
1950 } |
1951 |
1951 |
1952 /// \brief Returns true when the edge is edge in the original graph. |
1952 /// \brief Returns true when the edge is edge in the original graph. |
1953 /// |
1953 /// |
1954 /// Returns true when the edge is edge in the original graph. |
1954 /// Returns true when the edge is edge in the original graph. |
1955 static bool origEdge(const Edge& edge) { |
1955 static bool origEdge(const Edge& e) { |
1956 return edge.item.firstState(); |
1956 return e.item.firstState(); |
1957 } |
1957 } |
1958 |
1958 |
1959 /// \brief Returns true when the edge binds an in-node and an out-node. |
1959 /// \brief Returns true when the edge binds an in-node and an out-node. |
1960 /// |
1960 /// |
1961 /// Returns true when the edge binds an in-node and an out-node. |
1961 /// Returns true when the edge binds an in-node and an out-node. |
1962 static bool bindEdge(const Edge& edge) { |
1962 static bool bindEdge(const Edge& e) { |
1963 return edge.item.secondState(); |
1963 return e.item.secondState(); |
1964 } |
1964 } |
1965 |
1965 |
1966 /// \brief Gives back the in-node created from the \c node. |
1966 /// \brief Gives back the in-node created from the \c node. |
1967 /// |
1967 /// |
1968 /// Gives back the in-node created from the \c node. |
1968 /// Gives back the in-node created from the \c node. |
1969 static Node inNode(const GraphNode& node) { |
1969 static Node inNode(const GraphNode& n) { |
1970 return Node(node, true); |
1970 return Node(n, true); |
1971 } |
1971 } |
1972 |
1972 |
1973 /// \brief Gives back the out-node created from the \c node. |
1973 /// \brief Gives back the out-node created from the \c node. |
1974 /// |
1974 /// |
1975 /// Gives back the out-node created from the \c node. |
1975 /// Gives back the out-node created from the \c node. |
1976 static Node outNode(const GraphNode& node) { |
1976 static Node outNode(const GraphNode& n) { |
1977 return Node(node, false); |
1977 return Node(n, false); |
1978 } |
1978 } |
1979 |
1979 |
1980 /// \brief Gives back the edge binds the two part of the node. |
1980 /// \brief Gives back the edge binds the two part of the node. |
1981 /// |
1981 /// |
1982 /// Gives back the edge binds the two part of the node. |
1982 /// Gives back the edge binds the two part of the node. |
1983 static Edge edge(const GraphNode& node) { |
1983 static Edge edge(const GraphNode& n) { |
1984 return Edge(node); |
1984 return Edge(n); |
1985 } |
1985 } |
1986 |
1986 |
1987 /// \brief Gives back the edge of the original edge. |
1987 /// \brief Gives back the edge of the original edge. |
1988 /// |
1988 /// |
1989 /// Gives back the edge of the original edge. |
1989 /// Gives back the edge of the original edge. |
1990 static Edge edge(const GraphEdge& edge) { |
1990 static Edge edge(const GraphEdge& e) { |
1991 return Edge(edge); |
1991 return Edge(e); |
1992 } |
1992 } |
1993 |
1993 |
1994 typedef True NodeNumTag; |
1994 typedef True NodeNumTag; |
1995 |
1995 |
1996 int nodeNum() const { |
1996 int nodeNum() const { |
2323 adaptor->notifier(Node()).erase(nodes); |
2324 adaptor->notifier(Node()).erase(nodes); |
2324 } |
2325 } |
2325 virtual void erase(const std::vector<GraphNode>& gn) { |
2326 virtual void erase(const std::vector<GraphNode>& gn) { |
2326 std::vector<Node> nodes; |
2327 std::vector<Node> nodes; |
2327 std::vector<Edge> edges; |
2328 std::vector<Edge> edges; |
2328 for (int i = 0; i < (int)gn.size(); ++i) { |
2329 for (int i = 0; i < int(gn.size()); ++i) { |
2329 edges.push_back(AdaptorBase::Parent::edge(gn[i])); |
2330 edges.push_back(AdaptorBase::Parent::edge(gn[i])); |
2330 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); |
2331 nodes.push_back(AdaptorBase::Parent::inNode(gn[i])); |
2331 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); |
2332 nodes.push_back(AdaptorBase::Parent::outNode(gn[i])); |
2332 } |
2333 } |
2333 adaptor->notifier(Edge()).erase(edges); |
2334 adaptor->notifier(Edge()).erase(edges); |
2334 adaptor->notifier(Node()).erase(nodes); |
2335 adaptor->notifier(Node()).erase(nodes); |
2335 } |
2336 } |
2336 virtual void build() { |
2337 virtual void build() { |
2337 std::vector<Edge> edges; |
2338 std::vector<Edge> edges; |
2338 const typename Parent::Notifier* notifier = Parent::notifier(); |
2339 const typename Parent::Notifier* nf = Parent::notifier(); |
2339 GraphNode it; |
2340 GraphNode it; |
2340 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
2341 for (nf->first(it); it != INVALID; nf->next(it)) { |
2341 edges.push_back(AdaptorBase::Parent::edge(it)); |
2342 edges.push_back(AdaptorBase::Parent::edge(it)); |
2342 } |
2343 } |
2343 adaptor->notifier(Node()).build(); |
2344 adaptor->notifier(Node()).build(); |
2344 adaptor->notifier(Edge()).add(edges); |
2345 adaptor->notifier(Edge()).add(edges); |
2345 } |
2346 } |
2346 virtual void clear() { |
2347 virtual void clear() { |
2347 std::vector<Edge> edges; |
2348 std::vector<Edge> edges; |
2348 const typename Parent::Notifier* notifier = Parent::notifier(); |
2349 const typename Parent::Notifier* nf = Parent::notifier(); |
2349 GraphNode it; |
2350 GraphNode it; |
2350 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
2351 for (nf->first(it); it != INVALID; nf->next(it)) { |
2351 edges.push_back(AdaptorBase::Parent::edge(it)); |
2352 edges.push_back(AdaptorBase::Parent::edge(it)); |
2352 } |
2353 } |
2353 adaptor->notifier(Edge()).erase(edges); |
2354 adaptor->notifier(Edge()).erase(edges); |
2354 adaptor->notifier(Node()).clear(); |
2355 adaptor->notifier(Node()).clear(); |
2355 } |
2356 } |
2383 virtual void add(const GraphEdge& ge) { |
2384 virtual void add(const GraphEdge& ge) { |
2384 adaptor->notifier(Edge()).add(AdaptorBase::edge(ge)); |
2385 adaptor->notifier(Edge()).add(AdaptorBase::edge(ge)); |
2385 } |
2386 } |
2386 virtual void add(const std::vector<GraphEdge>& ge) { |
2387 virtual void add(const std::vector<GraphEdge>& ge) { |
2387 std::vector<Edge> edges; |
2388 std::vector<Edge> edges; |
2388 for (int i = 0; i < (int)ge.size(); ++i) { |
2389 for (int i = 0; i < int(ge.size()); ++i) { |
2389 edges.push_back(AdaptorBase::edge(ge[i])); |
2390 edges.push_back(AdaptorBase::edge(ge[i])); |
2390 } |
2391 } |
2391 adaptor->notifier(Edge()).add(edges); |
2392 adaptor->notifier(Edge()).add(edges); |
2392 } |
2393 } |
2393 virtual void erase(const GraphEdge& ge) { |
2394 virtual void erase(const GraphEdge& ge) { |
2394 adaptor->notifier(Edge()).erase(AdaptorBase::edge(ge)); |
2395 adaptor->notifier(Edge()).erase(AdaptorBase::edge(ge)); |
2395 } |
2396 } |
2396 virtual void erase(const std::vector<GraphEdge>& ge) { |
2397 virtual void erase(const std::vector<GraphEdge>& ge) { |
2397 std::vector<Edge> edges; |
2398 std::vector<Edge> edges; |
2398 for (int i = 0; i < (int)ge.size(); ++i) { |
2399 for (int i = 0; i < int(ge.size()); ++i) { |
2399 edges.push_back(AdaptorBase::edge(ge[i])); |
2400 edges.push_back(AdaptorBase::edge(ge[i])); |
2400 } |
2401 } |
2401 adaptor->notifier(Edge()).erase(edges); |
2402 adaptor->notifier(Edge()).erase(edges); |
2402 } |
2403 } |
2403 virtual void build() { |
2404 virtual void build() { |
2404 std::vector<Edge> edges; |
2405 std::vector<Edge> edges; |
2405 const typename Parent::Notifier* notifier = Parent::notifier(); |
2406 const typename Parent::Notifier* nf = Parent::notifier(); |
2406 GraphEdge it; |
2407 GraphEdge it; |
2407 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
2408 for (nf->first(it); it != INVALID; nf->next(it)) { |
2408 edges.push_back(AdaptorBase::Parent::edge(it)); |
2409 edges.push_back(AdaptorBase::Parent::edge(it)); |
2409 } |
2410 } |
2410 adaptor->notifier(Edge()).add(edges); |
2411 adaptor->notifier(Edge()).add(edges); |
2411 } |
2412 } |
2412 virtual void clear() { |
2413 virtual void clear() { |
2413 std::vector<Edge> edges; |
2414 std::vector<Edge> edges; |
2414 const typename Parent::Notifier* notifier = Parent::notifier(); |
2415 const typename Parent::Notifier* nf = Parent::notifier(); |
2415 GraphEdge it; |
2416 GraphEdge it; |
2416 for (notifier->first(it); it != INVALID; notifier->next(it)) { |
2417 for (nf->first(it); it != INVALID; nf->next(it)) { |
2417 edges.push_back(AdaptorBase::Parent::edge(it)); |
2418 edges.push_back(AdaptorBase::Parent::edge(it)); |
2418 } |
2419 } |
2419 adaptor->notifier(Edge()).erase(edges); |
2420 adaptor->notifier(Edge()).erase(edges); |
2420 } |
2421 } |
2421 |
2422 |