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 changed from new to needs_review
comment:2 Changed 13 years ago by
- Report Upstream set to N/A
- Status changed from needs_review to 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 changed from needs_work to 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
comment:4 Changed 13 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:5 Changed 13 years ago by
- Merged in set to sage-4.3.rc1
- Milestone changed from sage-4.3.1 to sage-4.3
- Resolution set to fixed
- Status changed from positive_review to closed
Here it is !!!