equal
deleted
inserted
replaced
1673 /// |
1673 /// |
1674 /// This function initializes the algorithm with a fractional |
1674 /// This function initializes the algorithm with a fractional |
1675 /// matching. This initialization is also called jumpstart heuristic. |
1675 /// matching. This initialization is also called jumpstart heuristic. |
1676 void fractionalInit() { |
1676 void fractionalInit() { |
1677 createStructures(); |
1677 createStructures(); |
|
1678 |
|
1679 _blossom_node_list.clear(); |
|
1680 _blossom_potential.clear(); |
1678 |
1681 |
1679 if (_fractional == 0) { |
1682 if (_fractional == 0) { |
1680 _fractional = new FractionalMatching(_graph, _weight, false); |
1683 _fractional = new FractionalMatching(_graph, _weight, false); |
1681 } |
1684 } |
1682 _fractional->run(); |
1685 _fractional->run(); |
1694 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
1697 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
1695 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
1698 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
1696 } |
1699 } |
1697 |
1700 |
1698 _unmatched = 0; |
1701 _unmatched = 0; |
|
1702 |
|
1703 _delta1->clear(); |
|
1704 _delta2->clear(); |
|
1705 _delta3->clear(); |
|
1706 _delta4->clear(); |
|
1707 _blossom_set->clear(); |
|
1708 _tree_set->clear(); |
1699 |
1709 |
1700 int index = 0; |
1710 int index = 0; |
1701 for (NodeIt n(_graph); n != INVALID; ++n) { |
1711 for (NodeIt n(_graph); n != INVALID; ++n) { |
1702 Value pot = _fractional->nodeValue(n); |
1712 Value pot = _fractional->nodeValue(n); |
1703 (*_node_index)[n] = index; |
1713 (*_node_index)[n] = index; |
1704 (*_node_data)[index].pot = pot; |
1714 (*_node_data)[index].pot = pot; |
|
1715 (*_node_data)[index].heap_index.clear(); |
|
1716 (*_node_data)[index].heap.clear(); |
1705 int blossom = |
1717 int blossom = |
1706 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1718 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1707 |
1719 |
1708 (*_blossom_data)[blossom].status = MATCHED; |
1720 (*_blossom_data)[blossom].status = MATCHED; |
1709 (*_blossom_data)[blossom].pred = INVALID; |
1721 (*_blossom_data)[blossom].pred = INVALID; |
3078 /// |
3090 /// |
3079 /// This function initializes the algorithm with a fractional |
3091 /// This function initializes the algorithm with a fractional |
3080 /// matching. This initialization is also called jumpstart heuristic. |
3092 /// matching. This initialization is also called jumpstart heuristic. |
3081 void fractionalInit() { |
3093 void fractionalInit() { |
3082 createStructures(); |
3094 createStructures(); |
|
3095 |
|
3096 _blossom_node_list.clear(); |
|
3097 _blossom_potential.clear(); |
3083 |
3098 |
3084 if (_fractional == 0) { |
3099 if (_fractional == 0) { |
3085 _fractional = new FractionalMatching(_graph, _weight, false); |
3100 _fractional = new FractionalMatching(_graph, _weight, false); |
3086 } |
3101 } |
3087 if (!_fractional->run()) { |
3102 if (!_fractional->run()) { |
3099 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
3114 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
3100 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
3115 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
3101 } |
3116 } |
3102 |
3117 |
3103 _unmatched = 0; |
3118 _unmatched = 0; |
|
3119 |
|
3120 _delta2->clear(); |
|
3121 _delta3->clear(); |
|
3122 _delta4->clear(); |
|
3123 _blossom_set->clear(); |
|
3124 _tree_set->clear(); |
3104 |
3125 |
3105 int index = 0; |
3126 int index = 0; |
3106 for (NodeIt n(_graph); n != INVALID; ++n) { |
3127 for (NodeIt n(_graph); n != INVALID; ++n) { |
3107 Value pot = _fractional->nodeValue(n); |
3128 Value pot = _fractional->nodeValue(n); |
3108 (*_node_index)[n] = index; |
3129 (*_node_index)[n] = index; |
3109 (*_node_data)[index].pot = pot; |
3130 (*_node_data)[index].pot = pot; |
|
3131 (*_node_data)[index].heap_index.clear(); |
|
3132 (*_node_data)[index].heap.clear(); |
3110 int blossom = |
3133 int blossom = |
3111 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
3134 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
3112 |
3135 |
3113 (*_blossom_data)[blossom].status = MATCHED; |
3136 (*_blossom_data)[blossom].status = MATCHED; |
3114 (*_blossom_data)[blossom].pred = INVALID; |
3137 (*_blossom_data)[blossom].pred = INVALID; |