Sage: Ticket #13730: Speed up some graph iterations
https://trac.sagemath.org/ticket/13730
<p>
Several graph methods can be significantly speed up improving the data structure, or at least the way some basic operations are performed.
For instance, many functions are faster using networkx graphs (conversion time included) instead of sage graphs.
</p>
<p>
In fact, NetworkX uses dictionaries to store edges. If G is a networkx graph, it is also a dictionary indexed by the vertices, and G[u] is a dictionary indexed by neighbors and containing edge data. This way, iterations are fast.
</p>
<pre class="wiki">sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
125 loops, best of 3: 1.63 ms per loop
sage: ggnx = G.networkx_graph()
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)]
625 loops, best of 3: 141 µs per loop
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx[u]]
625 loops, best of 3: 127 µs per loop
</pre><p>
We should at least improve iteration over the neighbors.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13730
Trac 1.1.6aziWed, 21 Nov 2012 15:20:36 GMT
https://trac.sagemath.org/ticket/13730#comment:1
https://trac.sagemath.org/ticket/13730#comment:1
<p>
Hello, dcoudert!!
</p>
<p>
First thing that I am wondering is why is sage constructing a set from the iterator and then returns the iterator of the set. Does anyone happen to know that? It does not seem to affect computational speed but I do not see why it is necessary. Anyone happens to know why is set() required in this case?
</p>
<pre class="wiki"> def neighbor_iterator(self, vertex):
if self._directed:
return iter(set(self.neighbor_out_iterator(vertex)) \
| set(self.neighbor_in_iterator(vertex)))
else:
return iter(set(self._backend.iterator_nbrs(vertex))))
</pre>
TicketdcoudertThu, 22 Nov 2012 12:24:16 GMT
https://trac.sagemath.org/ticket/13730#comment:2
https://trac.sagemath.org/ticket/13730#comment:2
<p>
I'm not expert enough in iterators to answer. Furthermore, the backend for graphs also constructs sets:
</p>
<pre class="wiki">def iterator_nbrs(self, v):
return iter(set(self.iterator_in_nbrs(v)) |
set(self.iterator_out_nbrs(v)))
</pre><p>
I don't know the reasons behind but this can certainly be improved/simplified.
</p>
<p>
David.
</p>
TicketaziSat, 24 Nov 2012 12:27:29 GMT
https://trac.sagemath.org/ticket/13730#comment:3
https://trac.sagemath.org/ticket/13730#comment:3
<p>
Agree!
</p>
<p>
It seems like something suspiciously complex is being done in these iterators (lists, to iterators, to sets, to iterators to sets..)
</p>
<p>
I've played around and removed the (intuitively) unneeded parts and observed that there is a minor performance gain.
</p>
<p>
But if we want to be as fast as networkx then we'd need to keep a hash table of neighbors for each vertex.
</p>
<p>
Before trying to implement this - does sage allow graphs with unhashable vertices?
</p>
TicketncohenSat, 24 Nov 2012 23:34:54 GMT
https://trac.sagemath.org/ticket/13730#comment:4
https://trac.sagemath.org/ticket/13730#comment:4
<p>
NOnonono, vertices are hashable or everything would break. I mean, or instance the code you just printed would not work at all !
</p>
<pre class="wiki">sage: set([set([1])])
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/home/ncohen/<ipython console> in <module>()
TypeError: unhashable type: 'set'
</pre><p>
Nathann
</p>
TicketaziFri, 21 Dec 2012 09:50:20 GMT
https://trac.sagemath.org/ticket/13730#comment:5
https://trac.sagemath.org/ticket/13730#comment:5
<p>
Hello guys!
</p>
<p>
I have implemented a stupid "fix" by adding a hash table to the graph object storing neighbours for every vertex of the graph. I then modified the add_edge/delete_edge methods to update the hash table accordingly.
</p>
<p>
The speedup was drastic (as with networkX graphs) and it also speed up other graph theory functions (since many things rely on obtaining the neighbours of some vertices)
</p>
<p>
HOWEVER. Many of the graph theory tests made sage crash which makes uncomfortable in posting the patch here. I am not aware enough of the graph internals to be able to write a sane patch that is not just some naive fix.
</p>
<p>
Hence I call someone that is more experienced with the c_graph implementation to add this feature. It is really really worth doing it!
</p>
TicketdcoudertFri, 21 Dec 2012 13:24:58 GMT
https://trac.sagemath.org/ticket/13730#comment:6
https://trac.sagemath.org/ticket/13730#comment:6
<p>
Hello,
</p>
<p>
you should post your patch so that others can try it and help identifying and fixing the problem. The status of this patch could be "needs work" or "needs info".
</p>
<p>
Best,
David.
</p>
TicketaziSat, 29 Dec 2012 16:15:15 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:7
https://trac.sagemath.org/ticket/13730#comment:7
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
</ul>
TicketslaniThu, 21 Feb 2013 16:53:07 GMTattachment set
https://trac.sagemath.org/ticket/13730
https://trac.sagemath.org/ticket/13730
<ul>
<li><strong>attachment</strong>
set to <em>trac_17710_needs_info.patch</em>
</li>
</ul>
TicketslaniThu, 21 Feb 2013 16:59:59 GMT
https://trac.sagemath.org/ticket/13730#comment:8
https://trac.sagemath.org/ticket/13730#comment:8
<p>
Hello.
</p>
<p>
I tried to implement what azi did. I added the hash tabel and update some methods. I didn't make other tests.
I'm new to SAGE and I would like to work on this problem. Please help me and tell me if this patch is going in the right direction.
</p>
<p>
Best regards,
</p>
<p>
slani
</p>
<pre class="wiki">new
==========================================================
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 479 Âµs per loop
sage: ggnx = G.networkx_graph()
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)]
625 loops, best of 3: 171 Âµs per loopsage: %timeit EE = [(u,v) for u in ggnx for v in ggnx[u]]
625 loops, best of 3: 159 Âµs per loop
sage: %timeit G.neighbors(3)
625 loops, best of 3: 5.35 Âµs per loop
===========================================================
old
===========================================================
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
125 loops, best of 3: 2.03 ms per loop
sage: ggnx = G.networkx_graph()
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)]
625 loops, best of 3: 177 Âµs per loop
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx[u]]
625 loops, best of 3: 159 Âµs per loop
%timeit G.neighbors(3)
625 loops, best of 3: 91.1 Âµs per loop
============================================================
</pre>
TicketslaniThu, 21 Feb 2013 18:31:35 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:9
https://trac.sagemath.org/ticket/13730#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketslaniThu, 21 Feb 2013 18:32:10 GMTcc changed
https://trac.sagemath.org/ticket/13730#comment:10
https://trac.sagemath.org/ticket/13730#comment:10
<ul>
<li><strong>cc</strong>
<em>slani</em> added
</li>
</ul>
TicketncohenFri, 22 Feb 2013 08:59:16 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:11
https://trac.sagemath.org/ticket/13730#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
....
</p>
<p>
This patch does not even contain an instruction to remove an element from your cached list when an edge is deleted....
</p>
<p>
This problem has to be fixed, but it has to be fixed properly... If the backend is slow it has to be fixed there or the backend should be changed.
</p>
<p>
Nathann
</p>
TicketslaniMon, 25 Feb 2013 14:54:41 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:12
https://trac.sagemath.org/ticket/13730#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello
</p>
<p>
I've added the function to handle vertex removals as well. I am aware that this solution is not good but I just wanted to write something to get us going. To make it work properly I would have to change the respective backends but I am clueless about the internal structure of the backends. Is there anyone here that can shed some light on it or point to the relevant documentation - I was not able to find any.
</p>
<p>
Where should this improvement be implemented?
</p>
TicketslaniMon, 25 Feb 2013 14:55:06 GMTattachment set
https://trac.sagemath.org/ticket/13730
https://trac.sagemath.org/ticket/13730
<ul>
<li><strong>attachment</strong>
set to <em>trac_17711_needs_info.patch</em>
</li>
</ul>
TicketncohenMon, 25 Feb 2013 16:34:59 GMT
https://trac.sagemath.org/ticket/13730#comment:13
https://trac.sagemath.org/ticket/13730#comment:13
<p>
Your updated patch would fail if there are two edges between two vertices, and the user removes one of the two edges.
</p>
<p>
You unnecessarily check whether the dictionaries contain a list associated to a vertex of the graph, and it would probably be better to associate an empty list to each vertex from the beginning. Anyway you have to make TESTS to decide what to do.
</p>
<p>
The functions you add are not doctested.
</p>
<p>
You do not document the features you add either.
</p>
<p>
I think that it would be better to add what you need in the code directly, without creating 2
</p>
<p>
Please, do not write this patch.
</p>
<blockquote class="citation">
<p>
Is there anyone here that can shed some light on it or point to the relevant documentation - I was not able to find any.
</p>
</blockquote>
<p>
There isn't, that's one of the problems. I write some comments in the code about some parts of it when I have to understand how it works to fix a bug.
</p>
<blockquote class="citation">
<p>
Where should this improvement be implemented?
</p>
</blockquote>
<p>
I do not know. What I would do if I were to write this patch, or what I will do if you force me to write it, is try to understand why the current implementation is so slow compared to dictionaries. I would try to locate the place which makes a difference in the timings. This has to come from the way edges are stored, and from what I remember this part of the code is not that clear.
</p>
<p>
Nathann
</p>
TicketncohenTue, 26 Feb 2013 11:17:22 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:14
https://trac.sagemath.org/ticket/13730#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketbrunellusSun, 03 Mar 2013 16:53:55 GMTcc changed
https://trac.sagemath.org/ticket/13730#comment:15
https://trac.sagemath.org/ticket/13730#comment:15
<ul>
<li><strong>cc</strong>
<em>brunellus</em> added
</li>
</ul>
TicketslaniTue, 04 Jun 2013 23:25:23 GMTattachment set
https://trac.sagemath.org/ticket/13730
https://trac.sagemath.org/ticket/13730
<ul>
<li><strong>attachment</strong>
set to <em>trac_17710_iter_set.patch</em>
</li>
</ul>
TicketslaniTue, 04 Jun 2013 23:28:01 GMT
https://trac.sagemath.org/ticket/13730#comment:16
https://trac.sagemath.org/ticket/13730#comment:16
<p>
<a style="padding:0; border:none" href="http://lobi.dev.si/s.png"><img src="http://lobi.dev.si/s.png" alt="http://lobi.dev.si/s.png" title="http://lobi.dev.si/s.png" /></a>
</p>
<p>
Hello,
</p>
<p>
on picture you can see a diagram what happens when we call neighbors() on graph. You can see there is a lot conversion from set/iter and then back again.
</p>
<p>
Where this conversion is not necessary I remove it.
</p>
<p>
But most time reduction was made (for ours specific test), when function neighbor_iterator (F2) start calling iterator_out_nbrs (F4.2) for undirected graph instead iterator_nbrs (F3.1). If graph is undirected we only need out nbrs. or in nbrs.??????????
</p>
<pre class="wiki">Before:
sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
125 loops, best of 3: 2.03 ms per loop
Now:
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 900 µs per loop
</pre><p>
I also remove
</p>
<pre class="wiki">#Sparse
if self._cg_rev is not None:
return iter([vertex_label(u_int,
self.vertex_ints,
self.vertex_labels,
self._cg)
for u_int in self._cg_rev.out_neighbors(v_int)])
</pre><p>
in iterator_in_nbrs (F 4.1). I don't know what relation this has with sparse/dense.
</p>
<p>
But most time consuming problem is conversion from vertex int to vertex label in iterator_out_nbrs (F4.2) and iterator_in_nbrs (F4.1)
</p>
<p>
This conversion for our specific test takes almost 500 µs.
I tried to implement array of python object in cython, where we can save vertex labels, but I was unsuccessful, because I don't know cython well (yet). Maybe someone can help me?
</p>
<p>
If this is a good solution then we can return iter of vertex labels instead of list of vertex int from cpdef list out_neighbors (F5).
</p>
<p>
So what do you think?
</p>
<p>
Best,
Uros
</p>
TicketslaniTue, 04 Jun 2013 23:28:38 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:17
https://trac.sagemath.org/ticket/13730#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketvdelecroixWed, 05 Jun 2013 06:53:46 GMTcc changed
https://trac.sagemath.org/ticket/13730#comment:18
https://trac.sagemath.org/ticket/13730#comment:18
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
</ul>
TicketvdelecroixWed, 05 Jun 2013 07:41:04 GMTattachment set
https://trac.sagemath.org/ticket/13730
https://trac.sagemath.org/ticket/13730
<ul>
<li><strong>attachment</strong>
set to <em>trac_13730-vd.patch</em>
</li>
</ul>
TicketvdelecroixWed, 05 Jun 2013 07:47:35 GMT
https://trac.sagemath.org/ticket/13730#comment:19
https://trac.sagemath.org/ticket/13730#comment:19
<p>
Hi,
</p>
<p>
I just upload <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13730/trac_13730-vd.patch" title="Attachment 'trac_13730-vd.patch' in Ticket #13730">trac_13730-vd.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13730/trac_13730-vd.patch" title="Download"></a> to show how you could do this. There is no reason to add extra attributes to graphs (it will only slow down everything). Right now, all graph data structures in Sage are implemented to be fast at Cython level (ie compiled code). In order to have reasonable timings at Python level you need to work a bit.
</p>
<p>
In <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13730/trac_13730-vd.patch" title="Attachment 'trac_13730-vd.patch' in Ticket #13730">trac_13730-vd.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13730/trac_13730-vd.patch" title="Download"></a>, there is a working iterator for the out neighbors in a dense graph (in <code>sage.graphs.base.dense_graph</code>). You might implement similar classes <code>InIteratorXXX</code>, <code>OutIteratorXXX</code> and <code>InAndOutIteratorXXX</code> for each graph backend <code>XXX</code> and then make some small wrapper in order to make it works for Sage graphs (ie translating ints to vertex labels).
</p>
<p>
I may help further if you need.
</p>
<p>
Best,
Vincent
</p>
TicketvdelecroixWed, 05 Jun 2013 07:47:43 GMTstatus changed
https://trac.sagemath.org/ticket/13730#comment:20
https://trac.sagemath.org/ticket/13730#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketvdelecroixFri, 07 Jun 2013 08:14:37 GMTattachment set
https://trac.sagemath.org/ticket/13730
https://trac.sagemath.org/ticket/13730
<ul>
<li><strong>attachment</strong>
set to <em>trac_13730-v2-vd.patch</em>
</li>
</ul>
TicketvdelecroixFri, 07 Jun 2013 08:15:15 GMT
https://trac.sagemath.org/ticket/13730#comment:21
https://trac.sagemath.org/ticket/13730#comment:21
<p>
Hi,
</p>
<p>
I appologize, I was a bit old school in my precedent message.
</p>
<p>
A long time ago, Cython did not support the yield statement and it was necessary either to write a class dedicated to iteration or to build the set on which we would like to iterate and return <code>iter(my_set)</code>. This is the reason why it is implemented like that in <code>sage.graphs.base.c_graph</code> and <code>sage.graphs.base.sparse_graph</code>.
</p>
<p>
I upload a patch where all iterators does not build the underlying set. The gain is not extraordinary (only a x2) and the output order is completely messed up (this need to be fixed).
</p>
TicketslaniSat, 08 Jun 2013 06:11:29 GMT
https://trac.sagemath.org/ticket/13730#comment:22
https://trac.sagemath.org/ticket/13730#comment:22
<p>
Hello,
</p>
<p>
I tried with yield in iterator_out_nbrs (l:1745, c_graph.pyx) but it does not improve anything.
</p>
<pre class="wiki">sage: G = graphs.RandomBarabasiAlbert(100,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 940 µs per loop
</pre><p>
I did a lot of modification and testing (also tried with new function in cython which use yield for returning nbrs), but didn't improve anything.
</p>
<p>
I also made a function (in generic_graph.py) which directly call cpdef list out_neighbors (base/sparse_graph.pyx; l:798):
</p>
<pre class="wiki">sage: %timeit E = [(u,v) for u in G for v in G.neighbors_three(u)]
625 loops, best of 3: 362 µs per loop
</pre><p>
It is still slower than NetworkX!
</p>
<p>
I don't know, but I came to the conclusion that we have tow problems:
</p>
<ol><li>conversion from vertex ints to vertex lables
</li><li>how to faster return vertex ints from data structure we have for nbrs
</li></ol><p>
Vincent, what do you think?
</p>
<p>
This is also interesting for me:
</p>
<pre class="wiki">sage: G
Graph on 100 vertices
sage: ggnx
<networkx.classes.graph.Graph object at 0x65c8ed0>
sage: %timeit E = [(u,v) for u in G for v in G.neighbors_three(u)]
625 loops, best of 3: 358 µs per loop
sage: %timeit E = [(u,v) for u in ggnx for v in G.neighbors_three(u)]
625 loops, best of 3: 273 µs per loop
sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors(u)]
625 loops, best of 3: 213 µs per loop
</pre><p>
Best,
Uros
</p>
TicketvdelecroixSat, 08 Jun 2013 06:54:55 GMT
https://trac.sagemath.org/ticket/13730#comment:23
https://trac.sagemath.org/ticket/13730#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13730#comment:22" title="Comment 22">slani</a>:
Hello,
</p>
<blockquote class="citation">
<p>
I don't know, but I came to the conclusion that we have tow problems:
</p>
<ol><li>conversion from vertex ints to vertex lables
</li></ol></blockquote>
<p>
This should not slow down too much (not x4). It is a lookup in an array. Did you make some timings to see whether this is slow ? Perhaps we have to dig the way it is implemented.
</p>
<blockquote class="citation">
<ol start="2"><li>how to faster return vertex ints from data structure we have for nbrs
</li></ol></blockquote>
<p>
It might be a good idea to see whether iterator over int vertices are faster compared to the labeled one.
</p>
<p>
Other possibilities
</p>
<ol start="3"><li>There are 3 levels in a graph: the <code>GenericGraph</code> class, the <code>backend</code> (stored at <code>my_graph._backend</code>) and then the datastructure (stored at <code>my_graph._backend._cg</code> for c graphs or <code>my_graph._backend._nxg</code> for networkx).
</li></ol><ol start="4"><li>Possibly <a class="closed ticket" href="https://trac.sagemath.org/ticket/14690" title="enhancement: Useless memory allocation in listing neighbors of a graph (closed: invalid)">#14690</a> might be a good speedup (if it works one day ;-)
</li></ol>
TicketslaniSat, 08 Jun 2013 07:18:05 GMT
https://trac.sagemath.org/ticket/13730#comment:24
https://trac.sagemath.org/ticket/13730#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13730#comment:23" title="Comment 23">vdelecroix</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13730#comment:22" title="Comment 22">slani</a>:
Hello,
</p>
<blockquote class="citation">
<p>
I don't know, but I came to the conclusion that we have tow problems:
</p>
<ol><li>conversion from vertex ints to vertex lables
</li></ol></blockquote>
<p>
This should not slow down too much (not x4). It is a lookup in an array. Did you make some timings to see whether this is slow ? Perhaps we have to dig the way it is implemented.
</p>
<blockquote class="citation">
<p>
Yes.
This is a timing when I'm calling iterator_out_nbrs (base/c_graph.pyx; l: 1754)
</p>
</blockquote>
</blockquote>
<pre class="wiki">sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 872 µs per loop
</pre><p>
This is a timing when I'm calling cpdef list out_neighbors (base/sparse_graph.pyx; l:798) directly (no conversions vertex int to vertex labels)
</p>
<pre class="wiki">sage: %timeit E = [(u,v) for u in G for v in G.neighbors_three(u)]
625 loops, best of 3: 362 µs per loop
</pre><blockquote class="citation">
<blockquote class="citation">
<ol start="2"><li>how to faster return vertex ints from data structure we have for nbrs
</li></ol></blockquote>
<p>
It might be a good idea to see whether iterator over int vertices are faster compared to the labeled one.
</p>
<blockquote class="citation">
<p>
I also trying with yield in sparse_graph.pyx
</p>
</blockquote>
</blockquote>
<pre class="wiki">+ def iter_out_nbrs_one(self, u):
+
+ cdef int i, num_nbrs = 0, current_nbr = 0
+ cdef int size = self.out_degrees[u]
+ if self.out_degrees[u] == 0:
+ return 0
+ cdef SparseGraphBTNode **pointers = <SparseGraphBTNode **> \
+ sage_malloc(size * sizeof(SparseGraphBTNode *))
+ if not pointers:
+ raise RuntimeError("Failure allocating memory.")
+ for i from u * self.hash_length <= i < (u+1) * self.hash_length:
+ if self.vertices[i] == NULL:
+ continue
+ if num_nbrs == size:
+ sage_free(pointers)
+ return -1
+ pointers[num_nbrs] = self.vertices[i]
+ yield self.vertices[i].vertex
+ num_nbrs += 1
+
+ # While all the neighbors have not been added to the list, explore
+ # element pointers[current_nbr] and append its children to the end
+ # of pointers if necessary, the increment current_nbr.
+ while current_nbr < num_nbrs:
+ if pointers[current_nbr].left != NULL:
+ if num_nbrs == size:
+ sage_free(pointers)
+ return -1
+ pointers[num_nbrs] = pointers[current_nbr].left
+ yield pointers[current_nbr].left.vertex
+ num_nbrs += 1
+ if pointers[current_nbr].right != NULL:
+ if num_nbrs == size:
+ sage_free(pointers)
+ return -1
+ pointers[num_nbrs] = pointers[current_nbr].right
+ yield pointers[current_nbr].right.vertex
+ num_nbrs += 1
+ current_nbr += 1
+ sage_free(pointers)
+
</pre><blockquote class="citation">
<blockquote class="citation">
<p>
This doesn’t improve anything. I suppose this is not a good implementation but it was just a test.
</p>
</blockquote>
<p>
Other possibilities
</p>
<ol start="3"><li>There are 3 levels in a graph: the <code>GenericGraph</code> class, the <code>backend</code> (stored at <code>my_graph._backend</code>) and then the datastructure (stored at <code>my_graph._backend._cg</code> for c graphs or <code>my_graph._backend._nxg</code> for networkx).
</li></ol><ol start="4"><li>Possibly <a class="closed ticket" href="https://trac.sagemath.org/ticket/14690" title="enhancement: Useless memory allocation in listing neighbors of a graph (closed: invalid)">#14690</a> might be a good speedup (if it works one day ;-)
</li></ol></blockquote>
TicketslaniMon, 10 Jun 2013 23:03:37 GMT
https://trac.sagemath.org/ticket/13730#comment:25
https://trac.sagemath.org/ticket/13730#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13730#comment:23" title="Comment 23">vdelecroix</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<ol start="4"><li>Possibly <a class="closed ticket" href="https://trac.sagemath.org/ticket/14690" title="enhancement: Useless memory allocation in listing neighbors of a graph (closed: invalid)">#14690</a> might be a good speedup (if it works one day ;-)
</li></ol></blockquote>
<blockquote>
<p>
<br />
</p>
</blockquote>
<p>
I modified data structure for saving nbrs. I implemented linked list and save all nbrs for vertex in one place in vertices (not on 16 different places). Obvious this is not good for adds and removes nbrs.
</p>
</blockquote>
<pre class="wiki">sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
625 loops, best of 3: 871 µs per loop
</pre><blockquote class="citation">
<p>
Very small improvements.<br />
</p>
<p>
How can networkX data structure (python dict) return data so fast?<br />
</p>
<p>
Best, <br />
Uros
</p>
</blockquote>
TicketaziTue, 13 Aug 2013 12:46:27 GMT
https://trac.sagemath.org/ticket/13730#comment:26
https://trac.sagemath.org/ticket/13730#comment:26
<p>
That may be interesting
</p>
<pre class="wiki">sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
1000 loops, best of 3: 1.65 ms per loop
sage: H = Graph(G.graph6_string(), implementation='networkx')
sage: %timeit E = [(u,v) for u in H for v in H.neighbor_iterator(u)]
100 loops, best of 3: 1.35 ms per loop
</pre>
TicketncohenTue, 13 Aug 2013 12:51:00 GMT
https://trac.sagemath.org/ticket/13730#comment:27
https://trac.sagemath.org/ticket/13730#comment:27
<p>
What about <a class="closed ticket" href="https://trac.sagemath.org/ticket/14806" title="enhancement: Immutable graph backend (closed: fixed)">#14806</a> ? <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketaziTue, 13 Aug 2013 12:56:21 GMT
https://trac.sagemath.org/ticket/13730#comment:28
https://trac.sagemath.org/ticket/13730#comment:28
<p>
Okay this is even more interesting and it indicates the problem is not really in the backend per se.
</p>
<pre class="wiki">
sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
1000 loops, best of 3: 1.68 ms per loop
</pre><p>
BUT:
</p>
<pre class="wiki">sage: S = SparseGraph(1000)
sage: for i,j in G.edges(labels=False): S.add_arc(i,j)
sage: %timeit E = [(u,v) for u in S.verts() for v in S.out_neighbors(u)]
1000 loops, best of 3: 374 us per loop
</pre><p>
<strong>What do you guys thin is going on here?</strong>
</p>
<p>
As for your static graphs thing If nobody wakes up then I promise to review it by the weekend! :-)
</p>
TicketaziTue, 13 Aug 2013 13:14:56 GMT
https://trac.sagemath.org/ticket/13730#comment:29
https://trac.sagemath.org/ticket/13730#comment:29
<p>
And also the relevant profilings.. If they are of any help..
</p>
<pre class="wiki">sage: G = graphs.RandomBarabasiAlbert(1000,2)
sage: %prun E = [(u,v) for u in G for v in G.neighbor_iterator(u)]
1003 function calls in 0.005 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1000 0.003 0.000 0.003 0.000 generic_graph.py:7848(neighbor_iterator)
1 0.002 0.002 0.005 0.005 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 generic_graph.py:7794(vertex_iterator)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
sage: %prun E = [(u,v) for u in S.verts() for v in S.out_neighbors(u)]
1003 function calls in 0.001 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 0.001 0.001 <string>:1(<module>)
1000 0.000 0.000 0.000 0.000 {method 'out_neighbors' of 'sage.graphs.base.sparse_graph.SparseGraph' objects}
1 0.000 0.000 0.000 0.000 {method 'verts' of 'sage.graphs.base.c_graph.CGraph' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
</pre>
TicketncohenTue, 13 Aug 2013 13:15:44 GMT
https://trac.sagemath.org/ticket/13730#comment:30
https://trac.sagemath.org/ticket/13730#comment:30
<blockquote class="citation">
<p>
Okay this is even more interesting and it indicates the problem is not really in the backend per se.
</p>
</blockquote>
<p>
Welll... Is it just forwarding the values returned by out_neighbors through neighbor_iterator ?
</p>
<blockquote class="citation">
<p>
As for your static graphs thing If nobody wakes up then I promise to review it by the weekend! :-)
</p>
</blockquote>
<p>
That'd be cool <code>:-PPPPPPPP</code>
</p>
<p>
Nathann
</p>
TicketaziTue, 13 Aug 2013 13:24:39 GMT
https://trac.sagemath.org/ticket/13730#comment:31
https://trac.sagemath.org/ticket/13730#comment:31
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13730#comment:30" title="Comment 30">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Okay this is even more interesting and it indicates the problem is not really in the backend per se.
</p>
</blockquote>
<p>
Welll... Is it just forwarding the values returned by out_neighbors through neighbor_iterator ?
</p>
</blockquote>
<p>
YES. But why does it take so long? This changes the runtime by a huge order of magnitude.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
As for your static graphs thing If nobody wakes up then I promise to review it by the weekend! :-)
</p>
</blockquote>
<p>
That'd be cool <code>:-PPPPPPPP</code>
</p>
<p>
Nathann
</p>
</blockquote>
TicketncohenTue, 13 Aug 2013 13:31:09 GMT
https://trac.sagemath.org/ticket/13730#comment:32
https://trac.sagemath.org/ticket/13730#comment:32
<blockquote class="citation">
<p>
YES. But why does it take so long? This changes the runtime by a huge order of magnitude.
</p>
</blockquote>
<p>
HMmmmm... I'd say "just Python being Python" <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketaziTue, 13 Aug 2013 13:37:01 GMT
https://trac.sagemath.org/ticket/13730#comment:33
https://trac.sagemath.org/ticket/13730#comment:33
<p>
Yes! The only confusing thing to me is why then is NetworkX (called without going through the frontend) efficient? (confusing because NetworkX is in Python)
</p>
<pre class="wiki">sage: N = G.networkx_graph()
sage: %timeit E = [(u,v) for u in N for v in N.neighbors_iter(u)]
1000 loops, best of 3: 599 us per loop
</pre><p>
So there is some Python being Python thing going on in the Graph frontend class.
</p>
TicketjdemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/13730#comment:34
https://trac.sagemath.org/ticket/13730#comment:34
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketaziFri, 30 Aug 2013 09:50:47 GMT
https://trac.sagemath.org/ticket/13730#comment:35
https://trac.sagemath.org/ticket/13730#comment:35
<p>
Here is a wrap up of what's going on with this problem <a class="ext-link" href="https://groups.google.com/forum/#!topic/sage-devel/CwKSNWXVJtU"><span class="icon"></span>https://groups.google.com/forum/#!topic/sage-devel/CwKSNWXVJtU</a>
</p>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/13730#comment:36
https://trac.sagemath.org/ticket/13730#comment:36
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/13730#comment:37
https://trac.sagemath.org/ticket/13730#comment:37
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/13730#comment:38
https://trac.sagemath.org/ticket/13730#comment:38
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
Ticket