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:

Status badges

Description (last modified by ncohen)

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 ncohen

  • Description modified (diff)
  • Status changed from new to needs_work
Note: See TracTickets for help on using tickets.