Eulerian orientation of a graph

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

Component: graph theory

Author: Nathann Cohen

Reviewer: Florent Hivert

Merged: sage-4.3.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/7364

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1,7 +1,7 @@
 Implement a method in Graph returning a DiGraph which corresponds 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.
+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 should return a DiGraph such that d^+ + d^- = d and | d^+ - d^- | <= 1
+If the graph is not eulerian, this method should return a DiGraph such that d^{+} + d^{-} = d and | d^{+} - d^{-} | <= 1

 Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1,7 +1,20 @@
 Implement a method in Graph returning a DiGraph which corresponds 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.
+An eulerian orientation of an eulerian graph is an orientation such that 

-If the graph is not eulerian, this method should return a DiGraph such that d^{+} + d^{-} = d and | d^{+} - d^{-} | <= 1
+```
+d^{+} = d^{-} = d/2 
+```
+for any vertex.
+
+If the graph is not eulerian, this method should return a DiGraph such that 
+
+```
+d^{+} + d^{-} = d }}}
+and 
+{{{
+| d^{+} - d^{-} | <= 1
+}}}

 Nathann
+```

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -10,11 +10,12 @@
 If the graph is not eulerian, this method should return a DiGraph such that 

-d^{+} + d^{-} = d }}} +d^{+} + d^{-} = d + and -{{{ + + | d^{+} - d^{-} | <= 1 -}}} +```

Nathann -```

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Implement a method in Graph returning a DiGraph which corresponds to an eulerian orientation of the graph.
+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 

@@ -7,7 +7,7 @@

for any vertex.

-If the graph is not eulerian, this method should return a DiGraph such that +If the graph is not eulerian, this method returns a DiGraph such that

 d^{+} + d^{-} = d 

[hivert]

Reviewer: Florent Hivert

[hivert]

comment:6

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

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

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

comment:8

Replying to @nathanncohen:

... 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...

[89c6e537-b2e3-45e6-882d-d4957b74ffe5]

comment:9

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

[hivert]

comment:10

Replying to @nathanncohen:

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:11

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.... ) * 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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:13

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:14

This patch should suit you :-)

Nathann

[hivert]

comment:15

Replying to @nathanncohen:

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 !

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:16

Done ! :-)

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Attachment: trac_7364.patch.gz

[hivert]

comment:17

Ok ! Ready to go !

[mwhansen]

Merged: sage-4.3.alpha1

[mwhansen]

Author: Nathann Cohen