COIN-OR::LEMON - Graph Library

Changeset 1189:a12cca3ad15a in lemon


Ignore:
Timestamp:
11/15/10 09:46:08 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

ListBpGraph? implementation (#69)

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r956 r1189  
    16001600
    16011601  /// @}
     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 end-nodes 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  /// @}
    16022481} //namespace lemon
    16032482
  • lemon/smart_graph.h

    r1188 r1189  
    10171017    }
    10181018    int blueId(Node v) const {
    1019       LEMON_DEBUG(nodes[v._id].red, "Node has to be blue");
     1019      LEMON_DEBUG(!nodes[v._id].red, "Node has to be blue");
    10201020      return nodes[v._id].partition_index;
    10211021    }
  • test/bpgraph_test.cc

    r1188 r1189  
    1818
    1919#include <lemon/concepts/bpgraph.h>
    20 //#include <lemon/list_graph.h>
     20#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    2222#include <lemon/full_graph.h>
     
    108108}
    109109
    110 template <class Graph>
     110template <class BpGraph>
     111void checkBpGraphErase() {
     112  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     113
     114  BpGraph G;
     115  Node
     116    n1 = G.addRedNode(), n2 = G.addBlueNode(),
     117    n3 = G.addBlueNode(), n4 = G.addRedNode();
     118  Edge
     119    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     120    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
     121
     122  // Check edge deletion
     123  G.erase(e2);
     124
     125  checkGraphNodeList(G, 4);
     126  checkGraphRedNodeList(G, 2);
     127  checkGraphBlueNodeList(G, 2);
     128  checkGraphEdgeList(G, 3);
     129  checkGraphArcList(G, 6);
     130
     131  checkGraphIncEdgeArcLists(G, n1, 1);
     132  checkGraphIncEdgeArcLists(G, n2, 2);
     133  checkGraphIncEdgeArcLists(G, n3, 1);
     134  checkGraphIncEdgeArcLists(G, n4, 2);
     135
     136  checkGraphConEdgeList(G, 3);
     137  checkGraphConArcList(G, 6);
     138
     139  // Check node deletion
     140  G.erase(n3);
     141
     142  checkGraphNodeList(G, 3);
     143  checkGraphRedNodeList(G, 2);
     144  checkGraphBlueNodeList(G, 1);
     145  checkGraphEdgeList(G, 2);
     146  checkGraphArcList(G, 4);
     147
     148  checkGraphIncEdgeArcLists(G, n1, 1);
     149  checkGraphIncEdgeArcLists(G, n2, 2);
     150  checkGraphIncEdgeArcLists(G, n4, 1);
     151
     152  checkGraphConEdgeList(G, 2);
     153  checkGraphConArcList(G, 4);
     154
     155}
     156
     157template <class BpGraph>
     158void checkBpGraphAlter() {
     159  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     160
     161  BpGraph G;
     162  Node
     163    n1 = G.addRedNode(), n2 = G.addBlueNode(),
     164    n3 = G.addBlueNode(), n4 = G.addRedNode();
     165  Edge
     166    e1 = G.addEdge(n1, n2), e2 = G.addEdge(n1, n3),
     167    e3 = G.addEdge(n4, n2), e4 = G.addEdge(n4, n3);
     168
     169  G.changeRed(e2, n4);
     170  check(G.redNode(e2) == n4, "Wrong red node");
     171  check(G.blueNode(e2) == n3, "Wrong blue node");
     172
     173  checkGraphNodeList(G, 4);
     174  checkGraphRedNodeList(G, 2);
     175  checkGraphBlueNodeList(G, 2);
     176  checkGraphEdgeList(G, 4);
     177  checkGraphArcList(G, 8);
     178
     179  checkGraphIncEdgeArcLists(G, n1, 1);
     180  checkGraphIncEdgeArcLists(G, n2, 2);
     181  checkGraphIncEdgeArcLists(G, n3, 2);
     182  checkGraphIncEdgeArcLists(G, n4, 3);
     183
     184  checkGraphConEdgeList(G, 4);
     185  checkGraphConArcList(G, 8);
     186
     187  G.changeBlue(e2, n2);
     188  check(G.redNode(e2) == n4, "Wrong red node");
     189  check(G.blueNode(e2) == n2, "Wrong blue node");
     190
     191  checkGraphNodeList(G, 4);
     192  checkGraphRedNodeList(G, 2);
     193  checkGraphBlueNodeList(G, 2);
     194  checkGraphEdgeList(G, 4);
     195  checkGraphArcList(G, 8);
     196
     197  checkGraphIncEdgeArcLists(G, n1, 1);
     198  checkGraphIncEdgeArcLists(G, n2, 3);
     199  checkGraphIncEdgeArcLists(G, n3, 1);
     200  checkGraphIncEdgeArcLists(G, n4, 3);
     201
     202  checkGraphConEdgeList(G, 4);
     203  checkGraphConArcList(G, 8);
     204}
     205
     206
     207template <class BpGraph>
    111208void checkBpGraphSnapshot() {
    112   TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
    113 
    114   Graph G;
     209  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     210
     211  BpGraph G;
    115212  Node
    116213    n1 = G.addRedNode(),
     
    127224  checkGraphArcList(G, 4);
    128225
    129   typename Graph::Snapshot snapshot(G);
     226  typename BpGraph::Snapshot snapshot(G);
    130227
    131228  Node n4 = G.addRedNode();
     
    191288}
    192289
    193 template <typename Graph>
     290template <typename BpGraph>
    194291void checkBpGraphValidity() {
    195   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    196   Graph g;
     292  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     293  BpGraph g;
    197294
    198295  Node
     
    326423
    327424void checkGraphs() {
     425  { // Checking ListGraph
     426    checkBpGraphBuild<ListBpGraph>();
     427    checkBpGraphErase<ListBpGraph>();
     428    checkBpGraphAlter<ListBpGraph>();
     429    checkBpGraphSnapshot<ListBpGraph>();
     430    checkBpGraphValidity<ListBpGraph>();
     431  }
    328432  { // Checking SmartGraph
    329433    checkBpGraphBuild<SmartBpGraph>();
Note: See TracChangeset for help on using the changeset viewer.