Custom Query (545 matches)
Results (76 - 78 of 545)
Ticket | Resolution | Summary | Owner | Reporter |
---|---|---|---|---|
#414 | fixed | Wrong mincut in preflow algorithm when a valid preflow is supplied. | ||
Description |
First, many thanks for a great bunch of code here. It's well written, cleanly coded, and is really nice to use. Excellent work! I've run into a bug with using the preflow algorithm for calculating the min cuts of a graph, and I'd be happy to help provide a fix. The problem is that the minCut is wrong when you supply a valid preflow to init() in which some of the edges are saturated. A simple example where this fails is the graph "source -> n1 -> n2 -> sink" with the capacity of (source, n1) = 20, (n1,n2) = 10, (n2, sink) = 20. In this case, if you supply a flow map with (source -> n1) = 20 and the rest 0, call init(flow_map), and startFirstPhase(), it incorrectly associates n1 with the sink. The reason I would like this functionality is that I have a huge graph in which I repeatedly make changes to the capacities of a small number of edges, then recalculate the cut. I've got a simple algorithm to turn the preflow from the previous run into a valid preflow on the new graph, and this new preflow is likely close to an optimal one for the new graph -- meaning that a number of the edges are saturated. It seems the problem is that the elevator _level is not initialized properly to account for saturated edges, and startFirstPhase() ignores any saturated edges. To try and fix this problem, I thought one could activate the nodes reachable by saturated edges. The following code added into init(flow_map&), around line 545 in preflow.h, does this: for (OutArcIt e(_graph, _source); e != INVALID; ++e) { Value rem = (*_capacity)[e] - (*_flow)[e]; if (_tolerance.positive(rem)) { Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); (*_excess)[u] += rem; if (u != _target && !_level->active(u)) { _level->activate(u); } } // >>> This part added else if(_tolerance.positive((*_capacity)[e])) { Node u = _graph.target(e); if (u != _target && !_level->active(u)) { _level->activate(u); OutArcIt first_e(_graph, u); if(first_e != INVALID) { std::vector<OutArcIt> iter_stack; iter_stack.push_back(first_e); while(true) { const OutArcIt& e = iter_stack.back(); Node v = _graph.target(e); if(v != _target && !_level->active(v) && ((*_capacity)[e] == (*_flow)[e]) && _tolerance.positive((*_capacity)[e])) { _level->activate(v); OutArcIt next_e = OutArcIt(_graph, v); if(next_e != INVALID) { iter_stack.push_back(next_e); continue; } } while( (++iter_stack.back()) == INVALID) { iter_stack.pop_back(); if(iter_stack.empty()) goto init_next_node; } } } } } init_next_node:; } However, while this successfully fixes all the simple cases, something is still missing in the above code, as this still does not work on more complex graphs. It seems there is something that I don't understand about how the elevator works. What would I be missing here? Is there a quick fix, or is this problem more difficult? Thanks! -- Hoyt P.S. I'm using the development branch from the repository (I think from a few weeks ago). P.P.S. I tried to post this to lemon-devel, but it didn't apparently go through. Apologies for cross-posting if it did. |
|||
#416 | done | Support for running the test with valgrind in CMAKE | ||
Description |
The attached patch adds two CMAKE parameters:
(This latter option basically replaces scripts/valgrind-wrapper.sh) |
|||
#418 | fixed | Compilation problem with CodeBlock + MinGW | ||
Description |
lemon/bits/windows.cc does not find Building CXX object lemon/CMakeFiles/lemon.dir/bits/windows.cc.obj L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:43:23: error: sys/times.h: No such file or directory L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc: In function 'void lemon::bits::getWinProcTimes(double&, double&, double&, double&, double&)': L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:82: error: 'tms' was not declared in this scope L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:82: error: expected ';' before 'ts' L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:83: error: '_SC_CLK_TCK' was not declared in this scope L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:83: error: 'sysconf' was not declared in this scope L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:84: error: 'ts' was not declared in this scope L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:84: error: 'times' was not declared in this scope L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc: In function 'std::string lemon::bits::getWinFormattedDate()': L:\projects\ELTE\ProgOK2\mylemon\lemon\bits\windows.cc:113: error: 'ctime_r' was not declared in this scope make.exe[2]: *** [lemon/CMakeFiles/lemon.dir/bits/windows.cc.obj] Error 1 make.exe[1]: *** [lemon/CMakeFiles/lemon.dir/all] Error 2 make.exe: *** [all] Error 2 Process terminated with status 2 (0 minutes, 2 seconds) 8 errors, 0 warnings I tried it with CodeBlock 10.5 using the official installer version bundled with MinGW. |