Flow, Matching, Connectivity, and some Hard problems

[ncohen]

Hello everybody !!!

Here are several new functions for the Graph class in Sage :

• def min_dominating_set(g, value_only=False,log=0):
• def min_independent_dominating_set(g, value_only=False,log=0):
• def min_vertex_cover(g,value_only=False,log=0):
• def max_matching(g,value_only=False, use_edge_labels=True):
• def max_flow(g,x,y,value_only=True,integer=False, use_edge_labels=True):
• def min_edge_cut(g,s,t,value_only=True,use_edge_labels=True):
• def min_vertex_cut(g,s,t,value_only=True):
• def edge_connectivity(g,value_only=True,use_edge_labels=True):
• def vertex_connectivity(g,value_only=True):

If you have no LP Solver installed, you can download GLPK or CBC from this address : http://www.sagemath.org/packages/optional/

[was]

test

[ncohen]

As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.

Sorry for the trouble, I'll try to make it quick !

Nathann

[ncohen]

New version attached !! Will put some energy into Sage's graph library ! ;-)

[ncohen]

I am splitting this ticket into smallers ones

[ncohen]

Totally duplicated ! See :

#7592 Flow method using LP #7593 Matching using LP #7594 Dominating set and Independent dominating Set #7599 vertex_cut and edge_cut ( minimum s-t cut ) #7600 Vertex cover #7601 Graph.edge_connectivity #7605 Graph.vertex_connectivity

Can be closed as duplicate.

[ncohen]

Let's say : * #7592 Flow method using LP * #7593 Matching using LP * #7594 Dominating set and Independent dominating Set * #7599 vertex_cut and edge_cut ( minimum s-t cut ) * #7600 Vertex cover * #7601 Graph.edge_connectivity * #7605 Graph.vertex_connectivity