r876:7f6e2bd76654
Wed, 17 Mar 2010 12:35:52
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -1163,12 +1163,17 @@ |
| 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; |
| ... | ... |
@@ -1902,12 +1907,16 @@ |
| 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; |
| ... | ... |
@@ -1672,12 +1672,15 @@ |
| 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 |
|
| ... | ... |
@@ -1694,17 +1697,26 @@ |
| 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); |
| ... | ... |
@@ -3077,12 +3089,15 @@ |
| 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; |
| ... | ... |
@@ -3099,17 +3114,25 @@ |
| 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); |
0 comments (0 inline)