id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
26941 improve method _build_flow_graph dcoudert "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
}}}" enhancement closed major sage-8.6 graph theory fixed David Coudert Travis Scrimshaw N/A 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd