Opened 9 years ago
Closed 9 years ago
#7364 closed enhancement (fixed)
Eulerian orientation of a graph
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.3 |
Component: | graph theory | Keywords: | |
Cc: | Merged in: | sage-4.3.alpha1 | |
Authors: | Nathann Cohen | Reviewers: | Florent Hivert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Implements Graph.eulerian_orientation which returns a DiGraph? corresponding to an eulerian orientation of the graph :
An eulerian orientation of an eulerian graph is an orientation such that
d^{+} = d^{-} = d/2
for any vertex.
If the graph is not eulerian, this method returns a DiGraph? such that
d^{+} + d^{-} = d
and
| d^{+} - d^{-} | <= 1
Nathann
Attachments (1)
Change History (19)
comment:1 Changed 9 years ago by
- Description modified (diff)
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:5 Changed 9 years ago by
- Summary changed from Implement eulerian orientation of a graph to Eulerian orientation of a graph
comment:6 Changed 9 years ago by
- Report Upstream set to N/A
- Reviewers set to Florent Hivert
comment:7 follow-ups: ↓ 8 ↓ 10 Changed 9 years ago by
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...
I am sending a mail to sage-devel about your great idea of a general "Complexity" note in algorithms.
Nathann
comment:8 in reply to: ↑ 7 Changed 9 years ago by
Replying to ncohen:
... 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...
You should use Sage's c_graphs directly: this will eliminate Python noise without forcing you to use pure C. Check out sage/graphs/graph_fast.pyx
for an example...
comment:9 Changed 9 years ago by
Sorry, I should have pointed you to sage/graphs/trees.pyx
for a good example. It all starts with either
from sage.graphs.base.sparse_graph cimport SparseGraph
or
from sage.graphs.base.dense_graph cimport DenseGraph
comment:10 in reply to: ↑ 7 Changed 9 years ago by
Replying to 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
comment:11 Changed 9 years ago by
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 ?
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^{2}2^{2}2^{2}2^{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 ) }
I'll update this patch today !
Nathann
comment:12 Changed 9 years ago by
I actually wrote 2^{{2}{2^{{2}{2^{{...}}}}*n. }
comment:13 Changed 9 years ago by
My god. I wrote what is called a "tower of exponentials". :-p
comment:14 follow-up: ↓ 15 Changed 9 years ago by
This patch should suit you :-)
Nathann
comment:15 in reply to: ↑ 14 Changed 9 years ago by
Replying to ncohen:
This patch should suit you :-)
I'm really sorry to bother you again:
This algorithm has complexity
O(m)
.
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 ;-)
I promiss I'll give you a positive review after that !
comment:16 Changed 9 years ago by
Done ! :-)
Changed 9 years ago by
comment:17 Changed 9 years ago by
- Status changed from needs_review to positive_review
Ok ! Ready to go !
comment:18 Changed 9 years ago by
- Merged in set to sage-4.3.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
Hi Nathann
Patch looks good. All tests passed! I'm ready to put a Positive review.
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.
Cheers,
Florent