Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#7292 closed enhancement (fixed)

Max Vertex/Edge disjoint st-paths

Reported by: Nathann Cohen Owned by: Robert Miller
Priority: major Milestone: sage-4.3.1
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.1.alpha2
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues: needs rebase (#7634)
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Nathann Cohen)

With the flow function from #7592, functions returning a maximal number of Vertex/Edge? disjoint st-path should be defined. The will obviously use the flow functions, but in many applications the user is just interested in these paths, and so there should be an easy way to find them in Sage.

Attachments (2)

trac_7292.patch (3.0 KB) - added by Nathann Cohen 13 years ago.
trac_7292-2.patch (3.7 KB) - added by Nathann Cohen 13 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 13 years ago by Nathann Cohen

Description: modified (diff)
Report Upstream: N/A

comment:2 Changed 13 years ago by Nathann Cohen

Status: newneeds_review

comment:3 Changed 13 years ago by Robert Miller

Status: needs_reviewneeds_work

vertex_disjoint_paths loops forever...

comment:4 Changed 13 years ago by Nathann Cohen

Status: needs_workneeds_review

not anymore :-)

Changed 13 years ago by Nathann Cohen

Attachment: trac_7292.patch added

comment:5 Changed 13 years ago by Robert Miller

Authors: Nathann Cohen
Reviewers: Robert Miller
Status: needs_reviewpositive_review

comment:6 Changed 13 years ago by Mike Hansen

Status: positive_reviewneeds_work

I get the following failure:

**********************************************************************
File "/scratch/mhansen/release/4.3/rc1/sage-4.3.rc1/devel/sage-main/sage/graphs/graph.py", line 3581:
    sage: g.vertex_cover(value_only=True)
Expected:
    9
Got nothing
**********************************************************************

comment:7 Changed 13 years ago by Nathann Cohen

This is because of an odd thing : when this patch is applied over #7600, the body of vertex_cover totally disappears : only the docstring remains, and the function returns nothing. I will send an updated version of the patch "after" #7600 has been applied :-)

comment:8 Changed 13 years ago by Nathann Cohen

Status: needs_workneeds_review

Here it is !!

Please check, when appying it, that nothing disappears "above" and "after" the added sections ! If this version is not easier to apply, I think the best way would be to create a patch based upon the version you are working on and the patch you already applied (this should not be long though, this patch just adds two consecutive functions)

Sorry for the trouble ! :-)

Nathann

comment:9 Changed 13 years ago by Robert Miller

Status: needs_reviewneeds_work
Work issues: needs rebase (#7634)

comment:10 Changed 13 years ago by Nathann Cohen

Status: needs_workneeds_review

Rebased !

Nathann

Changed 13 years ago by Nathann Cohen

Attachment: trac_7292-2.patch added

comment:11 Changed 13 years ago by Robert Miller

Merged in: 4.3.1.alpha2
Resolution: fixed
Status: needs_reviewclosed

positive review

comment:12 Changed 13 years ago by Minh Van Nguyen

Merged in: 4.3.1.alpha2sage-4.3.1.alpha2
Note: See TracTickets for help on using tickets.