Robert Miller wrote:
>>> 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.
Trac #1301
>>> (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.
I put this up on the wiki for sage days 7. I'm not sure that I put it
up in the right place or in the right format, but at least it's there so
it won't get lost.
>
>>> (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.
Trac #1303
>
>>> (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.
Indeed, it is Trac #743.
>
> Another ticket you might want to create, but that I would be most
> likely to implement, is edge-labeled graph isomorphism.
Trac #1304
>
>>> (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.
Trac #1305 and a note on the SD7 wiki.
>
>
>>> (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.
Trac #1306
>
>>> 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
Trac #1307
> Gordon Royle's data: not done
Trac #1308
>
>> 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...
Oops, well, now it won't get lost since it's a trac ticket :). i put a
note on the SD7 page.
>
>>> 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.
>
Trac #1309
>> 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?)
Tracs #1310 through #1319. Some of these should be really trivial, but
I put them up anyway so that they don't get lost.
>>> 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.
Trac #1320
>
>>> 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
[snip]
> 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...
Trac #1321
>
>> 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.
I put a note on SD7 wiki and created Trac #1322.
>>> 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?
>
Trac #1323
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/
-~----------~----~----~----~------~----~------~--~---
