Opened 9 years ago

Closed 9 years ago

#13362 closed defect (fixed)

Fix bug in build_flow_graph

Reported by: dcoudert Owned by: jason, ncohen, rlm
Priority: critical Milestone: sage-5.4
Component: graph theory Keywords:
Cc: ncohen 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 dcoudert 9 years ago.
with doctests

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 years ago by dcoudert

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by dcoudert

  • Type changed from PLEASE CHANGE to defect

comment:3 Changed 9 years ago by dcoudert

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

comment:4 Changed 9 years ago by 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 9 years ago by dcoudert

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 9 years ago by dcoudert

with doctests

comment:6 Changed 9 years ago by dcoudert

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 9 years ago by ncohen

  • Reviewers set to Keshav Kini, Nathann Cohen
  • Status changed from needs_review to positive_review

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

Nathann

comment:8 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.4.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.