lemon/min_cost_arborescence.h
changeset 581 aa1804409f29
parent 559 c5fd2d996909
child 584 33c6b6e755cd
equal deleted inserted replaced
1:f0fba3977e39 2:54a671d0f128
   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