# Ticket #10432(closed enhancement: fixed)

Opened 2 years ago

## is_directed_acyclic is Cython (--> without NetworX) and its certificates

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-4.6.2 graph theory mvngu N/A Robert Miller Nathann Cohen sage-4.6.2.alpha3

### Description (last modified by ncohen) (diff)

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

## Change History

### comment:1 Changed 2 years ago by ncohen

• Status changed from new to needs_work
• Description modified (diff)

### comment:2 Changed 2 years ago by mvngu

• Cc mvngu added

### comment:3 Changed 2 years ago by rlm

• Status changed from needs_work to needs_review
• Description modified (diff)

### comment:4 Changed 2 years ago by ncohen

• Description modified (diff)

### comment:5 Changed 2 years ago by ncohen

updated to pass -testall.. This code was actually used in many places ! I hope they'll like the speedup :-)

Nathann

### comment:6 Changed 2 years ago by rlm

• Status changed from needs_review to positive_review
• Reviewers set to Robert Miller
• Milestone changed from sage-4.6.1 to sage-4.6.2

Looks very good.

Keep Cythonizing graph theory! :)

### comment:7 Changed 2 years ago by jdemeyer

• Status changed from positive_review to needs_work

Line 791 of sage/graphs/digraphs.py should be EXAMPLES:

### comment:8 Changed 2 years ago by ncohen

• Status changed from needs_work to positive_review

Done.

Nathann

### comment:9 Changed 2 years ago by jdemeyer

• Status changed from positive_review to closed
• Resolution set to fixed
• Merged in set to sage-4.6.2.alpha3
Note: See TracTickets for help on using tickets.