lemon/list_graph.h
changeset 1045 4e8787627db3
parent 1021 a12cca3ad15a
child 1049 7bf489cf624e
equal deleted inserted replaced
30:1912fc6fd8b2 31:63e7900277b7
  1645       bool operator==(const Node& node) const {return id == node.id;}
  1645       bool operator==(const Node& node) const {return id == node.id;}
  1646       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;}
  1647       bool operator<(const Node& node) const {return id < node.id;}
  1648     };
  1648     };
  1649 
  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 
  1650     class Edge {
  1674     class Edge {
  1651       friend class ListBpGraphBase;
  1675       friend class ListBpGraphBase;
  1652     protected:
  1676     protected:
  1653 
  1677 
  1654       int id;
  1678       int id;
  1690 
  1714 
  1691 
  1715 
  1692     bool red(Node n) const { return nodes[n.id].red; }
  1716     bool red(Node n) const { return nodes[n.id].red; }
  1693     bool blue(Node n) const { return !nodes[n.id].red; }
  1717     bool blue(Node n) const { return !nodes[n.id].red; }
  1694 
  1718 
       
  1719     static RedNode asRedNodeUnsafe(Node n) { return RedNode(n.id); }
       
  1720     static BlueNode asBlueNodeUnsafe(Node n) { return BlueNode(n.id); }
       
  1721 
  1695     int maxNodeId() const { return nodes.size()-1; }
  1722     int maxNodeId() const { return nodes.size()-1; }
  1696     int maxRedId() const { return max_red; }
  1723     int maxRedId() const { return max_red; }
  1697     int maxBlueId() const { return max_blue; }
  1724     int maxBlueId() const { return max_blue; }
  1698     int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1725     int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1699     int maxArcId() const { return arcs.size()-1; }
  1726     int maxArcId() const { return arcs.size()-1; }
  1700 
  1727 
  1701     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
  1728     Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
  1702     Node target(Arc e) const { return Node(arcs[e.id].target); }
  1729     Node target(Arc e) const { return Node(arcs[e.id].target); }
  1703 
  1730 
  1704     Node redNode(Edge e) const { return Node(arcs[2 * e.id].target); }
  1731     RedNode redNode(Edge e) const {
  1705     Node blueNode(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
  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     }
  1706 
  1737 
  1707     static bool direction(Arc e) {
  1738     static bool direction(Arc e) {
  1708       return (e.id & 1) == 1;
  1739       return (e.id & 1) == 1;
  1709     }
  1740     }
  1710 
  1741 
  1718 
  1749 
  1719     void next(Node& node) const {
  1750     void next(Node& node) const {
  1720       node.id = nodes[node.id].next;
  1751       node.id = nodes[node.id].next;
  1721     }
  1752     }
  1722 
  1753 
  1723     void firstRed(Node& node) const {
  1754     void first(RedNode& node) const {
  1724       node.id = first_red;
  1755       node.id = first_red;
  1725     }
  1756     }
  1726 
  1757 
  1727     void nextRed(Node& node) const {
  1758     void next(RedNode& node) const {
  1728       node.id = nodes[node.id].partition_next;
  1759       node.id = nodes[node.id].partition_next;
  1729     }
  1760     }
  1730 
  1761 
  1731     void firstBlue(Node& node) const {
  1762     void first(BlueNode& node) const {
  1732       node.id = first_blue;
  1763       node.id = first_blue;
  1733     }
  1764     }
  1734 
  1765 
  1735     void nextBlue(Node& node) const {
  1766     void next(BlueNode& node) const {
  1736       node.id = nodes[node.id].partition_next;
  1767       node.id = nodes[node.id].partition_next;
  1737     }    
  1768     }    
  1738 
  1769 
  1739     void first(Arc& e) const {
  1770     void first(Arc& e) const {
  1740       int n = first_node;
  1771       int n = first_node;
  1833         d = true;
  1864         d = true;
  1834       }
  1865       }
  1835     }
  1866     }
  1836 
  1867 
  1837     static int id(Node v) { return v.id; }
  1868     static int id(Node v) { return v.id; }
  1838     int redId(Node v) const {
  1869     int id(RedNode v) const { return nodes[v.id].partition_index; }
  1839       LEMON_DEBUG(nodes[v.id].red, "Node has to be red");
  1870     int id(BlueNode v) const { return nodes[v.id].partition_index; }
  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; }
  1871     static int id(Arc e) { return e.id; }
  1847     static int id(Edge e) { return e.id; }
  1872     static int id(Edge e) { return e.id; }
  1848 
  1873 
  1849     static Node nodeFromId(int id) { return Node(id);}
  1874     static Node nodeFromId(int id) { return Node(id);}
  1850     static Arc arcFromId(int id) { return Arc(id);}
  1875     static Arc arcFromId(int id) { return Arc(id);}
  1863     bool valid(Edge e) const {
  1888     bool valid(Edge e) const {
  1864       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1889       return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
  1865         arcs[2 * e.id].prev_out != -2;
  1890         arcs[2 * e.id].prev_out != -2;
  1866     }
  1891     }
  1867 
  1892 
  1868     Node addRedNode() {
  1893     RedNode addRedNode() {
  1869       int n;
  1894       int n;
  1870 
  1895 
  1871       if(first_free_red==-1) {
  1896       if(first_free_red==-1) {
  1872         n = nodes.size();
  1897         n = nodes.size();
  1873         nodes.push_back(NodeT());
  1898         nodes.push_back(NodeT());
  1888       first_red = n;
  1913       first_red = n;
  1889       nodes[n].partition_prev = -1;
  1914       nodes[n].partition_prev = -1;
  1890 
  1915 
  1891       nodes[n].first_out = -1;
  1916       nodes[n].first_out = -1;
  1892 
  1917 
  1893       return Node(n);
  1918       return RedNode(n);
  1894     }
  1919     }
  1895 
  1920 
  1896     Node addBlueNode() {
  1921     BlueNode addBlueNode() {
  1897       int n;
  1922       int n;
  1898 
  1923 
  1899       if(first_free_blue==-1) {
  1924       if(first_free_blue==-1) {
  1900         n = nodes.size();
  1925         n = nodes.size();
  1901         nodes.push_back(NodeT());
  1926         nodes.push_back(NodeT());
  1916       first_blue = n;
  1941       first_blue = n;
  1917       nodes[n].partition_prev = -1;
  1942       nodes[n].partition_prev = -1;
  1918 
  1943 
  1919       nodes[n].first_out = -1;
  1944       nodes[n].first_out = -1;
  1920 
  1945 
  1921       return Node(n);
  1946       return BlueNode(n);
  1922     }
  1947     }
  1923 
  1948 
  1924     Edge addEdge(Node u, Node v) {
  1949     Edge addEdge(Node u, Node v) {
  1925       int n;
  1950       int n;
  1926 
  1951 
  2027         max_red = max_blue = first_free_red = first_free_blue = -1;
  2052         max_red = max_blue = first_free_red = first_free_blue = -1;
  2028     }
  2053     }
  2029 
  2054 
  2030   protected:
  2055   protected:
  2031 
  2056 
  2032     void changeRed(Edge e, Node n) {
  2057     void changeRed(Edge e, RedNode n) {
  2033       LEMON_DEBUG(nodes[n].red, "Node has to be red");
       
  2034       if(arcs[(2 * e.id) | 1].next_out != -1) {
  2058       if(arcs[(2 * e.id) | 1].next_out != -1) {
  2035         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  2059         arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
  2036           arcs[(2 * e.id) | 1].prev_out;
  2060           arcs[(2 * e.id) | 1].prev_out;
  2037       }
  2061       }
  2038       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  2062       if(arcs[(2 * e.id) | 1].prev_out != -1) {
  2050       arcs[(2 * e.id) | 1].prev_out = -1;
  2074       arcs[(2 * e.id) | 1].prev_out = -1;
  2051       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  2075       arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
  2052       nodes[n.id].first_out = ((2 * e.id) | 1);
  2076       nodes[n.id].first_out = ((2 * e.id) | 1);
  2053     }
  2077     }
  2054 
  2078 
  2055     void changeBlue(Edge e, Node n) {
  2079     void changeBlue(Edge e, BlueNode n) {
  2056       LEMON_DEBUG(nodes[n].red, "Node has to be blue");
  2080        if(arcs[2 * e.id].next_out != -1) {
  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;
  2081         arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
  2059       }
  2082       }
  2060       if(arcs[2 * e.id].prev_out != -1) {
  2083       if(arcs[2 * e.id].prev_out != -1) {
  2061         arcs[arcs[2 * e.id].prev_out].next_out =
  2084         arcs[arcs[2 * e.id].prev_out].next_out =
  2062           arcs[2 * e.id].next_out;
  2085           arcs[2 * e.id].next_out;
  2117 
  2140 
  2118     /// \brief Add a new red node to the graph.
  2141     /// \brief Add a new red node to the graph.
  2119     ///
  2142     ///
  2120     /// This function adds a red new node to the graph.
  2143     /// This function adds a red new node to the graph.
  2121     /// \return The new node.
  2144     /// \return The new node.
  2122     Node addRedNode() { return Parent::addRedNode(); }
  2145     RedNode addRedNode() { return Parent::addRedNode(); }
  2123 
  2146 
  2124     /// \brief Add a new blue node to the graph.
  2147     /// \brief Add a new blue node to the graph.
  2125     ///
  2148     ///
  2126     /// This function adds a blue new node to the graph.
  2149     /// This function adds a blue new node to the graph.
  2127     /// \return The new node.
  2150     /// \return The new node.
  2128     Node addBlueNode() { return Parent::addBlueNode(); }
  2151     BlueNode addBlueNode() { return Parent::addBlueNode(); }
  2129 
  2152 
  2130     /// \brief Add a new edge to the graph.
  2153     /// \brief Add a new edge to the graph.
  2131     ///
  2154     ///
  2132     /// This function adds a new edge to the graph between nodes
  2155     /// 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
  2156     /// \c u and \c v with inherent orientation from node \c u to
  2134     /// node \c v.
  2157     /// node \c v.
  2135     /// \return The new edge.
  2158     /// \return The new edge.
  2136     Edge addEdge(Node u, Node v) {
  2159     Edge addEdge(RedNode u, BlueNode v) {
       
  2160       return Parent::addEdge(u, v);
       
  2161     }
       
  2162     Edge addEdge(BlueNode v, RedNode u) {
  2137       return Parent::addEdge(u, v);
  2163       return Parent::addEdge(u, v);
  2138     }
  2164     }
  2139 
  2165 
  2140     ///\brief Erase a node from the graph.
  2166     ///\brief Erase a node from the graph.
  2141     ///
  2167     ///
  2186     ///changed edge are invalidated and all other iterators whose
  2212     ///changed edge are invalidated and all other iterators whose
  2187     ///base node is the changed node are also invalidated.
  2213     ///base node is the changed node are also invalidated.
  2188     ///
  2214     ///
  2189     ///\warning This functionality cannot be used together with the
  2215     ///\warning This functionality cannot be used together with the
  2190     ///Snapshot feature.
  2216     ///Snapshot feature.
  2191     void changeRed(Edge e, Node n) {
  2217     void changeRed(Edge e, RedNode n) {
  2192       Parent::changeRed(e,n);
  2218       Parent::changeRed(e, n);
  2193     }
  2219     }
  2194     /// \brief Change the blue node of an edge.
  2220     /// \brief Change the blue node of an edge.
  2195     ///
  2221     ///
  2196     /// This function changes the blue node of the given edge \c e to \c n.
  2222     /// This function changes the blue node of the given edge \c e to \c n.
  2197     ///
  2223     ///
  2200     ///all other iterators whose base node is the changed node are also
  2226     ///all other iterators whose base node is the changed node are also
  2201     ///invalidated.
  2227     ///invalidated.
  2202     ///
  2228     ///
  2203     ///\warning This functionality cannot be used together with the
  2229     ///\warning This functionality cannot be used together with the
  2204     ///Snapshot feature.
  2230     ///Snapshot feature.
  2205     void changeBlue(Edge e, Node n) {
  2231     void changeBlue(Edge e, BlueNode n) {
  2206       Parent::changeBlue(e,n);
  2232       Parent::changeBlue(e, n);
  2207     }
  2233     }
  2208 
  2234 
  2209     ///Clear the graph.
  2235     ///Clear the graph.
  2210 
  2236 
  2211     ///This function erases all nodes and arcs from the graph.
  2237     ///This function erases all nodes and arcs from the graph.