LEMON: {3} Active Tickets by Milestone
http://lemon.cs.elte.hu/trac/lemon/report/3
Trac Report - en-usLEMONhttp://lemon.cs.elte.hu/trac/lemon/chrome/site/lemon-logo.gif
http://lemon.cs.elte.hu/trac/lemon/report/3
Trac v1.0.1#376: A star (A*) algorithmFri, 09 Dec 2011 16:17:01 GMTFri, 02 Jul 2010 17:28:11 GMT<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="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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/376
http://lemon.cs.elte.hu/trac/lemon/ticket/376Report#384: Adaptor class for complementary graphFri, 15 Jul 2016 11:50:18 GMTSat, 31 Jul 2010 21:12:35 GMT<p>
It would be nice to have an adaptor class to obtain the complementary graph of a simple, undirected graph.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/384
http://lemon.cs.elte.hu/trac/lemon/ticket/384Report#394: Add supprt for lp_solveFri, 15 Jul 2016 11:52:55 GMTThu, 07 Oct 2010 05:21:21 GMT<p>
<a class="ext-link" href="http://lpsolve.sourceforge.net/5.5/"><span class="icon"></span>http://lpsolve.sourceforge.net/5.5/</a>
</p>
<p>
<a class="ext-link" href="http://sourceforge.net/projects/lpsolve/"><span class="icon"></span>http://sourceforge.net/projects/lpsolve/</a>
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/394
http://lemon.cs.elte.hu/trac/lemon/ticket/394Report#189: Add the functionality of ItemSetTraits to the graphsWed, 04 Nov 2009 18:28:10 GMTSun, 30 Nov 2008 21:25:17 GMT<p>
Maybe we could introduce the functionality of <tt>ItemSetTraits</tt> to the graph concepts and to the adaptors in order to have the followings for all graph types.
</p>
<ul><li><tt>Graph::Map<T, Value></tt>
</li><li><tt>Graph::It<T></tt> or <tt>Graph::ItemIt<T></tt>
</li></ul><p>
Where <tt>T</tt> can be <tt>Node</tt>, <tt>Arc</tt> or <tt>Edge</tt>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/189
http://lemon.cs.elte.hu/trac/lemon/ticket/189Report#78: Added functionality to graphToEps().Fri, 21 Nov 2008 15:00:35 GMTThu, 03 Apr 2008 15:36:35 GMT<p>
It would be nice to enable multiline copyright notices in <tt>GraphToEps::copyright()</tt>
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/78
http://lemon.cs.elte.hu/trac/lemon/ticket/78Report#77: Added functionality to nodePsTexts() named param. of graphToEps().Fri, 21 Nov 2008 15:00:25 GMTThu, 03 Apr 2008 15:33:20 GMT<p>
When a pure postscript block is inserted as each node with nodePsTexts(), it would be nice to offer the choice not to move to the center but pass the coordinates to the Postscript block inserted.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/77
http://lemon.cs.elte.hu/trac/lemon/ticket/77Report#425: API for giving back the state of RandomFri, 15 Jul 2016 11:57:05 GMTFri, 15 Jul 2011 15:36:26 GMT<p>
In some cases, it would be nice if we could query the state (i.e. the current seed) of Random in a format that is savable to a text file and retrievable later.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/425
http://lemon.cs.elte.hu/trac/lemon/ticket/425Report#191: Benchmark questions related to PreflowThu, 05 Nov 2009 10:09:40 GMTSun, 30 Nov 2008 21:43:09 GMT<p>
There are some efficiency questions about the <tt>Preflow</tt> implementation, that require thorough benchmarking.
</p>
<ul><li><tt>Elevator</tt> or <tt>LinkedElevator</tt> should be used by default?
</li><li>The BFS implementation in the <tt>init()</tt> function could be made more efficient using only one vector and three indices (<tt>first</tt>, <tt>last</tt>, <tt>new_level</tt>).
</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>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/191
http://lemon.cs.elte.hu/trac/lemon/ticket/191Report#33: BenchmarkingFri, 02 Aug 2013 12:33:35 GMTThu, 20 Mar 2008 10:51:41 GMT<p>
Lemon seriously needs a benchmarking environment to test
</p>
<ul><li>the effect of implementation changes on the running time
</li><li>performance of different compilers ans optimization settings
</li></ul><p>
This environment should contain
</p>
<ul><li>scripts for automated testing.
</li><li>carefully chosen set test files and graph generators.
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/33
http://lemon.cs.elte.hu/trac/lemon/ticket/33Report#421: Better DAG test and topological ordering implementationMon, 04 Mar 2013 16:55:55 GMTFri, 13 May 2011 17:16:52 GMT<p>
Currently all these functions use Dfs with a custom visitor. I have a feeling that a direct algorithm might be faster and/or more memory efficient. The algorithm I propose is the following:
</p>
<ul><li>Compute the in-degree of all nodes and store them in a <tt>NodeMap</tt> <tt>deg</tt>.
</li><li>Put all node <tt>n</tt> with <tt>deg[n]==0</tt> into a queue (or a stack) <tt>q</tt>.
</li><li>While <tt>q</tt> is not empty:
<ul><li>Get a node <tt>n</tt> from <tt>g</tt>. This is the next node in the topological order.
</li><li>For each out-arc <tt>a</tt> of <tt>n</tt>:
<ul><li>Decrease <tt>deg[target(a)]</tt> by 1
</li><li>If <tt>deg[target(a)]==0</tt> then put <tt>target(a)</tt> into <tt>q</tt>
</li></ul></li></ul></li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/421
http://lemon.cs.elte.hu/trac/lemon/ticket/421Report#249: Bidirectional Bfs and DijkstraFri, 09 Dec 2011 16:15:47 GMTFri, 27 Mar 2009 16:19:17 GMT<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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/249
http://lemon.cs.elte.hu/trac/lemon/ticket/249Report#225: Binary graph file formatFri, 15 Jul 2016 11:31:16 GMTWed, 18 Feb 2009 06:52:21 GMT<p>
The <tt>.lgf</tt> format is nice, but the files become extremely large for big graphs.
</p>
<p>
In some cases it would be nice to have a version of <tt>GraphReader</tt>/<tt>GraphWriter</tt> using a much more condensed binary format while providing close to the same API and feature set.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/225
http://lemon.cs.elte.hu/trac/lemon/ticket/225Report#375: Both lower and upper supply bounds in Network simplexFri, 01 Mar 2013 19:00:09 GMTThu, 01 Jul 2010 05:15:34 GMT<p>
The idea is to extend Network Simplex so that the form of the problems are fully compatible with the one used by the LP solvers i.e.
</p>
<pre class="wiki">m_l<=Ax<=m_u
l<=x<=u
</pre>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/375
http://lemon.cs.elte.hu/trac/lemon/ticket/375Report#310: Bounding box for Bezier-curvesTue, 18 Aug 2009 19:15:53 GMTTue, 18 Aug 2009 19:15:53 GMT<p>
The patch <a class="missing changeset" title="No changeset 1121710e18c9 in the repository">[1121710e18c9]</a> contains functions for bounding box computation of Bezier-curves.
</p>
deba
http://lemon.cs.elte.hu/trac/lemon/ticket/310
http://lemon.cs.elte.hu/trac/lemon/ticket/310Report#344: Cairo based version of graphToEps()Wed, 17 Feb 2010 06:05:45 GMTWed, 17 Feb 2010 06:05:45 GMT<p>
Currently graphToEps() directly generates its output .eps file. This is good because we do not depend on any third party library.
</p>
<p>
However using the cairo rendering backend would have a couple of advantages, most importantly it could directly create graphics in other formats like PDF, PNG (pixel graphics format) or SVG (editable vector graphics format). It would also allow easy integration to a GUI.
</p>
<p>
This enhancement could also be incorporated with <a class="assigned ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/86" title="enhancement: Virtualmap based graphToEps(). (assigned)">#86</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/344
http://lemon.cs.elte.hu/trac/lemon/ticket/344Report#365: Cannot include <lemon/adaptors.h> in any of my application source filesWed, 07 Aug 2013 14:29:46 GMTSun, 04 Apr 2010 05:12:15 GMT<p>
I am using the Gnu 4.4 compiler under MinGW with Codeblocks on Windows to build a large application. I cannot include <lemon/adaptors.h> or <lemon/connectivity.h> in my application without getting a stream of error messages I cannot figure out. My application must use these included file. I have placed error messages below.
</p>
<p>
Thanks for any help you can provide.
</p>
<pre class="wiki">C:\usr\include\lemon\adaptors.h|3459|error: expected nested-name-specifier before 'Value'|
C:\usr\include\lemon\adaptors.h|3459|error: expected ';' before 'Value'|
C:\usr\include\lemon\adaptors.h|3461|error: wrong number of template arguments (0, should be 2)|
C:\usr\include\lemon\bits\traits.h|155|error: provided for 'template<class Map, class Enable> struct lemon::MapTraits'|
C:\usr\include\lemon\adaptors.h|3462|error: wrong number of template arguments (0, should be 2)|
C:\usr\include\lemon\bits\traits.h|155|error: provided for 'template<class Map, class Enable> struct lemon::MapTraits'|
C:\usr\include\lemon\adaptors.h|3463|error: wrong number of template arguments (0, should be 2)|
C:\usr\include\lemon\bits\traits.h|155|error: provided for 'template<class Map, class Enable> struct lemon::MapTraits'|
C:\usr\include\lemon\adaptors.h|3464|error: wrong number of template arguments (0, should be 2)|
C:\usr\include\lemon\bits\traits.h|155|error: provided for 'template<class Map, class Enable> struct lemon::MapTraits'|
C:\usr\include\lemon\adaptors.h|3465|error: wrong number of template arguments (0, should be 2)|
C:\usr\include\lemon\bits\traits.h|155|error: provided for 'template<class Map, class Enable> struct lemon::MapTraits'|
C:\usr\include\lemon\adaptors.h|3468|error: expected ')' before ',' token|
C:\usr\include\lemon\adaptors.h|3472|error: ISO C++ forbids declaration of 'Value' with no type|
C:\usr\include\lemon\adaptors.h|3472|error: expected ';' before 'operator'|
C:\A+MyPrograms\CombinatoricsCalculator\src\graphs\algorithms\GraphAlgorithmCanvas.cpp|698|error: expected ';' at end of input|
C:\A+MyPrograms\CombinatoricsCalculator\src\graphs\algorithms\GraphAlgorithmCanvas.cpp|698|error: expected '}' at end of input|
C:\A+MyPrograms\CombinatoricsCalculator\src\graphs\algorithms\GraphAlgorithmCanvas.cpp|698|error: expected unqualified-id at end of input|
C:\A+MyPrograms\CombinatoricsCalculator\src\graphs\algorithms\GraphAlgorithmCanvas.cpp|698|error: expected '}' at end of input|
C:\usr\include\lemon\adaptors.h|3443|error: expected unqualified-id at end of input|
C:\usr\include\lemon\adaptors.h|3443|error: expected '}' at end of input|
||=== Build finished: 21 errors, 0 warnings ===|
</pre>wford
http://lemon.cs.elte.hu/trac/lemon/ticket/365
http://lemon.cs.elte.hu/trac/lemon/ticket/365Report#146: Cheap copy of maps (reference counting) PHASE II.Fri, 15 Jul 2016 11:22:32 GMTWed, 17 Sep 2008 14:06:45 GMT<p>
This is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/137" title="enhancement: Cheap copy of maps (reference counting) PHASE I. (closed: fixed)">#137</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/146
http://lemon.cs.elte.hu/trac/lemon/ticket/146Report#292: Checker functions for min cost flowFri, 15 Jul 2016 11:37:17 GMTTue, 12 May 2009 10:50:33 GMT<p>
Maybe we could have checker functions for the minimum cost flow algorithms according to the test file. E.g. <tt>checkFeasibility()</tt> and <tt>checkOptimality()</tt> or <tt>checkFlow()</tt> and <tt>checkPotential()</tt>.
They would be similar to the checker functions of <tt>Circulation</tt>.
</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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/292
http://lemon.cs.elte.hu/trac/lemon/ticket/292Report#227: Command line tool for executing various algorithmsFri, 15 Jul 2016 11:34:29 GMTWed, 18 Feb 2009 07:38:13 GMT<p>
This tool would read a .lgf file and run an algorithm on it. Finally it would report about the result or write the solution into a file. It should provide a wide range of algorithms which could be selected with command line options.
</p>
<p>
This is somewhat similar to that are proposed in <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/226" title="enhancement: DIMACS file solver (closed: fixed)">#226</a>, but I think they should be separate tools, as that one have a quite limited feature set, while this one will probably become a complex tool with tons of option with the time.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/227
http://lemon.cs.elte.hu/trac/lemon/ticket/227Report#373: Compile time assertionFri, 15 Jul 2016 11:43:33 GMTTue, 29 Jun 2010 14:06:30 GMT<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="code"><pre><span class="k">template</span> <span class="o"><</span><span class="kt">bool</span><span class="o">></span> <span class="k">struct</span> STATIC_ASSERT_FAILURE<span class="p">;</span>
<span class="k">template</span> <span class="o"><></span> <span class="k">struct</span> STATIC_ASSERT_FAILURE<span class="o"><</span><span class="nb">true</span><span class="o">></span> <span class="p">{};</span>
<span class="k">template</span><span class="o"><</span><span class="kt">int</span> x<span class="o">></span> <span class="k">struct</span> static_assert_test<span class="p">{};</span>
<span class="cp">#define LEMON_COMPILE_ASSERT(x) \
typedef static_assert_test<\
sizeof(STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
_static_assert_typedef_
</span></pre></div><p>
It could be used like that:
</p>
<pre class="wiki">LEMON_COMPILE_ASSERT(numeric_limits<T>::is_integer);
</pre>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/373
http://lemon.cs.elte.hu/trac/lemon/ticket/373Report#105: Consider using the "ziggurat" method in Random::gauss().Tue, 16 Nov 2010 09:02:28 GMTMon, 30 Jun 2008 11:55:05 GMT<p>
Currently, <a class="missing source">Random::gauss()</a> uses a Box-Muller transformation based method. Ziggurat method is reported to be a better way of generating normally distributed random numbers, though one should check if it is indeed noticeably better in practice.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/105
http://lemon.cs.elte.hu/trac/lemon/ticket/105Report#427: Create build() routine for StaticDigraph that allows # of arcs to be set explicitlyFri, 01 Mar 2013 19:00:09 GMTSun, 25 Sep 2011 03:23:52 GMT<p>
Hello,
</p>
<p>
I recently tried used <a class="missing wiki">StaticDigraph?</a> with an iterator that used a forward-only traversal concept, as it was a thin wrapper to some rather complicated underlying structures. The problem is that the std::distance() call cause the iterator to run through the entire set to get the number of arcs, even though this was something I knew beforehand. Rather than create some sort of clumsy workaround, I found it easy to add another version of build() that permitted one to pass in the number of arcs explicitly. It's possible that mine is a rare case, but in case people are interested, here is a patch that does this. It's complete with appropriate documentation changes.
</p>
hoytak
http://lemon.cs.elte.hu/trac/lemon/ticket/427
http://lemon.cs.elte.hu/trac/lemon/ticket/427Report#415: Custom cost types in NetworkSimplexThu, 07 Mar 2013 08:04:13 GMTMon, 28 Feb 2011 15:29:05 GMT<p>
Duraid Madina proposed an enhancement for <tt>NetworkSimplex</tt>:
</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>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/415
http://lemon.cs.elte.hu/trac/lemon/ticket/415Report#247: DegMapWed, 04 Nov 2009 18:31:01 GMTFri, 27 Mar 2009 15:45:57 GMT<p>
There are <tt>InDegMap</tt> and <tt>OutDegMap</tt> classes for directed graphs. So it would be nice to have a <tt>DegMap</tt> class for undirected graphs. I see that both <tt>InDegMap</tt> and <tt>OutDegMap</tt> can be used for this purpose, but it would be better to have <tt>DegMap</tt> even if it is just an alias for one of these maps.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/247
http://lemon.cs.elte.hu/trac/lemon/ticket/247Report#201: Delaunay triangulationSun, 12 Oct 2014 15:22:03 GMTTue, 13 Jan 2009 11:13:23 GMT<p>
Delunay triangulation is actually implemented in <tt>tools/lgf-gen.cc</tt>, but it would be nice to have it as a separate tool in the core library.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/201
http://lemon.cs.elte.hu/trac/lemon/ticket/201Report#475: DigraphWriter<> always saves Arc labelMon, 12 Sep 2016 12:49:51 GMTTue, 10 Sep 2013 08:32:55 GMT<p>
The <tt>DigraphWriter</tt> class always saves an <tt>label</tt> map in the <tt>@arcs</tt> section, even if it is not given explicitly not Arcs are saved in the <tt>@attributes</tt> section. I think it is unnecessary to save an auto generated label map in this case.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/475
http://lemon.cs.elte.hu/trac/lemon/ticket/475Report#123: dim2::Point default constructorWed, 04 Nov 2009 18:46:29 GMTMon, 14 Jul 2008 08:09:53 GMT<p>
I think the default constructor of <tt>dim2::Point</tt> should set the point (0,0). It is a natural request for any class that provides <tt>operator+</tt> 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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/123
http://lemon.cs.elte.hu/trac/lemon/ticket/123Report#318: Document MapIt, ConstMapIt and ItemIt classes of standard mapsThu, 07 Mar 2013 09:44:01 GMTTue, 06 Oct 2009 06:09:40 GMT<p>
There are three iterator classes: <tt>MapIt</tt>, <tt>ConstMapIt</tt> and <tt>ItemIt</tt> 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="defect: Improvements for graphs (closed: fixed)">#311</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/318
http://lemon.cs.elte.hu/trac/lemon/ticket/318Report#94: Easy erase in list graphsTue, 13 Oct 2009 10:55:30 GMTThu, 22 May 2008 18:25:57 GMT<p>
The arcs and nodes might be able to erase during an iteration very easy way in the list and smart graph implementations. If an iterator points to an arc or a node, and the item is deleted, then the increment should be valid operation until other change occurred on the graph. Of course, accessing such iterator should be avoided.
</p>
deba
http://lemon.cs.elte.hu/trac/lemon/ticket/94
http://lemon.cs.elte.hu/trac/lemon/ticket/94Report#370: Edge coloring algorithmsFri, 02 Aug 2013 12:29:22 GMTSun, 23 May 2010 04:33:16 GMT<p>
Hello,
</p>
<p>
for a project I am working on I had to implement a couple of edge
coloring algorithms. If there is any interest I could LEMON-ify them.
</p>
<p>
A valid edge coloring is a coloring of the edges so that each node has
no two incident edges colored in the same way.
</p>
<p>
What is implemented is:
</p>
<ul><li>An edge map to store valid colorings and that supports the queries
</li></ul><p>
needed by the algorithms in a fast way.
</p>
<ul><li>An algorithm that colors bipartite graphs using at most as many colors
</li></ul><p>
as the maximum node degree.
</p>
<ul><li>Vizing's algorithm to color general simple graphs using at most as
</li></ul><p>
many colors as the maximum node degree + 1.
</p>
<ul><li>Test cases
</li></ul><p>
Both algorithms are in O(m*n)
</p>
<p>
For general simple graphs it is not always possible to color them using
only maximum node degree. An example is K_3. Determining if this is
possible is NP-hard so Vizing's algorithm seems to be the best you can
get within polynomial time.
</p>
<p>
I've attached my code.
</p>
<p>
Best regards,
Ben Strasser
</p>
Ben Strasser
http://lemon.cs.elte.hu/trac/lemon/ticket/370
http://lemon.cs.elte.hu/trac/lemon/ticket/370Report#426: Expose CBC/CPL original interface in CbcMip and ClpLpTue, 19 Sep 2017 13:32:27 GMTMon, 15 Aug 2011 04:54:27 GMT<p>
Something like <a href="http://lemon.cs.elte.hu/pub/doc/1.2.2/a00148.html">GlpkBase::lpx*</a> would be a satisfactory solution.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/426
http://lemon.cs.elte.hu/trac/lemon/ticket/426Report#407: Extend random_test.ccFri, 15 Jul 2016 11:55:36 GMTSun, 09 Jan 2011 16:00:54 GMT<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/101" title="enhancement: Extend test cases for various tools (closed: done)">#101</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/407
http://lemon.cs.elte.hu/trac/lemon/ticket/407Report#409: Extend unionfind_test.ccFri, 15 Jul 2016 11:55:50 GMTSun, 09 Jan 2011 16:04:18 GMT<p>
The following classes should be tested:
</p>
<ul><li><tt>UnionFind</tt>
</li><li><tt>ExtendFindEnum</tt>
</li><li><tt>HeapUnionFind</tt>
</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="enhancement: Extend test cases for various tools (closed: done)">#101</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/409
http://lemon.cs.elte.hu/trac/lemon/ticket/409Report#462: Extended run time checking in debug modeSat, 26 Oct 2013 18:47:31 GMTFri, 10 May 2013 08:17:23 GMT<p>
When using more graph instances of the same time (e.g. <tt>ListDigraph</tt>) in a code, it is a very common error that a <tt>Node</tt> or <tt>Arc</tt> is used with a different graph that they actually belong to. For example a <tt>NodeMap</tt> may be indexed by a node belonging to another graph. These kind of errors remain hidden during the compilation.
</p>
<p>
I propose adding a pointer to the owner graph to each <tt>Node</tt> and <tt>Arc</tt> objects, and check their the validity of the relevant graph and map operations. This feature would be turned on <em>in debug mode only</em>.
</p>
<p>
Two things are worth checking:
</p>
<ul><li>The item should belong to the corresponding graph
</li><li>The item should be valid (i.e. not <tt>INVALID</tt> and point to an existing item)
</li></ul><p>
Here is a --- maybe incomplete --- list where checking could be made:
</p>
<ul><li><tt>source()</tt>, <tt>target()</tt>, <tt>u()</tt>, <tt>v()</tt>, <tt>runningNode()</tt>, <tt>baseNode()</tt>
</li><li><tt>id()</tt>
</li><li>constructors of the iterators
</li><li><tt>operator++()</tt> of the iterators (validity check only)
</li><li><tt>*Map<>::operator[]()'</tt>, <tt>*Map<>::set()'</tt>,
</li><li><tt>changeSource()</tt>, <tt>changeTarget()</tt>, <tt>reverse()</tt>
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/462
http://lemon.cs.elte.hu/trac/lemon/ticket/462Report#466: Extended std::vector<>Fri, 15 Jul 2016 12:03:18 GMTMon, 27 May 2013 07:28:12 GMT<p>
Based upon the idea of <a class="new ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/462" title="enhancement: Extended run time checking in debug mode (new)">#462</a>.
</p>
<p>
We could implement a wrapper around <tt>std::vector<></tt> with the following two extra features.
</p>
<ul><li>A extra permanent iterator. It has the same functionality as <tt>std::vector::iterator</tt> but remains valid even when the vector is extended by new elements. Technically, it contains a pointer to the base vector plus an index.
</li><li>An <tt>index</tt> type. In non-debug mode it is just a <tt>size_t</tt>, but in debug mode it also contains a pointer to the vector it indexes, thus <tt>operator[]()</tt> is able to check if the index indexes the right vector (and also if it is in the actual range).
</li></ul><p>
Both would be safer alternatives to referencing <tt>std::vector<></tt>'s elements by integer indices.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/466
http://lemon.cs.elte.hu/trac/lemon/ticket/466Report#250: Extensions for the interface of pathsFri, 23 Mar 2018 15:06:13 GMTFri, 27 Mar 2009 16:33:36 GMT<ol><li>Path structures have a function <tt>nth(int n)</tt> for getting the <em>n</em> th arc of the path. I suggest <tt>operator[]</tt> as an alias for this function.
</li></ol><ol start="2"><li><del>It would be nice to have <tt>source()</tt> and <tt>target()</tt> functions for paths. But it raise questions.</del>
<ul><li><del>Is it necessary that all the arcs in a path are directed in the same direction? Or we could store oppositely directed arc in a path as well? How should we define the source/target? Would the source node be equal to <tt>gr.source(path.front())</tt> and the target to <tt>gr.target(path.back())</tt>?</del>
</li><li><del>Should paths store source and target nodes explicitly? It would make it possible to handle paths of zero length (with a specified starting node).</del>
</li></ul></li></ol>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/250
http://lemon.cs.elte.hu/trac/lemon/ticket/250Report#300: Faster building of heapsWed, 04 Nov 2009 18:28:31 GMTWed, 08 Jul 2009 16:09:49 GMT<p>
For some heap structures it is possible to build them from an existing list of <tt>n</tt> items faster than calling <tt>push()</tt> <tt>n</tt> times.
E.g. for binary heap calling <tt>push()</tt> for each item takes <tt>O(n log n)</tt> time, while a heap can be built in <tt>O(n)</tt> time.
</p>
<p>
It would be nice to indroduce <tt>build()</tt> (or something like that) member functions into those heap structures, for which it could be done faster than calling <tt>push()</tt> <tt>n</tt> 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 <tt>push()</tt>, 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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/300
http://lemon.cs.elte.hu/trac/lemon/ticket/300Report#604: Faster MaxMatching implementationWed, 06 Jul 2016 15:12:29 GMTWed, 06 Jul 2016 11:26:18 GMT<p>
From Joran van Apeldoorn:
</p>
<blockquote class="citation">
<p>
On odd graphs it does not notice when a perfect matching (as in (n-1)/2 matched edges) is found and continues to do a BFS from the one unmatched vertex, off course without result.
This makes the running time for slightly dense graphs a lot longer on odd graphs then on even graphs, to the extend that it can take easely a 100 times longer on odd graphs.
</p>
</blockquote>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/604
http://lemon.cs.elte.hu/trac/lemon/ticket/604Report#379: Find odd cyclesFri, 02 Jul 2010 21:58:23 GMTFri, 02 Jul 2010 21:58:23 GMT<p>
We could extend the functions <tt>bipartite()</tt> and <tt>bipartitePartitions()</tt> so that they could return an odd cycle if the given graph is not bipartite.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/379
http://lemon.cs.elte.hu/trac/lemon/ticket/379Report#269: Function type interface for CirculationWed, 04 Nov 2009 18:30:25 GMTFri, 24 Apr 2009 14:49:56 GMT<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="task: Revise the interface of Circulation and Suurballe (closed: fixed)">#266</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/269
http://lemon.cs.elte.hu/trac/lemon/ticket/269Report#451: Functionality to test graph data structure consistencyFri, 15 Jul 2016 12:02:28 GMTTue, 25 Sep 2012 04:58:01 GMT<p>
The graph implementations (and other complex data structures, too) could provide a <tt>dsSelfCheck()</tt> member function, which thoroughly tests the inner consistency of the underlying data structures. This could help testing the correctness of the graph operations, thus preventing us from bugs like <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/450" title="defect: Serious bug in ListDigraph::erase(Node &) (closed: invalid)">#450</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/451
http://lemon.cs.elte.hu/trac/lemon/ticket/451Report#374: Functions for weakly connected componentsSat, 02 Mar 2013 17:07:15 GMTTue, 29 Jun 2010 14:17:46 GMT<p>
I suggest to have the following functions:
</p>
<div class="code"><pre><span class="kt">bool</span> <span class="nf">weaklyConnected</span> <span class="p">(</span><span class="k">const</span> Digraph <span class="o">&</span>graph<span class="p">);</span>
<span class="kt">int</span> <span class="nf">countWeaklyConnectedComponents</span> <span class="p">(</span><span class="k">const</span> Digraph <span class="o">&</span>graph<span class="p">);</span>
<span class="kt">int</span> <span class="nf">weaklyConnectedComponents</span> <span class="p">(</span><span class="k">const</span> Digraph <span class="o">&</span>graph<span class="p">,</span> NodeMap <span class="o">&</span>compMap<span class="p">);</span>
</pre></div><p>
which would work the same way as <tt>connected()</tt>, <tt>countConnectedComponents()</tt> and <tt>connectedComponents()</tt> for the undirected version of the digraph.
</p>
<p>
These proposed functions could be implemented easily using the <tt>Undirector</tt> adaptor and the undirected connectivity tools.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/374
http://lemon.cs.elte.hu/trac/lemon/ticket/374Report#297: Graph and map serializerFri, 15 Jul 2016 11:37:30 GMTWed, 10 Jun 2009 10:22:47 GMT<p>
For real distributed computing, it would be nice to have a <em>serializer</em> for the graphs and the map structures.
</p>
<p>
By a <em>serializer</em> I mean a facility to represent a graph/map as a compact raw sequence of bytes that can be sent to another (local or remote) process and the graph/map can be reconstructed from it.
</p>
<p>
The raw data format should be compact and easy to code and decode, however it cannot be independent from the underlying graph representation, as we must keep the node/arc IDs at the graph reconstruction.
</p>
<p>
This proposal is somewhat related to <a class="new ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/225" title="enhancement: Binary graph file format (new)">#225</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/297
http://lemon.cs.elte.hu/trac/lemon/ticket/297Report#8: GraphToEps() doesn't show loop egdesMon, 03 Nov 2008 17:16:46 GMTMon, 21 Jan 2008 12:35:54 GMT<p>
Although it would be nice.
</p>
<blockquote>
<p>
This ticket is a copy of report #27 of the old bug tracking system. It refers to svn trunk -r2561.
</p>
</blockquote>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/8
http://lemon.cs.elte.hu/trac/lemon/ticket/8Report#357: Guidelines for run/init/startMon, 12 Sep 2016 12:42:15 GMTMon, 15 Mar 2010 22:36:53 GMT<p>
Please add a few guidelines to the documentation about what are the invariants, pre and post conditions guaranteed by all algorithm objects and about the intended usage pattern. This includes documenting whenever:
</p>
<ul><li>The graph object and/or map objects must be fully constructed when the constructor of the algorithm object is run. (This is relevant if the graph and the algorithms objects are member of the same class, as may happen with algorithm objects that use a graph transformation based reduction.)
</li></ul><ul><li>At what point may the graph and the other algorithm parameters no longer be changed anymore without causing a crash or without invalidating the results. Calling start after changing the graph without rerunning init is allowed to crash. Changing the graph after start has completed should invalidate the results (or maybe not but in that case that behavior should be documented).
</li></ul><ul><li>Must the destructor of the algorithm object run before running the destructor of the graph object?
</li></ul>Ben
http://lemon.cs.elte.hu/trac/lemon/ticket/357
http://lemon.cs.elte.hu/trac/lemon/ticket/357Report#367: Gurobi backend for the LP interfaceFri, 16 Apr 2010 08:12:41 GMTFri, 16 Apr 2010 08:12:41 GMT<p>
<a class="ext-link" href="http://www.gurobi.com/"><span class="icon"></span>Gurobi Optimizer</a> focuses on parallel optimization and it is of increasing popularity. AFAK, it is freely available for academic purposes, thus it would be nice if LEMON supported it.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/367
http://lemon.cs.elte.hu/trac/lemon/ticket/367Report#328: Heuristic MinCostFlow and MinCostMaxFlowFri, 15 Jul 2016 11:38:43 GMTFri, 13 Nov 2009 00:23:26 GMT<p>
It could be worthwhile to create a heuristic min cost flow solver class named <tt>MinCostFlow</tt>. 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 <tt>MinCostMaxFlow</tt> using <tt>Preflow</tt> and <tt>MinCostFlow</tt>. Or the interface of <tt>MinCostFlow</tt> 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="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="task: Port the remaining min. cost flow algorithms (closed: done)">#180</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/328
http://lemon.cs.elte.hu/trac/lemon/ticket/328Report#220: Implement a Dual Network Simplex algorithmMon, 23 Mar 2009 22:27:17 GMTSat, 14 Feb 2009 06:29:16 GMT<p>
The title says everything.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/220
http://lemon.cs.elte.hu/trac/lemon/ticket/220Report#412: Implement Dinitz algorithm for the max flow problemWed, 11 Jan 2012 09:42:32 GMTSun, 09 Jan 2011 16:30:53 GMT<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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/412
http://lemon.cs.elte.hu/trac/lemon/ticket/412Report#413: Implement Young-Tarjan-Orlin algorithm for min mean cycleWed, 11 Jan 2012 09:43:26 GMTSun, 09 Jan 2011 16:37:01 GMT<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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/413
http://lemon.cs.elte.hu/trac/lemon/ticket/413Report#363: Implementing a planar graph typeThu, 20 Nov 2014 07:13:38 GMTFri, 19 Mar 2010 19:30:45 GMT<p>
My goal is to implement classes for planar graphs. The PlanarGraph class maintains a topology of nodes, edges and faces and provides algorithms that are characteristic to planar graphs. PlaneGraph extends this functionality with geometric properties, such as node coordinates and arc shapes.
</p>
gyorokp
http://lemon.cs.elte.hu/trac/lemon/ticket/363
http://lemon.cs.elte.hu/trac/lemon/ticket/363Report#183: Improve doc of ElevatorThu, 07 Mar 2013 09:44:17 GMTMon, 24 Nov 2008 10:22:17 GMT<p>
The documentation should describe the differences between <tt>Elevator</tt> and <tt>LinkedElevator</tt> and give some hints about their performance on specific tasks.
</p>
<p>
This is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/174" title="enhancement: Port the Elevator (closed: fixed)">#174</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/183
http://lemon.cs.elte.hu/trac/lemon/ticket/183Report#338: Infinite capacities in PreflowTue, 09 Feb 2010 22:28:34 GMTTue, 09 Feb 2010 22:28:34 GMT<p>
Infinite (or very high) capacities typically cause problems in <tt>Preflow</tt>, 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 <tt>Preflow</tt> 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="enhancement: Infinite capacities in Preflow (closed: done)">#319</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/338
http://lemon.cs.elte.hu/trac/lemon/ticket/338Report#284: LGF to EPS converter toolWed, 04 Nov 2009 18:29:44 GMTWed, 06 May 2009 08:33:32 GMT<p>
It would be nice to have a well configurable command line tool for converting LGF files into EPS.
</p>
<p>
Of course, it would be basically a command line wrapper around <tt>graph_to_eps()</tt>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/284
http://lemon.cs.elte.hu/trac/lemon/ticket/284Report#237: Line graph implementationsTue, 03 Mar 2009 12:29:46 GMTTue, 03 Mar 2009 12:29:46 GMT<p>
They can either be adaptors or just simple tools for creating the line graph of a given graph similarly to the graph copying tools.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/237
http://lemon.cs.elte.hu/trac/lemon/ticket/237Report#3: ListGraph should store/update the number of edges and nodesFri, 02 Aug 2013 12:34:26 GMTMon, 21 Jan 2008 12:10:42 GMT<p>
Counting the number of edges and nodes is a frequent graph operation. Now, it takes linear time to get these values. Instead we might store these values and update them at every edge/node addition and deletion.
</p>
<p>
Of course this change would slow down these operations a bit.
</p>
<blockquote>
<p>
This ticket is a copy of report #8 of the old bug tracking system. It refers to svn trunk -r2460.
</p>
</blockquote>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/3
http://lemon.cs.elte.hu/trac/lemon/ticket/3Report#402: Maps don't initialize subseqnetly added graph elements to the map-constructor's initial value.Mon, 12 Sep 2016 12:49:13 GMTMon, 06 Dec 2010 23:30:42 GMT<p>
Greetings all.
</p>
<p>
I'm experiencing a ( perceived ) problem with Maps. Maps "know" when new elements in a graph are added, and provide a default value. One of the two constructors for a map allows a user ( me ) to specify this default value. I expect that, all elements of a graph will receive that value upon map-construction, and I expect subsequent graph element additions to also take on that value. I observe that, all elements of a graph *do* receive the default value upon map-construction, but *do not* set my specified default-value when new elements are subsequently added to the graph.
</p>
<p>
I have a test program, which I will attach.
</p>
<p>
I also have a diff against lemon/bits/{array,vector}_map.h that attempt to remedy this situation, and hopefully reinforce my expected behaviour.
</p>
<p>
Please advise on if this is in fact a bit, or if it is intentional by design and my understanding is incorrect.
</p>
willo
http://lemon.cs.elte.hu/trac/lemon/ticket/402
http://lemon.cs.elte.hu/trac/lemon/ticket/402Report#216: Member in Circulation to transform the solution to a basic oneFri, 15 Jul 2016 11:28:42 GMTSat, 14 Feb 2009 06:17:27 GMT<p>
Having a basic solution for the circulation problem is sometime quite useful, e.g. it can be used as a staring solution of the primal Network Simplex algorithm.
</p>
<p>
The interface should also provide the tree (or forest) of the basis.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/216
http://lemon.cs.elte.hu/trac/lemon/ticket/216Report#238: Min cut iterators in PreflowFri, 15 Jul 2016 11:32:03 GMTWed, 04 Mar 2009 22:02:45 GMT<p>
It would be nice to have iterators for obtaining the min. cut in <tt>Preflow</tt> class. E.g. there could be <tt>MinCutNodeIt</tt> and <tt>MinCutArcIt</tt> similarly to the ones in <tt>GomoryHu</tt> class (but note that in <tt>Preflow</tt> we have directed cuts).
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/238
http://lemon.cs.elte.hu/trac/lemon/ticket/238Report#399: Missing getter and streaming operator for Node/Arc idFri, 15 Jul 2016 11:54:02 GMTWed, 17 Nov 2010 15:57:10 GMT<p>
please implement a getter and streaming operator for the id field of the Node and Arc class. This would be very helpful. Always have to use the graph class is very inconvenient and sometimes not even possible. thx
</p>
tobi_connect
http://lemon.cs.elte.hu/trac/lemon/ticket/399
http://lemon.cs.elte.hu/trac/lemon/ticket/399Report#251: More efficient graph copyingFri, 15 Jul 2016 11:34:46 GMTFri, 27 Mar 2009 16:44:14 GMT<p>
Is there any way to make graph copying faster for graph types like <tt>List(Di)Graph</tt> and <tt>Smart(Di)Graph</tt>?
</p>
<p>
Maybe we could have specialized versions of <tt>(di)graphCopy()</tt> 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 <tt>SmartDigraph</tt> and copies it to another <tt>SmartDigraph</tt> structure, then the iteration orders of the nodes and arcs are reversed.
</li></ul>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/251
http://lemon.cs.elte.hu/trac/lemon/ticket/251Report#400: MPL LpSolver/MipSolver backendFri, 15 Jul 2016 11:54:13 GMTFri, 19 Nov 2010 05:33:02 GMT<p>
The idea is to write an LP/MIP interface that is able to build up the problem, but when solving, it first create an MPL file, call the external command line solver, then parse back the output of the solver.
</p>
<p>
Of course it will be less efficient than using the C API of the same solver, but
</p>
<ul><li>it can be useful to have the LP program built up by our code in MPL format, so that we can play with the solver separately (e.g. for experimenting with the tuning options).
</li><li>for some legal reason, it may simply be impossible to link the mip/lp solver to our code.
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/400
http://lemon.cs.elte.hu/trac/lemon/ticket/400Report#296: Multicommodity flow algorithmsThu, 05 Nov 2009 10:21:38 GMTTue, 26 May 2009 16:47:21 GMT<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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/296
http://lemon.cs.elte.hu/trac/lemon/ticket/296Report#222: Network Simplex alg. for a simplified problemSun, 09 Jan 2011 16:50:39 GMTSat, 14 Feb 2009 06:40:59 GMT<p>
A simpler (but in fact equivalent) form of the Network Flow Problems when we have no upper limit on the arcs. We can also assume that the lower limit is 0 everywhere.
</p>
<p>
In this case Network Simplex algorithms becomes much easier:
</p>
<ul><li>A basis is just a tree, and it's trivial to obtaine both the primal and the dual solutions from it.
</li><li>A starting dual feasible solution is just a feasible potential w.r.t. the cost, so it can be computed by a shortest path algorithm.
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/222
http://lemon.cs.elte.hu/trac/lemon/ticket/222Report#76: New features for graphToEps()Mon, 03 Nov 2008 17:22:10 GMTThu, 03 Apr 2008 15:23:46 GMT<p>
Some additional features for <tt>graphToEps()</tt> would be nice to have.
For example:
</p>
<ul><li>The ability of setting linestyles, such az dotted, dashed etc.
</li><li>The ability of the assignment of a second color to the edges along with a percentage value. Then the edges would be colored with to color according to the percentage.
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/76
http://lemon.cs.elte.hu/trac/lemon/ticket/76Report#345: Obtaining and storing the LP solutionFri, 01 Mar 2013 19:00:09 GMTFri, 19 Feb 2010 11:48:59 GMT<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="enhancement: MipSolver interface fixes and extension (closed: fixed)">#326</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/345
http://lemon.cs.elte.hu/trac/lemon/ticket/345Report#37: operator= for RangeMap and SparseMapWed, 04 Nov 2009 18:45:17 GMTSat, 22 Mar 2008 17:50:14 GMT<p>
Now <tt>operator=</tt> function is private (without implementation) in <tt>RangeMap</tt> and <tt>SparseMap</tt> classes. Do we need public <tt>operator=</tt>?
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/37
http://lemon.cs.elte.hu/trac/lemon/ticket/37Report#218: Path decomposition subroutine in Preflow.Fri, 15 Jul 2016 11:29:07 GMTSat, 14 Feb 2009 06:22:08 GMT<p>
The title says everything.
</p>
<p>
See also <a class="assigned ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/217" title="enhancement: Subroutine in Preflow alg. to make the solution cycle-less (assigned)">#217</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/218
http://lemon.cs.elte.hu/trac/lemon/ticket/218Report#611: Planar drawing algorithm requires at least 3 nodesMon, 21 May 2018 11:17:41 GMTMon, 21 May 2018 11:17:41 GMT<p>
Planar drawing algorithm fails if it called with less than 3 nodes
</p>
deba
http://lemon.cs.elte.hu/trac/lemon/ticket/611
http://lemon.cs.elte.hu/trac/lemon/ticket/611Report#610: PlanarDrawing::run() is incompatible with the PlanarEmbedding algorithmTue, 15 May 2018 12:20:07 GMTTue, 15 May 2018 12:16:06 GMTdeba
http://lemon.cs.elte.hu/trac/lemon/ticket/610
http://lemon.cs.elte.hu/trac/lemon/ticket/610Report#168: Port bipartite matching algorithmsFri, 02 Aug 2013 12:46:14 GMTTue, 04 Nov 2008 12:02:18 GMT<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/48" title="task: Port matching algorithms (closed: fixed)">#48</a>.
</p>
<p>
The following tools are affected:
</p>
<ul><li>lemon/bipartite_matching.h
</li><li>lemon/pr_bipartite_matching.h (I really dislike this filename)
</li><li>test/bipartite_matching_test.cc
</li></ul><p>
It also depends on <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/69" title="task: Revise and port bipartite graphs (closed: fixed)">#69</a> (the port of the bipartite graphs).
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/168
http://lemon.cs.elte.hu/trac/lemon/ticket/168Report#64: Port constrained shortest path algorithmMon, 15 Dec 2008 16:05:21 GMTFri, 28 Mar 2008 13:06:02 GMT<p>
Namely, this file:
</p>
<ul><li>lemon/csp.h
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/64
http://lemon.cs.elte.hu/trac/lemon/ticket/64Report#178: Port dynamic tree based max flow algs.Thu, 05 Nov 2009 10:21:07 GMTFri, 14 Nov 2008 10:34:10 GMT<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/47" title="task: Port network flow algorithms (closed: fixed)">#47</a>.
</p>
<p>
Affected files are:
</p>
<ul><li>lemon/dynamic_tree.h
</li><li>lemon/goldberg_tarjan.h
</li><li>lemon/dinitz_sleator_tarjan.h
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/178
http://lemon.cs.elte.hu/trac/lemon/ticket/178Report#63: Port metaheuristicsSat, 03 Jul 2010 15:57:27 GMTFri, 28 Mar 2008 13:04:23 GMT<p>
The following files are affected.
</p>
<ul><li>lemon/tabu_search.h
</li><li>lemon/simann.h
</li><li>test/simann_test.cc
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/63
http://lemon.cs.elte.hu/trac/lemon/ticket/63Report#200: Port sparse SubGraph adaptor from SVNThu, 05 Nov 2009 10:21:30 GMTTue, 13 Jan 2009 10:45:53 GMT<p>
The <tt>SubGraph</tt> class in the 0.x series stores the unhidden edges/nodes as a double linked list (just as <tt>ListGraph</tt> does), therefore it provides better performance than the <tt>SubGraphAdaptor</tt> when the subgraph is sparse.
</p>
<p>
<tt>SubGraphAdaptor</tt> has been renamed to <tt>SubGraph</tt> in the 1.x series, thus I suggest to call the linked list based implementation as <tt>SparseSubGraph</tt>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/200
http://lemon.cs.elte.hu/trac/lemon/ticket/200Report#71: Port Steiner tree approximation algorithmMon, 24 Nov 2008 12:44:37 GMTFri, 28 Mar 2008 15:24:31 GMT<p>
Namely, the file
</p>
<ul><li>lemon/steiner.h
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/71
http://lemon.cs.elte.hu/trac/lemon/ticket/71Report#351: Port the LP utilitiesFri, 15 Jul 2016 11:41:21 GMTSun, 28 Feb 2010 23:07:03 GMT<p>
Revise and port the Lp utilities from SVN, namely
</p>
<ul><li><tt>lp_utils.h</tt>
</li><li><tt>lp_utils.cc</tt>
</li></ul>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/351
http://lemon.cs.elte.hu/trac/lemon/ticket/351Report#73: Port the remaining miscellaneous toolsWed, 07 Oct 2009 14:40:50 GMTFri, 28 Mar 2008 15:29:50 GMT<p>
The following files should be considered.
</p>
<ul><li>lemon/dist_log.h
</li><li>lemon/refptr.h
</li><li><del>lemon/iterable_maps.h</del>
</li><li>lemon/bits/debug_map.h
</li><li>lemon/matrix_maps.h
</li><li>lemon/polynomial.h
</li><li>lemon/concepts/matrix_maps.h
</li><li>lemon/map_iterator.h
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/73
http://lemon.cs.elte.hu/trac/lemon/ticket/73Report#346: Port the remaining shortest path algorithmsFri, 15 Jul 2016 11:41:08 GMTFri, 19 Feb 2010 13:10:36 GMT<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="task: Port the remaining shortest path algorithms (closed: done)">#51</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/346
http://lemon.cs.elte.hu/trac/lemon/ticket/346Report#59: Port the remaining spanning tree algorithmsFri, 08 Mar 2013 10:44:35 GMTFri, 28 Mar 2008 12:49:48 GMT<p>
The following files are affected.
</p>
<ul><li>lemon/fredman_tarjan.h
</li><li>lemon/prim.h
</li></ul>alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/59
http://lemon.cs.elte.hu/trac/lemon/ticket/59Report#70: Port VirtualMapsSun, 23 Nov 2008 08:28:59 GMTFri, 28 Mar 2008 15:22:47 GMT<p>
This affects
</p>
<ul><li>lemon/vmap.h
</li></ul><p>
but this tool is still in an early stage.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/70
http://lemon.cs.elte.hu/trac/lemon/ticket/70Report#151: Possible improvement in the function-type implementation of BFS/DFS/DijkstraSun, 02 Aug 2009 11:20:55 GMTWed, 24 Sep 2008 15:38:45 GMT<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/96" title="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 <tt>NodeMap</tt>s (instead of <tt>NullMap</tt>s) as <tt>PredMap</tt> and <tt>DistMap</tt> structures in the cases when they are not necessary. So the default type of these maps would be a <tt>NullMap</tt> in <tt>Bfs/Dfs/DijkstraWizardDefaultTraits</tt> classes, and it would be changed only if it is really needed (i.e. <tt>path()</tt> and/or <tt>dist()</tt> 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 <tt>ForkMap</tt>s".
</p>
<p>
It is a benchmark question however, that this implementation would be more efficient or not in practice.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/151
http://lemon.cs.elte.hu/trac/lemon/ticket/151Report#221: Primal Network Simplex algorithm with given starting solutionFri, 15 Jul 2016 11:29:23 GMTSat, 14 Feb 2009 06:32:24 GMT<p>
If a primal solution is available, then we don't need the extension of the underlying graphs, which may speed up the algorithm sometimes.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/221
http://lemon.cs.elte.hu/trac/lemon/ticket/221Report#271: Provide output in dimacs-solverFri, 15 Jul 2016 11:36:19 GMTFri, 24 Apr 2009 22:05:42 GMT<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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/271
http://lemon.cs.elte.hu/trac/lemon/ticket/271Report#235: Push-relabel max flow (Preflow) for undirected graphsWed, 25 Feb 2009 12:45:02 GMTWed, 25 Feb 2009 12:45:02 GMT<p>
The current Preflow algorithm works well on undirected graphs, however a specialized version for undirected graphs could more efficient than the current solution. The flow map could be <a class="missing wiki">EdgeMap?</a> in this case and the edges do not need to be iterated twice (outgoing and incoming arcs). I think the overall improvement could be a small factor both in time and storage complexity.
</p>
deba
http://lemon.cs.elte.hu/trac/lemon/ticket/235
http://lemon.cs.elte.hu/trac/lemon/ticket/235Report#385: QuadHeap instead of BinHeap in DijkstraFri, 15 Jul 2016 11:50:56 GMTSat, 31 Jul 2010 21:33:32 GMT<p>
It is questionable whether <tt>Dijkstra</tt> should use <tt>QuadHeap</tt> instead of <tt>BinHeap</tt> 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 <tt>QuadHeap</tt> turned out to be typically faster than <tt>BinHeap</tt>, especially when many <tt>decrease()</tt> 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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/385
http://lemon.cs.elte.hu/trac/lemon/ticket/385Report#98: Read-Write LoggerBoolMapMon, 12 Oct 2009 13:44:06 GMTSat, 14 Jun 2008 17:40:18 GMT<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="code"><pre><span class="k">typedef</span> LoggerBoolMap<span class="o"><</span><span class="p">...</span><span class="o">></span> LoggerMap<span class="p">;</span>
BoolEdgeMap map<span class="p">;</span>
LoggerMap log<span class="p">;</span>
ForkMap<span class="o"><</span>BoolEdgeMap<span class="p">,</span> LoggerMap<span class="o">></span> m<span class="p">(</span>map<span class="p">,</span> log<span class="p">);</span>
</pre></div>kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/98
http://lemon.cs.elte.hu/trac/lemon/ticket/98Report#431: Remember the lastly evaluated arcs in Circulation (and in Preflow)Sat, 09 Mar 2013 10:07:35 GMTSat, 10 Dec 2011 06:53:37 GMT<p>
The <a class="attachment" href="http://lemon.cs.elte.hu/trac/lemon/attachment/ticket/431/23a4fa3a7e62.patch" title="Attachment '23a4fa3a7e62.patch' in Ticket #431">attached patch</a><a class="trac-rawlink" href="http://lemon.cs.elte.hu/trac/lemon/raw-attachment/ticket/431/23a4fa3a7e62.patch" title="Download"></a> changes the behavior of <tt>Circulation</tt> class.
</p>
<p>
For each node, we now store the lastly evaluated arc, so we can continue from this arc instead of starting from the beginning when the node is evaluated again.
</p>
<p>
A test on a network of 32768 nodes and 262892 arcs (generated by <tt>netgen</tt>) shows a running time improvement of 24%. A much more comprehensive test would of course be necessary, but this number seems quite promising.
</p>
<p>
The same idea can (should?) also be applied to the <tt>Preflow</tt> class.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/431
http://lemon.cs.elte.hu/trac/lemon/ticket/431Report#313: Revise the implementation of PairingHeap and RadixHeapTue, 01 Sep 2009 19:58:47 GMTTue, 01 Sep 2009 19:43:45 GMT<p>
The implementation of <tt>PairingHeap</tt> and <tt>RadixHeap</tt> 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, <tt>PairingHeap</tt> and <tt>RadixHeap</tt> are almost always slower than <tt>BinHeap</tt> 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 <tt>PairingHeap</tt>:
</p>
<ol><li>It does not contain the heuristic that the small heaps created by <tt>push()</tt> and <tt>decrease()</tt> 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 <tt>pop()</tt> or <tt>prio()</tt>).
</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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/313
http://lemon.cs.elte.hu/trac/lemon/ticket/313Report#358: Runtime complexity for every algorithmSun, 09 Jan 2011 17:00:27 GMTMon, 15 Mar 2010 22:39:55 GMT<p>
Some algorithms such as <tt>MaxWeightedPerfectMatching</tt> include the complexity of the runtime. Others such as <tt>MaxMatching</tt> do not. It might be nice to add this information to the documentation of every algorithm object.
</p>
Ben
http://lemon.cs.elte.hu/trac/lemon/ticket/358
http://lemon.cs.elte.hu/trac/lemon/ticket/358Report#246: s() and t() as an alias for source() and target()Fri, 15 Jul 2016 11:32:58 GMTFri, 27 Mar 2009 15:11:03 GMT<p>
As we have <tt>u()</tt> and <tt>v()</tt> for undirected graphs, it seems to be a good idea to have shorter alias names for <tt>source()</tt> and <tt>target()</tt>, e.g. <tt>s()</tt> and <tt>t()</tt>, since they are among the most frequently used functions.
</p>
<p>
What do you think about it?
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/246
http://lemon.cs.elte.hu/trac/lemon/ticket/246Report#355: SCIP MipSolver backendTue, 03 Dec 2013 21:12:00 GMTFri, 12 Mar 2010 09:39:38 GMT<p>
The title says everything. Please find Ambros Gleixner's beta version implementation attached. His comments comes below.
</p>
<blockquote>
<p>
Sziasztok,
</p>
</blockquote>
<blockquote>
<p>
attached is a beta version of the SCIP interface. There is one segfault
bug which I somehow cannot figure out. I will have to solve this with
my colleagues in Berlin.
</p>
</blockquote>
<blockquote>
<p>
Do you have some more extensive test files for the MIP interfaces
besides test/mip_test.cc? If so, I would be happy to run them.
</p>
</blockquote>
<blockquote>
<p>
Üdv,
ambros
</p>
</blockquote>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/355
http://lemon.cs.elte.hu/trac/lemon/ticket/355Report#381: Simplified heaps without priority updateFri, 15 Jul 2016 11:46:06 GMTWed, 21 Jul 2010 15:41:14 GMT<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 <tt>increase()</tt>, <tt>decrease()</tt>, <tt>erase()</tt>, etc. functions.
However, simplified heaps could be implemented with a limited functionality (<tt>push()</tt>, <tt>pop()</tt>, <tt>top()</tt>, <tt>prio()</tt>, <tt>size()</tt>, <tt>empty()</tt>, <tt>clear()</tt>, etc.) without this cross reference map. For such heaps, the basic <tt>push()</tt> and <tt>pop()</tt> 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 <tt>pop()</tt> 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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/381
http://lemon.cs.elte.hu/trac/lemon/ticket/381Report#252: Smaller iterator classes for some graph structuresThu, 07 Mar 2013 08:51:08 GMTFri, 27 Mar 2009 16:58:58 GMT<p>
All the <tt>NodeIt</tt>, <tt>ArcIt</tt>, <tt>EdgeIt</tt> etc. iterator classes stores a pointer for the underlying (di)graph. However it wouldn't be necessary in some cases.
</p>
<p>
E.g. <tt>SmartDigraph::next(Node&)</tt> and <tt>SmartDigraph::next(Arc&)</tt> are static functions. Thus <tt>SmartDigraph::NodeIt</tt> and <tt>SmartDigraph::ArcIt</tt> could be implemented without a pointer to the graph. The three <tt>next()</tt> functions of <tt>SmartGraph</tt> are not static, but they could/should be. The special graph structures (<tt>FullGraph</tt>, <tt>HypercubeGraph</tt>, <tt>GridGraph</tt>) also have static <tt>next()</tt> functions.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/252
http://lemon.cs.elte.hu/trac/lemon/ticket/252Report#377: Smaller version of StaticDigraphWed, 12 Apr 2017 15:16:52 GMTFri, 02 Jul 2010 20:39:29 GMT<p>
The current implementation of <tt>StaticDigraph</tt> stores <tt>2n+4m</tt> int values (for <tt>n</tt> nodes and <tt>m</tt> arcs). However, in many cases, one needs outgoing arc iteration only. For such cases, a static graph representation could be implemented with <tt>n+2m</tt> integers by fully omitting the outgoing and incomming arc lists (but arcs would be sorted by their source nodes).
</p>
<p>
The <tt>NodeIt</tt>, <tt>ArcIt</tt> and <tt>OutArcIt</tt> iterators could be implemented efficiently, but the basic iteration of the ougoing arcs would be somewhat slower (see <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/68" title="task: Port static graph implementation (closed: done)">#68</a> for antecedents). For ensuring the compatibility with the <tt>Digraph</tt> interface, an <tt>InArcIt</tt> iterator should also be implemented, but it would be really slow (as slow as full arc iteration).
</p>
<p>
What do you think? Would this data structure make sense?
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/377
http://lemon.cs.elte.hu/trac/lemon/ticket/377Report#329: Sort outgoing arcs in the build() function of StaticDigraphFri, 15 Jul 2016 11:39:32 GMTFri, 13 Nov 2009 09:40:32 GMT<p>
In the <tt>build()</tt> function of <tt>StaticDigraph</tt> 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 <tt>build()</tt> function (and copying a graph to <tt>StaticDigraph</tt>) 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 <tt>build()</tt> function). However, the default option is of high importance here, since it will be used by <tt>DigraphCopy</tt>.
</p>
<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/68" title="task: Port static graph implementation (closed: done)">#68</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/329
http://lemon.cs.elte.hu/trac/lemon/ticket/329Report#287: Specify argument order for ArgParserFri, 01 Mar 2013 19:00:09 GMTFri, 08 May 2009 11:04:08 GMT<p>
I think it would be nice if the order in which <tt>ArgParser</tt> 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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/287
http://lemon.cs.elte.hu/trac/lemon/ticket/287Report#224: Static graph mapsFri, 15 Jul 2016 11:29:50 GMTSat, 14 Feb 2009 20:02:38 GMT<p>
Sometimes it would be nice to have a map which is not registered in the alteration notifier of the graph.
</p>
<p>
One reason might be running time efficiency, but the more important is multi-thread applications (see <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/223" title="enhancement: Thread safe graphs (closed: done)">#223</a>). Currently, it is not safe to run say two Dijkstra algorithms on the same graph in parallel, as they would allocate maps and register them into the alteration notifier simultaneously, which is not safe. Changing these map allocations to static one would solve this problem.
</p>
<p>
My suggestion is to use the standard maps with a special constructor for this purpose, e.g.
</p>
<pre class="wiki">ListGraph::NodeMap<int> map1(g,STATIC);
ListGraph::NodeMap<int> map1(g,15,STATIC);
</pre><p>
or
</p>
<pre class="wiki">ListGraph::NodeMap<int> map1(STATIC,g);
ListGraph::NodeMap<int> map1(STATIC,g,15);
</pre><p>
See also <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/223" title="enhancement: Thread safe graphs (closed: done)">#223</a>.
</p>
<p>
<strong>'
</strong></p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/224
http://lemon.cs.elte.hu/trac/lemon/ticket/224Report#594: STL syle iterators - phase II.Thu, 08 Oct 2015 08:31:25 GMTTue, 14 Apr 2015 18:46:57 GMT<p>
STL style iterators could be also added to other places. These possibilities should be discussed here.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/594
http://lemon.cs.elte.hu/trac/lemon/ticket/594Report#32: Storing Arcs instead of OutArcIts in Dfs stackFri, 02 Aug 2013 12:34:35 GMTThu, 20 Mar 2008 10:47:17 GMT<p>
The OutArcIt contains an int data field and a pointer to the graph, while the Arc just stores the int member. If we used Arcs in the Dfs stack, that could decrease the memory request of Dfs and it may provide better runtime performance.
</p>
deba
http://lemon.cs.elte.hu/trac/lemon/ticket/32
http://lemon.cs.elte.hu/trac/lemon/ticket/32Report#217: Subroutine in Preflow alg. to make the solution cycle-lessFri, 15 Jul 2016 11:28:55 GMTSat, 14 Feb 2009 06:21:47 GMT<p>
The title says everything.
</p>
<p>
See also <a class="assigned ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/218" title="enhancement: Path decomposition subroutine in Preflow. (assigned)">#218</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/217
http://lemon.cs.elte.hu/trac/lemon/ticket/217Report#343: Support arbitrary precision integers and rationals in LEMONThu, 18 Feb 2010 05:17:23 GMTTue, 16 Feb 2010 05:19:02 GMT<p>
Of course we should rely on a third party library, but it would still be nice if e.g. dimacs-solver could provide dead true results.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/343
http://lemon.cs.elte.hu/trac/lemon/ticket/343Report#261: Support floating-point data in min-cost flow algorithmsThu, 25 May 2017 15:29:49 GMTSat, 11 Apr 2009 14:31:07 GMT<p>
This is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/254" title="enhancement: Support real value types in NetworkSimplex (closed: done)">#254</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/261
http://lemon.cs.elte.hu/trac/lemon/ticket/261Report#244: Support min. cost max. flow in MCF classesFri, 15 Jul 2016 11:32:19 GMTWed, 25 Mar 2009 21:29:41 GMT<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="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 <tt>maxFlow(Node s, Node t)</tt> function, which could be used instead of <tt>supplyMap()</tt> and <tt>stSupply()</tt>. In this case <tt>Preflow::runMinCut()</tt> should be called to determine the max. flow value (instead of <tt>Circualtion</tt>), and the algorithm have to be initialized as if <tt>stSupport()</tt> was called with this flow value. However apart from that nothing have to be changed.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/244
http://lemon.cs.elte.hu/trac/lemon/ticket/244Report#139: Support short and long style parameters in ArgParserMon, 03 Nov 2008 17:17:01 GMTMon, 25 Aug 2008 16:19:35 GMT<p>
This is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/104" title="defect: Meaningless parameter in ArgParser::boolOption() (closed: fixed)">ticket:104</a>.
</p>
<p>
I would propose a member function like <tt>void style(StyleEnum st)</tt>, where the parameter <tt>st</tt> would choose from the following options:
</p>
<ul><li><strong>Short style</strong>, where the form of the parameters are
<pre class="wiki">-param value
</pre></li><li><strong>Long style</strong>, where the form of the parameters are
<pre class="wiki">-param=value
</pre></li><li><strong>Mixed style</strong>, where options starting with one dash use the short form while those starting with two use the long style.
</li></ul><p>
With this approach, one can implement POSIX compliant parameters.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/139
http://lemon.cs.elte.hu/trac/lemon/ticket/139Report#145: Support SunCC compilerFri, 15 Jul 2016 11:22:15 GMTFri, 12 Sep 2008 15:55:13 GMT<p>
Currently (as of <a class="changeset" href="http://lemon.cs.elte.hu/trac/lemon/changeset/c691064dfd4f/lemon" title="Merge">[c691064dfd4f]</a>), SunCC reports some pretty strange errors.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/145
http://lemon.cs.elte.hu/trac/lemon/ticket/145Report#452: time_measure.h uses obsolete headearsMon, 12 Sep 2016 12:49:38 GMTThu, 11 Oct 2012 13:20:07 GMT<p>
<a class="missing source">time_measure.h</a> includes obsolete (pre C++) headers, such as <tt>unistd.h</tt>, <tt>sys/times.h</tt> and <tt>sys/time.h</tt> which in turn define a couple of things in the global namespace. Using the C++ counterparts of these headers (I hope they exist) would be a better option.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/452
http://lemon.cs.elte.hu/trac/lemon/ticket/452Report#352: Tolerance in GomoryHuTue, 02 Mar 2010 09:08:31 GMTTue, 02 Mar 2010 09:07:56 GMT<p>
For <tt>GomoryHu</tt> class, <tt>Tolerance</tt> 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="task: Tolerance in min cut algorithms (closed: fixed)">#306</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/352
http://lemon.cs.elte.hu/trac/lemon/ticket/352Report#361: Tolerance support in BellmanFordThu, 18 Mar 2010 07:25:06 GMTThu, 18 Mar 2010 00:31:54 GMT<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="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="defect: VS compilation error (closed: fixed)">#360</a>.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/361
http://lemon.cs.elte.hu/trac/lemon/ticket/361Report#378: Transitive closureFri, 02 Jul 2010 21:09:37 GMTFri, 02 Jul 2010 21:09:37 GMT<p>
It would be nice to have a tool that generates the transitive closure of an input graph to another graph (similarly to <tt>digraphCopy()</tt>).
</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>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/378
http://lemon.cs.elte.hu/trac/lemon/ticket/378Report#85: Use eps.h for drawing in graphToEps()Mon, 03 Nov 2008 17:22:54 GMTThu, 17 Apr 2008 16:31:52 GMT<p>
We should consider using eps.h for the actual drawing in graphToEps().
</p>
<p>
See also <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/43" title="task: Port graph_to_eps and eps.h (closed: fixed)">ticket:43</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/85
http://lemon.cs.elte.hu/trac/lemon/ticket/85Report#152: Using processed map in Dijkstra::processed()Mon, 24 Nov 2008 11:59:41 GMTFri, 26 Sep 2008 04:31:33 GMT<p>
This ticket is a follow-up of <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/149" title="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 <tt>ProcessedMap</tt> type is <tt>NullMap</tt> or not and whether it uses local map or not. It would be nice that the given processed map (<tt>_processed</tt>) is used if it is not of type <tt>NullMap</tt> 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 <tt>SetProcessedMap</tt> or <tt>SetStandardProcessedMap</tt> named class parameters were used. But in the the later case extra codes in <tt>DijkstraWizard</tt> would also be needed, since it does not use the above named class parameters but defining a traits class explicitly.
</p>
kpeter
http://lemon.cs.elte.hu/trac/lemon/ticket/152
http://lemon.cs.elte.hu/trac/lemon/ticket/152Report#597: VF2 (sub)graph isomoprism algorithmSat, 07 Oct 2017 16:26:16 GMTFri, 15 May 2015 10:09:18 GMT<p>
The changesets <a class="changeset" href="http://lemon.cs.elte.hu/trac/lemon/changeset/a037254714b3/lemon" title="VF2 algorithm added (#597)
The implementation of this feature was ...">[a037254714b3]</a>, <a class="changeset" href="http://lemon.cs.elte.hu/trac/lemon/changeset/2f479109a71d/lemon" title="Documentation for VF2 (#597)
The implementation of this feature was ...">[2f479109a71d]</a> and <a class="changeset" href="http://lemon.cs.elte.hu/trac/lemon/changeset/f85ee41c84bc/lemon" title="Bugfix in Vf2 - missing initialization (#597)">[f85ee41c84bc]</a> implement a slightly modified version of the VF2 algorithm for finding isomorphic copy of a graph as subgraph of another. It can find either normal or induced subgraph, or an isomorphism between the two graphs. It is also capable of enumerating all possible embedding. Finally, nodes can be labeled in order to model different (i.e. unmatchable) node types.
</p>
<p>
The function type interface can be considered final, the base class may be refined later.
</p>
<p>
This development was sponsored by QuantumBio Inc.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/597
http://lemon.cs.elte.hu/trac/lemon/ticket/597Report#6: VGraph and VMapSun, 23 Nov 2008 08:28:10 GMTMon, 21 Jan 2008 12:29:31 GMT<p>
It would be nice to have maps and graph with virtual functions in their interface. They would be inherited from common base classes, and there would be factories to "virtualize" graphs and maps. All these would make it possible to avoid the use of templates when the speed is not an issue.
</p>
<p>
This ticket is a copy of report #24 of the old bug tracking system. It refers to release 0.5.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/6
http://lemon.cs.elte.hu/trac/lemon/ticket/6Report#86: Virtualmap based graphToEps().Wed, 17 Feb 2010 05:58:36 GMTThu, 17 Apr 2008 16:35:35 GMT<p>
A rewrite of graphToEps() using virtual-maps instead of named template parameters would result in a much faster compilation time, at a cost of a slower execution, which is not really an issue here.
</p>
<p>
See also <a class="closed ticket" href="http://lemon.cs.elte.hu/trac/lemon/ticket/43" title="task: Port graph_to_eps and eps.h (closed: fixed)">ticket:43</a>.
</p>
alpar
http://lemon.cs.elte.hu/trac/lemon/ticket/86
http://lemon.cs.elte.hu/trac/lemon/ticket/86Report