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 ncohen)

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)

trac_7364.patch (3.9 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:4 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:5 Changed 9 years ago by ncohen

  • Summary changed from Implement eulerian orientation of a graph to Eulerian orientation of a graph

comment:6 Changed 9 years ago by hivert

  • Report Upstream set to N/A
  • Reviewers set to Florent Hivert

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

comment:7 follow-ups: Changed 9 years ago by 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...

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 rlm

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 rlm

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 hivert

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 ncohen

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 (22222222.... ) * 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 ncohen

I actually wrote 2{2{2{2{2{...}}}}*n.

comment:13 Changed 9 years ago by ncohen

My god. I wrote what is called a "tower of exponentials". :-p

comment:14 follow-up: Changed 9 years ago by ncohen

This patch should suit you :-)

Nathann

comment:15 in reply to: ↑ 14 Changed 9 years ago by hivert

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 ncohen

Done ! :-)

Changed 9 years ago by ncohen

comment:17 Changed 9 years ago by hivert

  • Status changed from needs_review to positive_review

Ok ! Ready to go !

comment:18 Changed 9 years ago by mhansen

  • Authors set to Nathann Cohen
  • Merged in set to sage-4.3.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.