Changes between Initial Version and Version 1 of Ticket #10432


Ignore:
Timestamp:
12/05/10 18:18:50 (10 years ago)
Author:
ncohen
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #10432

    • Property Status changed from new to needs_work

  • Ticket #10432 – Description

    initial v1  
    11This 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
    22
     3{{{
     4#!python
     5def random_acyclic(n, p):
     6...    g = graphs.RandomGNP(n, p)
     7...    h = DiGraph()
     8...    h.add_edges([ ((u,v) if u<v else (v,u)) for u,v,_ in g.edges() ])
     9...    return h
     10}}}
     11
     12Before :
     13
     14{{{
     15#!python
     16sage: g = random_acyclic(100, .2)
     17sage: %timeit g.is_directed_acyclic()
     18125 loops, best of 3: 6.54 ms per loop
     19sage: g = random_acyclic(100, .2)
     20sage: %timeit g.is_directed_acyclic()
     21125 loops, best of 3: 6.79 ms per loop
     22sage: g = random_acyclic(100, .2)
     23sage: %timeit g.is_directed_acyclic()
     24125 loops, best of 3: 6.72 ms per loop
     25sage: g = random_acyclic(100, .2)
     26sage: %timeit g.is_directed_acyclic()
     27125 loops, best of 3: 6.96 ms per loop
     28}}}
     29
     30After :
     31
     32{{{
     33#!python
     34g = random_acyclic(100, .2)
     35%timeit g.is_directed_acyclic()
     36}}}
     37
    338Nathann