LEMON: Ticket Query
http://lemon.cs.elte.hu/trac/lemon/query?status=!closed&reporter=kpeter&order=priority
Library for Efficient Modeling and Optimization in Networksen-USLEMONhttp://lemon.cs.elte.hu/trac/lemon/chrome/site/lemon-logo.gif
http://lemon.cs.elte.hu/trac/lemon/query?status=!closed&reporter=kpeter&order=priority
Trac 1.2.3
http://lemon.cs.elte.hu/trac/lemon/ticket/346
http://lemon.cs.elte.hu/trac/lemon/ticket/346#346: Port the remaining shortest path algorithmsFri, 19 Feb 2010 13:10:36 GMTPeter Kovacs<p>
The following files are affected:
</p>
<ul><li>lemon/floyd_warshall.h
</li><li>lemon/johnson.h
</li><li>lemon/dag_shortest_path.h
</li><li>test/all_pairs_shortest_path_test.cc
</li></ul><p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/51" title="#51: task: Port the remaining shortest path algorithms (closed: done)">#51</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/346#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/37
http://lemon.cs.elte.hu/trac/lemon/ticket/37#37: operator= for RangeMap and SparseMapSat, 22 Mar 2008 17:50:14 GMTPeter Kovacs<p>
Now <code>operator=</code> function is private (without implementation) in <code>RangeMap</code> and <code>SparseMap</code> classes. Do we need public <code>operator=</code>?
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/37#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/98
http://lemon.cs.elte.hu/trac/lemon/ticket/98#98: Read-Write LoggerBoolMapSat, 14 Jun 2008 17:40:18 GMTPeter Kovacs<p>
LoggerBoolMap map is only writable, so e.g. it can be used for ProcessedMap, but it cannot be used for ReachedMap in Bfs, Dfs, Dijkstra.
</p>
<p>
Now the simplest way for creating such a map is
</p>
<div class="wiki-code"><div class="code"><pre>typedef LoggerBoolMap<...> LoggerMap;
BoolEdgeMap map;
LoggerMap log;
ForkMap<BoolEdgeMap, LoggerMap> m(map, log);
</pre></div></div>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/98#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/152
http://lemon.cs.elte.hu/trac/lemon/ticket/152#152: Using processed map in Dijkstra::processed()Fri, 26 Sep 2008 04:31:33 GMTPeter Kovacs<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/149" title="#149: task: Removing \todo commands (closed: fixed)">#149</a>.
</p>
<p>
Now <a class="missing source">Dijkstra::processed()</a> uses the heap to determine the return value whether or not the current <code>ProcessedMap</code> type is <code>NullMap</code> or not and whether it uses local map or not. It would be nice that the given processed map (<code>_processed</code>) is used if it is not of type <code>NullMap</code> and the heap is used otherwise.
</p>
<p>
I think it would need some template tricks to implement. Otherwise we could introduce a bool flag that shows whether <code>SetProcessedMap</code> or <code>SetStandardProcessedMap</code> named class parameters were used. But in the the later case extra codes in <code>DijkstraWizard</code> would also be needed, since it does not use the above named class parameters but defining a traits class explicitly.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/152#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/189
http://lemon.cs.elte.hu/trac/lemon/ticket/189#189: Add the functionality of ItemSetTraits to the graphsSun, 30 Nov 2008 21:25:17 GMTPeter Kovacs<p>
Maybe we could introduce the functionality of <code>ItemSetTraits</code> to the graph concepts and to the adaptors in order to have the followings for all graph types.
</p>
<ul><li><code>Graph::Map<T, Value></code>
</li><li><code>Graph::It<T></code> or <code>Graph::ItemIt<T></code>
</li></ul><p>
Where <code>T</code> can be <code>Node</code>, <code>Arc</code> or <code>Edge</code>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/189#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/191
http://lemon.cs.elte.hu/trac/lemon/ticket/191#191: Benchmark questions related to PreflowSun, 30 Nov 2008 21:43:09 GMTPeter Kovacs<p>
There are some efficiency questions about the <code>Preflow</code> implementation, that require thorough benchmarking.
</p>
<ul><li><code>Elevator</code> or <code>LinkedElevator</code> should be used by default?
</li><li>The BFS implementation in the <code>init()</code> function could be made more efficient using only one vector and three indices (<code>first</code>, <code>last</code>, <code>new_level</code>).
</li><li>We should try very large instances and check again whether the current heuristics and the constant 20 factor that is used for them are really optimal or not.
</li><li>We should try Goldberg's new idea of partial augmentations. (However it should probably be a new class.)
</li></ul>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/191#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/238
http://lemon.cs.elte.hu/trac/lemon/ticket/238#238: Min cut iterators in PreflowWed, 04 Mar 2009 22:02:45 GMTPeter Kovacs<p>
It would be nice to have iterators for obtaining the min. cut in <code>Preflow</code> class. E.g. there could be <code>MinCutNodeIt</code> and <code>MinCutArcIt</code> similarly to the ones in <code>GomoryHu</code> class (but note that in <code>Preflow</code> we have directed cuts).
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/238#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/244
http://lemon.cs.elte.hu/trac/lemon/ticket/244#244: Support min. cost max. flow in MCF classesWed, 25 Mar 2009 21:29:41 GMTPeter Kovacs<p>
The new concept of the min cost flow classes (see <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/234" title="#234: task: Port and revise Network Simplex algorithm (closed: fixed)">#234</a>) makes it easy to provide interface for the min. cost maximum flow problem, too.
</p>
<p>
For example, there could be a <code>maxFlow(Node s, Node t)</code> function, which could be used instead of <code>supplyMap()</code> and <code>stSupply()</code>. In this case <code>Preflow::runMinCut()</code> should be called to determine the max. flow value (instead of <code>Circualtion</code>), and the algorithm have to be initialized as if <code>stSupport()</code> was called with this flow value. However apart from that nothing have to be changed.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/244#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/246
http://lemon.cs.elte.hu/trac/lemon/ticket/246#246: s() and t() as an alias for source() and target()Fri, 27 Mar 2009 15:11:03 GMTPeter Kovacs<p>
As we have <code>u()</code> and <code>v()</code> for undirected graphs, it seems to be a good idea to have shorter alias names for <code>source()</code> and <code>target()</code>, e.g. <code>s()</code> and <code>t()</code>, since they are among the most frequently used functions.
</p>
<p>
What do you think about it?
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/246#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/247
http://lemon.cs.elte.hu/trac/lemon/ticket/247#247: DegMapFri, 27 Mar 2009 15:45:57 GMTPeter Kovacs<p>
There are <code>InDegMap</code> and <code>OutDegMap</code> classes for directed graphs. So it would be nice to have a <code>DegMap</code> class for undirected graphs. I see that both <code>InDegMap</code> and <code>OutDegMap</code> can be used for this purpose, but it would be better to have <code>DegMap</code> even if it is just an alias for one of these maps.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/247#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/249
http://lemon.cs.elte.hu/trac/lemon/ticket/249#249: Bidirectional Bfs and DijkstraFri, 27 Mar 2009 16:19:17 GMTPeter Kovacs<p>
It would be nice to have bidirectional Bfs and Dijkstra implementation in LEMON for the s-t shortest path problem.
</p>
<p>
Theoretically it is simple: the algorithm should be started "in parallel" from the source node s on the original graph and from the target node t on the reversed graph. As soon as we have a node u for which both direction have set the final <em>dist</em> and <em>pred</em> values, we can finish searching and construct the s->t path form the s->u path and the opposite of the t->u path. It could be faster by about a factor of two due to smaller search spaces.
</p>
<p>
However it is not clear for me how difficult it would be to implement it.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/249#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/251
http://lemon.cs.elte.hu/trac/lemon/ticket/251#251: More efficient graph copyingFri, 27 Mar 2009 16:44:14 GMTPeter Kovacs<p>
Is there any way to make graph copying faster for graph types like <code>List(Di)Graph</code> and <code>Smart(Di)Graph</code>?
</p>
<p>
Maybe we could have specialized versions of <code>(di)graphCopy()</code> for the cases when both types are the same, e.g. list or smart graph, which function would directly copy the vectors that represent the graph.
</p>
<p>
I'm not sure about the implementation, but I think this method would have two advantages:
</p>
<ul><li>It could be faster.
</li><li>It would keep the node, arc and/or edge ids and the order of the items. Now if you have a <code>SmartDigraph</code> and copies it to another <code>SmartDigraph</code> structure, then the iteration orders of the nodes and arcs are reversed.
</li></ul>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/251#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/252
http://lemon.cs.elte.hu/trac/lemon/ticket/252#252: Smaller iterator classes for some graph structuresFri, 27 Mar 2009 16:58:58 GMTPeter Kovacs<p>
All the <code>NodeIt</code>, <code>ArcIt</code>, <code>EdgeIt</code> etc. iterator classes stores a pointer for the underlying (di)graph. However it wouldn't be necessary in some cases.
</p>
<p>
E.g. <code>SmartDigraph::next(Node&)</code> and <code>SmartDigraph::next(Arc&)</code> are static functions. Thus <code>SmartDigraph::NodeIt</code> and <code>SmartDigraph::ArcIt</code> could be implemented without a pointer to the graph. The three <code>next()</code> functions of <code>SmartGraph</code> are not static, but they could/should be. The special graph structures (<code>FullGraph</code>, <code>HypercubeGraph</code>, <code>GridGraph</code>) also have static <code>next()</code> functions.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/252#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/269
http://lemon.cs.elte.hu/trac/lemon/ticket/269#269: Function type interface for CirculationFri, 24 Apr 2009 14:49:56 GMTPeter Kovacs<p>
It would be nice to have a function type interface for Circulation.
It should have almost the same named parameters as NetworkSimplex (without costs), and it should be implemented without map copying to be as efficient as the class interface.
</p>
<p>
This ticket is a folow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/266" title="#266: task: Revise the interface of Circulation and Suurballe (closed: fixed)">#266</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/269#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/271
http://lemon.cs.elte.hu/trac/lemon/ticket/271#271: Provide output in dimacs-solverFri, 24 Apr 2009 22:05:42 GMTPeter Kovacs<p>
Currently dimacs-solver reports only the shortest path length (distance), the max flow value or the min flow cost. It would be better to provide the full solution in DIMACS format.
</p>
<p>
For the max flow here is a relevant output format (from the webpage of A. V. Goldberg):<br />
<a class="ext-link" href="http://www.avglab.com/andrew/CATS/maxflow_formats.htm"><span class="icon"></span>http://www.avglab.com/andrew/CATS/maxflow_formats.htm</a>
</p>
<p>
This format can be used for min cost flow problems as well. I found an MCF solver that actually use this, see the attached sample file.
</p>
<p>
However I didn't find such output format for shortest path problems. There are various formats for correctness checking and performance reporting, but they are very specific to the 9th DIMACS implementation challenge and follow a slightly different concept.<br />
<a class="ext-link" href="http://www.dis.uniroma1.it/~challenge9/format.shtml"><span class="icon"></span>http://www.dis.uniroma1.it/~challenge9/format.shtml</a>
</p>
<p>
Maybe we should invent a shortest path output format according to the other dimacs input/output formats, or only provide output for the flow problems.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/271#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/287
http://lemon.cs.elte.hu/trac/lemon/ticket/287#287: Specify argument order for ArgParserFri, 08 May 2009 11:04:08 GMTPeter Kovacs<p>
I think it would be nice if the order in which <code>ArgParser</code> prints out the arguments and their documentations would be able to be changed. A good example is lgf-gen, for which a lot of command line arguments are printed and the alphabetical order makes them more difficult to overview.
</p>
<p>
I suggest two options: alphabetical order and the order in which the arguments were specified. The first one could be the default, but the second one could be selected as an alternative.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/287#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/292
http://lemon.cs.elte.hu/trac/lemon/ticket/292#292: Checker functions for min cost flowTue, 12 May 2009 10:50:33 GMTPeter Kovacs<p>
Maybe we could have checker functions for the minimum cost flow algorithms according to the test file. E.g. <code>checkFeasibility()</code> and <code>checkOptimality()</code> or <code>checkFlow()</code> and <code>checkPotential()</code>.
They would be similar to the checker functions of <code>Circulation</code>.
</p>
<p>
However it is questionable whether these functions should be introduced to all MCF algorithms or we should have them separetly, since the implementation would be independent form the algorithms.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/292#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/296
http://lemon.cs.elte.hu/trac/lemon/ticket/296#296: Multicommodity flow algorithmsTue, 26 May 2009 16:47:21 GMTPeter Kovacs<p>
It would be important to implement various multicommodity flow algorithms in LEMON. Approximation (and maybe exact) solution methods for fractional, integral and unsplittable multicommodity flow problems.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/296#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/300
http://lemon.cs.elte.hu/trac/lemon/ticket/300#300: Faster building of heapsWed, 08 Jul 2009 16:09:49 GMTPeter Kovacs<p>
For some heap structures it is possible to build them from an existing list of <code>n</code> items faster than calling <code>push()</code> <code>n</code> times.
E.g. for binary heap calling <code>push()</code> for each item takes <code>O(n log n)</code> time, while a heap can be built in <code>O(n)</code> time.
</p>
<p>
It would be nice to indroduce <code>build()</code> (or something like that) member functions into those heap structures, for which it could be done faster than calling <code>push()</code> <code>n</code> times. Or maybe such a function could be introduced to the heap concept itself and all the heap structures (it could be implemented by calling <code>push()</code>, if it is not slower).
</p>
<p>
The main reason why we have heaps is to use them in algorithms like Dijkstra and Prim. These algorithms do not need such a function, but if one would like to use LEMON heaps for other purposes, it may be useful.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/300#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/313
http://lemon.cs.elte.hu/trac/lemon/ticket/313#313: Revise the implementation of PairingHeap and RadixHeapTue, 01 Sep 2009 19:43:45 GMTPeter Kovacs<p>
The implementation of <code>PairingHeap</code> and <code>RadixHeap</code> should be revised, since they could most likely be made more efficient.
</p>
<p>
For example, in LEDA (according to their tests) pairing heap is always faster than Fibonacci heap, moreover it is usually faster than binary heap. Radix heap is also very fast, it is usually better than both pairing and binary heaps. However according to my tests, <code>PairingHeap</code> and <code>RadixHeap</code> are almost always slower than <code>BinHeap</code> in LEMON.
</p>
<p>
LEDA results: <a class="ext-link" href="http://www.cs.elte.hu/~kiraly/sanyag.adatstr/LEDAbook.heaps.ps"><span class="icon"></span>http://www.cs.elte.hu/~kiraly/sanyag.adatstr/LEDAbook.heaps.ps</a>
</p>
<p>
Two hints for <code>PairingHeap</code>:
</p>
<ol><li>It does not contain the heuristic that the small heaps created by <code>push()</code> and <code>decrease()</code> operations are collected in a temporary storage and they are merged into the main heap only if it is necessary (e.g. in case of a <code>pop()</code> or <code>prio()</code>).
</li><li>The underlying binary tree is currently stored using two indices (pointers) and a bool value at each node. This needs less space than storing three indices (for the parent and the two children), but it is not clear if it is faster or slower. The latter representation should also be implemented and tested.
</li></ol><p>
Apart from that, there could be other points in which the code could be made better.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/313#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/318
http://lemon.cs.elte.hu/trac/lemon/ticket/318#318: Document MapIt, ConstMapIt and ItemIt classes of standard mapsTue, 06 Oct 2009 06:09:40 GMTPeter Kovacs<p>
There are three iterator classes: <code>MapIt</code>, <code>ConstMapIt</code> and <code>ItemIt</code> for all standard graph maps, which seem to be useful. However they are neither documented nor tested in the concept classes. I think, they sohuld be.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/311" title="#311: defect: Improvements for graphs (closed: fixed)">#311</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/318#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/328
http://lemon.cs.elte.hu/trac/lemon/ticket/328#328: Heuristic MinCostFlow and MinCostMaxFlowFri, 13 Nov 2009 00:23:26 GMTPeter Kovacs<p>
It could be worthwhile to create a heuristic min cost flow solver class named <code>MinCostFlow</code>. It would have the same interface as the single algorithms, but it could try to select the best algorithm to run according to the parameters of the problem (size of the graph, density, max. capacity etc.). This class could be used in e.g. thew dimacs solver.
</p>
<p>
Similarly, we could have a heuristic <code>MinCostMaxFlow</code> using <code>Preflow</code> and <code>MinCostFlow</code>. Or the interface of <code>MinCostFlow</code> could be extended to support min cost max flow. See also <a class="assigned ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/244" title="#244: enhancement: Support min. cost max. flow in MCF classes (assigned)">#244</a>.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/180" title="#180: task: Port the remaining min. cost flow algorithms (closed: done)">#180</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/328#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/329
http://lemon.cs.elte.hu/trac/lemon/ticket/329#329: Sort outgoing arcs in the build() function of StaticDigraphFri, 13 Nov 2009 09:40:32 GMTPeter Kovacs<p>
In the <code>build()</code> function of <code>StaticDigraph</code> which takes another digraph as an argument, the outgoing arcs of each node are sorted
with respect to their target nodes.
</p>
<p>
It clearly makes the <code>build()</code> function (and copying a graph to <code>StaticDigraph</code>) somewhat slower. Preliminary tests showed a difference of about 15 percent. On the other hand, it could make the usage of the constructed graph more efficient due to better caching. However, the trade-off is not clear.
</p>
<p>
I suggest to make this sorting optional (e.g. by adding a bool parameter to the <code>build()</code> function). However, the default option is of high importance here, since it will be used by <code>DigraphCopy</code>.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/68" title="#68: task: Port static graph implementation (closed: done)">#68</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/329#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/345
http://lemon.cs.elte.hu/trac/lemon/ticket/345#345: Obtaining and storing the LP solutionFri, 19 Feb 2010 11:48:59 GMTPeter Kovacs<p>
It would be nice if the LP and MIP solver interfaces provided functions for obtaining the LP solution at once. We could use a class that can store the solution efficiently, i.e. it should store variable-value pairs for the non-zero valued variables.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/326" title="#326: enhancement: MipSolver interface fixes and extension (closed: fixed)">#326</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/345#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/351
http://lemon.cs.elte.hu/trac/lemon/ticket/351#351: Port the LP utilitiesSun, 28 Feb 2010 23:07:03 GMTPeter Kovacs<p>
Revise and port the Lp utilities from SVN, namely
</p>
<ul><li><code>lp_utils.h</code>
</li><li><code>lp_utils.cc</code>
</li></ul>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/351#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/352
http://lemon.cs.elte.hu/trac/lemon/ticket/352#352: Tolerance in GomoryHuTue, 02 Mar 2010 09:07:56 GMTPeter Kovacs<p>
For <code>GomoryHu</code> class, <code>Tolerance</code> type/object cannot be set, but it could be useful. The tolerance could be passed to the Preflow instances used by the algorithm.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/306" title="#306: task: Tolerance in min cut algorithms (closed: fixed)">#306</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/352#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/361
http://lemon.cs.elte.hu/trac/lemon/ticket/361#361: Tolerance support in BellmanFordThu, 18 Mar 2010 00:31:54 GMTPeter Kovacs<p>
BellmanFord (and maybe Dijkstra as well) could construct and store an instance of the operation traits class and use the operation traits functionalities through this object. This makes it possible to have such op. traits objects that can hold an <em>epsilon</em> value or a tolerance instance. It would also be important to have set/get functions for this instance in the algorithm class(es).
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/51" title="#51: task: Port the remaining shortest path algorithms (closed: done)">#51</a> and <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/360" title="#360: defect: VS compilation error (closed: fixed)">#360</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/361#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/373
http://lemon.cs.elte.hu/trac/lemon/ticket/373#373: Compile time assertionTue, 29 Jun 2010 14:06:30 GMTPeter Kovacs<p>
Compile time assertion would be useful in some cases (instead of LEMON_ASSERT).
</p>
<p>
A possible solution is the following:
</p>
<div class="wiki-code"><div class="code"><pre>template <bool> struct STATIC_ASSERT_FAILURE;
template <> struct STATIC_ASSERT_FAILURE<true> {};
template<int x> struct static_assert_test{};
#define LEMON_COMPILE_ASSERT(x) \
typedef static_assert_test<\
sizeof(STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
_static_assert_typedef_
</pre></div></div><p>
It could be used like that:
</p>
<pre class="wiki">LEMON_COMPILE_ASSERT(numeric_limits<T>::is_integer);
</pre>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/373#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/374
http://lemon.cs.elte.hu/trac/lemon/ticket/374#374: Functions for weakly connected componentsTue, 29 Jun 2010 14:17:46 GMTPeter Kovacs<p>
I suggest to have the following functions:
</p>
<div class="wiki-code"><div class="code"><pre>bool weaklyConnected (const Digraph &graph);
int countWeaklyConnectedComponents (const Digraph &graph);
int weaklyConnectedComponents (const Digraph &graph, NodeMap &compMap);
</pre></div></div><p>
which would work the same way as <code>connected()</code>, <code>countConnectedComponents()</code> and <code>connectedComponents()</code> for the undirected version of the digraph.
</p>
<p>
These proposed functions could be implemented easily using the <code>Undirector</code> adaptor and the undirected connectivity tools.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/374#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/376
http://lemon.cs.elte.hu/trac/lemon/ticket/376#376: A star (A*) algorithmFri, 02 Jul 2010 17:28:11 GMTPeter Kovacs<p>
It would be nice to have an A-star (A*) algorithm implementation in LEMON. Additionally, a bidirectional version could also be implemented (see also: <a class="assigned ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/249" title="#249: enhancement: Bidirectional Bfs and Dijkstra (assigned)">#249</a>).
</p>
<p>
<a class="ext-link" href="http://en.wikipedia.org/wiki/A*_search_algorithm"><span class="icon"></span>http://en.wikipedia.org/wiki/A*_search_algorithm</a>
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/376#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/378
http://lemon.cs.elte.hu/trac/lemon/ticket/378#378: Transitive closureFri, 02 Jul 2010 21:09:37 GMTPeter Kovacs<p>
It would be nice to have a tool that generates the transitive closure of an input graph to another graph (similarly to <code>digraphCopy()</code>).
</p>
<p>
There are efficient solution methods based on the computation of the strongly connected components and their topological order.
</p>
<p>
For more details see:<br />
<a class="ext-link" href="http://www.cs.hut.fi/~enu/thesis.html"><span class="icon"></span>http://www.cs.hut.fi/~enu/thesis.html</a>
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/378#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/379
http://lemon.cs.elte.hu/trac/lemon/ticket/379#379: Find odd cyclesFri, 02 Jul 2010 21:58:23 GMTPeter Kovacs<p>
We could extend the functions <code>bipartite()</code> and <code>bipartitePartitions()</code> so that they could return an odd cycle if the given graph is not bipartite.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/379#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/381
http://lemon.cs.elte.hu/trac/lemon/ticket/381#381: Simplified heaps without priority updateWed, 21 Jul 2010 15:41:14 GMTPeter Kovacs<p>
The existing heap implementations in LEMON cointain an Item->int map to indicate the current location of each item. It is required to implement <code>increase()</code>, <code>decrease()</code>, <code>erase()</code>, etc. functions.
However, simplified heaps could be implemented with a limited functionality (<code>push()</code>, <code>pop()</code>, <code>top()</code>, <code>prio()</code>, <code>size()</code>, <code>empty()</code>, <code>clear()</code>, etc.) without this cross reference map. For such heaps, the basic <code>push()</code> and <code>pop()</code> operations could be implemented more efficiently, but the duplications of items could not be avoided.
</p>
<p>
A Dijkstra or Prim algorithm could be implemented with such heaps, but it would require slight modifications. A node should be pushed each time its distance label is updated (i.e. more than once in some cases), and the duplicate nodes should be skipped after each <code>pop()</code> operation.
</p>
<p>
It would be nice to introduce such implementations in LEMON. I think, they would lead to better performance in many practical cases, because not too many duplications would be expected on typical graphs. However, there are some problems with this proposal. First, such heaps would not conform to the current heap concept. Second, using them would require different implementation of the algorithms.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/381#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/384
http://lemon.cs.elte.hu/trac/lemon/ticket/384#384: Adaptor class for complementary graphSat, 31 Jul 2010 21:12:35 GMTPeter Kovacs<p>
It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/384#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/385
http://lemon.cs.elte.hu/trac/lemon/ticket/385#385: QuadHeap instead of BinHeap in DijkstraSat, 31 Jul 2010 21:33:32 GMTPeter Kovacs<p>
It is questionable whether <code>Dijkstra</code> should use <code>QuadHeap</code> instead of <code>BinHeap</code> by default.
</p>
<p>
In theory, a fourary heap is at least as efficient as a binary heap independently of the actual use case. I made some benchmark tests in which <code>QuadHeap</code> turned out to be typically faster than <code>BinHeap</code>, especially when many <code>decrease()</code> operations are performed. See the benchmark results <a class="attachment" href="http://lemon.cs.elte.hu/trac/lemon/attachment/ticket/313/heap_benchmark_results.txt" title="Attachment 'heap_benchmark_results.txt' in Ticket #313">here</a><a class="trac-rawlink" href="http://lemon.cs.elte.hu/trac/lemon/raw-attachment/ticket/313/heap_benchmark_results.txt" title="Download"></a>. However, binary heap is the "standard" choice.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/385#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/407
http://lemon.cs.elte.hu/trac/lemon/ticket/407#407: Extend random_test.ccSun, 09 Jan 2011 16:00:54 GMTPeter Kovacs<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/101" title="#101: enhancement: Extend test cases for various tools (closed: done)">#101</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/407#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/409
http://lemon.cs.elte.hu/trac/lemon/ticket/409#409: Extend unionfind_test.ccSun, 09 Jan 2011 16:04:18 GMTPeter Kovacs<p>
The following classes should be tested:
</p>
<ul><li><code>UnionFind</code>
</li><li><code>ExtendFindEnum</code>
</li><li><code>HeapUnionFind</code>
</li></ul><p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/101" title="#101: enhancement: Extend test cases for various tools (closed: done)">#101</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/409#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/412
http://lemon.cs.elte.hu/trac/lemon/ticket/412#412: Implement Dinitz algorithm for the max flow problemSun, 09 Jan 2011 16:30:53 GMTPeter Kovacs<p>
It would be nice to implement the "original" Dinitz algorithm for the max flow problem.
</p>
<p>
We have an implementation that uses dynamic trees, but it would be better to have a separate implementation without dynamic trees, as well.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/412#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/413
http://lemon.cs.elte.hu/trac/lemon/ticket/413#413: Implement Young-Tarjan-Orlin algorithm for min mean cycleSun, 09 Jan 2011 16:37:01 GMTPeter Kovacs<p>
It would be nice to implement the Young-Tarjan-Orlin algorithm for the minimum mean cycle problem.
</p>
<p>
According to several survey papers, it is one of the fastest solution methods for this problem (and its extension: the optimum cycle ratio problem). Another method that is highly efficient is Howard's algorithm, which is already implemented in LEMON.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/413#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/415
http://lemon.cs.elte.hu/trac/lemon/ticket/415#415: Custom cost types in NetworkSimplexMon, 28 Feb 2011 15:29:05 GMTPeter Kovacs<p>
Duraid Madina proposed an enhancement for <code>NetworkSimplex</code>:
</p>
<pre class="wiki"> I have been using Lemon's network-simplex code for some time.
Recently I wanted to use it with a custom Cost type and int Value type.
In order to make this simpler, I have patched network_simplex.h
so that the Cost class/type does not need/use operator*.
At the moment, my patch requires that a custom Cost class must
still implement operator* for (Cost, int) pairs. However, this is only
for the initialization of ART_COST, and for totalCost(). It is also
possible to eliminate these uses of operator*, but I have not needed
to make these changes.
The patch consists of three things:
1) the addition of a unitMul() function for multiplying Costs by
"unit values" -1, 0 and 1
2) changing all occurences of Cost*unit value multipication to
calls to unitMul()
3) a small change to totalCost() allowing exact total costs to
be computed (requires the custom Cost class to provide Cost*Value
multiplication, but not Cost*Cost multiplication.)
There is one potential problem with the patch. On x86 machines
and "int" Cost type, there is a speed penalty of about 15%. This can be
eliminated through template specialization of the unitMul function for
"int" Costs, but I have not done this for two reasons:
1) It would be great if you could do it in your preferred "LEMON
style"
2) On some machines, such as ia64 (Itanium), the unitMul in the
attached patch actually leads to a speed _gain_ of about 10%. The
reason is that there does not seem to be any compiler which can
detect that the "*" can be replaced by predicated/conditional clears
and negations.
So rather than constant tempate specialization, perhaps
the choice of unitMul() implementation could be left to the user,
with a simple "*"-based implementation as default?
Anyway, I hope this patch makes sense and you consider it
for inclusion in your code. I would like to conclude by saying a
big "thank you!" for the excellent LEMON library!!
Yours sincerely,
Duraid MADINA
RIKEN
</pre>Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/415#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/123
http://lemon.cs.elte.hu/trac/lemon/ticket/123#123: dim2::Point default constructorMon, 14 Jul 2008 08:09:53 GMTPeter Kovacs<p>
I think the default constructor of <code>dim2::Point</code> should set the point (0,0). It is a natural request for any class that provides <code>operator+</code> to be able to sum it correctly with a template function.
</p>
<p>
I also made benchmark tests. They showed that this variant is not slower than the current one.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/123#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/151
http://lemon.cs.elte.hu/trac/lemon/ticket/151#151: Possible improvement in the function-type implementation of BFS/DFS/DijkstraWed, 24 Sep 2008 15:38:45 GMTPeter Kovacs<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/96" title="#96: enhancement: Revise function-type interface of BFS/DFS/Dijkstra (closed: fixed)">#96</a>.
</p>
<p>
Maybe it would be better if we could avoid using <code>NodeMap</code>s (instead of <code>NullMap</code>s) as <code>PredMap</code> and <code>DistMap</code> structures in the cases when they are not necessary. So the default type of these maps would be a <code>NullMap</code> in <code>Bfs/Dfs/DijkstraWizardDefaultTraits</code> classes, and it would be changed only if it is really needed (i.e. <code>path()</code> and/or <code>dist()</code> named parameter is used).
</p>
<p>
Balazs suggested a solution for this, saying: "iff at least one s-t path search is queried, real pred map should be defined, and iff at least one length of an s-t path queried, real dist map should be used. It could be done with the <code>ForkMap</code>s".
</p>
<p>
It is a benchmark question however, that this implementation would be more efficient or not in practice.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/151#changelog
http://lemon.cs.elte.hu/trac/lemon/ticket/338
http://lemon.cs.elte.hu/trac/lemon/ticket/338#338: Infinite capacities in PreflowTue, 09 Feb 2010 22:28:34 GMTPeter Kovacs<p>
Infinite (or very high) capacities typically cause problems in <code>Preflow</code>, since the algorithm usually saturate arcs.
</p>
<p>
This problem could be overcome by finding a finite cut and replace the huge capacities on the outgoing arcs of the source node with the value of the found cut if such a cut exists. Otherwise the max. flow value is infinite.
</p>
<p>
This solution could be implemented in the <code>Preflow</code> class itself or rather in a separate wrapper class (it should be used in the DIMACS solver utility, as well).
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/319" title="#319: enhancement: Infinite capacities in Preflow (closed: done)">#319</a>.
</p>
Resultshttp://lemon.cs.elte.hu/trac/lemon/ticket/338#changelog