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()); |
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. |