Graph Database Module

INFO:

This module implements classes (GraphDatabase, GraphQuery, GenericGraphQuery) for interfacing with the sqlite database graphs.db.

The GraphDatabase class interfaces with the sqlite database graphs.db. It is an immutable database that inherits from SQLDatabase (see sage.databases.database.py).

The database contains all unlabeled graphs with 7 or fewer nodes. This class will also interface with the optional database package containing all unlabeled graphs with 8 or fewer nodes. The database(s) consists of five tables, and has the structure given by the function graph_info. (For a full description including column data types, create a GraphDatabase instance and call the method get_skeleton).

AUTHORS:

  • Emily A. Kirkman (2008-09-20): first version of interactive queries, cleaned up code and generalized many elements to sage.databases.database.py
  • Emily A. Kirkman (2007-07-23): inherits GenericSQLDatabase, also added classes: GraphQuery and GenericGraphQuery
  • Emily A. Kirkman (2007-05-11): initial sqlite version
  • Emily A. Kirkman (2007-02-13): initial version (non-sqlite)

REFERENCES:

class sage.graphs.graph_database.GenericGraphQuery(query_string, database=None, param_tuple=None)
Bases: sage.databases.database.GenericSQLQuery
class sage.graphs.graph_database.GraphDatabase

Bases: sage.databases.database.GenericSQLDatabase

interactive_query(display_cols, **kwds)

TODO: This function could use improvement. Add full options of typical GraphQuery (i.e.: have it accept list input); and update options in interact to make it less annoying to put in operators.

Generates an interact shell (in the notebook only) that allows the user to manipulate query parameters and see the updated results.

EXAMPLE:

sage: D = GraphDatabase()
sage: D.interactive_query(display_cols=['graph6','num_vertices','degree_sequence'],num_edges=5,max_degree=3)
<html>...</html>
query(query_dict=None, display_cols=None, **kwds)

Creates a GraphQuery on this database. For full class details, type GraphQuery? and press shift+enter.

EXAMPLE:

sage: D = GraphDatabase()
sage: q = D.query(display_cols=['graph6','num_vertices','degree_sequence'],num_edges=['<=',5])
sage: q.show()
Graph6               Num Vertices         Degree Sequence     
------------------------------------------------------------
@                    1                    [0]                 
A?                   2                    [0, 0]              
A_                   2                    [1, 1]              
B?                   3                    [0, 0, 0]           
BG                   3                    [0, 1, 1]           
BW                   3                    [1, 1, 2]           
Bw                   3                    [2, 2, 2]           
C?                   4                    [0, 0, 0, 0]        
C@                   4                    [0, 0, 1, 1]        
CB                   4                    [0, 1, 1, 2]        
CK                   4                    [1, 1, 1, 1]        
CF                   4                    [1, 1, 1, 3]        
CJ                   4                    [0, 2, 2, 2]        
CL                   4                    [1, 1, 2, 2]        
CN                   4                    [1, 2, 2, 3]        
C]                   4                    [2, 2, 2, 2]        
C^                   4                    [2, 2, 3, 3]        
D??                  5                    [0, 0, 0, 0, 0]     
D?C                  5                    [0, 0, 0, 1, 1]     
D?K                  5                    [0, 0, 1, 1, 2]     
D@O                  5                    [0, 1, 1, 1, 1]     
D?[                  5                    [0, 1, 1, 1, 3]     
D@K                  5                    [0, 0, 2, 2, 2]     
D_K                  5                    [1, 1, 1, 1, 2]     
D@S                  5                    [0, 1, 1, 2, 2]     
D?{                  5                    [1, 1, 1, 1, 4]     
D@[                  5                    [0, 1, 2, 2, 3]     
D@s                  5                    [1, 1, 1, 2, 3]     
DBg                  5                    [1, 1, 2, 2, 2]     
DBW                  5                    [0, 2, 2, 2, 2]     
D`K                  5                    [1, 1, 2, 2, 2]     
D@{                  5                    [1, 1, 2, 2, 4]     
DB[                  5                    [0, 2, 2, 3, 3]     
DIk                  5                    [1, 2, 2, 2, 3]     
DBk                  5                    [1, 1, 2, 3, 3]     
DK[                  5                    [1, 2, 2, 2, 3]     
DLo                  5                    [2, 2, 2, 2, 2]     
E???                 6                    [0, 0, 0, 0, 0, 0]  
E??G                 6                    [0, 0, 0, 0, 1, 1]  
E??W                 6                    [0, 0, 0, 1, 1, 2]  
E?C_                 6                    [0, 0, 1, 1, 1, 1]  
E??w                 6                    [0, 0, 1, 1, 1, 3]  
E?CW                 6                    [0, 0, 0, 2, 2, 2]  
EG?W                 6                    [0, 1, 1, 1, 1, 2]  
E?Cg                 6                    [0, 0, 1, 1, 2, 2]  
E@Q?                 6                    [1, 1, 1, 1, 1, 1]  
E?@w                 6                    [0, 1, 1, 1, 1, 4]  
E?Cw                 6                    [0, 0, 1, 2, 2, 3]  
E?Dg                 6                    [0, 1, 1, 1, 2, 3]  
E_?w                 6                    [1, 1, 1, 1, 1, 3]  
E?LO                 6                    [0, 1, 1, 2, 2, 2]  
E?N?                 6                    [1, 1, 1, 1, 2, 2]  
E?Ko                 6                    [0, 0, 2, 2, 2, 2]  
EGCW                 6                    [0, 1, 1, 2, 2, 2]  
E_Cg                 6                    [1, 1, 1, 1, 2, 2]  
E?Bw                 6                    [1, 1, 1, 1, 1, 5]  
E?Dw                 6                    [0, 1, 1, 2, 2, 4]  
E?Fg                 6                    [1, 1, 1, 1, 2, 4]  
E?Kw                 6                    [0, 0, 2, 2, 3, 3]  
E@HW                 6                    [0, 1, 2, 2, 2, 3]  
E@FG                 6                    [1, 1, 1, 2, 2, 3]  
E?LW                 6                    [0, 1, 1, 2, 3, 3]  
E?NG                 6                    [1, 1, 1, 1, 3, 3]  
E@N?                 6                    [1, 1, 2, 2, 2, 2]  
E@YO                 6                    [1, 1, 2, 2, 2, 2]  
E@QW                 6                    [1, 1, 1, 2, 2, 3]  
E@Ow                 6                    [0, 1, 2, 2, 2, 3]  
E_Cw                 6                    [1, 1, 1, 2, 2, 3]  
E@T_                 6                    [0, 2, 2, 2, 2, 2]  
E_Ko                 6                    [1, 1, 2, 2, 2, 2]  
F????                7                    [0, 0, 0, 0, 0, 0, 0]
F???G                7                    [0, 0, 0, 0, 0, 1, 1]
F???W                7                    [0, 0, 0, 0, 1, 1, 2]
F??G_                7                    [0, 0, 0, 1, 1, 1, 1]
F???w                7                    [0, 0, 0, 1, 1, 1, 3]
F??GW                7                    [0, 0, 0, 0, 2, 2, 2]
F@??W                7                    [0, 0, 1, 1, 1, 1, 2]
F??Gg                7                    [0, 0, 0, 1, 1, 2, 2]
F?Ca?                7                    [0, 1, 1, 1, 1, 1, 1]
F??@w                7                    [0, 0, 1, 1, 1, 1, 4]
F??Gw                7                    [0, 0, 0, 1, 2, 2, 3]
F??Hg                7                    [0, 0, 1, 1, 1, 2, 3]
FG??w                7                    [0, 1, 1, 1, 1, 1, 3]
F??XO                7                    [0, 0, 1, 1, 2, 2, 2]
F??Z?                7                    [0, 1, 1, 1, 1, 2, 2]
F??Wo                7                    [0, 0, 0, 2, 2, 2, 2]
F@?GW                7                    [0, 0, 1, 1, 2, 2, 2]
FK??W                7                    [1, 1, 1, 1, 1, 1, 2]
FG?Gg                7                    [0, 1, 1, 1, 1, 2, 2]
F??Bw                7                    [0, 1, 1, 1, 1, 1, 5]
F??Hw                7                    [0, 0, 1, 1, 2, 2, 4]
F??Jg                7                    [0, 1, 1, 1, 1, 2, 4]
F_?@w                7                    [1, 1, 1, 1, 1, 1, 4]
F??Ww                7                    [0, 0, 0, 2, 2, 3, 3]
F?CPW                7                    [0, 0, 1, 2, 2, 2, 3]
F?CJG                7                    [0, 1, 1, 1, 2, 2, 3]
F??^?                7                    [1, 1, 1, 1, 1, 2, 3]
F??XW                7                    [0, 0, 1, 1, 2, 3, 3]
F??ZG                7                    [0, 1, 1, 1, 1, 3, 3]
F?CZ?                7                    [0, 1, 1, 2, 2, 2, 2]
F_?Hg                7                    [1, 1, 1, 1, 1, 2, 3]
F?CqO                7                    [0, 1, 1, 2, 2, 2, 2]
F?CaW                7                    [0, 1, 1, 1, 2, 2, 3]
F?LCG                7                    [1, 1, 1, 1, 2, 2, 2]
F?C_w                7                    [0, 0, 1, 2, 2, 2, 3]
FG?Gw                7                    [0, 1, 1, 1, 2, 2, 3]
F?Ch_                7                    [0, 0, 2, 2, 2, 2, 2]
FG?Wo                7                    [0, 1, 1, 2, 2, 2, 2]
F_?XO                7                    [1, 1, 1, 1, 2, 2, 2]
FK?GW                7                    [1, 1, 1, 1, 2, 2, 2]
class sage.graphs.graph_database.GraphQuery(graph_db=None, query_dict=None, display_cols=None, **kwds)

Bases: sage.databases.database.SQLQuery, sage.graphs.graph_database.GenericGraphQuery

get_graphs_list()

Returns a list of Sage Graph objects that satisfy the query.

EXAMPLES:

sage: Q = GraphQuery(display_cols=['graph6','num_vertices','degree_sequence'],num_edges=['<=',5],min_degree=1)
sage: L = Q.get_graphs_list()
sage: L[0]
Graph on 2 vertices
sage: len(L)
35
number_of()

Returns the number of graphs in the database that satisfy the query.

EXAMPLES:

sage: Q = GraphQuery(display_cols=['graph6','num_vertices','degree_sequence'],num_edges=['<=',5],min_degree=1)
sage: Q.number_of()
35
query_iterator()

Returns an iterator over the results list of the GraphQuery.

EXAMPLE:

sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
sage: for g in Q:
...     print g.graph6_string()
F@?]O
F@OKg
F?`po
F?gqg
FIAHo
F@R@o
FA_pW
FGC{o
FEOhW

sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
sage: it = iter(Q)
sage: while True:
...     try: print it.next().graph6_string()
...     except StopIteration: break 
F@?]O
F@OKg
F?`po
F?gqg
FIAHo
F@R@o
FA_pW
FGC{o
FEOhW
show(max_field_size=20, with_picture=False)

Displays the results of a query in table format.

INPUT:

  • max_field_size - width of fields in command prompt version
  • with_picture - whether or not to display results with a picture of the graph (available only in the notebook)

EXAMPLES:

sage: G = GraphDatabase()
sage: Q = GraphQuery(G, display_cols=['graph6','num_vertices','aut_grp_size'], num_vertices=4, aut_grp_size=4)
sage: Q.show()
Graph6               Num Vertices         Aut Grp Size        
------------------------------------------------------------
C@                   4                    4                   
C^                   4                    4                   
sage: R = GraphQuery(G, display_cols=['graph6','num_vertices','degree_sequence'], num_vertices=4)
sage: R.show()
Graph6               Num Vertices         Degree Sequence     
------------------------------------------------------------
C?                   4                    [0, 0, 0, 0]        
C@                   4                    [0, 0, 1, 1]        
CB                   4                    [0, 1, 1, 2]        
CK                   4                    [1, 1, 1, 1]        
CF                   4                    [1, 1, 1, 3]        
CJ                   4                    [0, 2, 2, 2]        
CL                   4                    [1, 1, 2, 2]        
CN                   4                    [1, 2, 2, 3]        
C]                   4                    [2, 2, 2, 2]        
C^                   4                    [2, 2, 3, 3]        
C~                   4                    [3, 3, 3, 3]        

Show the pictures (in notebook mode only):

sage: S = GraphQuery(G, display_cols=['graph6','aut_grp_size'], num_vertices=4)
sage: S.show(with_picture=True)
...
NotImplementedError: Cannot display plot on command line.            

Note that pictures can be turned off:

sage: S.show(with_picture=False)
Graph6               Aut Grp Size
----------------------------------------
C?                   24
C@                   4
CB                   2
CK                   8
CF                   6
CJ                   6
CL                   2
CN                   2
C]                   8
C^                   4
C~                   24

Show your own query (note that the output is not reformatted for generic queries):

sage: (GenericGraphQuery('select degree_sequence from degrees where max_degree=2 and min_degree >= 1',G)).show()
degree_sequence     
--------------------
211                 
222                 
2211                
2222                
21111               
22211               
22211               
22222               
221111              
221111              
222211              
222211              
222211              
222222              
222222              
2111111             
2221111             
2221111             
2221111             
2222211             
2222211             
2222211             
2222211             
2222222             
2222222
sage.graphs.graph_database.data_to_degseq(data, graph6=None)

Takes the database integer data type (one digit per vertex representing its degree, sorted high to low) and converts it to degree sequence list. The graph6 identifier is required for all graphs with no edges, so that the correct number of zeros will be returned.

EXAMPLE:

sage: from sage.graphs.graph_database import data_to_degseq
sage: data_to_degseq(3221)
[1, 2, 2, 3]
sage: data_to_degseq(0,'D??')
[0, 0, 0, 0, 0]
sage.graphs.graph_database.degseq_to_data(degree_sequence)

Takes a degree sequence list (of Integers) and converts to a sorted (max-min) integer data type, as used for faster access in the underlying database.

EXAMPLE:

sage: from sage.graphs.graph_database import degseq_to_data
sage: degseq_to_data([2,2,3,1])
3221
sage.graphs.graph_database.graph6_to_plot(graph6)

Constructs a graph from a graph6 string and returns a Graphics object with arguments preset for show function.

EXAMPLE:

sage: from sage.graphs.graph_database import graph6_to_plot
sage: type(graph6_to_plot('D??'))
<class 'sage.plot.plot.Graphics'>
sage.graphs.graph_database.graph_db_info(tablename=None)

Returns a dictionary of allowed table and column names.

INPUT:

  • tablename - restricts the output to a single table

EXAMPLE:

sage: graph_db_info().keys()
['graph_data', 'degrees', 'spectrum', 'misc', 'aut_grp']
sage: graph_db_info(tablename='graph_data')
['complement_graph6',
 'eulerian',
 'graph6',
 'lovasz_number',
 'num_cycles',
 'num_edges',
 'num_hamiltonian_cycles',
 'num_vertices',
 'perfect',
 'planar']
sage.graphs.graph_database.subgraphs_to_query(subgraphs, db)

Constructs and returns a GraphQuery object respecting the special input required for the induced_subgraphs parameter. This input can be an individual graph6 string (in which case it is evaluated without the use of this method) or a list of strings. In the latter case, the list should be of one of the following two formats: 1. [‘one_of’,String,...,String] Will search for graphs containing a subgraph isomorphic to any of the graph6 strings in the list. 2. [‘all_of’,String,...,String] Will search for graphs containing a subgraph isomorphic to each of the graph6 strings in the list.

This is a helper method called by the GraphQuery constructor to handle this special format. This method should not be used on its own because it doesn’t set any display columns in the query string, causing a failure to fetch the data when run.

EXAMPLE:

sage: from sage.graphs.graph_database import subgraphs_to_query
sage: gd = GraphDatabase()
sage: q = subgraphs_to_query(['all_of','A?','B?','C?'],gd)
sage: q.get_query_string()
'SELECT , ,, ,,  FROM misc WHERE ( ( misc.induced_subgraphs regexp ? ) AND ( misc.induced_subgraphs regexp ? ) ) AND ( misc.induced_subgraphs regexp ? )'

Previous topic

Graph Coloring

Next topic

A collection of constructors of common graphs.

This Page