#7364: Eulerian orientation of a graph
----------------------------+-----------------------------------------------
Reporter: ncohen | Owner: rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.3
Component: graph theory | Keywords:
Work_issues: | Author:
Upstream: N/A | Reviewer: Florent Hivert
Merged: |
----------------------------+-----------------------------------------------
Comment(by hivert):
Replying to [comment:7 ncohen]:
> 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".
>
> 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...
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 ? ;-)
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.
Cheers,
Florent
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7364#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=.
