Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#7292 closed enhancement (fixed)

Max Vertex/Edge disjoint st-paths

Reported by: ncohen Owned by: rlm
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:

Description (last modified by ncohen)

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 ncohen 9 years ago.
trac_7292-2.patch (3.7 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)
  • Report Upstream set to N/A

comment:2 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:3 Changed 9 years ago by rlm

  • Status changed from needs_review to needs_work

vertex_disjoint_paths loops forever...

comment:4 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

not anymore :-)

Changed 9 years ago by ncohen

comment:5 Changed 9 years ago by rlm

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

comment:6 Changed 9 years ago by mhansen

  • Status changed from positive_review to needs_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 9 years ago by ncohen

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

  • Status changed from needs_work to needs_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 9 years ago by rlm

  • Status changed from needs_review to needs_work
  • Work issues set to needs rebase (#7634)

comment:10 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Rebased !

Nathann

Changed 9 years ago by ncohen

comment:11 Changed 9 years ago by rlm

  • Merged in set to 4.3.1.alpha2
  • Resolution set to fixed
  • Status changed from needs_review to closed

positive review

comment:12 Changed 9 years ago by mvngu

  • Merged in changed from 4.3.1.alpha2 to sage-4.3.1.alpha2
Note: See TracTickets for help on using tickets.