lemon-1.3: comparison lemon/nagamochi

equal deleted inserted replaced

-:95b33e55a0e8
+:1d90eb454bf5
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2010
+* Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 }
 protected:
 //This is here to avoid a gcc-3.3 compilation error.
 //It should never be called.
 NagamochiIbaraki() {}
 public:
 typedef NagamochiIbaraki Create;
 int index = 0;
 for (typename Graph::NodeIt n(_graph); n != INVALID; ++n) {
 for (typename Graph::OutArcIt a(_graph, n); a != INVALID; ++a) {
 typename Graph::Node m = _graph.target(a);
 if (!(n < m)) continue;
 (*_nodes)[n].sum += (*_capacity)[a];
 (*_nodes)[m].sum += (*_capacity)[a];
 int c = (*_nodes)[m].curr_arc;
 if (c != -1 && _arcs[c ^ 1].target == n) {
 _edges[c >> 1].capacity += (*_capacity)[a];
 } else {
 _edges[index].capacity = (*_capacity)[a];
 _arcs[index << 1].prev = -1;
 if ((*_nodes)[n].first_arc != -1) {
 _arcs[(*_nodes)[n].first_arc].prev = (index << 1);
 }
 _arcs[index << 1].next = (*_nodes)[n].first_arc;
 (*_nodes)[n].first_arc = (index << 1);
 _arcs[index << 1].target = m;
 (*_nodes)[m].curr_arc = (index << 1);
 _arcs[(index << 1) | 1].prev = -1;
 if ((*_nodes)[m].first_arc != -1) {
 _arcs[(*_nodes)[m].first_arc].prev = ((index << 1) | 1);
 }
 _arcs[(index << 1) | 1].next = (*_nodes)[m].first_arc;
 (*_nodes)[m].first_arc = ((index << 1) | 1);
 _arcs[(index << 1) | 1].target = n;
 ++index;
 }
 }
 }
 typename Graph::Node cut_node = INVALID;
 _min_cut = std::numeric_limits<Value>::max();
 for (typename Graph::Node n = _first_node;
 n != INVALID; n = (*_nodes)[n].next) {
 if ((*_nodes)[n].sum < _min_cut) {
 cut_node = n;
 _min_cut = (*_nodes)[n].sum;
 }
 ///\return %True when the algorithm finished.
 bool processNextPhase() {
 if (_first_node == INVALID) return true;
 _heap->clear();
 for (typename Graph::Node n = _first_node;
 n != INVALID; n = (*_nodes)[n].next) {
 (*_heap_cross_ref)[n] = Heap::PRE_HEAP;
 }
 std::vector<typename Graph::Node> order;
 Value v = _heap->prio();
 _heap->pop();
 for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
 switch (_heap->state(_arcs[a].target)) {
 case Heap::PRE_HEAP:
 {
 Value nv = _edges[a >> 1].capacity;
 _heap->push(_arcs[a].target, nv);
 _edges[a >> 1].cut = nv;
 } break;
 bool merged = false;
 for (int a = (*_nodes)[n].first_arc; a != -1; a = _arcs[a].next) {
 if (!(_edges[a >> 1].cut < pmc)) {
 if (!merged) {
 for (int b = (*_nodes)[n].first_arc; b != -1; b = _arcs[b].next) {
 (*_nodes)[_arcs[b].target].curr_arc = b;
 }
 merged = true;
 }
 typename Graph::Node m = _arcs[a].target;
 int nb = 0;
 for (int b = (*_nodes)[m].first_arc; b != -1; b = nb) {
 nb = _arcs[b].next;
 if ((b ^ a) == 1) continue;
 typename Graph::Node o = _arcs[b].target;
 int c = (*_nodes)[o].curr_arc;
 if (c != -1 && _arcs[c ^ 1].target == n) {
 _edges[c >> 1].capacity += _edges[b >> 1].capacity;
 (*_nodes)[n].sum += _edges[b >> 1].capacity;
 if (_edges[b >> 1].cut < _edges[c >> 1].cut) {
 _edges[b >> 1].cut = _edges[c >> 1].cut;
 if (_arcs[a].prev != -1) {
 _arcs[_arcs[a].prev].next = _arcs[a].next;
 } else {
 (*_nodes)[n].first_arc = _arcs[a].next;
 }
 if (_arcs[a].next != -1) {
 _arcs[_arcs[a].next].prev = _arcs[a].prev;
 }
 (*_nodes)[n].sum -= _edges[a >> 1].capacity;
 (*_next_rep)[(*_nodes)[n].last_rep] = m;
 (*_nodes)[n].last_rep = (*_nodes)[m].last_rep;
 if ((*_nodes)[m].prev != INVALID) {
 (*_nodes)[(*_nodes)[m].prev].next = (*_nodes)[m].next;
 } else{
 _first_node = (*_nodes)[m].next;
 }

branch	1.3
changeset 1112	b6bad215bccd
parent 978	eb252f805431