On 5/21/14, 13:21, William Stein wrote:
On Wed, May 21, 2014 at 11:18 AM, kcrisman <[email protected]> wrote:
I'm about to give a very intro talk about graph theory in Sage, and
the graph database section [1] of the reference manual begins: "...
This class will also interface with the optional database package
containing all unlabeled graphs with 8 or fewer nodes."
I can't find any optional package to install to get these extra graphs
up to 8 vertices. Anybody have any idea what happened to this? I
realize that this stuff was originally done by Robert Miller and Emily
Kirkman, who have moved on to other things (Home Depot and Actuarial
work, I think...), but maybe somebody has kept track... If not, we
should delete that line from the reference manual.
There is a database included in Sage with graphs up to 7 nodes:
for k in [1..9]:
print k, GraphQuery(display_cols=['num_vertices'],
num_vertices=k).number_of()
1 1
2 2
3 4
4 11
5 34
6 15
7 1044
8 0
9 0
So the builtin database is pretty tiny -- only just over a thousand
graphs total?
Well, the problem is that there is a LOT of information in the database,
some of which is quite expensive to compute for all isomorphism classes.
I appreciate that.
Also, the database must still exist in some sense, or
http://artsci.drake.edu/grout/graphs/ wouldn't work... I just found all
three graphs with degree sequence 22222222 - which leads me to wonder how
that syntax would have to change if two-digit (in decimal) values for degree
were possible if the database were bigger ;-)
That database http://artsci.drake.edu/grout/graphs/ was maybe a key
part of Jason Grout's Ph.D. work -- and making a Sage version of it
(which is what is in Sage up to 7 vertices) was one of the things that
got him involved with Sage development.
It was actually for my masters thesis that I originally did the
database. And it was the very first thing that got me involved in Sage
development.
You can see at the http://artsci.drake.edu/grout/graphs/ page that I
still have the 8-vertex database up. It's a mysql database, and I just
dumped it to a sql file and posted it here:
http://boxen.math.washington.edu/home/jason/graph-database.sql.gz
To answer Karl-Dieter's question, obviously the degree sequence string
format would change, or we could count in hex or something.
Thanks,
Jason
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
