Opened 8 years ago

Closed 8 years ago

#11046 closed enhancement (fixed)

Some comments in the code of SparseGraph

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: trivial Milestone: sage-4.7
Component: graph theory Keywords:
Cc: rlm Merged in: sage-4.7.alpha5
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

I was reading this code to understand a bit better how the SparseGraph? backend worked (as it is the default one in Sage), and added comments while I was at it. I also replaced some loops initializing values by a memset, as it is usually faster. This produces next-to-zero improvement in Sage, but well.. :-)

Before :

625 loops, best of 3: 1.26 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.47 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.25 ms per loop
sage: %timeit Graph(100)
625 loops, best of 3: 94.7 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 98.8 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.8 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.2 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 96.6 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 95.2 µs per loop

After

sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.21 ms per loop
sage: %timeit Graph(10000)
625 loops, best of 3: 1.15 ms per loop
sage: %timeit Graph(100)
625 loops, best of 3: 94.5 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 92.7 µs per loop
sage: %timeit Graph(100)
625 loops, best of 3: 93.5 µs per loop

By the way Robert, this is all mostly about touching your code and adding comments, and as I am trespassing I expect you may not like some of those :-)

Nathann

Attachments (1)

trac_11046.patch (10.2 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 8 years ago by ncohen

  • Cc rlm added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by rlm

  • Status changed from needs_review to needs_work

Nathann,

I'm happy with this patch except for one thing: I'd like you to change each added occurrence of the word "edge" to "arc" in the SparseGraph? code. The reason being that SparseGraphs? are never directed as implemented, and I think using the word arc helps keep this clear throughout.

Otherwise it looks fine to me. Any extra explanation of the rather complicated SparseGraph? structure will be helpful, I think.

comment:3 Changed 8 years ago by ncohen

+1 ! An old patch of mine was refused once because I was told "We stick to the terminology "edge" instead of arc". I completely agree with you on that one :-D

Nathann

Changed 8 years ago by ncohen

comment:4 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

Patch updated... I have been thinking about the graph structure for a while now... I have had to write some C code for a fast computation of "all pairs distance" (did you get my email about it ?), and I had to quickly redefine a Graph in C which lists all of its edges in a contiguous memory area so that it is optimal to list all edges of a graph. I also thought that because of the lack of red/black trees you mentionned in that code, your good implementation is badly misused : very often the edges of a graph are added in "lexicographical order", and in this case all your trees are actually linked lists.... But I need to think a bit more before coming up with a good solution :-)

Nathann

comment:5 Changed 8 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:6 Changed 8 years ago by jdemeyer

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