equal
deleted
inserted
replaced
291 for (int i = 1; i < int(nodes.size()); ++i) { |
291 for (int i = 1; i < int(nodes.size()); ++i) { |
292 if ((*_cost_arcs)[nodes[i]].value < minimum.value) { |
292 if ((*_cost_arcs)[nodes[i]].value < minimum.value) { |
293 minimum = (*_cost_arcs)[nodes[i]]; |
293 minimum = (*_cost_arcs)[nodes[i]]; |
294 } |
294 } |
295 } |
295 } |
296 _arc_order->set(minimum.arc, _dual_variables.size()); |
296 (*_arc_order)[minimum.arc] = _dual_variables.size(); |
297 DualVariable var(_dual_node_list.size() - 1, |
297 DualVariable var(_dual_node_list.size() - 1, |
298 _dual_node_list.size(), minimum.value); |
298 _dual_node_list.size(), minimum.value); |
299 _dual_variables.push_back(var); |
299 _dual_variables.push_back(var); |
300 for (int i = 0; i < int(nodes.size()); ++i) { |
300 for (int i = 0; i < int(nodes.size()); ++i) { |
301 (*_cost_arcs)[nodes[i]].value -= minimum.value; |
301 (*_cost_arcs)[nodes[i]].value -= minimum.value; |
333 for (int i = 1; i < int(nodes.size()); ++i) { |
333 for (int i = 1; i < int(nodes.size()); ++i) { |
334 if ((*_cost_arcs)[nodes[i]].value < minimum.value) { |
334 if ((*_cost_arcs)[nodes[i]].value < minimum.value) { |
335 minimum = (*_cost_arcs)[nodes[i]]; |
335 minimum = (*_cost_arcs)[nodes[i]]; |
336 } |
336 } |
337 } |
337 } |
338 _arc_order->set(minimum.arc, _dual_variables.size()); |
338 (*_arc_order)[minimum.arc] = _dual_variables.size(); |
339 DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); |
339 DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); |
340 _dual_variables.push_back(var); |
340 _dual_variables.push_back(var); |
341 StackLevel level; |
341 StackLevel level; |
342 level.node_level = node_bottom; |
342 level.node_level = node_bottom; |
343 for (int i = 0; i < int(nodes.size()); ++i) { |
343 for (int i = 0; i < int(nodes.size()); ++i) { |
362 _heap->push(node, (*_arc_order)[arc]); |
362 _heap->push(node, (*_arc_order)[arc]); |
363 _pred->set(node, arc); |
363 _pred->set(node, arc); |
364 while (!_heap->empty()) { |
364 while (!_heap->empty()) { |
365 Node source = _heap->top(); |
365 Node source = _heap->top(); |
366 _heap->pop(); |
366 _heap->pop(); |
367 _node_order->set(source, -1); |
367 (*_node_order)[source] = -1; |
368 for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { |
368 for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { |
369 if ((*_arc_order)[it] < 0) continue; |
369 if ((*_arc_order)[it] < 0) continue; |
370 Node target = _digraph->target(it); |
370 Node target = _digraph->target(it); |
371 switch(_heap->state(target)) { |
371 switch(_heap->state(target)) { |
372 case Heap::PRE_HEAP: |
372 case Heap::PRE_HEAP: |
648 void init() { |
648 void init() { |
649 createStructures(); |
649 createStructures(); |
650 _heap->clear(); |
650 _heap->clear(); |
651 for (NodeIt it(*_digraph); it != INVALID; ++it) { |
651 for (NodeIt it(*_digraph); it != INVALID; ++it) { |
652 (*_cost_arcs)[it].arc = INVALID; |
652 (*_cost_arcs)[it].arc = INVALID; |
653 _node_order->set(it, -3); |
653 (*_node_order)[it] = -3; |
654 _heap_cross_ref->set(it, Heap::PRE_HEAP); |
654 (*_heap_cross_ref)[it] = Heap::PRE_HEAP; |
655 _pred->set(it, INVALID); |
655 _pred->set(it, INVALID); |
656 } |
656 } |
657 for (ArcIt it(*_digraph); it != INVALID; ++it) { |
657 for (ArcIt it(*_digraph); it != INVALID; ++it) { |
658 _arborescence->set(it, false); |
658 _arborescence->set(it, false); |
659 _arc_order->set(it, -1); |
659 (*_arc_order)[it] = -1; |
660 } |
660 } |
661 _dual_node_list.clear(); |
661 _dual_node_list.clear(); |
662 _dual_variables.clear(); |
662 _dual_variables.clear(); |
663 } |
663 } |
664 |
664 |