Opened 12 years ago

Closed 11 years ago

Last modified 11 years ago

#6680 closed enhancement (duplicate)

Flow, Matching, Connectivity, and some Hard problems

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: tombuc Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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/

Attachments (1)

graphfunctions-1.patch (24.5 KB) - added by ncohen 11 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 12 years ago by was

test

comment:3 Changed 12 years ago by ncohen

  • Summary changed from [with patch, needs review] (uses Linear Programming) to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems (uses Linear Programming)

comment:4 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:5 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:6 Changed 12 years ago by ncohen

  • Description modified (diff)

comment:7 Changed 12 years ago by ncohen

  • Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems (uses Linear Programming) to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems

comment:8 Changed 12 years ago by ncohen

  • Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems to [with patch, needs work] Flow, Matching, Connectivity, and some Hard problems

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

comment:9 Changed 12 years ago by ncohen

  • Description modified (diff)
  • Summary changed from [with patch, needs work] Flow, Matching, Connectivity, and some Hard problems to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems

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

comment:10 Changed 11 years ago by ncohen

  • Cc tombuc added

comment:11 Changed 11 years ago by ncohen

  • Description modified (diff)

comment:12 Changed 11 years ago by ncohen

  • Description modified (diff)

Changed 11 years ago by ncohen

comment:13 Changed 11 years ago by ncohen

  • Report Upstream set to N/A

I am splitting this ticket into smallers ones

comment:14 Changed 11 years ago by ncohen

  • Resolution set to duplicate
  • Status changed from needs_review to closed

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.

comment:15 Changed 11 years ago by 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

comment:16 Changed 11 years ago by mvngu

  • Milestone changed from sage-4.3 to sage-duplicate/invalid/wontfix
  • Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems to Flow, Matching, Connectivity, and some Hard problems
Note: See TracTickets for help on using tickets.