> > We need to be able to convert to and from the graph6 and sparse6 formats
> > to an adjacency matrix and to a graph.
Done.
> > We need some hooks to nauty.
Not done: we have reimplemented instead. If I don't do it before Sage
Days 7, I will do it there: create a (necessarily optional) spkg to
include nauty, and give all the relevant functions the option to call
nauty instead. I believe geng is part of nauty, so this would come
along for the ride. This should definitely be a wishlist trac ticket.
> > (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.
Done. (Orbits are not part of the output, but can be easily read off
from the generators, and is a function of a permutation group (I
certainly hope))
> > (b) Determine if two graphs are isomorphic; if they are then provide the
> > isomorphism, if they are not, return canonical labels.
Done.
> > A python generator
> > based on geng. (This could be more useful in some respects than a
> > database.)
Done. For example:
sage: for g in graphs(3):
if g.order() != 0: print g.spectrum()
....:
[0.0]
[0.0, 0.0]
[0.0, 0.0, 0.0]
[-1.0, 0.0, 1.0]
[-1.41421356237, 1.16280682999e-16, 1.41421356237]
[-1.0, 1.0]
[-1.0, -1.0, 2.0]
> > (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.
Comments: Emily Kirkman has done some extensive work on embedding
graphs in surfaces, and I'd love to see some conversation about this
at Sage Days 7.
> > (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.
Cayley graphs are implemented, but most likely not to the extent
anyone wants. For example, you can call cayley_graph on some groups,
and get the graph back, but the functionality is very limited. There
is certainly no CayleyGraph class, which would be a thousand times
better than the current situation. Definitely create a ticket for
this.
> > (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.
There is an existing trac ticket for improving the vertex association
setup- most likely these comments should just go on that ticket. Any
object at all can be the label for an edge, so I don't think there is
too much to do here.
Another ticket you might want to create, but that I would be most
likely to implement, is edge-labeled graph isomorphism.
> > (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?
Graphs and codes are implemented, but I don't think designs are.
Ultimately, there should be an incidence structure class which they
inherit from etc etc etc. Definitely a wishlist ticket, and likely a
good coding sprint idea for Sage Days 7.
> > (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.
Nobody I know of. If you did this type of stuff in your dissertation,
then I nominate you! Create a 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.
Database of small graphs: done
Ted Spence's regular graphs: not done
Gordon Royle's data: not done
> Trac ticket?
Maybe not yet for this one. We've invited Gordon Royle to SD7, and if
he comes, you and he and Emily could have a session about databases...
> > 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.
If you look into the code that graphs(7) calls, you will notice that
you can pass it any vertex-hereditary property, including being a
tree. So in some sense, this is already implemented. However, this
could be its own constructor, and more importantly, I know of a way to
optimize the generation of trees to go much faster than it would with
what I described above. Create a ticket, and assign it to me.
> > 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?)
I would expect so, since Sage wants to be as fast as possible at
anything Linear Algebra. Someone who knows more should comment...
> 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?
Not really sure. Optimally, Chris Godsil might speak about something
like this at SD7.
> > 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.
Emily Kirkman understands a linear time algorithm for testing for
planarity. There is one in BOOST, which is GPL, and has been nominated
for inclusion in Sage several times.
> > 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.
Sean Howe wrote a javascript editor, and that is lurking in my email
somewhere. I think it was decided against for reasons of notebook
security, and in favor of the new Java3d stuff. The problem is that
interactive GUIs is a difficult problem for anything in Sage. Also,
nothing has been written for the Java3d stuff yet. The problem with a
lot of graph visualizers and editors already written is that most of
them aren't very high quality, and there are so many low quality
ones...
> 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.
I was brainstorming about something like widgets a while ago, before
the notebook underwent its sea change. We (>= you and I) should make
this a coding sprint at SD7.
> > 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.
Mike's department.
> > 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?
See above.
> > 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?
Maybe make a ticket for this?
--
Robert L. Miller
University of Washington
Department of Mathematics
http://www.rlmiller.org/
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
