Opened 13 years ago

Closed 13 years ago

#7358 closed enhancement (fixed)

Strong orientations of 2-connected graphs

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

GitHub link to the corresponding issue


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

Attachments (1)

trac_7358.patch (4.0 KB) - added by ncohen 13 years ago.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 13 years ago by ncohen

Status: newneeds_review

Here it is !!!

comment:2 Changed 13 years ago by rlm

Report Upstream: N/A
Status: needs_reviewneeds_work
  1. You need to describe what a strongly connected orientation is in your docstrings.
  1. You also need to clearly describe the output, i.e. what type of object is it...
  1. 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.

comment:3 Changed 13 years ago by ncohen

Status: needs_workneeds_review

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

Changed 13 years ago by ncohen

Attachment: trac_7358.patch added

comment:4 Changed 13 years ago by rlm

Authors: Nathann Cohen
Reviewers: Robert Miller
Status: needs_reviewpositive_review

comment:5 Changed 13 years ago by mhansen

Merged in: sage-4.3.rc1
Milestone: sage-4.3.1sage-4.3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.