Strong orientations of 2-connected graphs

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

A special case of #7303 ( which is much easier and efficient to implement ) is to find a strongly connected orientation of the edges of a bridgeless connected graph.

This can be done using the short algorithm given in : Schriver Combinatorial optimization Volume B page 1037

Component: graph theory

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.rc1

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

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

comment:1

Here it is !!!

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

comment:2

1. You need to describe what a strongly connected orientation is in your docstrings.

2. You also need to clearly describe the output, i.e. what type of object is it...

3. The function shouldn't assume but rather check whether the necessary conditions are met, and print a helpful error message if they aren't. If you're concerned about speed, then you can make use of a check=False option.

Other than these minor issues, the patch applies and passes tests, and looks good.

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

comment:3

I added a definition of both "orientation" and "strong", plsu a reference to the wikipedia page, and described the output. This function is actually useful in both situations ( when the graph is not 2-connected, or when it is ), so I removed "of a 2-connected graph" in the first sentence of the docstring : it is explicitely written later that if the graph is not 2-connected, the result will be "as best as can be hoped for" in this situation ( and I assure you this part of the function is useful by itself :-) )

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

Author: Nathann Cohen

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

comment:4

Attachment: trac_7358.patch.gz

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

Reviewer: Robert Miller

[mwhansen]

Merged: sage-4.3.rc1