396 /// |
396 /// |
397 /// Returns the value of the dual solution. It should be |
397 /// Returns the value of the dual solution. It should be |
398 /// equal to the arborescence value. |
398 /// equal to the arborescence value. |
399 Value dualValue() const { |
399 Value dualValue() const { |
400 Value sum = 0; |
400 Value sum = 0; |
401 for (int i = 0; i < (int)_dual_variables.size(); ++i) { |
401 for (int i = 0; i < int(_dual_variables.size()); ++i) { |
402 sum += _dual_variables[i].value; |
402 sum += _dual_variables[i].value; |
403 } |
403 } |
404 return sum; |
404 return sum; |
405 } |
405 } |
406 |
406 |
457 } |
457 } |
458 return *this; |
458 return *this; |
459 } |
459 } |
460 |
460 |
461 bool operator==(const DualIt& it) const { |
461 bool operator==(const DualIt& it) const { |
462 return (Node)(*this) == (Node)it; |
462 return static_cast<Node>(*this) == static_cast<Node>(it); |
463 } |
463 } |
464 bool operator!=(const DualIt& it) const { |
464 bool operator!=(const DualIt& it) const { |
465 return (Node)(*this) != (Node)it; |
465 return static_cast<Node>(*this) != static_cast<Node>(it); |
466 } |
466 } |
467 bool operator<(const DualIt& it) const { |
467 bool operator<(const DualIt& it) const { |
468 return (Node)(*this) < (Node)it; |
468 return static_cast<Node>(*this) < static_cast<Node>(it); |
469 } |
469 } |
470 |
470 |
471 private: |
471 private: |
472 const MinCostArborescence* _algorithm; |
472 const MinCostArborescence* _algorithm; |
473 int _variable; |
473 int _variable; |
496 _heap->clear(); |
496 _heap->clear(); |
497 for (NodeIt it(*graph); it != INVALID; ++it) { |
497 for (NodeIt it(*graph); it != INVALID; ++it) { |
498 (*_cost_edges)[it].edge = INVALID; |
498 (*_cost_edges)[it].edge = INVALID; |
499 _node_order->set(it, -3); |
499 _node_order->set(it, -3); |
500 _heap_cross_ref->set(it, Heap::PRE_HEAP); |
500 _heap_cross_ref->set(it, Heap::PRE_HEAP); |
|
501 _pred->set(it, INVALID); |
501 } |
502 } |
502 for (EdgeIt it(*graph); it != INVALID; ++it) { |
503 for (EdgeIt it(*graph); it != INVALID; ++it) { |
503 _arborescence->set(it, false); |
504 _arborescence->set(it, false); |
504 _edge_order->set(it, -1); |
505 _edge_order->set(it, -1); |
505 } |
506 } |
680 (*_cost_edges)[source].value = value; |
681 (*_cost_edges)[source].value = value; |
681 } |
682 } |
682 } |
683 } |
683 } |
684 } |
684 CostEdge minimum = (*_cost_edges)[nodes[0]]; |
685 CostEdge minimum = (*_cost_edges)[nodes[0]]; |
685 for (int i = 1; i < (int)nodes.size(); ++i) { |
686 for (int i = 1; i < int(nodes.size()); ++i) { |
686 if ((*_cost_edges)[nodes[i]].value < minimum.value) { |
687 if ((*_cost_edges)[nodes[i]].value < minimum.value) { |
687 minimum = (*_cost_edges)[nodes[i]]; |
688 minimum = (*_cost_edges)[nodes[i]]; |
688 } |
689 } |
689 } |
690 } |
690 _edge_order->set(minimum.edge, _dual_variables.size()); |
691 _edge_order->set(minimum.edge, _dual_variables.size()); |
691 DualVariable var(_dual_node_list.size() - 1, |
692 DualVariable var(_dual_node_list.size() - 1, |
692 _dual_node_list.size(), minimum.value); |
693 _dual_node_list.size(), minimum.value); |
693 _dual_variables.push_back(var); |
694 _dual_variables.push_back(var); |
694 for (int i = 0; i < (int)nodes.size(); ++i) { |
695 for (int i = 0; i < int(nodes.size()); ++i) { |
695 (*_cost_edges)[nodes[i]].value -= minimum.value; |
696 (*_cost_edges)[nodes[i]].value -= minimum.value; |
696 level.edges.push_back((*_cost_edges)[nodes[i]]); |
697 level.edges.push_back((*_cost_edges)[nodes[i]]); |
697 (*_cost_edges)[nodes[i]].edge = INVALID; |
698 (*_cost_edges)[nodes[i]].edge = INVALID; |
698 } |
699 } |
699 level_stack.push_back(level); |
700 level_stack.push_back(level); |
703 Edge contract(Node node) { |
704 Edge contract(Node node) { |
704 int node_bottom = bottom(node); |
705 int node_bottom = bottom(node); |
705 std::vector<Node> nodes; |
706 std::vector<Node> nodes; |
706 while (!level_stack.empty() && |
707 while (!level_stack.empty() && |
707 level_stack.back().node_level >= node_bottom) { |
708 level_stack.back().node_level >= node_bottom) { |
708 for (int i = 0; i < (int)level_stack.back().edges.size(); ++i) { |
709 for (int i = 0; i < int(level_stack.back().edges.size()); ++i) { |
709 Edge edge = level_stack.back().edges[i].edge; |
710 Edge edge = level_stack.back().edges[i].edge; |
710 Node source = graph->source(edge); |
711 Node source = graph->source(edge); |
711 Value value = level_stack.back().edges[i].value; |
712 Value value = level_stack.back().edges[i].value; |
712 if ((*_node_order)[source] >= node_bottom) continue; |
713 if ((*_node_order)[source] >= node_bottom) continue; |
713 if ((*_cost_edges)[source].edge == INVALID) { |
714 if ((*_cost_edges)[source].edge == INVALID) { |
722 } |
723 } |
723 } |
724 } |
724 level_stack.pop_back(); |
725 level_stack.pop_back(); |
725 } |
726 } |
726 CostEdge minimum = (*_cost_edges)[nodes[0]]; |
727 CostEdge minimum = (*_cost_edges)[nodes[0]]; |
727 for (int i = 1; i < (int)nodes.size(); ++i) { |
728 for (int i = 1; i < int(nodes.size()); ++i) { |
728 if ((*_cost_edges)[nodes[i]].value < minimum.value) { |
729 if ((*_cost_edges)[nodes[i]].value < minimum.value) { |
729 minimum = (*_cost_edges)[nodes[i]]; |
730 minimum = (*_cost_edges)[nodes[i]]; |
730 } |
731 } |
731 } |
732 } |
732 _edge_order->set(minimum.edge, _dual_variables.size()); |
733 _edge_order->set(minimum.edge, _dual_variables.size()); |
733 DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); |
734 DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); |
734 _dual_variables.push_back(var); |
735 _dual_variables.push_back(var); |
735 StackLevel level; |
736 StackLevel level; |
736 level.node_level = node_bottom; |
737 level.node_level = node_bottom; |
737 for (int i = 0; i < (int)nodes.size(); ++i) { |
738 for (int i = 0; i < int(nodes.size()); ++i) { |
738 (*_cost_edges)[nodes[i]].value -= minimum.value; |
739 (*_cost_edges)[nodes[i]].value -= minimum.value; |
739 level.edges.push_back((*_cost_edges)[nodes[i]]); |
740 level.edges.push_back((*_cost_edges)[nodes[i]]); |
740 (*_cost_edges)[nodes[i]].edge = INVALID; |
741 (*_cost_edges)[nodes[i]].edge = INVALID; |
741 } |
742 } |
742 level_stack.push_back(level); |
743 level_stack.push_back(level); |