Opened 19 months ago

Closed 18 months 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) Commit: 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd
Dependencies: Stopgaps:

Description (last modified by 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

Change History (3)

comment:1 Changed 19 months ago by dcoudert

  • Branch set to public/26941_build_flow_graph
  • Commit set to 0a24c032fc4dccaa5047f352e14ff0429a3cbdfd
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

​0a24c03trac #26941: improve _build_flow_graph

comment:2 Changed 19 months ago by tscrim

  • 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 18 months ago by vbraun

  • 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.