Opened 8 years ago
Closed 8 years ago
#10432 closed enhancement (fixed)
is_directed_acyclic is Cython (--> without NetworX) and its certificates
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | graph theory | Keywords: | |
Cc: | mvngu | Merged in: | sage-4.6.2.alpha3 |
Authors: | Nathann Cohen | Reviewers: | Robert Miller |
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 :
sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 376 µs per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 375 µs per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 388 µs per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 380 µs per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 383 µs per loop sage: g = random_acyclic(100, .2) sage: %timeit g.is_directed_acyclic() 625 loops, best of 3: 380 µs per loop
Nathann
Requires #10435
Attachments (1)
Change History (10)
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_work
comment:2 Changed 8 years ago by
- Cc mvngu added
comment:3 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:4 Changed 8 years ago by
- Description modified (diff)
comment:5 Changed 8 years ago by
comment:6 Changed 8 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
Looks very good.
Keep Cythonizing graph theory! :)
comment:7 Changed 8 years ago by
- Status changed from positive_review to needs_work
Line 791 of sage/graphs/digraphs.py
should be EXAMPLES:
Changed 8 years ago by
comment:9 Changed 8 years ago by
- Merged in set to sage-4.6.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
updated to pass -testall.. This code was actually used in many places ! I hope they'll like the speedup
:-)
Nathann