Changeset 1021:a12cca3ad15a in lemonmain for lemon/list_graph.h
 Timestamp:
 11/15/10 09:46:08 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r877 r1021 1600 1600 1601 1601 /// @} 1602 1603 class ListBpGraphBase { 1604 1605 protected: 1606 1607 struct NodeT { 1608 int first_out; 1609 int prev, next; 1610 int partition_prev, partition_next; 1611 int partition_index; 1612 bool red; 1613 }; 1614 1615 struct ArcT { 1616 int target; 1617 int prev_out, next_out; 1618 }; 1619 1620 std::vector<NodeT> nodes; 1621 1622 int first_node, first_red, first_blue; 1623 int max_red, max_blue; 1624 1625 int first_free_red, first_free_blue; 1626 1627 std::vector<ArcT> arcs; 1628 1629 int first_free_arc; 1630 1631 public: 1632 1633 typedef ListBpGraphBase BpGraph; 1634 1635 class Node { 1636 friend class ListBpGraphBase; 1637 protected: 1638 1639 int id; 1640 explicit Node(int pid) { id = pid;} 1641 1642 public: 1643 Node() {} 1644 Node (Invalid) { id = 1; } 1645 bool operator==(const Node& node) const {return id == node.id;} 1646 bool operator!=(const Node& node) const {return id != node.id;} 1647 bool operator<(const Node& node) const {return id < node.id;} 1648 }; 1649 1650 class Edge { 1651 friend class ListBpGraphBase; 1652 protected: 1653 1654 int id; 1655 explicit Edge(int pid) { id = pid;} 1656 1657 public: 1658 Edge() {} 1659 Edge (Invalid) { id = 1; } 1660 bool operator==(const Edge& edge) const {return id == edge.id;} 1661 bool operator!=(const Edge& edge) const {return id != edge.id;} 1662 bool operator<(const Edge& edge) const {return id < edge.id;} 1663 }; 1664 1665 class Arc { 1666 friend class ListBpGraphBase; 1667 protected: 1668 1669 int id; 1670 explicit Arc(int pid) { id = pid;} 1671 1672 public: 1673 operator Edge() const { 1674 return id != 1 ? edgeFromId(id / 2) : INVALID; 1675 } 1676 1677 Arc() {} 1678 Arc (Invalid) { id = 1; } 1679 bool operator==(const Arc& arc) const {return id == arc.id;} 1680 bool operator!=(const Arc& arc) const {return id != arc.id;} 1681 bool operator<(const Arc& arc) const {return id < arc.id;} 1682 }; 1683 1684 ListBpGraphBase() 1685 : nodes(), first_node(1), 1686 first_red(1), first_blue(1), 1687 max_red(1), max_blue(1), 1688 first_free_red(1), first_free_blue(1), 1689 arcs(), first_free_arc(1) {} 1690 1691 1692 bool red(Node n) const { return nodes[n.id].red; } 1693 bool blue(Node n) const { return !nodes[n.id].red; } 1694 1695 int maxNodeId() const { return nodes.size()1; } 1696 int maxRedId() const { return max_red; } 1697 int maxBlueId() const { return max_blue; } 1698 int maxEdgeId() const { return arcs.size() / 2  1; } 1699 int maxArcId() const { return arcs.size()1; } 1700 1701 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); } 1702 Node target(Arc e) const { return Node(arcs[e.id].target); } 1703 1704 Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); } 1705 Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); } 1706 1707 static bool direction(Arc e) { 1708 return (e.id & 1) == 1; 1709 } 1710 1711 static Arc direct(Edge e, bool d) { 1712 return Arc(e.id * 2 + (d ? 1 : 0)); 1713 } 1714 1715 void first(Node& node) const { 1716 node.id = first_node; 1717 } 1718 1719 void next(Node& node) const { 1720 node.id = nodes[node.id].next; 1721 } 1722 1723 void firstRed(Node& node) const { 1724 node.id = first_red; 1725 } 1726 1727 void nextRed(Node& node) const { 1728 node.id = nodes[node.id].partition_next; 1729 } 1730 1731 void firstBlue(Node& node) const { 1732 node.id = first_blue; 1733 } 1734 1735 void nextBlue(Node& node) const { 1736 node.id = nodes[node.id].partition_next; 1737 } 1738 1739 void first(Arc& e) const { 1740 int n = first_node; 1741 while (n != 1 && nodes[n].first_out == 1) { 1742 n = nodes[n].next; 1743 } 1744 e.id = (n == 1) ? 1 : nodes[n].first_out; 1745 } 1746 1747 void next(Arc& e) const { 1748 if (arcs[e.id].next_out != 1) { 1749 e.id = arcs[e.id].next_out; 1750 } else { 1751 int n = nodes[arcs[e.id ^ 1].target].next; 1752 while(n != 1 && nodes[n].first_out == 1) { 1753 n = nodes[n].next; 1754 } 1755 e.id = (n == 1) ? 1 : nodes[n].first_out; 1756 } 1757 } 1758 1759 void first(Edge& e) const { 1760 int n = first_node; 1761 while (n != 1) { 1762 e.id = nodes[n].first_out; 1763 while ((e.id & 1) != 1) { 1764 e.id = arcs[e.id].next_out; 1765 } 1766 if (e.id != 1) { 1767 e.id /= 2; 1768 return; 1769 } 1770 n = nodes[n].next; 1771 } 1772 e.id = 1; 1773 } 1774 1775 void next(Edge& e) const { 1776 int n = arcs[e.id * 2].target; 1777 e.id = arcs[(e.id * 2)  1].next_out; 1778 while ((e.id & 1) != 1) { 1779 e.id = arcs[e.id].next_out; 1780 } 1781 if (e.id != 1) { 1782 e.id /= 2; 1783 return; 1784 } 1785 n = nodes[n].next; 1786 while (n != 1) { 1787 e.id = nodes[n].first_out; 1788 while ((e.id & 1) != 1) { 1789 e.id = arcs[e.id].next_out; 1790 } 1791 if (e.id != 1) { 1792 e.id /= 2; 1793 return; 1794 } 1795 n = nodes[n].next; 1796 } 1797 e.id = 1; 1798 } 1799 1800 void firstOut(Arc &e, const Node& v) const { 1801 e.id = nodes[v.id].first_out; 1802 } 1803 void nextOut(Arc &e) const { 1804 e.id = arcs[e.id].next_out; 1805 } 1806 1807 void firstIn(Arc &e, const Node& v) const { 1808 e.id = ((nodes[v.id].first_out) ^ 1); 1809 if (e.id == 2) e.id = 1; 1810 } 1811 void nextIn(Arc &e) const { 1812 e.id = ((arcs[e.id ^ 1].next_out) ^ 1); 1813 if (e.id == 2) e.id = 1; 1814 } 1815 1816 void firstInc(Edge &e, bool& d, const Node& v) const { 1817 int a = nodes[v.id].first_out; 1818 if (a != 1 ) { 1819 e.id = a / 2; 1820 d = ((a & 1) == 1); 1821 } else { 1822 e.id = 1; 1823 d = true; 1824 } 1825 } 1826 void nextInc(Edge &e, bool& d) const { 1827 int a = (arcs[(e.id * 2)  (d ? 1 : 0)].next_out); 1828 if (a != 1 ) { 1829 e.id = a / 2; 1830 d = ((a & 1) == 1); 1831 } else { 1832 e.id = 1; 1833 d = true; 1834 } 1835 } 1836 1837 static int id(Node v) { return v.id; } 1838 int redId(Node v) const { 1839 LEMON_DEBUG(nodes[v.id].red, "Node has to be red"); 1840 return nodes[v.id].partition_index; 1841 } 1842 int blueId(Node v) const { 1843 LEMON_DEBUG(!nodes[v.id].red, "Node has to be blue"); 1844 return nodes[v.id].partition_index; 1845 } 1846 static int id(Arc e) { return e.id; } 1847 static int id(Edge e) { return e.id; } 1848 1849 static Node nodeFromId(int id) { return Node(id);} 1850 static Arc arcFromId(int id) { return Arc(id);} 1851 static Edge edgeFromId(int id) { return Edge(id);} 1852 1853 bool valid(Node n) const { 1854 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 1855 nodes[n.id].prev != 2; 1856 } 1857 1858 bool valid(Arc a) const { 1859 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 1860 arcs[a.id].prev_out != 2; 1861 } 1862 1863 bool valid(Edge e) const { 1864 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 1865 arcs[2 * e.id].prev_out != 2; 1866 } 1867 1868 Node addRedNode() { 1869 int n; 1870 1871 if(first_free_red==1) { 1872 n = nodes.size(); 1873 nodes.push_back(NodeT()); 1874 nodes[n].partition_index = ++max_red; 1875 nodes[n].red = true; 1876 } else { 1877 n = first_free_red; 1878 first_free_red = nodes[n].next; 1879 } 1880 1881 nodes[n].next = first_node; 1882 if (first_node != 1) nodes[first_node].prev = n; 1883 first_node = n; 1884 nodes[n].prev = 1; 1885 1886 nodes[n].partition_next = first_red; 1887 if (first_red != 1) nodes[first_red].partition_prev = n; 1888 first_red = n; 1889 nodes[n].partition_prev = 1; 1890 1891 nodes[n].first_out = 1; 1892 1893 return Node(n); 1894 } 1895 1896 Node addBlueNode() { 1897 int n; 1898 1899 if(first_free_blue==1) { 1900 n = nodes.size(); 1901 nodes.push_back(NodeT()); 1902 nodes[n].partition_index = ++max_blue; 1903 nodes[n].red = false; 1904 } else { 1905 n = first_free_blue; 1906 first_free_blue = nodes[n].next; 1907 } 1908 1909 nodes[n].next = first_node; 1910 if (first_node != 1) nodes[first_node].prev = n; 1911 first_node = n; 1912 nodes[n].prev = 1; 1913 1914 nodes[n].partition_next = first_blue; 1915 if (first_blue != 1) nodes[first_blue].partition_prev = n; 1916 first_blue = n; 1917 nodes[n].partition_prev = 1; 1918 1919 nodes[n].first_out = 1; 1920 1921 return Node(n); 1922 } 1923 1924 Edge addEdge(Node u, Node v) { 1925 int n; 1926 1927 if (first_free_arc == 1) { 1928 n = arcs.size(); 1929 arcs.push_back(ArcT()); 1930 arcs.push_back(ArcT()); 1931 } else { 1932 n = first_free_arc; 1933 first_free_arc = arcs[n].next_out; 1934 } 1935 1936 arcs[n].target = u.id; 1937 arcs[n  1].target = v.id; 1938 1939 arcs[n].next_out = nodes[v.id].first_out; 1940 if (nodes[v.id].first_out != 1) { 1941 arcs[nodes[v.id].first_out].prev_out = n; 1942 } 1943 arcs[n].prev_out = 1; 1944 nodes[v.id].first_out = n; 1945 1946 arcs[n  1].next_out = nodes[u.id].first_out; 1947 if (nodes[u.id].first_out != 1) { 1948 arcs[nodes[u.id].first_out].prev_out = (n  1); 1949 } 1950 arcs[n  1].prev_out = 1; 1951 nodes[u.id].first_out = (n  1); 1952 1953 return Edge(n / 2); 1954 } 1955 1956 void erase(const Node& node) { 1957 int n = node.id; 1958 1959 if(nodes[n].next != 1) { 1960 nodes[nodes[n].next].prev = nodes[n].prev; 1961 } 1962 1963 if(nodes[n].prev != 1) { 1964 nodes[nodes[n].prev].next = nodes[n].next; 1965 } else { 1966 first_node = nodes[n].next; 1967 } 1968 1969 if (nodes[n].partition_next != 1) { 1970 nodes[nodes[n].partition_next].partition_prev = nodes[n].partition_prev; 1971 } 1972 1973 if (nodes[n].partition_prev != 1) { 1974 nodes[nodes[n].partition_prev].partition_next = nodes[n].partition_next; 1975 } else { 1976 if (nodes[n].red) { 1977 first_red = nodes[n].partition_next; 1978 } else { 1979 first_blue = nodes[n].partition_next; 1980 } 1981 } 1982 1983 if (nodes[n].red) { 1984 nodes[n].next = first_free_red; 1985 first_free_red = n; 1986 } else { 1987 nodes[n].next = first_free_blue; 1988 first_free_blue = n; 1989 } 1990 nodes[n].prev = 2; 1991 } 1992 1993 void erase(const Edge& edge) { 1994 int n = edge.id * 2; 1995 1996 if (arcs[n].next_out != 1) { 1997 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; 1998 } 1999 2000 if (arcs[n].prev_out != 1) { 2001 arcs[arcs[n].prev_out].next_out = arcs[n].next_out; 2002 } else { 2003 nodes[arcs[n  1].target].first_out = arcs[n].next_out; 2004 } 2005 2006 if (arcs[n  1].next_out != 1) { 2007 arcs[arcs[n  1].next_out].prev_out = arcs[n  1].prev_out; 2008 } 2009 2010 if (arcs[n  1].prev_out != 1) { 2011 arcs[arcs[n  1].prev_out].next_out = arcs[n  1].next_out; 2012 } else { 2013 nodes[arcs[n].target].first_out = arcs[n  1].next_out; 2014 } 2015 2016 arcs[n].next_out = first_free_arc; 2017 first_free_arc = n; 2018 arcs[n].prev_out = 2; 2019 arcs[n  1].prev_out = 2; 2020 2021 } 2022 2023 void clear() { 2024 arcs.clear(); 2025 nodes.clear(); 2026 first_node = first_free_arc = first_red = first_blue = 2027 max_red = max_blue = first_free_red = first_free_blue = 1; 2028 } 2029 2030 protected: 2031 2032 void changeRed(Edge e, Node n) { 2033 LEMON_DEBUG(nodes[n].red, "Node has to be red"); 2034 if(arcs[(2 * e.id)  1].next_out != 1) { 2035 arcs[arcs[(2 * e.id)  1].next_out].prev_out = 2036 arcs[(2 * e.id)  1].prev_out; 2037 } 2038 if(arcs[(2 * e.id)  1].prev_out != 1) { 2039 arcs[arcs[(2 * e.id)  1].prev_out].next_out = 2040 arcs[(2 * e.id)  1].next_out; 2041 } else { 2042 nodes[arcs[2 * e.id].target].first_out = 2043 arcs[(2 * e.id)  1].next_out; 2044 } 2045 2046 if (nodes[n.id].first_out != 1) { 2047 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id)  1); 2048 } 2049 arcs[2 * e.id].target = n.id; 2050 arcs[(2 * e.id)  1].prev_out = 1; 2051 arcs[(2 * e.id)  1].next_out = nodes[n.id].first_out; 2052 nodes[n.id].first_out = ((2 * e.id)  1); 2053 } 2054 2055 void changeBlue(Edge e, Node n) { 2056 LEMON_DEBUG(nodes[n].red, "Node has to be blue"); 2057 if(arcs[2 * e.id].next_out != 1) { 2058 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out; 2059 } 2060 if(arcs[2 * e.id].prev_out != 1) { 2061 arcs[arcs[2 * e.id].prev_out].next_out = 2062 arcs[2 * e.id].next_out; 2063 } else { 2064 nodes[arcs[(2 * e.id)  1].target].first_out = 2065 arcs[2 * e.id].next_out; 2066 } 2067 2068 if (nodes[n.id].first_out != 1) { 2069 arcs[nodes[n.id].first_out].prev_out = 2 * e.id; 2070 } 2071 arcs[(2 * e.id)  1].target = n.id; 2072 arcs[2 * e.id].prev_out = 1; 2073 arcs[2 * e.id].next_out = nodes[n.id].first_out; 2074 nodes[n.id].first_out = 2 * e.id; 2075 } 2076 2077 }; 2078 2079 typedef BpGraphExtender<ListBpGraphBase> ExtendedListBpGraphBase; 2080 2081 2082 /// \addtogroup graphs 2083 /// @{ 2084 2085 ///A general undirected graph structure. 2086 2087 ///\ref ListBpGraph is a versatile and fast undirected graph 2088 ///implementation based on linked lists that are stored in 2089 ///\c std::vector structures. 2090 /// 2091 ///This type fully conforms to the \ref concepts::BpGraph "BpGraph concept" 2092 ///and it also provides several useful additional functionalities. 2093 ///Most of its member functions and nested classes are documented 2094 ///only in the concept class. 2095 /// 2096 ///This class provides only linear time counting for nodes, edges and arcs. 2097 /// 2098 ///\sa concepts::BpGraph 2099 ///\sa ListDigraph 2100 class ListBpGraph : public ExtendedListBpGraphBase { 2101 typedef ExtendedListBpGraphBase Parent; 2102 2103 private: 2104 /// BpGraphs are \e not copy constructible. Use BpGraphCopy instead. 2105 ListBpGraph(const ListBpGraph &) :ExtendedListBpGraphBase() {}; 2106 /// \brief Assignment of a graph to another one is \e not allowed. 2107 /// Use BpGraphCopy instead. 2108 void operator=(const ListBpGraph &) {} 2109 public: 2110 /// Constructor 2111 2112 /// Constructor. 2113 /// 2114 ListBpGraph() {} 2115 2116 typedef Parent::OutArcIt IncEdgeIt; 2117 2118 /// \brief Add a new red node to the graph. 2119 /// 2120 /// This function adds a red new node to the graph. 2121 /// \return The new node. 2122 Node addRedNode() { return Parent::addRedNode(); } 2123 2124 /// \brief Add a new blue node to the graph. 2125 /// 2126 /// This function adds a blue new node to the graph. 2127 /// \return The new node. 2128 Node addBlueNode() { return Parent::addBlueNode(); } 2129 2130 /// \brief Add a new edge to the graph. 2131 /// 2132 /// This function adds a new edge to the graph between nodes 2133 /// \c u and \c v with inherent orientation from node \c u to 2134 /// node \c v. 2135 /// \return The new edge. 2136 Edge addEdge(Node u, Node v) { 2137 return Parent::addEdge(u, v); 2138 } 2139 2140 ///\brief Erase a node from the graph. 2141 /// 2142 /// This function erases the given node along with its incident arcs 2143 /// from the graph. 2144 /// 2145 /// \note All iterators referencing the removed node or the incident 2146 /// edges are invalidated, of course. 2147 void erase(Node n) { Parent::erase(n); } 2148 2149 ///\brief Erase an edge from the graph. 2150 /// 2151 /// This function erases the given edge from the graph. 2152 /// 2153 /// \note All iterators referencing the removed edge are invalidated, 2154 /// of course. 2155 void erase(Edge e) { Parent::erase(e); } 2156 /// Node validity check 2157 2158 /// This function gives back \c true if the given node is valid, 2159 /// i.e. it is a real node of the graph. 2160 /// 2161 /// \warning A removed node could become valid again if new nodes are 2162 /// added to the graph. 2163 bool valid(Node n) const { return Parent::valid(n); } 2164 /// Edge validity check 2165 2166 /// This function gives back \c true if the given edge is valid, 2167 /// i.e. it is a real edge of the graph. 2168 /// 2169 /// \warning A removed edge could become valid again if new edges are 2170 /// added to the graph. 2171 bool valid(Edge e) const { return Parent::valid(e); } 2172 /// Arc validity check 2173 2174 /// This function gives back \c true if the given arc is valid, 2175 /// i.e. it is a real arc of the graph. 2176 /// 2177 /// \warning A removed arc could become valid again if new edges are 2178 /// added to the graph. 2179 bool valid(Arc a) const { return Parent::valid(a); } 2180 2181 /// \brief Change the red node of an edge. 2182 /// 2183 /// This function changes the red node of the given edge \c e to \c n. 2184 /// 2185 ///\note \c EdgeIt and \c ArcIt iterators referencing the 2186 ///changed edge are invalidated and all other iterators whose 2187 ///base node is the changed node are also invalidated. 2188 /// 2189 ///\warning This functionality cannot be used together with the 2190 ///Snapshot feature. 2191 void changeRed(Edge e, Node n) { 2192 Parent::changeRed(e,n); 2193 } 2194 /// \brief Change the blue node of an edge. 2195 /// 2196 /// This function changes the blue node of the given edge \c e to \c n. 2197 /// 2198 ///\note \c EdgeIt iterators referencing the changed edge remain 2199 ///valid, but \c ArcIt iterators referencing the changed edge and 2200 ///all other iterators whose base node is the changed node are also 2201 ///invalidated. 2202 /// 2203 ///\warning This functionality cannot be used together with the 2204 ///Snapshot feature. 2205 void changeBlue(Edge e, Node n) { 2206 Parent::changeBlue(e,n); 2207 } 2208 2209 ///Clear the graph. 2210 2211 ///This function erases all nodes and arcs from the graph. 2212 /// 2213 ///\note All iterators of the graph are invalidated, of course. 2214 void clear() { 2215 Parent::clear(); 2216 } 2217 2218 /// Reserve memory for nodes. 2219 2220 /// Using this function, it is possible to avoid superfluous memory 2221 /// allocation: if you know that the graph you want to build will 2222 /// be large (e.g. it will contain millions of nodes and/or edges), 2223 /// then it is worth reserving space for this amount before starting 2224 /// to build the graph. 2225 /// \sa reserveEdge() 2226 void reserveNode(int n) { nodes.reserve(n); }; 2227 2228 /// Reserve memory for edges. 2229 2230 /// Using this function, it is possible to avoid superfluous memory 2231 /// allocation: if you know that the graph you want to build will 2232 /// be large (e.g. it will contain millions of nodes and/or edges), 2233 /// then it is worth reserving space for this amount before starting 2234 /// to build the graph. 2235 /// \sa reserveNode() 2236 void reserveEdge(int m) { arcs.reserve(2 * m); }; 2237 2238 /// \brief Class to make a snapshot of the graph and restore 2239 /// it later. 2240 /// 2241 /// Class to make a snapshot of the graph and restore it later. 2242 /// 2243 /// The newly added nodes and edges can be removed 2244 /// using the restore() function. 2245 /// 2246 /// \note After a state is restored, you cannot restore a later state, 2247 /// i.e. you cannot add the removed nodes and edges again using 2248 /// another Snapshot instance. 2249 /// 2250 /// \warning Node and edge deletions and other modifications 2251 /// (e.g. changing the endnodes of edges or contracting nodes) 2252 /// cannot be restored. These events invalidate the snapshot. 2253 /// However, the edges and nodes that were added to the graph after 2254 /// making the current snapshot can be removed without invalidating it. 2255 class Snapshot { 2256 protected: 2257 2258 typedef Parent::NodeNotifier NodeNotifier; 2259 2260 class NodeObserverProxy : public NodeNotifier::ObserverBase { 2261 public: 2262 2263 NodeObserverProxy(Snapshot& _snapshot) 2264 : snapshot(_snapshot) {} 2265 2266 using NodeNotifier::ObserverBase::attach; 2267 using NodeNotifier::ObserverBase::detach; 2268 using NodeNotifier::ObserverBase::attached; 2269 2270 protected: 2271 2272 virtual void add(const Node& node) { 2273 snapshot.addNode(node); 2274 } 2275 virtual void add(const std::vector<Node>& nodes) { 2276 for (int i = nodes.size()  1; i >= 0; ++i) { 2277 snapshot.addNode(nodes[i]); 2278 } 2279 } 2280 virtual void erase(const Node& node) { 2281 snapshot.eraseNode(node); 2282 } 2283 virtual void erase(const std::vector<Node>& nodes) { 2284 for (int i = 0; i < int(nodes.size()); ++i) { 2285 snapshot.eraseNode(nodes[i]); 2286 } 2287 } 2288 virtual void build() { 2289 Node node; 2290 std::vector<Node> nodes; 2291 for (notifier()>first(node); node != INVALID; 2292 notifier()>next(node)) { 2293 nodes.push_back(node); 2294 } 2295 for (int i = nodes.size()  1; i >= 0; i) { 2296 snapshot.addNode(nodes[i]); 2297 } 2298 } 2299 virtual void clear() { 2300 Node node; 2301 for (notifier()>first(node); node != INVALID; 2302 notifier()>next(node)) { 2303 snapshot.eraseNode(node); 2304 } 2305 } 2306 2307 Snapshot& snapshot; 2308 }; 2309 2310 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { 2311 public: 2312 2313 EdgeObserverProxy(Snapshot& _snapshot) 2314 : snapshot(_snapshot) {} 2315 2316 using EdgeNotifier::ObserverBase::attach; 2317 using EdgeNotifier::ObserverBase::detach; 2318 using EdgeNotifier::ObserverBase::attached; 2319 2320 protected: 2321 2322 virtual void add(const Edge& edge) { 2323 snapshot.addEdge(edge); 2324 } 2325 virtual void add(const std::vector<Edge>& edges) { 2326 for (int i = edges.size()  1; i >= 0; ++i) { 2327 snapshot.addEdge(edges[i]); 2328 } 2329 } 2330 virtual void erase(const Edge& edge) { 2331 snapshot.eraseEdge(edge); 2332 } 2333 virtual void erase(const std::vector<Edge>& edges) { 2334 for (int i = 0; i < int(edges.size()); ++i) { 2335 snapshot.eraseEdge(edges[i]); 2336 } 2337 } 2338 virtual void build() { 2339 Edge edge; 2340 std::vector<Edge> edges; 2341 for (notifier()>first(edge); edge != INVALID; 2342 notifier()>next(edge)) { 2343 edges.push_back(edge); 2344 } 2345 for (int i = edges.size()  1; i >= 0; i) { 2346 snapshot.addEdge(edges[i]); 2347 } 2348 } 2349 virtual void clear() { 2350 Edge edge; 2351 for (notifier()>first(edge); edge != INVALID; 2352 notifier()>next(edge)) { 2353 snapshot.eraseEdge(edge); 2354 } 2355 } 2356 2357 Snapshot& snapshot; 2358 }; 2359 2360 ListBpGraph *graph; 2361 2362 NodeObserverProxy node_observer_proxy; 2363 EdgeObserverProxy edge_observer_proxy; 2364 2365 std::list<Node> added_nodes; 2366 std::list<Edge> added_edges; 2367 2368 2369 void addNode(const Node& node) { 2370 added_nodes.push_front(node); 2371 } 2372 void eraseNode(const Node& node) { 2373 std::list<Node>::iterator it = 2374 std::find(added_nodes.begin(), added_nodes.end(), node); 2375 if (it == added_nodes.end()) { 2376 clear(); 2377 edge_observer_proxy.detach(); 2378 throw NodeNotifier::ImmediateDetach(); 2379 } else { 2380 added_nodes.erase(it); 2381 } 2382 } 2383 2384 void addEdge(const Edge& edge) { 2385 added_edges.push_front(edge); 2386 } 2387 void eraseEdge(const Edge& edge) { 2388 std::list<Edge>::iterator it = 2389 std::find(added_edges.begin(), added_edges.end(), edge); 2390 if (it == added_edges.end()) { 2391 clear(); 2392 node_observer_proxy.detach(); 2393 throw EdgeNotifier::ImmediateDetach(); 2394 } else { 2395 added_edges.erase(it); 2396 } 2397 } 2398 2399 void attach(ListBpGraph &_graph) { 2400 graph = &_graph; 2401 node_observer_proxy.attach(graph>notifier(Node())); 2402 edge_observer_proxy.attach(graph>notifier(Edge())); 2403 } 2404 2405 void detach() { 2406 node_observer_proxy.detach(); 2407 edge_observer_proxy.detach(); 2408 } 2409 2410 bool attached() const { 2411 return node_observer_proxy.attached(); 2412 } 2413 2414 void clear() { 2415 added_nodes.clear(); 2416 added_edges.clear(); 2417 } 2418 2419 public: 2420 2421 /// \brief Default constructor. 2422 /// 2423 /// Default constructor. 2424 /// You have to call save() to actually make a snapshot. 2425 Snapshot() 2426 : graph(0), node_observer_proxy(*this), 2427 edge_observer_proxy(*this) {} 2428 2429 /// \brief Constructor that immediately makes a snapshot. 2430 /// 2431 /// This constructor immediately makes a snapshot of the given graph. 2432 Snapshot(ListBpGraph &gr) 2433 : node_observer_proxy(*this), 2434 edge_observer_proxy(*this) { 2435 attach(gr); 2436 } 2437 2438 /// \brief Make a snapshot. 2439 /// 2440 /// This function makes a snapshot of the given graph. 2441 /// It can be called more than once. In case of a repeated 2442 /// call, the previous snapshot gets lost. 2443 void save(ListBpGraph &gr) { 2444 if (attached()) { 2445 detach(); 2446 clear(); 2447 } 2448 attach(gr); 2449 } 2450 2451 /// \brief Undo the changes until the last snapshot. 2452 /// 2453 /// This function undos the changes until the last snapshot 2454 /// created by save() or Snapshot(ListBpGraph&). 2455 /// 2456 /// \warning This method invalidates the snapshot, i.e. repeated 2457 /// restoring is not supported unless you call save() again. 2458 void restore() { 2459 detach(); 2460 for(std::list<Edge>::iterator it = added_edges.begin(); 2461 it != added_edges.end(); ++it) { 2462 graph>erase(*it); 2463 } 2464 for(std::list<Node>::iterator it = added_nodes.begin(); 2465 it != added_nodes.end(); ++it) { 2466 graph>erase(*it); 2467 } 2468 clear(); 2469 } 2470 2471 /// \brief Returns \c true if the snapshot is valid. 2472 /// 2473 /// This function returns \c true if the snapshot is valid. 2474 bool valid() const { 2475 return attached(); 2476 } 2477 }; 2478 }; 2479 2480 /// @} 1602 2481 } //namespace lemon 1603 2482
Note: See TracChangeset
for help on using the changeset viewer.