I'm CCing this to sage-devel since William asked for all development conversations to be posted there.
Robert Miller wrote: > On Nov 27, 2007 10:47 PM, Jason Grout <[EMAIL PROTECTED]> wrote: > >> Robert, >> >> A couple of months ago I talked with Chris Godsil about ways to improve >> the graph theory stuff in Sage. He mentioned that he had given you a >> list of things that he could use in Sage. Do you have that list handy >> and would you be willing to put it up somewhere, like the wiki or >> something? I could work on Butterfly graphs and getting feature-parity >> with Combinatorica, but it seems like it would be more valuable to work >> first on stuff that someone actually could use :). >> > > William and I just had a very similar conversation- it's better to > compete for specific users than to try to beat out software just to > beat it. The list is here- > > http://sage.math.washington.edu/home/rlmill/wshlst.pdf > > It looks like you've already done a lot of this. I'd like to make trac tickets for what we haven't done, but I realized that you know things better than I do. Can you (or anyone else) confirm our progress? The rest of this email takes Chris's list point by point. > We need to be able to convert to and from the graph6 and sparse6 formats > to an adjacency matrix and to a graph. This is done, right? Well, we can't directly convert from graph6 to a matrix, but we can convert to a graph and immediately call am(), like Graph('graph6 string').am() to convert to an adjacency matrix. > We need some hooks to nauty. In particular we want to be able to the > following: > (a) Given a graph and a partition of its vertex set, get generators, > orbits and > the order of the group of automorphisms of the graph that preserve the > partition. This is done, right? The examples in automorphism_group() seem to indicate so. > (b) Determine if two graphs are isomorphic; if they are then provide the > isomorphism, if they are not, return canonical labels. This is done too, if I understand things correctly, though we have to do things in two steps. G.is_isomorphic(H, certify=True) returns the isomorphism. We can separately call canonical_label() to get canonical labels. > I know that with sage installed, it is easy enough to download nauty. > However > I have not been able to work out how to actually invoke nauty from sage. > It would also be very useful to have something like a python generator > based on geng. (This could be more useful in some respects than a > database.) It seems like you were working on this. I agree that it would be very useful. I think it might also be useful to wrap geng for those of us that have it installed. > (a) Graphs on surfaces: [This item is a place-holder; I am not sure what > data structures people will want.] I'll pass on this for now until we know more about what we should do. > (b) Cayley graphs: These can be dealt with in GAP, but I think it would be > useful to have a class, with the group and generating set explicit. Cayley > graphs could be directed or undirected. Circulants and Cayley graphs > for Zd (where p is prime) could be useful special cases. Is anyone working on this? If not, I'll make a trac ticket. I've already implemented circulant graphs. > (c) Edge-colored graphs: A graph and functions from its edges to an index > set, and vice versa. These could also be represented as a set of > matchings, > and this data structure can be used to represent maps on surfaces. I think we should make a nice system for attaching arbitrary metadata to vertices and edges of a graph. Something like an attribute dictionary for each vertex and edge. > (d) Bipartite graphs: We will need to deal with some incidence structures, > and these can be encoded as bipartite graphs. We want to get the point > graphs and line graphs of incidence structures. If we have a procedure to > convert a graph G to an incidence structure of vertices and edges, then > the line graph of the incidence structure is the line graph of G. Do we have a way to represent and work with incidence structures in Sage natively? > (e) Bundles: Start with a base graph G with vertices {1, . . . , n}. > For each > vertex i we are given a graph Ci . For each edge ij we are given a > bipartite > graph joining V (Ci ) to V (Cj ). (There is an implicit orientation here.) > Some examples: > (i) The Petersen graph: n = 2, C1 is the 5-cycle, C2 is its complement > and the bipartite graph is a 5-matching. > (ii) The Hoffman-Singleton graph can be constructed with n = 2, where > C1 is an independent set on 15 vertices, C2 is a nice distance regular > graph on 35 vertices,. . . > (iii) Covering graphs. Here the graphs Ci are empty on r vertices, and > each bipartite graphs is either an r-matching or is empty. Huh, I used this idea extensively in my dissertation and a research paper. I used the "blowup graph" terminology, though, from extremal graph theory. Is anyone working on this? If not, I'll make a trac ticket. > A database of small graphs. Put Ted Spence’s strongly regular graphs > into a > database. (In this case the important thing is to have the graphs > themselves, > we would not necessarily need much data.) Gordon Royle has more data > than he knows what to do with. Trac ticket? > A database of trees, or a generator for trees. I think it would be > reasonably > straightforward to generate rooted trees, and hence get trees. The > generators > would be more useful than the database. It is not impossible that > something > in the nauty package generates trees. Again, I thought this was something you (Robert) were working on. If not, I'll make it a trac ticket. > A lot of this will be in NetworkX, and I am not sure what is there. It > would > be useful to have quick and dirty recursive routines to find max cliques, > max independent set, chromatic number, Hamilton cycles, Hamilton paths, > chromatic polynomial, Tutte polynomial. Edge colorings. Efficient routines > would be better, but the problem is to find them. There is a clique > routine > in C at http://users.tkk.fi/∼pat/cliquer.html > I would want to be able to find cut vertices and 2-cuts (and hence decide > if the graph is 3-connected). Eventually someone will ask about computing > vertex and/or edge connectivity; I assume some of this is in NetworkX. > Personally, I want some eigenvalue stuff. For small graphs, I want the > eigenvalues computed fast in floating point, and the eigenspaces. NTL will > compute the characteristic polynomial of quite large graphs. Already done: * max cliques (see cliques() and cliques_*) * computing eigenvalues (is it as fast as Chris is thinking?) Not done (and fodder for trac tickets): * max independent set * chromatic number * hamiltonian cycles and paths * chromatic polynomial * Tutte polynomial * finding edge colorings * compare cliques() and related functions with the routine at http://users.tkk.fi/~pat/cliquer.html (the routine is released under GPL) * cut-sets (more generally, min/max flow algorithms) * vertex and edge connectivity (I don't think this is in NetworkX) * eigenspaces * characteristic polynomial (NTL?) > I would like a procedure which given an n × n (sparse) matrix A and an > n-vector z, would compute the monic polynomial of least degree f such that > f (A)z = 0. In other words, find the least integer d such that Ad z > lies in the > span of > z, Az, . . . , A^(d−1) z > and give me the coefficients of A^d z when we write it as a linear > combination of > these vectors. I could use this to derive information about walk > generating > functions for large graphs, and hence get spectral information. The field > could be Q, or Zp . (We might need the latter to circumvent coefficient > growth problems.) This sounds like a good problem for other parts of Sage. Can we do this already? > Someone is eventually going to ask for a routine to test for planarity. I > believe that there are good ones in existence, but it’s going to be > hard to get > a good one with an open source licence. The nauty README has this to say about the new planarity testing feature: "New program planarg to test for planarity and find planar embeddings: planarg -help for details. The planarity code was written by Paulette Lieby for the Magma project and used with permission." Does anyone know Paulette Lieby? Can we ask about releasing the code under GPL? It looks like the source has now been released as a part of nauty. > A graph editor. This would allow graphs to be constructed and edited by > pointing and clicking. It should be able to output ps/pdf files. We > want to > be able to save the current state in machine readable form, and to be able > to input graphs in this form. This means we will have drawings as explicit > objects. (Thus it would be easy to write programs to generate drawings.) > If we have a graph displayed in the editor, we should be able to access it > from sage/python, and compute parameters there. So I would like to be able > to adjust the graph with the mouse, or from sage. > Some people will want to be able to use arbitrarily complicated curves > for the edges, and to place all sorts of text around the drawing. This > will > lead to something like xfig rewritten in sage. Indeed, this does sound like a very ambitious project. We might look at incorporating other graph editors. There are a few written in Java that might be useful. As it is, though, do we have any GUI things we can work with other than Java (like the recent interactive 3d plots) or some sort of AJAX trickery? We may be able to do something with javascript draggable objects here, using jquery or some other javascript GUI library. It seems like at one point someone mentioned another javascript library for drawing on a web page. If we do this in the web, then having interactive widgets in the notebook seems like the way to go. That's another project that would be useful. > The reference here is Stanton and White. We want rank, unrank and genera- > tors for basis combinatorial objects. For example, permutations: the > unrank > function, given i such that 1 ≤ i ≤ n!, returns the i-th permutation, > the rank > function is its inverse. [Well, I might have rank and unrank swapped, but > the idea should be clear.] > Basic objects include sets, k-sets, elements of S n (Grey codes), permuta- > tions, set partitions, integer partitions, perfect matchings,. . . Are there any of these that Mike has not implemented? I know he's done a pretty comprehensive job. > There is another important issue here. It is quite common to want to > construct a graph as follows. We have a set S of things (e.g., > permutations) > which will be our vertices and a binary function f on S. Two vertices > a and b > are adjacent if f (a, b) takes a specified value. It would be > extremely useful to > be able to construct graphs directly from a specified set and binary > function. This is done (see trac #850). > It would be very useful to be able to form incidence structures from > differ- > ence sets. Here the input would be a group G and some subsets S1 , . . > . , Sm ; > the point set of the incidence structure would be G, and the blocks would > be the translates Sig for i = 1, . . . , m and g in G. Even just the > case G = Zd > n > would be a good start. Again, do we have facilities for working with incidence structures in Sage? > Sometimes I want to construct graphs whose vertices are subspaces of a > vector space over a finite field. It could be useful to have a > generator for > the lines of the associated projective space, or even subspaces of a given > dimension. Is there an easy way to generate all of the subspaces of a vector space already in Sage, maybe restricted to a particular dimension, from the original vector space? Thanks, Jason --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
