Max Vertex/Edge disjoint st-paths

[nathanncohen]

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.

Component: graph theory

Work Issues: needs rebase (#7634)

Author: Nathann Cohen

Reviewer: Robert Miller

Merged: sage-4.3.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/7292

[rlmill]

comment:3

vertex_disjoint_paths loops forever...

[nathanncohen]

comment:4

not anymore :-)

[rlmill]

Author: Nathann Cohen

[rlmill]

comment:5

Attachment: trac_7292.patch.gz

[rlmill]

Reviewer: Robert Miller

[mwhansen]

comment:6

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
**********************************************************************

[nathanncohen]

comment:7

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 :-)

[nathanncohen]

comment:8

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

[rlmill]

Work Issues: needs rebase (#7634)

[nathanncohen]

comment:10

Rebased !

Nathann

[rlmill]

Merged: 4.3.1.alpha2

[rlmill]

comment:11

Attachment: trac_7292-2.patch.gz

positive review

[sagetrac-mvngu]

Changed merged from 4.3.1.alpha2 to sage-4.3.1.alpha2