Hi folks, I vaguely remember a thread started by Nathann Cohen about moving some implementation of graph theoretic algorithms to some sort of algorithm modules. From what I can recall, it had something to do with the bloat of methods that each instance of a graph object has. For example, as of Sage 4.6.1.alpha3 an undirected graph object has 251 methods. That's what I think is an example of an object being bloated. I can't recall nor find the original thread(s), so my apology for raising the issue again.
Many methods that a graph object inherits can be refactored out into common algorithm modules with names such as clique.py(x), cluster.py(x), traversal.py(x), spanning_tree.py(x), shortest_path.py(x), etc. NetworkX does this for many graph theoretic algorithms and I'm partial to the approach. I'm working on ticket #10433 [1], whose goal is to rewrite or at least clean up the implementation of minimum spanning tree. But I would like to move all code relating to spanning trees into a new module called sage/graphs/spanning_tree.py(x) In this way, stuff relating to spanning trees and minimum spanning trees are organized in one file and many graph objects would be less bloated with over 200 methods. Part of my reason for doing so is this. Imagine you want to find out information about what spanning tree algorithms are implemented in the Sage library. The top-level documentation [2] of graph theory doesn't help at all. So let's try the documentation for generic graphs: no. How about undirected graphs: yes. How about digraphs: no. So you've looked through three different documentation pages only to find out that minimum spanning trees are only implemented for undirected graphs. But if code relating to spanning trees were organized in sage/graphs/spanning_tree.py(x) and advertised at [2], you could have saved a lot of time. Another advantage is that we need not implement spanning tree code for digraphs in the digraph module. The proposed module sage/graphs/spanning_tree.py(x) should at least take care of the following: * spanning tree algorithms * minimum spanning tree algorithms: randomized algorithms, Kruskal's algorithm, Prim's algorithm, Boruvka's algorithm * implement the above algorithms for undirected graphs, digraphs, multigraphs, multidigraphs Comments, suggestions, and criticisms are welcome. [1] http://trac.sagemath.org/sage_trac/ticket/10433 [2] http://www.sagemath.org/doc/reference/graphs.html -- Regards Minh Van Nguyen -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
