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: |
Description
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)
Change History (6)
comment:1 Changed 13 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 13 years ago by
Report Upstream: | → N/A |
---|---|
Status: | needs_review → needs_work |
- You need to describe what a strongly connected orientation is in your docstrings.
- You also need to clearly describe the output, i.e. what type of object is it...
- 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
Status: | needs_work → needs_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
Attachment: | trac_7358.patch added |
---|
comment:4 Changed 13 years ago by
Authors: | → Nathann Cohen |
---|---|
Reviewers: | → Robert Miller |
Status: | needs_review → positive_review |
comment:5 Changed 13 years ago by
Merged in: | → sage-4.3.rc1 |
---|---|
Milestone: | sage-4.3.1 → sage-4.3 |
Resolution: | → fixed |
Status: | positive_review → closed |
Here it is !!!