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