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: |

### 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)

### Change History (9)

### comment:1 Changed 10 years ago by

Status: | new → needs_review |
---|

### comment:2 Changed 10 years ago by

Type: | PLEASE CHANGE → defect |
---|

### comment:3 Changed 10 years ago by

### comment:4 Changed 10 years ago by

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

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.

### comment:6 Changed 10 years ago by

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

Reviewers: | → Keshav Kini, Nathann Cohen |
---|---|

Status: | needs_review → positive_review |

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

Nathann

### comment:8 Changed 10 years ago by

Merged in: | → sage-5.4.beta2 |
---|---|

Resolution: | → fixed |

Status: | positive_review → closed |

**Note:**See TracTickets for help on using tickets.

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