Flow, Matching, Connectivity, and some Hard problems

[nathanncohen]

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/

CC: @sagetrac-tombuc

Component: graph theory

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

[williamstein]

comment:2

test

[nathanncohen]

comment:8

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

[nathanncohen]

comment:9

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

[nathanncohen]

comment:13

Attachment: graphfunctions-1.patch.gz

I am splitting this ticket into smallers ones

[nathanncohen]

comment:14

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.

[nathanncohen]

comment:15

Let's say :

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