Changes between Initial Version and Version 1 of Ticket #26941


Ignore:
Timestamp:
12/22/18 12:43:55 (20 months ago)
Author:
dcoudert
Comment:

New commits:

0a24c03trac #26941: improve _build_flow_graph

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #26941

    • Property Status changed from new to needs_review
    • Property Commit changed from to 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd
    • Property Branch changed from to public/26941_build_flow_graph
  • Ticket #26941 – Description

    initial v1  
    1 We use method `is_directed_acyclic` to search for cycles instead of computing shortest paths. This should have been done long ago as it's faster this way.
     1We 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.
     2
     3Before:
     4{{{
     5sage: D = digraphs.TransitiveTournament(10)
     6sage: D.add_edges((i+1, i) for i in range(9))
     7sage: flow = {e: 1 for e in D.edge_iterator(labels=0)}
     8sage: %time F = D._build_flow_graph(flow, False)
     9CPU times: user 1.45 ms, sys: 320 µs, total: 1.77 ms
     10Wall time: 1.55 ms
     11}}}
     12
     13After:
     14{{{
     15sage: D = digraphs.TransitiveTournament(10)
     16sage: D.add_edges((i+1, i) for i in range(9))
     17sage: flow = {e: 1 for e in D.edge_iterator(labels=0)}
     18sage: %time F = D._build_flow_graph(flow, False)
     19CPU times: user 958 µs, sys: 244 µs, total: 1.2 ms
     20Wall time: 1.02 ms
     21}}}