Sage: Ticket #7364: Eulerian orientation of a graph
https://trac.sagemath.org/ticket/7364
<p>
Implements Graph.eulerian_orientation which returns a <a class="missing wiki">DiGraph?</a> corresponding to an eulerian orientation of the graph :
</p>
<p>
An eulerian orientation of an eulerian graph is an orientation such that
</p>
<pre class="wiki">d^{+} = d^{-} = d/2
</pre><p>
for any vertex.
</p>
<p>
If the graph is not eulerian, this method returns a <a class="missing wiki">DiGraph?</a> such that
</p>
<pre class="wiki">d^{+} + d^{-} = d
</pre><p>
and
</p>
<pre class="wiki">| d^{+} - d^{-} | <= 1
</pre><p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7364
Trac 1.1.6ncohenSat, 31 Oct 2009 20:48:47 GMTdescription changed
https://trac.sagemath.org/ticket/7364#comment:1
https://trac.sagemath.org/ticket/7364#comment:1
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/7364?action=diff&version=1">diff</a>)
</li>
</ul>
TicketncohenSat, 31 Oct 2009 20:49:34 GMTdescription changed
https://trac.sagemath.org/ticket/7364#comment:2
https://trac.sagemath.org/ticket/7364#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/7364?action=diff&version=2">diff</a>)
</li>
</ul>
TicketncohenSat, 31 Oct 2009 20:49:51 GMTdescription changed
https://trac.sagemath.org/ticket/7364#comment:3
https://trac.sagemath.org/ticket/7364#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/7364?action=diff&version=3">diff</a>)
</li>
</ul>
TicketncohenSun, 01 Nov 2009 10:57:50 GMTstatus, description changed
https://trac.sagemath.org/ticket/7364#comment:4
https://trac.sagemath.org/ticket/7364#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/7364?action=diff&version=4">diff</a>)
</li>
</ul>
TicketncohenSun, 01 Nov 2009 10:58:34 GMTsummary changed
https://trac.sagemath.org/ticket/7364#comment:5
https://trac.sagemath.org/ticket/7364#comment:5
<ul>
<li><strong>summary</strong>
changed from <em>Implement eulerian orientation of a graph</em> to <em>Eulerian orientation of a graph</em>
</li>
</ul>
TickethivertSun, 22 Nov 2009 18:40:19 GMTreviewer, upstream set
https://trac.sagemath.org/ticket/7364#comment:6
https://trac.sagemath.org/ticket/7364#comment:6
<ul>
<li><strong>reviewer</strong>
set to <em>Florent Hivert</em>
</li>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
</ul>
<p>
Hi Nathann
</p>
<p>
Patch looks good. All tests passed! I'm ready to put a Positive review.
</p>
<p>
However, I'm not a graph expert so I've no idea how clever is the algorithm.
So maybe it should be reviewed by a graph expert. Speaking about clever algorithm, if the complexity is known and in particular if it's known to be optimal or not, it could be a good idea to put a "..note:" in the doc giving this information. Of course the preceding remarks apply to any graph algorithm (and even to any algorithm). So maybe you want to put a positive review anyway.
</p>
<p>
Cheers,
</p>
<p>
Florent
</p>
TicketncohenSun, 22 Nov 2009 19:08:21 GMT
https://trac.sagemath.org/ticket/7364#comment:7
https://trac.sagemath.org/ticket/7364#comment:7
<p>
From the "complexity" point of view, this algorithm is linear in the number of edges in the graph, so I think it could be filed as "optimal".
</p>
<p>
From the "practical" point of view, I do not think it would be easy to improve, though I am more and more thinking about trying to write such methods in C rather than in Python... Most of the time in these algorithms is spent on Python considerations rather than on actual Graph computations...
</p>
<p>
I am sending a mail to sage-devel about your great idea of a general "Complexity" note in algorithms.
</p>
<p>
Nathann
</p>
TicketrlmSun, 22 Nov 2009 19:55:04 GMT
https://trac.sagemath.org/ticket/7364#comment:8
https://trac.sagemath.org/ticket/7364#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7364#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<p>
... though I am more and more thinking about trying to write such methods in C rather than in Python... Most of the time in these algorithms is spent on Python considerations rather than on actual Graph computations...
</p>
</blockquote>
<p>
You should use Sage's c_graphs directly: this will eliminate Python noise without forcing you to use pure C. Check out <code>sage/graphs/graph_fast.pyx</code> for an example...
</p>
TicketrlmSun, 22 Nov 2009 20:00:17 GMT
https://trac.sagemath.org/ticket/7364#comment:9
https://trac.sagemath.org/ticket/7364#comment:9
<p>
Sorry, I should have pointed you to <code>sage/graphs/trees.pyx</code> for a good example. It all starts with either
<code>from sage.graphs.base.sparse_graph cimport SparseGraph</code>
or
<code>from sage.graphs.base.dense_graph cimport DenseGraph</code>
</p>
TickethivertMon, 23 Nov 2009 00:47:45 GMT
https://trac.sagemath.org/ticket/7364#comment:10
https://trac.sagemath.org/ticket/7364#comment:10
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7364#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<p>
From the "complexity" point of view, this algorithm is linear in the number of edges in the graph, so I think it could be filed as "optimal".
</p>
<p>
From the "practical" point of view, I do not think it would be easy to improve, though I am more and more thinking about trying to write such methods in C rather than in Python... Most of the time in these algorithms is spent on Python considerations rather than on actual Graph computations...
</p>
</blockquote>
<p>
If the complexity is optimal, going from python to C will only improve the speed by a constant factor. Be sure it's really worth it before spending to much time. I'm a little extreme on this, but is it worth spending hours of researchears time, where we can spend money for a faster computer ? ;-)
</p>
<p>
Note: this does *not* mean I'm not trying to improve the speed of my code ! It only means that a good algorithm is an slow language is much better than a bad algorithm in a fast language. When needed the first is much easier to improve. I'm generally reluctant towards premature optimization.
</p>
<p>
Cheers,
</p>
<p>
Florent
</p>
TicketncohenMon, 23 Nov 2009 06:57:55 GMT
https://trac.sagemath.org/ticket/7364#comment:11
https://trac.sagemath.org/ticket/7364#comment:11
<p>
To Robert : Thank you very much !!!! I'll definitely give it a look ! But you make it sound like I would then have to work on a new graph rather than use the Python one ! In this case, I do not really need to create a new graph but I would like the functions "get an edge coming out of this vertex" and "tell me where it goes" to be extremely fast... When will the default Sage Graph the be C ones ?
</p>
<p>
To Florent : I'm aware this only means changing a "factor", but I am living among computer scientists who find it extremely hard to stop thinking like "it is NP-complete : there is no algooorithm to solve it". And I swear I did not forget the word "polynomial". At some point I also wanted to write an algorithm ion Sage to compute the crossign number of a graph. Bruce Reed published a Linear Time algorithm for this problem, using Graph Minor theory. The result is a (2<sup>2</sup>2<sup>2</sup>2<sup>2</sup>2<sup>2.... ) * n algorithm which no one can implement, even less use. That's why I prefer mentionning the "two". Besides, one of the reasons people in my lab keep from really switching to Sage is that they currently use Java, which is way faster. ( of course they have less algorithms, of course they miss many things, but Still, it is faster )
</sup></p>
<p>
I'll update this patch today !
</p>
<p>
Nathann
</p>
TicketncohenMon, 23 Nov 2009 07:00:49 GMT
https://trac.sagemath.org/ticket/7364#comment:12
https://trac.sagemath.org/ticket/7364#comment:12
<p>
I actually wrote 2<sup>{2</sup>{2<sup>{2</sup>{2<sup>{...}}}}*n.
</sup></p>
TicketncohenMon, 23 Nov 2009 07:01:30 GMT
https://trac.sagemath.org/ticket/7364#comment:13
https://trac.sagemath.org/ticket/7364#comment:13
<p>
My god. I wrote what is called a "tower of exponentials". :-p
</p>
TicketncohenMon, 23 Nov 2009 12:42:35 GMT
https://trac.sagemath.org/ticket/7364#comment:14
https://trac.sagemath.org/ticket/7364#comment:14
<p>
This patch should suit you :-)
</p>
<p>
Nathann
</p>
TickethivertMon, 23 Nov 2009 15:28:28 GMT
https://trac.sagemath.org/ticket/7364#comment:15
https://trac.sagemath.org/ticket/7364#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7364#comment:14" title="Comment 14">ncohen</a>:
</p>
<blockquote class="citation">
<p>
This patch should suit you :-)
</p>
</blockquote>
<p>
I'm really sorry to bother you again:
</p>
<blockquote class="citation">
<p>
This algorithm has complexity <code>O(m)</code>.
</p>
</blockquote>
<p>
Is this a standard in graph theory to call 'm' the number of ??? Actually what ? Edge, Vertex or sum of Both... Maybe this is obvious but better explicit than implicit ;-)
</p>
<p>
I promiss I'll give you a positive review after that !
</p>
TicketncohenMon, 23 Nov 2009 15:35:24 GMT
https://trac.sagemath.org/ticket/7364#comment:16
https://trac.sagemath.org/ticket/7364#comment:16
<p>
Done ! :-)
</p>
TicketncohenMon, 23 Nov 2009 15:35:38 GMTattachment set
https://trac.sagemath.org/ticket/7364
https://trac.sagemath.org/ticket/7364
<ul>
<li><strong>attachment</strong>
set to <em>trac_7364.patch</em>
</li>
</ul>
TickethivertMon, 23 Nov 2009 16:33:44 GMTstatus changed
https://trac.sagemath.org/ticket/7364#comment:17
https://trac.sagemath.org/ticket/7364#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Ok ! Ready to go !
</p>
TicketmhansenSun, 29 Nov 2009 05:24:11 GMTstatus changed; resolution, merged, author set
https://trac.sagemath.org/ticket/7364#comment:18
https://trac.sagemath.org/ticket/7364#comment:18
<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.3.alpha1</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
Ticket