Opened 2 years ago
Closed 2 years ago
#26941 closed enhancement (fixed)
improve method _build_flow_graph
Reported by: | dcoudert | 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 2 years ago by
- Branch set to public/26941_build_flow_graph
- Commit set to 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 2 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to positive_review
This seems like a better approach (at least it makes the code more natural). So LGTM.
comment:3 Changed 2 years ago by
- Branch changed from public/26941_build_flow_graph to 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
New commits:
trac #26941: improve _build_flow_graph