[sage-devel] Re: Graph neighbours - room for huge performance boost
FYI, often I will first convert a graph to a list of bitsets representing the neighbors, then I use Cython to access the bitsets for really fast access. Wayyy later : you may like patch #14589 ! Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
[sage-devel] Re: Graph neighbours - room for huge performance boost
Hellooo !!! You are totally right about the performance issue, but do you know the memory size of a Sage graph compared to dict of dict ? I have no idea -- I have just been *VERY* scared by the size of a dict of dict compared to a C array in the past. Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
Le 02/01/2013 09:22, Nathann Cohen a écrit : Hellooo !!! You are totally right about the performance issue, but do you know the memory size of a Sage graph compared to dict of dict ? I have no idea -- I have just been *VERY* scared by the size of a dict of dict compared to a C array in the past. Nathann -- A similar problem exists withn sparse matrices used by scipy:; scipy builds a dict of (i,j) for all the non zero coefficients of the matrix; this is so slow that it cannot be used in any real application ! t.d. -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. attachment: tdumont.vcf
[sage-devel] Re: Graph neighbours - room for huge performance boost
Heey! Do we actually need to have a dict of a dict? Aren't sets implemented with some other data structure? I suppose if networkX uses this approach then it is doable! Best, Jernej On Wednesday, 2 January 2013 09:22:08 UTC+1, Nathann Cohen wrote: Hellooo !!! You are totally right about the performance issue, but do you know the memory size of a Sage graph compared to dict of dict ? I have no idea -- I have just been *VERY* scared by the size of a dict of dict compared to a C array in the past. Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
Helloo !!! Do we actually need to have a dict of a dict? Aren't sets implemented with some other data structure? I suppose if networkX uses this approach then it is doable! Oh. You wanted a dictionary of sets ? Well, the main reason I have not rewritten this backend 10 times since I started working on Sage is that in order to replace it you need to deal with a wealth of unpleasant things : loops, multiple edges and labels. These things are a nightmare. This being said, I think that the memory cost of dict or dict and sets are comparable... Whatever it is :-) Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 2013-01-02, Nathann Cohen nathann.co...@gmail.com wrote: --20cf3003bcb0a9ec4404d24bbbff Content-Type: text/plain; charset=ISO-8859-1 Helloo !!! Do we actually need to have a dict of a dict? Aren't sets implemented with some other data structure? I suppose if networkX uses this approach then it is doable! Oh. You wanted a dictionary of sets ? Well, the main reason I have not rewritten this backend 10 times since I started working on Sage is that in order to replace it you need to deal with a wealth of unpleasant things : loops, multiple edges and labels. These things are a nightmare. This being said, I think that the memory cost of dict or dict and sets are comparable... Whatever it is :-) I suppose that for many graph algorithms the graph can well stay immutable, and this does not really need a dictionary (perhaps at a slight cost of efficiency of determining whether two vertices are adjacent). And many algorithms actually do not need the latter, as they parse the neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Dima Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
I suppose that for many graph algorithms the graph can well stay immutable, and this does not really need a dictionary (perhaps at a slight cost of efficiency of determining whether two vertices are adjacent). And many algorithms actually do not need the latter, as they parse the neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Not a backend, but still... :-P http://www.sagemath.org/doc/reference/sage/graphs/base/static_sparse_graph.html I also prefer to write a good graph structure for my algorithms than to use Sage's when it is worth spending the extra time :-) Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
Le 02/01/2013 13:54, Nathann Cohen a écrit : I suppose that for many graph algorithms the graph can well stay immutable, and this does not really need a dictionary (perhaps at a slight cost of efficiency of determining whether two vertices are adjacent). And many algorithms actually do not need the latter, as they parse the neighbourhouds of vertices and the vertices themselves sequentially. In these cases representing graphs as lists of edges is very bad, one would be much better off using a tuple of sets (or even the list of lists) to represent the graph. I don't know whether there are backhands available to deal with this. Not a backend, but still... :-P http://www.sagemath.org/doc/reference/sage/graphs/base/static_sparse_graph.html This structure is used for the sparse matrices which appear in the solution of discretized PDE (known as csl or csr structures, have a look at scipy): everybody uses this, and, at the time I write thousands of codes are running this. OK, BUT: how do you build this structure ? In my applications (PDEs), the pairs of coefficients (i,j) appear in *any* order. Do you know an efficient algorithm to build the structure ? This is here that the dictionary appears: you first put your coefficients in the dictionary in the order they appear; when your graph has been fully constructed, you transform it into this static graph structure. The problem is that Python dictionaries are *very* slow. Do you know how they are implemented? Personally (but not is Sage), I use a C++ stl::map: mapint,int. Actually, C++ maps are represented by B-Trees. They are reasonably fast and the transformation into the static graph structure is very easy: you just use a mapint,int::iterator to get the coefficients in the order they will appear in the final structure. If you want do do this in parallel (current problems can have 10^10 edges), it's a bit more tricky, but feasible, and it is not the concern, here. t.d. I also prefer to write a good graph structure for my algorithms than to use Sage's when it is worth spending the extra time :-) Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. attachment: tdumont.vcf
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 1/2/13 6:29 AM, Thierry Dumont wrote: The problem is that Python dictionaries are *very* slow. Do you know how they are implemented? a hash table: http://hg.python.org/cpython/file/tip/Objects/dictobject.c http://hg.python.org/cpython/file/tip/Include/dictobject.h http://hg.python.org/cpython/file/tip/Objects/dictnotes.txt http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented has many good answers, it seems. Thanks, Jason -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented has many good answers, it seems. Wow. And they flagged it as non constructive. These guys are great. Thank you very much Jason !!! O_O Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
see inline. On Wed, Jan 2, 2013 at 12:31 PM, Nathann Cohen nathann.co...@gmail.com wrote: http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented has many good answers, it seems. Wow. And they flagged it as non constructive. These guys are great. Stackoverflow is totally botched! I decided never more to try to use that place. Kjetil Thank you very much Jason !!! O_O Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. -- If you want a picture of the future - imagine a boot stamping on the human face - forever. George Orwell (1984) -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On Jan 2, 5:29 am, Thierry Dumont tdum...@math.univ-lyon1.fr wrote: The problem is that Python dictionaries are *very* slow. Do you know how they are implemented? That's an interesting observation. I think python developers have put a lot of time into optimizing their dict structures, because they are used *everywhere* in python itself (global variables and attribute lookups are all dictionary based). The main hurdle for hash tables is the computation of the hash function. So perhaps your indices are slow to hash? Or perhaps your code is written in such a way that there's quite a bit of allocation/deallocation for lookup of a key (e.g. the construction of a tuple)? For your application it seems you know a lot about the key format beforehand, so it's possible that that allows a more efficient implementation anyway. However, if you find yourself stuck with having to use python dictionaries and you're unhappy with the speed, my guess would be: - check if you can use/design a key that's fast to hash - check if you can carry around entire keys in your code (i.e., don't pack/unpack into/from tuples all the time) As far as hash tables go, Python dicts are supposed to be one of the state-of-the-art implementations. -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 1/2/13 5:54 AM, Nathann Cohen wrote: I also prefer to write a good graph structure for my algorithms than to use Sage's when it is worth spending the extra time :-) FYI, often I will first convert a graph to a list of bitsets representing the neighbors, then I use Cython to access the bitsets for really fast access. Thanks, Jason -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 1/2/13 10:22 AM, Nils Bruin wrote: So perhaps your indices are slow to hash? Or perhaps your code is written in such a way that there's quite a bit of allocation/deallocation for lookup of a key (e.g. the construction of a tuple)? IIRC, our discussion is that the dict approach *is* the faster one (faster than Sage's data structure), about a tenth the time in one concrete benchmark. In this benchmark, the vertices are just plain integers. Sage does not use plain dicts to store the neighborhood lists, if I recall correctly, and it doesn't do nearly as well as networkx, which does use dicts to store neighborhoods. To repeat the benchmark on my computer: sage: G = graphs.RandomBarabasiAlbert(100,2) sage: type(G.vertices()[0]) int here is Sage's implementation: sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)] 1000 loops, best of 3: 1.14 ms per loop and here is a neighborhood dict approach: sage: ggnx = G.networkx_graph() sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] 1 loops, best of 3: 111 us per loop Thanks, Jason -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 1/2/13 11:56 AM, Jason Grout wrote: To repeat the benchmark on my computer: sage: G = graphs.RandomBarabasiAlbert(100,2) sage: type(G.vertices()[0]) int here is Sage's implementation: sage: %timeit E = [(u,v) for u in G for v in G.neighbor_iterator(u)] 1000 loops, best of 3: 1.14 ms per loop and here is a neighborhood dict approach: sage: ggnx = G.networkx_graph() sage: %timeit EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] 1 loops, best of 3: 111 us per loop A few more data points to narrow in on just the neighbors functionality: Sage: sage: %timeit G.neighbors(0) 1 loops, best of 3: 23.2 us per loop sage: %timeit G[0] 1 loops, best of 3: 24 us per loop Networkx: sage: %timeit ggnx.neighbors(0) 100 loops, best of 3: 1.21 us per loop sage: %timeit ggnx[0].keys() 100 loops, best of 3: 1.02 us per loop sage: %timeit ggnx[0] # return the neighbors dictionary 100 loops, best of 3: 590 ns per loop Thanks, Jason -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
Helloo A few more data points to narrow in on just the neighbors functionality: We are definitely way behind when it comes to the enumeration of neighbors. At the time we moved from default networkx backends to Sage's own implementation, the point was more to improve the runtime of more complicated algorithms (than the enumeration of neighbors), i.e. the computation of distances/shortest path and all versions that take weidhted edges into account. Having Cython graphs is a way to get more performances on such algorithms than it would be possible with just plain dictionaries otherwise, with everything written at C level. For instance the content of this file : http://www.sagenb.org/src/graphs/base/c_graph.pyx And there is yet another kind of algorithms for which the solution is different : dedicated code for which it is more interesting to make a copy of the graph in a format optimised for the algorithm itself. Many of the most time-consuming methods of Graph actually do that : - everything related to cliques is solved with Cliquer, which has its own structure - everything solved with LP solvers - everything related to the computations of distances between all pairs of vertices The problem lies in this space : the algorithms whose running time is not sufficient to deserve a copy of the graph into a better structure. And we are definitely way behind networkx for the enumeration of neighbors. I expect that we are much more compact in memory, though. I always wanted to dig inside of the graph backends but never went that far. Recently, I prefer to think of new graph structures that can be used by time-consuming algorithms, especially because it prevents me from having to deal with the labels/loops/multiple edges hell that drives me crazy at the slightest touch :-P This being said, if we ever go back to networkx-type graph structure, I would prefer to have our own implementation of it. Otherwise I will spend my time working for networkx, and I won't like that :-P Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
Le 02/01/2013 18:22, Nils Bruin a écrit : On Jan 2, 5:29 am, Thierry Dumont tdum...@math.univ-lyon1.fr wrote: The problem is that Python dictionaries are *very* slow. Do you know how they are implemented? That's an interesting observation. I think python developers have put a lot of time into optimizing their dict structures, because they are used *everywhere* in python itself (global variables and attribute lookups are all dictionary based). The main hurdle for hash tables is the computation of the hash function. So perhaps your indices are slow to hash? Or perhaps your code is written in such a way that there's quite a bit of allocation/deallocation for lookup of a key (e.g. the construction of a tuple)? I'll try to make precise measurements and comparisons, otherwise this discussion is non sense I ll do it, when I'll have time :-( But anyway, why a hash table? In C++, to build these graph structures we are talking about, I only use B-Tree based structures, for which we only need to have an order (actually a weak ordering), and an order on pairs of integers is something simple to compute; also B-Trees allow much more memory locality than containers based on hash tables. If dict rely on hash tables (because we do not presuppose we have an ordering?--may be this is necessary for other purpose--) this is certainly slower... I'll look a this... For your application it seems you know a lot about the key format beforehand, so it's possible that that allows a more efficient implementation anyway. However, if you find yourself stuck with having to use python dictionaries and you're unhappy with the speed, my guess would be: - check if you can use/design a key that's fast to hash - check if you can carry around entire keys in your code (i.e., don't pack/unpack into/from tuples all the time) As far as hash tables go, Python dicts are supposed to be one of the state-of-the-art implementations. -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. attachment: tdumont.vcf
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
But anyway, why a hash table? In C++, to build these graph structures we are talking about, I only use B-Tree based structures, for which we only need to have an order (actually a weak ordering), and an order on pairs of integers is something simple to compute; Yeah. But we have labels to deal with. Remove vertex and edge labels from Graphs and you will not recognize the running time :-P Nathann -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
Re: [sage-devel] Re: Graph neighbours - room for huge performance boost
I decided to do some profiling. And there is something that worries my slightly more then the factor +/-10 difference in iteration speed that caused the start of this topici. Namely conversion from a sparse sage graph to a networkx graph seems to have quadratic runtime complexity instead of linear. As you can see below you see the timings of: G = graphs.RandomBarabasiAlbert(2^i,2) E = [(u,v) for u in G for v in G.neighbor_iterator(u)] #and EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] seem to double each step as one would expect with linear complexity. However the time of ggnx = G.networkx_graph() increases each step by a factor of about 4, indicating quadratic runtime complexity :S. sage: for i in range(10,21): : print i : time G = graphs.RandomBarabasiAlbert(2^i,2) : time E = [(u,v) for u in G for v in G.neighbor_iterator(u)] : time ggnx = G.networkx_graph() : time EE = [(u,v) for u in ggnx for v in ggnx.neighbors_iter(u)] : 10 Time: CPU 0.05 s, Wall: 0.05 s Time: CPU 0.02 s, Wall: 0.02 s Time: CPU 0.03 s, Wall: 0.03 s Time: CPU 0.00 s, Wall: 0.00 s 11 Time: CPU 0.09 s, Wall: 0.09 s Time: CPU 0.03 s, Wall: 0.03 s Time: CPU 0.07 s, Wall: 0.07 s Time: CPU 0.01 s, Wall: 0.01 s 12 Time: CPU 0.19 s, Wall: 0.19 s Time: CPU 0.07 s, Wall: 0.07 s Time: CPU 0.20 s, Wall: 0.20 s Time: CPU 0.01 s, Wall: 0.01 s 13 Time: CPU 0.40 s, Wall: 0.40 s Time: CPU 0.13 s, Wall: 0.13 s Time: CPU 0.66 s, Wall: 0.66 s Time: CPU 0.02 s, Wall: 0.02 s 14 Time: CPU 0.92 s, Wall: 0.92 s Time: CPU 0.27 s, Wall: 0.27 s Time: CPU 2.45 s, Wall: 2.46 s Time: CPU 0.04 s, Wall: 0.04 s 15 Time: CPU 1.86 s, Wall: 1.87 s Time: CPU 0.55 s, Wall: 0.55 s Time: CPU 8.85 s, Wall: 8.86 s Time: CPU 0.08 s, Wall: 0.08 s 16 Time: CPU 3.96 s, Wall: 3.96 s Time: CPU 1.10 s, Wall: 1.10 s Time: CPU 33.85 s, Wall: 33.85 s Time: CPU 0.16 s, Wall: 0.16 s 17 Time: CPU 8.29 s, Wall: 8.30 s Time: CPU 2.21 s, Wall: 2.22 s Time: CPU 139.72 s, Wall: 140.03 s Time: CPU 0.35 s, Wall: 0.35 s 18 Time: CPU 18.02 s, Wall: 18.08 s Time: CPU 4.46 s, Wall: 4.46 s ^C^C -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
On 1/1/13 2:45 PM, Jernej Azarija wrote: This can of course be improved by storing a hash map for each vertex and updating its neighbouring vertices on each addition/deletion of an edge and deletion of a vertex. IIRC, this is exactly how networkx works, as a dict of vertices/neighbors. Thanks, Jason -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
[sage-devel] Re: Graph neighbours - room for huge performance boost
As mentioned on the ticket it might be good to still post your broken patch. Not every patch needs to be perfect the first time. By posting your code it is easier for people to see exactly what is broken by your faster code (probably it is because there are some functions that directly modify the graph without using add_edge/delete_edge). It should really be a matter of looking at which doctests fail and fix the introduced bugs accordingly. A pastebin (www.pastebin.com) containing the failing doctest might also be usefull. Le mardi 1 janvier 2013 22:45:32 UTC+1, Jernej Azarija a écrit : Hello! By profiling Sage scripts involving graphs one can easily see that the bottleneck is usually in computing the list of neighbours (Graph.neighbours). This is somehow to be expected since most graph-theoretical algorithms perform operations on neighbours of vertices. Currently it appears that for each such query, the native graph backed computes the list of neighbours from the list of edges. This can of course be improved by storing a hash map for each vertex and updating its neighbouring vertices on each addition/deletion of an edge and deletion of a vertex. As is, it is often best to first convert the graph to a networkX graph and perform the computation there. Example: == 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 == I don't feel confident enough to simply patch the current graph backed since it appears to be written in a very precise fashion and there are parts of the specification and implementation that I do not understand completely. That said if someone is willing to provide the necessary information (on how and what needs be changed) or is willing to code it himself, here is the relevant trac ticket: http://trac.sagemath.org/sage_trac/ticket/13730 Best, Jernej -- You received this message because you are subscribed to the Google Groups sage-devel group. To post to this group, send email to sage-devel@googlegroups.com. To unsubscribe from this group, send email to sage-devel+unsubscr...@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en.
