Opened 10 years ago
Last modified 10 years ago
#10432 closed enhancement
is_directed_acyclic is Cython (--> without NetworX) and its certificates — at Version 1
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | graph theory | Keywords: | |
Cc: | mvngu | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch contains an Cython implementation of a method testing whether a given digraph is acyclic. If it is, the method returns a topological sort, and returns a circuit otherwise. The method is then called through current Sage methods which relied on NetworkX
def random_acyclic(n, p): ... g = graphs.RandomGNP(n, p) ... h = DiGraph() ... h.add_edges([ ((u,v) if u<v else (v,u)) for u,v,_ in g.edges() ]) ... return h
Before :
sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 125 loops, best of 3: 6.54 ms per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 125 loops, best of 3: 6.79 ms per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 125 loops, best of 3: 6.72 ms per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 125 loops, best of 3: 6.96 ms per loop
After :
g = random_acyclic(100, .2) %timeit g.is_directed_acyclic()
Nathann
Change History (1)
comment:1 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_work
Note: See
TracTickets for help on using
tickets.