r876:7f6e2bd76654
Wed, 17 Mar 2010 12:35:52
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -1157,24 +1157,29 @@ |
| 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); |
| ... | ... |
@@ -1896,24 +1901,28 @@ |
| 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 |
| ... | ... |
@@ -1666,51 +1666,63 @@ |
| 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; |
| ... | ... |
@@ -3071,51 +3083,62 @@ |
| 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); |
0 comments (0 inline)