Opened 10 years ago

Closed 10 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)

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

Download all attachments as: .zip

Change History (6)

comment:1 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

Here it is !!!

comment:2 Changed 10 years ago by rlm

  • Report Upstream set to N/A
  • Status changed from needs_review to needs_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 10 years ago by ncohen

  • 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 10 years ago by ncohen

comment:4 Changed 10 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:5 Changed 10 years ago by mhansen

  • 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
Note: See TracTickets for help on using tickets.