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 )
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)
Change History (7)
comment:1 Changed 8 years ago by
- Cc rlm added
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
+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
comment:4 Changed 8 years ago by
- 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
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:6 Changed 8 years ago by
- Merged in set to sage-4.7.alpha5
- Resolution set to fixed
- Status changed from positive_review to closed
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.