r876:7f6e2bd76654
Wed, 17 Mar 2010 12:35:52
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -1145,48 +1145,53 @@ |
| 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); |
| ... | ... |
@@ -1884,48 +1889,52 @@ |
| 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 |
} |
| ... | ... |
@@ -1654,75 +1654,87 @@ |
| 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)); |
| ... | ... |
@@ -3059,75 +3071,86 @@ |
| 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 |
|
0 comments (0 inline)