Sage: Ticket #9910: Longest path
https://trac.sagemath.org/ticket/9910
<p>
This method computes a longest path in a graph/digraph...
</p>
<p>
Apply after :
</p>
<ul><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/9698" title="enhancement: Hamiltonian cycles in undirected graphs - backtracking algorithm. (closed: fixed)">#9698</a>
</li><li><a class="closed ticket" href="https://trac.sagemath.org/ticket/10043" title="enhancement: Complete rewrite of LP solver interfaces (closed: fixed)">#10043</a>
</li></ul><p>
<strong>Apply:</strong>
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9910/trac_9910.patch" title="Attachment 'trac_9910.patch' in Ticket #9910">trac_9910.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9910/trac_9910.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9910/trac-9910_reviewer.patch" title="Attachment 'trac-9910_reviewer.patch' in Ticket #9910">trac-9910_reviewer.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9910/trac-9910_reviewer.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9910/trac_9910-fixing_documentation.patch" title="Attachment 'trac_9910-fixing_documentation.patch' in Ticket #9910">trac_9910-fixing_documentation.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9910/trac_9910-fixing_documentation.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9910
Trac 1.1.6ncohenTue, 14 Sep 2010 19:19:30 GMTstatus changed
https://trac.sagemath.org/ticket/9910#comment:1
https://trac.sagemath.org/ticket/9910#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenWed, 20 Oct 2010 12:15:01 GMTdescription changed
https://trac.sagemath.org/ticket/9910#comment:2
https://trac.sagemath.org/ticket/9910#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9910?action=diff&version=2">diff</a>)
</li>
</ul>
TicketncohenWed, 20 Oct 2010 12:15:16 GMTattachment set
https://trac.sagemath.org/ticket/9910
https://trac.sagemath.org/ticket/9910
<ul>
<li><strong>attachment</strong>
set to <em>trac_9910.2.patch</em>
</li>
</ul>
TicketncohenWed, 20 Oct 2010 12:16:05 GMT
https://trac.sagemath.org/ticket/9910#comment:3
https://trac.sagemath.org/ticket/9910#comment:3
<p>
sorry for the two version, they're both the same <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketmvnguThu, 04 Nov 2010 11:11:38 GMTcc changed
https://trac.sagemath.org/ticket/9910#comment:4
https://trac.sagemath.org/ticket/9910#comment:4
<ul>
<li><strong>cc</strong>
<em>mvngu</em> added
</li>
</ul>
TicketrlmFri, 26 Nov 2010 17:13:41 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/9910#comment:5
https://trac.sagemath.org/ticket/9910#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase</em>
</li>
</ul>
TicketncohenFri, 26 Nov 2010 20:49:02 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/9910#comment:6
https://trac.sagemath.org/ticket/9910#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>rebase</em> deleted
</li>
</ul>
<p>
Updated !
</p>
<p>
Nathann
</p>
TicketncohenFri, 26 Nov 2010 20:49:19 GMTattachment set
https://trac.sagemath.org/ticket/9910
https://trac.sagemath.org/ticket/9910
<ul>
<li><strong>attachment</strong>
set to <em>trac_9910.patch</em>
</li>
</ul>
TicketmvnguSat, 27 Nov 2010 19:19:59 GMTattachment set
https://trac.sagemath.org/ticket/9910
https://trac.sagemath.org/ticket/9910
<ul>
<li><strong>attachment</strong>
set to <em>trac-9910_reviewer.patch</em>
</li>
</ul>
TicketmvnguSat, 27 Nov 2010 19:24:52 GMTdescription changed; reviewer, author set
https://trac.sagemath.org/ticket/9910#comment:7
https://trac.sagemath.org/ticket/9910#comment:7
<ul>
<li><strong>reviewer</strong>
set to <em>Robert Miller, Minh Van Nguyen</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9910?action=diff&version=7">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
I'm OK with most of your patch. But here are some general comments:
</p>
<ul><li>I don't quite understand this documentation:
<pre class="wiki"> - ``s`` (vertex) -- forces the source of the path. Set to
``None`` by default.
- ``t`` (vertex) -- forces the destination of the path. Set to
``None`` by default.
</pre>What do you mean by "forces", etc. You need to elaborate here.
</li></ul><ul><li>The following code block
<pre class="wiki"> if self._directed:
from sage.graphs.all import DiGraph
return [0, DiGraph()] if weighted else DiGraph()
else:
from sage.graphs.all import Graph
return [0, Graph()] if weighted else Graph()
</pre>is equivalent to
<pre class="wiki"> if self._directed:
from sage.graphs.all import DiGraph
return [0, DiGraph()] if weighted else DiGraph()
from sage.graphs.all import Graph
return [0, Graph()] if weighted else Graph()
</pre></li></ul><ul><li>You really need to start seriously writing Python code that conforms to Python coding conventions (wherever possible); see <a class="ext-link" href="http://www.python.org/dev/peps/pep-0008/"><span class="icon"></span>PEP 8</a> for more information.
</li></ul><p>
Most of the above issues are fixed in my reviewer patch.
</p>
TicketncohenSat, 27 Nov 2010 21:09:06 GMT
https://trac.sagemath.org/ticket/9910#comment:8
https://trac.sagemath.org/ticket/9910#comment:8
<p>
Hello !!!
</p>
<p>
Here is a patch to import on top of your, to fix the documentation. These options are just a way for the user to compute the "longest path leaving from s", or the "longest path ending in t", or the "longest s-t-path"
</p>
<p>
About the if/else, I knew it was not useful but I let it stay anyway thinking it would be easier to understand the code. When I look at it from afar, I like to see a <a class="missing wiki">If/Else?</a> with return lines at the end of both, which ensures the method ends because of this part of the code (and I like to preserve symmetry when there is no reason not to <code>^^;</code>). That's just me, if you think it's better without the "else", then let it be.
</p>
<p>
I am really sorry you had to waste time fixing my spaces and long lines. I know I never paid attention to spaces, but I will from now on, and I thought I was wary enough of long lines, which is clearly untrue. I also thought I had learned not to write <code></code>x == None<code></code> too... <code>:-/</code>
</p>
<p>
Here is the slight fix in the documentation you asked. If it suits you, the ticket is good to go.
</p>
<p>
Thank you for your precious help, once again !
</p>
<p>
Nathann
</p>
TicketmvnguSat, 27 Nov 2010 22:03:08 GMT
https://trac.sagemath.org/ticket/9910#comment:9
https://trac.sagemath.org/ticket/9910#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9910#comment:8" title="Comment 8">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Here is a patch to import on top of your, to fix the documentation. These options are just a way for the user to compute the "longest path leaving from s", or the "longest path ending in t", or the "longest s-t-path"
</p>
</blockquote>
<p>
Your improved documentation is certainly very clear to me. But note a typo in the following:
</p>
<pre class="wiki">4384 returns the longest path starting at ``s``). Thie argument is Set to
</pre><p>
I think you mean "The" instead of "Thie". And two more in these lines:
</p>
<pre class="wiki">4388 - ``s`` (vertex) -- forces the destination of the path (the method then
4389 returns the longest path ending at ``s``). Thie argument is Set to
</pre><p>
I think you mean the above to be about the argument "t", as opposed to repeating the documentation for the argument "s". If you fix these, then the ticket is good to go.
<br /><br />
</p>
<blockquote class="citation">
<p>
About the if/else, I knew it was not useful but I let it stay anyway thinking it would be easier to understand the code. When I look at it from afar, I like to see a <a class="missing wiki">If/Else?</a> with return lines at the end of both, which ensures the method ends because of this part of the code (and I like to preserve symmetry when there is no reason not to <code>^^;</code>). That's just me, if you think it's better without the "else", then let it be.
</p>
</blockquote>
<p>
In many cases, removing the redundant "else" can result in faster code than if you leave in the "else". Here's a sample profiling session:
</p>
<div class="wiki-code"><div class="code"><pre>sage<span class="p">:</span> <span class="c"># define functions whose runtime are to be compared</span>
sage<span class="p">:</span> <span class="k">def</span> <span class="nf">con_else</span><span class="p">(</span>n<span class="p">):</span>
<span class="o">....</span><span class="p">:</span> <span class="k">if</span> n <span class="o">&</span> <span class="mi">1</span><span class="p">:</span>
<span class="o">....</span><span class="p">:</span> <span class="mi">2</span> <span class="o">*</span> n
<span class="o">....</span><span class="p">:</span> <span class="k">return</span>
<span class="o">....</span><span class="p">:</span> <span class="k">else</span><span class="p">:</span>
<span class="o">....</span><span class="p">:</span> n <span class="o">+</span> <span class="mi">1</span>
<span class="o">....</span><span class="p">:</span> <span class="k">return</span>
<span class="o">....</span><span class="p">:</span>
sage<span class="p">:</span> <span class="k">def</span> <span class="nf">con_no_else</span><span class="p">(</span>n<span class="p">):</span>
<span class="o">....</span><span class="p">:</span> <span class="k">if</span> n <span class="o">&</span> <span class="mi">1</span><span class="p">:</span>
<span class="o">....</span><span class="p">:</span> <span class="mi">2</span> <span class="o">*</span> n
<span class="o">....</span><span class="p">:</span> <span class="k">return</span>
<span class="o">....</span><span class="p">:</span> n <span class="o">+</span> <span class="mi">1</span>
<span class="o">....</span><span class="p">:</span> <span class="k">return</span>
<span class="o">....</span><span class="p">:</span>
sage<span class="p">:</span>
sage<span class="p">:</span> <span class="c"># get runtime samples for the above functions</span>
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">781</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">787</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">795</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">785</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">781</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">792</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">784</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">798</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">784</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">766</span> ns per loop
sage<span class="p">:</span> T1even <span class="o">=</span> <span class="p">[</span><span class="mi">781</span><span class="p">,</span> <span class="mi">787</span><span class="p">,</span> <span class="mi">795</span><span class="p">,</span> <span class="mi">785</span><span class="p">,</span> <span class="mi">781</span><span class="p">,</span> <span class="mi">792</span><span class="p">,</span> <span class="mi">784</span><span class="p">,</span> <span class="mi">798</span><span class="p">,</span> <span class="mi">784</span><span class="p">,</span> <span class="mi">766</span><span class="p">]</span>
sage<span class="p">:</span>
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">771</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">769</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">771</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">768</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">772</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">766</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">772</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">768</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">769</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">774</span> ns per loop
sage<span class="p">:</span> T1odd <span class="o">=</span> <span class="p">[</span><span class="mi">771</span><span class="p">,</span> <span class="mi">769</span><span class="p">,</span> <span class="mi">771</span><span class="p">,</span> <span class="mi">768</span><span class="p">,</span> <span class="mi">772</span><span class="p">,</span> <span class="mi">766</span><span class="p">,</span> <span class="mi">772</span><span class="p">,</span> <span class="mi">768</span><span class="p">,</span> <span class="mi">769</span><span class="p">,</span> <span class="mi">774</span><span class="p">]</span>
sage<span class="p">:</span>
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">661</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">667</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">669</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">667</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">669</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">661</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">666</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">674</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">667</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">100</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">664</span> ns per loop
sage<span class="p">:</span> T2even <span class="o">=</span> <span class="p">[</span><span class="mi">661</span><span class="p">,</span> <span class="mi">667</span><span class="p">,</span> <span class="mi">669</span><span class="p">,</span> <span class="mi">667</span><span class="p">,</span> <span class="mi">669</span><span class="p">,</span> <span class="mi">661</span><span class="p">,</span> <span class="mi">666</span><span class="p">,</span> <span class="mi">674</span><span class="p">,</span> <span class="mi">667</span><span class="p">]</span>
sage<span class="p">:</span>
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">680</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">677</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">680</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">685</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">679</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">677</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">678</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">679</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">685</span> ns per loop
sage<span class="p">:</span> <span class="o">%</span>timeit con_no_else<span class="p">(</span><span class="mi">101</span><span class="p">)</span>
<span class="mi">625</span> loops<span class="p">,</span> best of <span class="mi">3</span><span class="p">:</span> <span class="mi">675</span> ns per loop
sage<span class="p">:</span> T2odd <span class="o">=</span> <span class="p">[</span><span class="mi">680</span><span class="p">,</span> <span class="mi">677</span><span class="p">,</span> <span class="mi">680</span><span class="p">,</span> <span class="mi">685</span><span class="p">,</span> <span class="mi">679</span><span class="p">,</span> <span class="mi">677</span><span class="p">,</span> <span class="mi">678</span><span class="p">,</span> <span class="mi">679</span><span class="p">,</span> <span class="mi">685</span><span class="p">,</span> <span class="mi">675</span><span class="p">]</span>
sage<span class="p">:</span>
sage<span class="p">:</span> <span class="c"># And now a comparison of the average runtime</span>
sage<span class="p">:</span> RR<span class="p">(</span><span class="nb">sum</span><span class="p">(</span>T1even<span class="p">)</span> <span class="o">/</span> <span class="nb">len</span><span class="p">(</span>T1even<span class="p">))</span>
<span class="mf">785.300000000000</span>
sage<span class="p">:</span> RR<span class="p">(</span><span class="nb">sum</span><span class="p">(</span>T2even<span class="p">)</span> <span class="o">/</span> <span class="nb">len</span><span class="p">(</span>T2even<span class="p">))</span>
<span class="mf">666.777777777778</span>
sage<span class="p">:</span> RR<span class="p">(</span><span class="nb">sum</span><span class="p">(</span>T1odd<span class="p">)</span> <span class="o">/</span> <span class="nb">len</span><span class="p">(</span>T1odd<span class="p">))</span>
<span class="mf">770.000000000000</span>
sage<span class="p">:</span> RR<span class="p">(</span><span class="nb">sum</span><span class="p">(</span>T2odd<span class="p">)</span> <span class="o">/</span> <span class="nb">len</span><span class="p">(</span>T2odd<span class="p">))</span>
<span class="mf">679.500000000000</span>
</pre></div></div><p>
<br />
</p>
<blockquote class="citation">
<p>
I am really sorry you had to waste time fixing my spaces and long lines. I know I never paid attention to spaces, but I will from now on, and I thought I was wary enough of long lines, which is clearly untrue. I also thought I had learned not to write <code></code>x == None<code></code> too... <code>:-/</code>
</p>
</blockquote>
<p>
I care about your code and how fast it runs. That's why I suggested that you use "is not" or "is" when you do a comparison with "None", because in that case the comparison is faster than if you used "!=" or "=".
<br /><br />
</p>
<blockquote class="citation">
<p>
Here is the slight fix in the documentation you asked. If it suits you, the ticket is good to go.
</p>
<p>
Thank you for your precious help, once again !
</p>
</blockquote>
<p>
Don't take my comments above the wrong way. Had I not cared about your code and how fast you can make it run, I wouldn't bother reading your patches and suggest where you can improve the runtime of your code. There are many tricks in Python programming that can result in fast code without having to use Cython. I just want to share with you any tricks I know. As regards coding conventions, many programming languages have them and people who program in such a language would more or less adhere to the corresponding coding conventions. Remember that conventions are guidelines that many if not most experienced programmers find to result in readable, maintainable, and elegant looking code. This means that in some cases, it makes sense to break a convention. In case you are uncertain about whether to follow a convention or not, you need to use your judgement.
</p>
TicketncohenSun, 28 Nov 2010 08:46:16 GMT
https://trac.sagemath.org/ticket/9910#comment:10
https://trac.sagemath.org/ticket/9910#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9910#comment:9" title="Comment 9">mvngu</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9910#comment:8" title="Comment 8">ncohen</a>:
Your improved documentation is certainly very clear to me. But note a typo in the following:
</p>
</blockquote>
<p>
Fixed in the updated patch !
</p>
<blockquote class="citation">
<p>
Don't take my comments above the wrong way.
</p>
</blockquote>
<p>
By now I have understood that both your patience and attention to details are about boundless. It makes me all the more eager to learn from you !
</p>
<p>
Nathann
</p>
TicketncohenSun, 28 Nov 2010 08:47:14 GMTattachment set
https://trac.sagemath.org/ticket/9910
https://trac.sagemath.org/ticket/9910
<ul>
<li><strong>attachment</strong>
set to <em>trac_9910-fixing_documentation.patch</em>
</li>
</ul>
TicketmvnguMon, 29 Nov 2010 08:46:33 GMTstatus, description changed
https://trac.sagemath.org/ticket/9910#comment:11
https://trac.sagemath.org/ticket/9910#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9910?action=diff&version=11">diff</a>)
</li>
</ul>
TicketjdemeyerMon, 29 Nov 2010 14:28:34 GMTmilestone changed
https://trac.sagemath.org/ticket/9910#comment:12
https://trac.sagemath.org/ticket/9910#comment:12
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.6.1</em> to <em>sage-4.6.2</em>
</li>
</ul>
TicketpangFri, 31 Dec 2010 16:42:09 GMT
https://trac.sagemath.org/ticket/9910#comment:13
https://trac.sagemath.org/ticket/9910#comment:13
<p>
This is a comment from an outsider, so it may not make much sense: you mention in the docstring that this problem is NP-hard, and I agree there doesn't seem to be an algorithm that is polinomial in the number of edges, but:
</p>
<p>
In the paper
</p>
<p>
<a class="ext-link" href="http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf"><span class="icon"></span>http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf</a>
</p>
<p>
there is an algorithm to list all elementary circuits in a graph that is linear in the number of circuits. This algorithm is implemented in version 1.4 of networkx:
</p>
<p>
<a class="ext-link" href="https://networkx.lanl.gov/trac/ticket/394"><span class="icon"></span>https://networkx.lanl.gov/trac/ticket/394</a>
</p>
<p>
Is the situation for paths instead of circuits much different? Is a MILP algorithm better than listing all elementary paths by a Johnson-like algorithm and finding the max lenght? Maybe MILP is better in practice but is it in theory?
</p>
TicketncohenSat, 01 Jan 2011 11:13:15 GMT
https://trac.sagemath.org/ticket/9910#comment:14
https://trac.sagemath.org/ticket/9910#comment:14
<p>
Hello !
</p>
<blockquote class="citation">
<p>
Is the situation for paths instead of circuits much different?
</p>
</blockquote>
<p>
The situation for directed graphs is not different at all : by just replacing each undirected edge by two edges, on in each direction, you transform one problem into the other. Besides, your algorithms shouldn't make much more operations than necessary because of the transformation.
</p>
<blockquote class="citation">
<blockquote>
<p>
Is a MILP algorithm better than listing all elementary paths by a Johnson-like algorithm and finding the max lenght? Maybe MILP is better in practice but is it in theory?
</p>
</blockquote>
</blockquote>
<p>
Let me first begin by saying that I can not *stand* complexity theory. I mean -- I like the theory, some of its conjectures, it sometimes says interesting things, and even though it is most of the times for bad reasons (see *) it motivates people to do research on maths, which is perfectly nice.
</p>
<p>
This being said, many recent results and directions of research in complexity have forgotten practice a long time ago. They are still interesting results, they are still analysis of what our modelling of "what is an efficient algorith" is, (*) but there is a point where this modelling is not representative of the reality anymore (at which point we are expected to adapt our theory).
So in theory, no there are no differences between those two algorithms. Well, perhaps there is one : it is very hard to analyse the runtime of a specific linear program, especially when it makes use of many heuristics hidden in the LP solvers (and CPLEX and GLPK may behave very differently on the same instance, even though they are given the same formulations). On the other hand, I suspect it should be possible to produce graphs for which listing all the paths before finding one of maximum length (usually you would need to enumerat them all to be sure you found the best one, but if you happen to find a hamiltonian path at some point you needn't press further) takes an exponential time.
Which means I can not prove the LP is faster than the complete enumeration. Of course -- nothing more than that -- it is probably possible to do it anyway, my ignorance hopefully being a personnal drama :-D
</p>
<p>
To answer further, there is an heuristic added to the Longest Path method in Sage. It works by randomly extending paths, for as long as possible, with some other healthy rules to go back in the exploration if bad choices have been made. It isn't the algorithm you mentionned, but it is a good way to get an idea of their relative performances without having to implement the actual enumeration.
</p>
<p>
Let me also add that if you were willing to implement this enumeration (and then again, I of course have no proof LP is better. Especially when we can put complexity analysis to death by saying -- "we are just interested in practical instances", which can not be defined. That's precisely where a simple programming trick can divide the running time by 100 even though Theory does not see the difference), using the NetworkX implementation would be a very bad choice, considering it is written in Python. I had to write an enumeration algorithm in Cython for the graph methods subgraph_search*, and the Python version I had written previously was just .... not working. I didn't say "slow", I said that the running time of the SAME algorithm was comparatively so large that it wasn't even worthy of being used for small instances. Yeah, there again they both have the same asymptotic complexity. Python is extremely slow for complete enumerations, so you really want to save running time by writing low-level code as soon as possible :-)
</p>
<p>
In the end, one thing to remember : I have no way to prove one is better than the other, but I suspect it is (LP is actually enumerating all the solutions -- with many heuristics -- but it is able to say very early "I do not need to search further in this direction, because reasons that have no graph-theoretic meaning (the relaxed version of my LP) tell me there will be no solution this way). LP are very nice because they are easy to write, but it is very hard to know how efficient they are in practice. And complete enumeration in Python is often a waste of time :-)
</p>
<p>
Note for myself : if I want to lead my war against complexity further, I first need to study it much more :-)
</p>
<p>
Happy new year !
</p>
<p>
Nathann
</p>
TicketjdemeyerWed, 12 Jan 2011 06:33:09 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/9910#comment:15
https://trac.sagemath.org/ticket/9910#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.6.2.alpha0</em>
</li>
</ul>
Ticket