6688
Comment:

← Revision 14 as of 20081114 13:42:10 ⇥
6709
converted to 1.6 markup

Deletions are marked like this.  Additions are marked like this. 
Line 3:  Line 3: 
The SAGE [http://wiki.sagemath.org/graph Graph Theory Project] aims to implement Graph objects and algorithms in ["SAGE"].  The SAGE [[http://wiki.sagemath.org/graphGraph Theory Project]] aims to implement Graph objects and algorithms in [[SAGE]]. 
Line 9:  Line 9: 
[[TableOfContents]]  <<TableOfContents>> 
Line 15:  Line 15: 
* [http://amalfi.dis.unina.it/graph/ Link]  * [[http://amalfi.dis.unina.it/graph/Link]] 
Line 22:  Line 22: 
* [http://www.bioinformatics.ucla.edu/pygr/ Link]  * [[http://www.bioinformatics.ucla.edu/pygr/Link]] 
Line 28:  Line 28: 
* [http://comad2005.persistent.co.in/COMAD2005Proc/pages138147.pdf Paper] * [http://osl.iiitb.ac.in/oslwiki/index.php/GRACE Link] 
* [[http://comad2005.persistent.co.in/COMAD2005Proc/pages138147.pdfPaper]] * [[http://osl.iiitb.ac.in/oslwiki/index.php/GRACELink]] 
Line 34:  Line 34: 
* [http://documents.wolfram.com/mathematica/AddonsLinks/DatabaseLink/Examples/GraphDatabase/index.en.html Link]  * [[http://documents.wolfram.com/mathematica/AddonsLinks/DatabaseLink/Examples/GraphDatabase/index.en.htmlLink]] 
Line 39:  Line 39: 
* [http://magma.maths.usyd.edu.au/magma/htmlhelp/text1477.htm Link] * A catalogue of strongly regular graphs is available. This catalogue has been put together from various sources by B. !McKay and can be found [http://cs.anu.edu.au/~bdm/data/ here]. Graphs in the database are indexed by a sequence of four parameters. They are, in order: the order of the graph, its degree, the number of common neighbours to each pair of adjacent vertices, and the number of common neighbours to each pair of nonadjacent vertices. 
* [[http://magma.maths.usyd.edu.au/magma/htmlhelp/text1477.htmLink]] * A catalogue of strongly regular graphs is available. This catalogue has been put together from various sources by B. !McKay and can be found [[http://cs.anu.edu.au/~bdm/data/here]]. Graphs in the database are indexed by a sequence of four parameters. They are, in order: the order of the graph, its degree, the number of common neighbours to each pair of adjacent vertices, and the number of common neighbours to each pair of nonadjacent vertices. 
Line 44:  Line 44: 
* [http://people.csse.uwa.edu.au/gordon/data.html Link]  * [[http://people.csse.uwa.edu.au/gordon/data.htmlLink]] 
Line 62:  Line 62: 
* [https://math.byu.edu/~grout/graphs/ Link]  * [[https://math.byu.edu/~grout/graphs/Link]] 
Line 83:  Line 83: 
* Database is being moved to SQLite and/or PostgreSQL. The web interface will probably remain much the same. A standalone [http://www.riverbankcomputing.co.uk/pyqt/ PyQT] frontend is also being developed (with GPL license by requirement of PyQT).  * Database is being moved to SQLite and/or PostgreSQL. The web interface will probably remain much the same. A standalone [[http://www.riverbankcomputing.co.uk/pyqt/PyQT]] frontend is also being developed (with GPL license by requirement of PyQT). 
Introduction
The SAGE Graph Theory Project aims to implement Graph objects and algorithms in SAGE.
The purpose of this survey is to compare currently existing Graph Database software. I am looking for a substantially large database of graphs and their properties, so that users can query properties and efficiently obtain a list of graphs. I am looking for programs as examples, to gather information, or to potentially wrap into our Graph Theory Package. Recommendations are welcome. Please note the section set aside for suggestions.
Emily Kirkman is working on this project.
Contents
Suggestions
 ???
The Graph Database
 Purpose: To provide standard test ground for benchmarking matching algorithims.
 The graphs have been randomly generated according to six different generation models, each involving different possible parameter settings. As a result, 84 diverse kinds of graphs are contained in the database. Each type is represented by thousands of pairs of graphs for which an isomorphism or a graphsubgraph isomorphism relation holds, for a total of 143,600 graphs.
 would have to fill dict's with our algorithms, but could use their graphs
 seems free and open but no license info
Pygr
 Pygr is an open source software project to develop graph database interfaces for the popular Python language, with a strong emphasis on bioinformatics applications ranging from genomewide analysis of alternative splicing patterns, to comparative genomics queries of multigenome alignment data. We have used Pygr successfully for many projects, but it is prerelease software!
 might be interesting example, but won't be using the same properties
 open source
GRACE
 GRACE is a database management system for managing data that is in the form of labeled undirected graphs. GRACE introduces a new data model for graph data and a query language called Safari, which supports both attribute and structural searches. The users can add graphs to a database. The graphs can be retrieved based on their properties. The properties of a graph include the attributes associated with a graph and the structure of the graph.
 appears free and open, but no license info
Mathematica Graph Database Package
 No info on how many graphs or how they were generated
 Queryable properties include: graph, order, edges,vertex connectivity, edge connectivity, diameter, girth, number of spanning trees, spectrum length, is simple, is connected, is bipartite, is planar, is regular, is eulerian, is hamiltonian, is tree, is biconnected, is complete, is perfect, is selfcomplementary
MAGMA Graph Database and Graph Generation
A catalogue of strongly regular graphs is available. This catalogue has been put together from various sources by B. McKay and can be found here. Graphs in the database are indexed by a sequence of four parameters. They are, in order: the order of the graph, its degree, the number of common neighbours to each pair of adjacent vertices, and the number of common neighbours to each pair of nonadjacent vertices.
There link above gives BD McKay's catalogue, which list graphs by category: Simple, Eulerian, Strongly Regular, Ramsey, Hypohamilitonian, Planar
Combinatorial Catalogues
These are also organized by type, and also (similar to MAGMA) in BD McKay’s graph6 and sparse6 format. Nauty handles this format, but there is also an open source (no visible copyright or license) C program called readg available at this site. It gives a couple of text format options: list, adj matrix, edge list.
 Here are the headings from Gordon Royle’s database:
 Small graphs
 Small multigraphs
 Cubic graphs
 Symmetric cubic graphs (Foster Census)
 Vertextransitive graphs
 Cayley graphs (by group)
 Vertextransitive cubic graphs
 Cubic Cages and higher valency cages
 Planar graphs
 Cubic Planar graphs (drawings!)
 Strongly regular graphs (parameters)
 SelfComplementary Graphs
 Constructions of Certain Graphs
Graph Database
 Web application, query by property
 will list query results in table next to pictures of graphs, sorted by number of nodes
 can use to check properties
 13,598 graphs in the database (run empty query)
 free, but closed source
Notes from the author (Jason Grout):
Version 1 (as reviewed above):
 Includes all graphs having 8 or fewer vertices.
 Uses MySQL on the backend and PHP scripts to query the database.
Most data (graph parameters, subgraphs, etc.) in the first version was generated using a combination of the Mathematica Combinatorica package, Magma, Brendan McKay's pickg program with various options, custom C programs, and shell scripts to translate things into SQL INSERT statements.
 Pictures were done using the graphviz software.
 PHP scripts and SQL source available (and usable in SAGE) upon request.
 Properties include degree sequence properties, spectrum properties, automorphism group properties, induced subgraph and forbidden subgraph properties, complements, standard graph invariants (girth, radius, clique number, connectivity, Eulerian, planar, perfect, etc.). Each of these is queryable and displayable.
Main identifier is BD McKay's graph6 code.
Version 2 (in progress and almost done as of January 2007):
 Will include all graphs up through 9 vertices (288,266 graphs).
 Data is being completely regenerated using Mathematica Combinatorica package, Magma, and other programs. All programs used to do this are available upon request so they can be inspected for correctness.
Database is being moved to SQLite and/or PostgreSQL. The web interface will probably remain much the same. A standalone PyQT frontend is also being developed (with GPL license by requirement of PyQT).
 SQLite database and SQL source available (and usable in SAGE) upon request.