Opened 4 years ago

Closed 4 years ago

#17163 closed defect (fixed)

Speed improvement for DiGraph.in_degree

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: graph theory Keywords:
Cc: jmantysalo Merged in:
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 0bcb1b7 (Commits) Commit: 0bcb1b78e32614db88ea00658caf986eff07a3f1
Dependencies: Stopgaps:

Description

As reported by Jori, the following is... unexpected:

sage: g = digraphs.RandomDirectedGNP(300,.2)
sage: %timeit g.sinks() # vertices of outdegree 0
1000 loops, best of 3: 376 µs per loop
sage: %timeit g.sources() # vertices of indegree 0
100 loops, best of 3: 7.78 ms per loop

With this patch:

sage: g = digraphs.RandomDirectedGNP(300,.2)      
sage: %timeit g.sinks() # vertices of outdegree 0 
1000 loops, best of 3: 370 µs per loop
sage: %timeit g.sources() # vertices of indegree 0
1000 loops, best of 3: 361 µs per loop

Cause:

This is because the function in_degree was not implemented at the data structure level, but "abstractly" by iterating over all incoming edges of a vertices and counting them. This is bad, especially since any sensible backends already stores that information.

What the branch does:

1) Add a in_degree function in the CGraph backend.

2) Add a in_degree and out_degree (empty) function in the GenericGraph backend (the only point is to write somewhere that the in_degree/out_degree functions should be implemented by all graph backends

3) Add a in_degree/out_degree function to the NetworkX backend. This backend is only used in one doctest, and this is the only backend that did not have this function.

4) Because all backends now have the in_degree/out_degree functions, it is now useless to 'check if the backend has the function' before calling it. As a result the code of DiGraph.in_degree/out_degree is simplified.

Nathann

Change History (9)

comment:1 Changed 4 years ago by ncohen

  • Branch set to u/ncohen/17163
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 303ad6cc6643b491f160b539c0750153a8158486

Branch pushed to git repo; I updated commit sha1. New commits:

303ad6ctrac #17163: Speed improvement for DiGraph.in_degree

comment:3 Changed 4 years ago by jmantysalo

Seems to work; now top() and bottom() on posets take same time. This also explains why timings with #13223 where little strange.

Unfortunately I don't know enought Sage to be able to really review this.

comment:4 follow-up: Changed 4 years ago by dcoudert

  • Reviewers set to David Coudert

The patch is working well. However, there are several places in src/sage/graphs/base/c_graph.pyx where you have such instruction (this one from your patch):

cdef v_int = get_vertex(v,
                        self.vertex_ints,
                        self.vertex_labels,
                        self._cg)

Shouldn't you specify the int type ?

comment:5 Changed 4 years ago by git

  • Commit changed from 303ad6cc6643b491f160b539c0750153a8158486 to 0bcb1b78e32614db88ea00658caf986eff07a3f1

Branch pushed to git repo; I updated commit sha1. New commits:

c51510ftrac #17163: Merged with beta6
0bcb1b7trac #17163: missing 'int'

comment:6 in reply to: ↑ 4 Changed 4 years ago by ncohen

Shouldn't you specify the int type ?

Indeed. I just did, thanks.

Nathann

comment:7 Changed 4 years ago by dcoudert

  • Status changed from needs_review to positive_review

All tests pass on src/sage/graphs/, so I give positive review.

comment:8 Changed 4 years ago by ncohen

Thanks !

Nathann

comment:9 Changed 4 years ago by vbraun

  • Branch changed from u/ncohen/17163 to 0bcb1b78e32614db88ea00658caf986eff07a3f1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.