COIN-OR::LEMON - Graph Library

Changeset 1147:138714057145 in lemon-main


Ignore:
Timestamp:
05/22/15 17:44:29 (5 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1139:0900cfe4a84d (diff), 1146: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
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/list_graph.h

    r1092 r1147  
    583583        }
    584584        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) {
    586586            snapshot.addNode(nodes[i]);
    587587          }
     
    633633        }
    634634        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) {
    636636            snapshot.addArc(arcs[i]);
    637637          }
     
    13951395        }
    13961396        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) {
    13981398            snapshot.addNode(nodes[i]);
    13991399          }
     
    14451445        }
    14461446        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) {
    14481448            snapshot.addEdge(edges[i]);
    14491449          }
  • lemon/list_graph.h

    r1146 r1147  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    446446    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
    447447    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
    448     ///iterators are invalidated for the incomming arcs of \c v.
     448    ///iterators are invalidated for the incoming arcs of \c v.
    449449    ///Moreover all iterators referencing node \c v or the removed
    450450    ///loops are also invalidated. Other iterators remain valid.
     
    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 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  /// @}
    16022507} //namespace lemon
    16032508
Note: See TracChangeset for help on using the changeset viewer.