As a matroid theorist I care about creating millions and millions of small graphs (10 vertices is already a LOT). I don't modify them once they're ready, but graph modification can be helpful in creating a copy of the graph with an edge contracted, with an edge deleted, or with a vertex deleted. Oh, and I really dig multiple edges, loops, and edge labels.
I care about the same thing when it comes to sets, and Sage's Set data structure just doesn't cut it. Graphs don't bother too much with the category framework, right? --Stefan On Tuesday, October 27, 2015 at 10:40:21 AM UTC-5, Nathann Cohen wrote: > > Hello everybody, > > I have nothing planned yet, but these days I often think of the > different data structures available for graphs (and digraphs) in Sage. > > Currently, Sage's default data structure is optimized for a fast "edge > test" detection (log n). This is good for some applications, and bad > for others. > > One thing is very important when it comes to (graph) algorithms: the > defaut data structure only matters for (sub)-linear algorithms. > Indeed, for algorithms of higher complexity it is comparatively cheap > to change the data structure, and work on the copy instead. > > The current default data structure, however, makes it hard to load > *large* (> millions of nodes) graphs in memory, for adding an edge is > relatively expensive and the data structures wastes quite some memory. > > For those applications, it would make more sense to have a simpler > data structure. Deleting an edge/vertex, however, or testing adjacency > between two vertices would be *very* slow. In those case, copying the > graph to another (the current default) data structure would be > 'required'. > > If you use graphs in your code, could you tell me if you instensively > remove vertices/edges or test adjacency? Or would you prefer to > exchange that for a reduced memory cost? > > Once more: I have nothing planned. Just wondering. And knowing what > you think may help. > > Thanks, > > 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/d/optout.
