Opened 10 years ago

Closed 10 years ago

#13362 closed defect (fixed)

Fix bug in build_flow_graph

Reported by: David Coudert Owned by: jason, ncohen, rlm
Priority: critical Milestone: sage-5.4
Component: graph theory Keywords:
Cc: Nathann Cohen Merged in: sage-5.4.beta2
Authors: David Coudert Reviewers: Keshav Kini, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The function build_flow_graph (called by the flow function) contains a

g.set_edge_label(l)

instead of

g.set_edge_label(sp[i],sp[i+1],l) 

where l is a number.

Attachments (1)

trac_13362.patch (2.5 KB) - added by David Coudert 10 years ago.
with doctests

Download all attachments as: .zip

Change History (9)

comment:1 Changed 10 years ago by David Coudert

Status: newneeds_review

comment:2 Changed 10 years ago by David Coudert

Type: PLEASE CHANGEdefect

comment:3 Changed 10 years ago by David Coudert

The patch is working for both sage-5.3.beta0 and sage-5.3.beta1.

comment:4 Changed 10 years ago by Keshav Kini

It looks like the call you replaced is just completely broken and would throw TypeError when executed. I assume that this wasn't caught by a doctest. Could you write a doctest which goes through this code path?

comment:5 Changed 10 years ago by David Coudert

It wasn't in the doctests. In fact the existence of 0-cost cycles in flows depends on the LP solver and the instance. Some LP solver simplifies the solution returning the minimum possible number of non zero variables.

I added some very artificial doctests, but it does the job.

Changed 10 years ago by David Coudert

Attachment: trac_13362.patch added

with doctests

comment:6 Changed 10 years ago by David Coudert

every lines of the _build_flow_graph method have trailing white spaces. This is super boring!!! I have only removed those from edited lines, but I'm eager to remove all of them...

comment:7 Changed 10 years ago by Nathann Cohen

Reviewers: Keshav Kini, Nathann Cohen
Status: needs_reviewpositive_review

Well, then if doctests pass and the bug is fixed... :-)

Nathann

comment:8 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.4.beta2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.