[Nauty] Version 2.2 beta 3 released; future things

[Sterten at aol.com]

 >Recent versions of nauty have the in-principle capability of
 >processing objects other than graphs.  The same program can
 >even use nauty on several types of object at once.  So far
 >I have not released any code for this but a few bits exist
 >in working protypes.  Here is a list of what is planned.
 >
 >1. Sparse graphs.  Presently a graph needs n^2 bits of storage
 >  irrespective of the number of edges, so getting past about
 >  60,000 vertices is nearly impossible.  This facility will allow
 >  you to process graphs and multigraphs up to millions of vertices
 >  provided they fit into memory at 16 bytes per edge.  There will
 >  be an option for allowing colours on the edges.

sometimes you don't have the edges explicitely, but a numerical
subroutine, which -given u,v- computes whether there is an
edge between them (e.g. chess-queen-graphs). The graphs can be
very big and many things can be done even without having the edges stored.

One problem which I encountered with tiling problems are intersection graphs.
Suppose you have S={1..100} and V is a large subset of its powerset.
There is an edge v-w, if v and w have nonempty intersection.
You can't store the adjacency matrix but still want to find
connected components,large cliques,cycles,holes,cutsets,certain subgraphs
or calculate some parameters etc.



 >Requests will be considered.

what about directed graphs and graphs with loops ?
I.e. any relation = n*n matrix with entries from {0,1} .
That's a natural generalization IMO and maybe some or most
undirected routines can be generalized.


Guenter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20021120/4845a743/attachment.html