r876:7f6e2bd76654
Wed, 17 Mar 2010 12:35:52
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -1121,96 +1121,101 @@ |
| 1121 | 1121 |
int right_tree = _tree_set->find(right); |
| 1122 | 1122 |
alternatePath(right, right_tree); |
| 1123 | 1123 |
destroyTree(right_tree); |
| 1124 | 1124 |
_matching->set(right, _graph.oppositeArc(arc)); |
| 1125 | 1125 |
} |
| 1126 | 1126 |
|
| 1127 | 1127 |
public: |
| 1128 | 1128 |
|
| 1129 | 1129 |
/// \brief Constructor |
| 1130 | 1130 |
/// |
| 1131 | 1131 |
/// Constructor. |
| 1132 | 1132 |
MaxWeightedFractionalMatching(const Graph& graph, const WeightMap& weight, |
| 1133 | 1133 |
bool allow_loops = true) |
| 1134 | 1134 |
: _graph(graph), _weight(weight), _matching(0), |
| 1135 | 1135 |
_node_potential(0), _node_num(0), _allow_loops(allow_loops), |
| 1136 | 1136 |
_status(0), _pred(0), |
| 1137 | 1137 |
_tree_set_index(0), _tree_set(0), |
| 1138 | 1138 |
|
| 1139 | 1139 |
_delta1_index(0), _delta1(0), |
| 1140 | 1140 |
_delta2_index(0), _delta2(0), |
| 1141 | 1141 |
_delta3_index(0), _delta3(0), |
| 1142 | 1142 |
|
| 1143 | 1143 |
_delta_sum() {}
|
| 1144 | 1144 |
|
| 1145 | 1145 |
~MaxWeightedFractionalMatching() {
|
| 1146 | 1146 |
destroyStructures(); |
| 1147 | 1147 |
} |
| 1148 | 1148 |
|
| 1149 | 1149 |
/// \name Execution Control |
| 1150 | 1150 |
/// The simplest way to execute the algorithm is to use the |
| 1151 | 1151 |
/// \ref run() member function. |
| 1152 | 1152 |
|
| 1153 | 1153 |
///@{
|
| 1154 | 1154 |
|
| 1155 | 1155 |
/// \brief Initialize the algorithm |
| 1156 | 1156 |
/// |
| 1157 | 1157 |
/// This function initializes the algorithm. |
| 1158 | 1158 |
void init() {
|
| 1159 | 1159 |
createStructures(); |
| 1160 | 1160 |
|
| 1161 | 1161 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1162 | 1162 |
(*_delta1_index)[n] = _delta1->PRE_HEAP; |
| 1163 | 1163 |
(*_delta2_index)[n] = _delta2->PRE_HEAP; |
| 1164 | 1164 |
} |
| 1165 | 1165 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1166 | 1166 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 1167 | 1167 |
} |
| 1168 | 1168 |
|
| 1169 |
_delta1->clear(); |
|
| 1170 |
_delta2->clear(); |
|
| 1171 |
_delta3->clear(); |
|
| 1172 |
_tree_set->clear(); |
|
| 1173 |
|
|
| 1169 | 1174 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1170 | 1175 |
Value max = 0; |
| 1171 | 1176 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1172 | 1177 |
if (_graph.target(e) == n && !_allow_loops) continue; |
| 1173 | 1178 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 1174 | 1179 |
max = (dualScale * _weight[e]) / 2; |
| 1175 | 1180 |
} |
| 1176 | 1181 |
} |
| 1177 | 1182 |
_node_potential->set(n, max); |
| 1178 | 1183 |
_delta1->push(n, max); |
| 1179 | 1184 |
|
| 1180 | 1185 |
_tree_set->insert(n); |
| 1181 | 1186 |
|
| 1182 | 1187 |
_matching->set(n, INVALID); |
| 1183 | 1188 |
_status->set(n, EVEN); |
| 1184 | 1189 |
} |
| 1185 | 1190 |
|
| 1186 | 1191 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1187 | 1192 |
Node left = _graph.u(e); |
| 1188 | 1193 |
Node right = _graph.v(e); |
| 1189 | 1194 |
if (left == right && !_allow_loops) continue; |
| 1190 | 1195 |
_delta3->push(e, ((*_node_potential)[left] + |
| 1191 | 1196 |
(*_node_potential)[right] - |
| 1192 | 1197 |
dualScale * _weight[e]) / 2); |
| 1193 | 1198 |
} |
| 1194 | 1199 |
} |
| 1195 | 1200 |
|
| 1196 | 1201 |
/// \brief Start the algorithm |
| 1197 | 1202 |
/// |
| 1198 | 1203 |
/// This function starts the algorithm. |
| 1199 | 1204 |
/// |
| 1200 | 1205 |
/// \pre \ref init() must be called before using this function. |
| 1201 | 1206 |
void start() {
|
| 1202 | 1207 |
enum OpType {
|
| 1203 | 1208 |
D1, D2, D3 |
| 1204 | 1209 |
}; |
| 1205 | 1210 |
|
| 1206 | 1211 |
int unmatched = _node_num; |
| 1207 | 1212 |
while (unmatched > 0) {
|
| 1208 | 1213 |
Value d1 = !_delta1->empty() ? |
| 1209 | 1214 |
_delta1->prio() : std::numeric_limits<Value>::max(); |
| 1210 | 1215 |
|
| 1211 | 1216 |
Value d2 = !_delta2->empty() ? |
| 1212 | 1217 |
_delta2->prio() : std::numeric_limits<Value>::max(); |
| 1213 | 1218 |
|
| 1214 | 1219 |
Value d3 = !_delta3->empty() ? |
| 1215 | 1220 |
_delta3->prio() : std::numeric_limits<Value>::max(); |
| 1216 | 1221 |
|
| ... | ... |
@@ -1860,96 +1865,100 @@ |
| 1860 | 1865 |
Node right = _graph.target(arc); |
| 1861 | 1866 |
int right_tree = _tree_set->find(right); |
| 1862 | 1867 |
alternatePath(right, right_tree); |
| 1863 | 1868 |
destroyTree(right_tree); |
| 1864 | 1869 |
_matching->set(right, _graph.oppositeArc(arc)); |
| 1865 | 1870 |
} |
| 1866 | 1871 |
|
| 1867 | 1872 |
public: |
| 1868 | 1873 |
|
| 1869 | 1874 |
/// \brief Constructor |
| 1870 | 1875 |
/// |
| 1871 | 1876 |
/// Constructor. |
| 1872 | 1877 |
MaxWeightedPerfectFractionalMatching(const Graph& graph, |
| 1873 | 1878 |
const WeightMap& weight, |
| 1874 | 1879 |
bool allow_loops = true) |
| 1875 | 1880 |
: _graph(graph), _weight(weight), _matching(0), |
| 1876 | 1881 |
_node_potential(0), _node_num(0), _allow_loops(allow_loops), |
| 1877 | 1882 |
_status(0), _pred(0), |
| 1878 | 1883 |
_tree_set_index(0), _tree_set(0), |
| 1879 | 1884 |
|
| 1880 | 1885 |
_delta2_index(0), _delta2(0), |
| 1881 | 1886 |
_delta3_index(0), _delta3(0), |
| 1882 | 1887 |
|
| 1883 | 1888 |
_delta_sum() {}
|
| 1884 | 1889 |
|
| 1885 | 1890 |
~MaxWeightedPerfectFractionalMatching() {
|
| 1886 | 1891 |
destroyStructures(); |
| 1887 | 1892 |
} |
| 1888 | 1893 |
|
| 1889 | 1894 |
/// \name Execution Control |
| 1890 | 1895 |
/// The simplest way to execute the algorithm is to use the |
| 1891 | 1896 |
/// \ref run() member function. |
| 1892 | 1897 |
|
| 1893 | 1898 |
///@{
|
| 1894 | 1899 |
|
| 1895 | 1900 |
/// \brief Initialize the algorithm |
| 1896 | 1901 |
/// |
| 1897 | 1902 |
/// This function initializes the algorithm. |
| 1898 | 1903 |
void init() {
|
| 1899 | 1904 |
createStructures(); |
| 1900 | 1905 |
|
| 1901 | 1906 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1902 | 1907 |
(*_delta2_index)[n] = _delta2->PRE_HEAP; |
| 1903 | 1908 |
} |
| 1904 | 1909 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1905 | 1910 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 1906 | 1911 |
} |
| 1907 | 1912 |
|
| 1913 |
_delta2->clear(); |
|
| 1914 |
_delta3->clear(); |
|
| 1915 |
_tree_set->clear(); |
|
| 1916 |
|
|
| 1908 | 1917 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1909 | 1918 |
Value max = - std::numeric_limits<Value>::max(); |
| 1910 | 1919 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1911 | 1920 |
if (_graph.target(e) == n && !_allow_loops) continue; |
| 1912 | 1921 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 1913 | 1922 |
max = (dualScale * _weight[e]) / 2; |
| 1914 | 1923 |
} |
| 1915 | 1924 |
} |
| 1916 | 1925 |
_node_potential->set(n, max); |
| 1917 | 1926 |
|
| 1918 | 1927 |
_tree_set->insert(n); |
| 1919 | 1928 |
|
| 1920 | 1929 |
_matching->set(n, INVALID); |
| 1921 | 1930 |
_status->set(n, EVEN); |
| 1922 | 1931 |
} |
| 1923 | 1932 |
|
| 1924 | 1933 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1925 | 1934 |
Node left = _graph.u(e); |
| 1926 | 1935 |
Node right = _graph.v(e); |
| 1927 | 1936 |
if (left == right && !_allow_loops) continue; |
| 1928 | 1937 |
_delta3->push(e, ((*_node_potential)[left] + |
| 1929 | 1938 |
(*_node_potential)[right] - |
| 1930 | 1939 |
dualScale * _weight[e]) / 2); |
| 1931 | 1940 |
} |
| 1932 | 1941 |
} |
| 1933 | 1942 |
|
| 1934 | 1943 |
/// \brief Start the algorithm |
| 1935 | 1944 |
/// |
| 1936 | 1945 |
/// This function starts the algorithm. |
| 1937 | 1946 |
/// |
| 1938 | 1947 |
/// \pre \ref init() must be called before using this function. |
| 1939 | 1948 |
bool start() {
|
| 1940 | 1949 |
enum OpType {
|
| 1941 | 1950 |
D2, D3 |
| 1942 | 1951 |
}; |
| 1943 | 1952 |
|
| 1944 | 1953 |
int unmatched = _node_num; |
| 1945 | 1954 |
while (unmatched > 0) {
|
| 1946 | 1955 |
Value d2 = !_delta2->empty() ? |
| 1947 | 1956 |
_delta2->prio() : std::numeric_limits<Value>::max(); |
| 1948 | 1957 |
|
| 1949 | 1958 |
Value d3 = !_delta3->empty() ? |
| 1950 | 1959 |
_delta3->prio() : std::numeric_limits<Value>::max(); |
| 1951 | 1960 |
|
| 1952 | 1961 |
_delta_sum = d3; OpType ot = D3; |
| 1953 | 1962 |
if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
|
| 1954 | 1963 |
|
| 1955 | 1964 |
if (_delta_sum == std::numeric_limits<Value>::max()) {
|
| ... | ... |
@@ -1630,123 +1630,135 @@ |
| 1630 | 1630 |
_delta2->clear(); |
| 1631 | 1631 |
_delta3->clear(); |
| 1632 | 1632 |
_delta4->clear(); |
| 1633 | 1633 |
_blossom_set->clear(); |
| 1634 | 1634 |
_tree_set->clear(); |
| 1635 | 1635 |
|
| 1636 | 1636 |
int index = 0; |
| 1637 | 1637 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1638 | 1638 |
Value max = 0; |
| 1639 | 1639 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1640 | 1640 |
if (_graph.target(e) == n) continue; |
| 1641 | 1641 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 1642 | 1642 |
max = (dualScale * _weight[e]) / 2; |
| 1643 | 1643 |
} |
| 1644 | 1644 |
} |
| 1645 | 1645 |
(*_node_index)[n] = index; |
| 1646 | 1646 |
(*_node_data)[index].heap_index.clear(); |
| 1647 | 1647 |
(*_node_data)[index].heap.clear(); |
| 1648 | 1648 |
(*_node_data)[index].pot = max; |
| 1649 | 1649 |
_delta1->push(n, max); |
| 1650 | 1650 |
int blossom = |
| 1651 | 1651 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 1652 | 1652 |
|
| 1653 | 1653 |
_tree_set->insert(blossom); |
| 1654 | 1654 |
|
| 1655 | 1655 |
(*_blossom_data)[blossom].status = EVEN; |
| 1656 | 1656 |
(*_blossom_data)[blossom].pred = INVALID; |
| 1657 | 1657 |
(*_blossom_data)[blossom].next = INVALID; |
| 1658 | 1658 |
(*_blossom_data)[blossom].pot = 0; |
| 1659 | 1659 |
(*_blossom_data)[blossom].offset = 0; |
| 1660 | 1660 |
++index; |
| 1661 | 1661 |
} |
| 1662 | 1662 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1663 | 1663 |
int si = (*_node_index)[_graph.u(e)]; |
| 1664 | 1664 |
int ti = (*_node_index)[_graph.v(e)]; |
| 1665 | 1665 |
if (_graph.u(e) != _graph.v(e)) {
|
| 1666 | 1666 |
_delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot - |
| 1667 | 1667 |
dualScale * _weight[e]) / 2); |
| 1668 | 1668 |
} |
| 1669 | 1669 |
} |
| 1670 | 1670 |
} |
| 1671 | 1671 |
|
| 1672 | 1672 |
/// \brief Initialize the algorithm with fractional matching |
| 1673 | 1673 |
/// |
| 1674 | 1674 |
/// This function initializes the algorithm with a fractional |
| 1675 | 1675 |
/// matching. This initialization is also called jumpstart heuristic. |
| 1676 | 1676 |
void fractionalInit() {
|
| 1677 | 1677 |
createStructures(); |
| 1678 |
|
|
| 1679 |
_blossom_node_list.clear(); |
|
| 1680 |
_blossom_potential.clear(); |
|
| 1678 | 1681 |
|
| 1679 | 1682 |
if (_fractional == 0) {
|
| 1680 | 1683 |
_fractional = new FractionalMatching(_graph, _weight, false); |
| 1681 | 1684 |
} |
| 1682 | 1685 |
_fractional->run(); |
| 1683 | 1686 |
|
| 1684 | 1687 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
| 1685 | 1688 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
| 1686 | 1689 |
} |
| 1687 | 1690 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1688 | 1691 |
(*_delta1_index)[n] = _delta1->PRE_HEAP; |
| 1689 | 1692 |
} |
| 1690 | 1693 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1691 | 1694 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 1692 | 1695 |
} |
| 1693 | 1696 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 1694 | 1697 |
(*_delta2_index)[i] = _delta2->PRE_HEAP; |
| 1695 | 1698 |
(*_delta4_index)[i] = _delta4->PRE_HEAP; |
| 1696 | 1699 |
} |
| 1697 | 1700 |
|
| 1698 | 1701 |
_unmatched = 0; |
| 1699 | 1702 |
|
| 1703 |
_delta1->clear(); |
|
| 1704 |
_delta2->clear(); |
|
| 1705 |
_delta3->clear(); |
|
| 1706 |
_delta4->clear(); |
|
| 1707 |
_blossom_set->clear(); |
|
| 1708 |
_tree_set->clear(); |
|
| 1709 |
|
|
| 1700 | 1710 |
int index = 0; |
| 1701 | 1711 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1702 | 1712 |
Value pot = _fractional->nodeValue(n); |
| 1703 | 1713 |
(*_node_index)[n] = index; |
| 1704 | 1714 |
(*_node_data)[index].pot = pot; |
| 1715 |
(*_node_data)[index].heap_index.clear(); |
|
| 1716 |
(*_node_data)[index].heap.clear(); |
|
| 1705 | 1717 |
int blossom = |
| 1706 | 1718 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 1707 | 1719 |
|
| 1708 | 1720 |
(*_blossom_data)[blossom].status = MATCHED; |
| 1709 | 1721 |
(*_blossom_data)[blossom].pred = INVALID; |
| 1710 | 1722 |
(*_blossom_data)[blossom].next = _fractional->matching(n); |
| 1711 | 1723 |
if (_fractional->matching(n) == INVALID) {
|
| 1712 | 1724 |
(*_blossom_data)[blossom].base = n; |
| 1713 | 1725 |
} |
| 1714 | 1726 |
(*_blossom_data)[blossom].pot = 0; |
| 1715 | 1727 |
(*_blossom_data)[blossom].offset = 0; |
| 1716 | 1728 |
++index; |
| 1717 | 1729 |
} |
| 1718 | 1730 |
|
| 1719 | 1731 |
typename Graph::template NodeMap<bool> processed(_graph, false); |
| 1720 | 1732 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1721 | 1733 |
if (processed[n]) continue; |
| 1722 | 1734 |
processed[n] = true; |
| 1723 | 1735 |
if (_fractional->matching(n) == INVALID) continue; |
| 1724 | 1736 |
int num = 1; |
| 1725 | 1737 |
Node v = _graph.target(_fractional->matching(n)); |
| 1726 | 1738 |
while (n != v) {
|
| 1727 | 1739 |
processed[v] = true; |
| 1728 | 1740 |
v = _graph.target(_fractional->matching(v)); |
| 1729 | 1741 |
++num; |
| 1730 | 1742 |
} |
| 1731 | 1743 |
|
| 1732 | 1744 |
if (num % 2 == 1) {
|
| 1733 | 1745 |
std::vector<int> subblossoms(num); |
| 1734 | 1746 |
|
| 1735 | 1747 |
subblossoms[--num] = _blossom_set->find(n); |
| 1736 | 1748 |
_delta1->push(n, _fractional->nodeValue(n)); |
| 1737 | 1749 |
v = _graph.target(_fractional->matching(n)); |
| 1738 | 1750 |
while (n != v) {
|
| 1739 | 1751 |
subblossoms[--num] = _blossom_set->find(v); |
| 1740 | 1752 |
_delta1->push(v, _fractional->nodeValue(v)); |
| 1741 | 1753 |
v = _graph.target(_fractional->matching(v)); |
| 1742 | 1754 |
} |
| 1743 | 1755 |
|
| 1744 | 1756 |
int surface = |
| 1745 | 1757 |
_blossom_set->join(subblossoms.begin(), subblossoms.end()); |
| 1746 | 1758 |
(*_blossom_data)[surface].status = EVEN; |
| 1747 | 1759 |
(*_blossom_data)[surface].pred = INVALID; |
| 1748 | 1760 |
(*_blossom_data)[surface].next = INVALID; |
| 1749 | 1761 |
(*_blossom_data)[surface].pot = 0; |
| 1750 | 1762 |
(*_blossom_data)[surface].offset = 0; |
| 1751 | 1763 |
|
| 1752 | 1764 |
_tree_set->insert(surface); |
| ... | ... |
@@ -3035,123 +3047,134 @@ |
| 3035 | 3047 |
|
| 3036 | 3048 |
_delta2->clear(); |
| 3037 | 3049 |
_delta3->clear(); |
| 3038 | 3050 |
_delta4->clear(); |
| 3039 | 3051 |
_blossom_set->clear(); |
| 3040 | 3052 |
_tree_set->clear(); |
| 3041 | 3053 |
|
| 3042 | 3054 |
int index = 0; |
| 3043 | 3055 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 3044 | 3056 |
Value max = - std::numeric_limits<Value>::max(); |
| 3045 | 3057 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 3046 | 3058 |
if (_graph.target(e) == n) continue; |
| 3047 | 3059 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 3048 | 3060 |
max = (dualScale * _weight[e]) / 2; |
| 3049 | 3061 |
} |
| 3050 | 3062 |
} |
| 3051 | 3063 |
(*_node_index)[n] = index; |
| 3052 | 3064 |
(*_node_data)[index].heap_index.clear(); |
| 3053 | 3065 |
(*_node_data)[index].heap.clear(); |
| 3054 | 3066 |
(*_node_data)[index].pot = max; |
| 3055 | 3067 |
int blossom = |
| 3056 | 3068 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 3057 | 3069 |
|
| 3058 | 3070 |
_tree_set->insert(blossom); |
| 3059 | 3071 |
|
| 3060 | 3072 |
(*_blossom_data)[blossom].status = EVEN; |
| 3061 | 3073 |
(*_blossom_data)[blossom].pred = INVALID; |
| 3062 | 3074 |
(*_blossom_data)[blossom].next = INVALID; |
| 3063 | 3075 |
(*_blossom_data)[blossom].pot = 0; |
| 3064 | 3076 |
(*_blossom_data)[blossom].offset = 0; |
| 3065 | 3077 |
++index; |
| 3066 | 3078 |
} |
| 3067 | 3079 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 3068 | 3080 |
int si = (*_node_index)[_graph.u(e)]; |
| 3069 | 3081 |
int ti = (*_node_index)[_graph.v(e)]; |
| 3070 | 3082 |
if (_graph.u(e) != _graph.v(e)) {
|
| 3071 | 3083 |
_delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot - |
| 3072 | 3084 |
dualScale * _weight[e]) / 2); |
| 3073 | 3085 |
} |
| 3074 | 3086 |
} |
| 3075 | 3087 |
} |
| 3076 | 3088 |
|
| 3077 | 3089 |
/// \brief Initialize the algorithm with fractional matching |
| 3078 | 3090 |
/// |
| 3079 | 3091 |
/// This function initializes the algorithm with a fractional |
| 3080 | 3092 |
/// matching. This initialization is also called jumpstart heuristic. |
| 3081 | 3093 |
void fractionalInit() {
|
| 3082 | 3094 |
createStructures(); |
| 3095 |
|
|
| 3096 |
_blossom_node_list.clear(); |
|
| 3097 |
_blossom_potential.clear(); |
|
| 3083 | 3098 |
|
| 3084 | 3099 |
if (_fractional == 0) {
|
| 3085 | 3100 |
_fractional = new FractionalMatching(_graph, _weight, false); |
| 3086 | 3101 |
} |
| 3087 | 3102 |
if (!_fractional->run()) {
|
| 3088 | 3103 |
_unmatched = -1; |
| 3089 | 3104 |
return; |
| 3090 | 3105 |
} |
| 3091 | 3106 |
|
| 3092 | 3107 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
| 3093 | 3108 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
| 3094 | 3109 |
} |
| 3095 | 3110 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 3096 | 3111 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 3097 | 3112 |
} |
| 3098 | 3113 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 3099 | 3114 |
(*_delta2_index)[i] = _delta2->PRE_HEAP; |
| 3100 | 3115 |
(*_delta4_index)[i] = _delta4->PRE_HEAP; |
| 3101 | 3116 |
} |
| 3102 | 3117 |
|
| 3103 | 3118 |
_unmatched = 0; |
| 3104 | 3119 |
|
| 3120 |
_delta2->clear(); |
|
| 3121 |
_delta3->clear(); |
|
| 3122 |
_delta4->clear(); |
|
| 3123 |
_blossom_set->clear(); |
|
| 3124 |
_tree_set->clear(); |
|
| 3125 |
|
|
| 3105 | 3126 |
int index = 0; |
| 3106 | 3127 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 3107 | 3128 |
Value pot = _fractional->nodeValue(n); |
| 3108 | 3129 |
(*_node_index)[n] = index; |
| 3109 | 3130 |
(*_node_data)[index].pot = pot; |
| 3131 |
(*_node_data)[index].heap_index.clear(); |
|
| 3132 |
(*_node_data)[index].heap.clear(); |
|
| 3110 | 3133 |
int blossom = |
| 3111 | 3134 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 3112 | 3135 |
|
| 3113 | 3136 |
(*_blossom_data)[blossom].status = MATCHED; |
| 3114 | 3137 |
(*_blossom_data)[blossom].pred = INVALID; |
| 3115 | 3138 |
(*_blossom_data)[blossom].next = _fractional->matching(n); |
| 3116 | 3139 |
(*_blossom_data)[blossom].pot = 0; |
| 3117 | 3140 |
(*_blossom_data)[blossom].offset = 0; |
| 3118 | 3141 |
++index; |
| 3119 | 3142 |
} |
| 3120 | 3143 |
|
| 3121 | 3144 |
typename Graph::template NodeMap<bool> processed(_graph, false); |
| 3122 | 3145 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 3123 | 3146 |
if (processed[n]) continue; |
| 3124 | 3147 |
processed[n] = true; |
| 3125 | 3148 |
if (_fractional->matching(n) == INVALID) continue; |
| 3126 | 3149 |
int num = 1; |
| 3127 | 3150 |
Node v = _graph.target(_fractional->matching(n)); |
| 3128 | 3151 |
while (n != v) {
|
| 3129 | 3152 |
processed[v] = true; |
| 3130 | 3153 |
v = _graph.target(_fractional->matching(v)); |
| 3131 | 3154 |
++num; |
| 3132 | 3155 |
} |
| 3133 | 3156 |
|
| 3134 | 3157 |
if (num % 2 == 1) {
|
| 3135 | 3158 |
std::vector<int> subblossoms(num); |
| 3136 | 3159 |
|
| 3137 | 3160 |
subblossoms[--num] = _blossom_set->find(n); |
| 3138 | 3161 |
v = _graph.target(_fractional->matching(n)); |
| 3139 | 3162 |
while (n != v) {
|
| 3140 | 3163 |
subblossoms[--num] = _blossom_set->find(v); |
| 3141 | 3164 |
v = _graph.target(_fractional->matching(v)); |
| 3142 | 3165 |
} |
| 3143 | 3166 |
|
| 3144 | 3167 |
int surface = |
| 3145 | 3168 |
_blossom_set->join(subblossoms.begin(), subblossoms.end()); |
| 3146 | 3169 |
(*_blossom_data)[surface].status = EVEN; |
| 3147 | 3170 |
(*_blossom_data)[surface].pred = INVALID; |
| 3148 | 3171 |
(*_blossom_data)[surface].next = INVALID; |
| 3149 | 3172 |
(*_blossom_data)[surface].pot = 0; |
| 3150 | 3173 |
(*_blossom_data)[surface].offset = 0; |
| 3151 | 3174 |
|
| 3152 | 3175 |
_tree_set->insert(surface); |
| 3153 | 3176 |
++_unmatched; |
| 3154 | 3177 |
} |
| 3155 | 3178 |
} |
| 3156 | 3179 |
|
| 3157 | 3180 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
0 comments (0 inline)