Opened 4 years ago

Closed 4 years ago

## #26941 closed enhancement (fixed)

# improve method _build_flow_graph

Reported by: | David Coudert | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | sage-8.6 |

Component: | graph theory | Keywords: | |

Cc: | Merged in: | ||

Authors: | David Coudert | Reviewers: | Travis Scrimshaw |

Report Upstream: | N/A | Work issues: | |

Branch: | 0a24c03 (Commits, GitHub, GitLab) | Commit: | 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd |

Dependencies: | Stopgaps: |

### Description (last modified by )

We use method `is_directed_acyclic`

to find cycles instead of computing shortest paths. This should have been done long ago as it's faster this way.

Before:

sage: D = digraphs.TransitiveTournament(10) sage: D.add_edges((i+1, i) for i in range(9)) sage: flow = {e: 1 for e in D.edge_iterator(labels=0)} sage: %time F = D._build_flow_graph(flow, False) CPU times: user 1.45 ms, sys: 320 µs, total: 1.77 ms Wall time: 1.55 ms

After:

sage: D = digraphs.TransitiveTournament(10) sage: D.add_edges((i+1, i) for i in range(9)) sage: flow = {e: 1 for e in D.edge_iterator(labels=0)} sage: %time F = D._build_flow_graph(flow, False) CPU times: user 958 µs, sys: 244 µs, total: 1.2 ms Wall time: 1.02 ms

### Change History (3)

### comment:1 Changed 4 years ago by

Branch: | → public/26941_build_flow_graph |
---|---|

Commit: | → 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd |

Description: | modified (diff) |

Status: | new → needs_review |

### comment:2 Changed 4 years ago by

Reviewers: | → Travis Scrimshaw |
---|---|

Status: | needs_review → positive_review |

This seems like a better approach (at least it makes the code more natural). So LGTM.

### comment:3 Changed 4 years ago by

Branch: | public/26941_build_flow_graph → 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd |
---|---|

Resolution: | → fixed |

Status: | positive_review → closed |

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

New commits:

`trac #26941: improve _build_flow_graph`