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: map<int,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 map<int,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>>
