The SAGE [http://sage.math.washington.edu:9001/graph Graph Theory Project] aims to implement Graph objects and algorithms in ["SAGE"].

The goal of the Graph Database is to implement constructors for many common graphs, as well as thorough docstrings that can be used for reference. The Graph Database will grow as the Graph Theory Project does. Robert Miller has been working on a graphics primitive for SAGE Graph objects, which has allowed us to pre-set a position dictionary for the x-y coordinates of each node. (Browse code and examples below). We also have the ability to view graphs in a SAGE Graphics Array, write text on the graphs, etc. that we inherit from having an associated SAGE Graphics Object for each SAGE Graph.

As we implement algorithms into the Graph Theory Package, the constructors of known graphs would set their properties upon instantiation as well. For example, if someone created a very large complete bipartite graph and then asked if it is a bipartite graph (not currently implemented), then instead of running through an algorithm to check it, we could return a value set at instantiation. Further, this will improve the reference use of the docstrings as we would list the properties of each named graph.

I am also launching a [http://sage.math.washington.edu:9001/graph_db_survey survey] of existing graph database software. I am looking for a substantially large database of graphs and their properties, so that users can query properties.

Scroll down to see current status and examples. There are lots of pictures, so I recommend using the Table of Contents to navigate. Also, please note the suggestions section. Posting suggestions there will be easiest for me to keep on top of.

Emily Kirkman is working on this project.

TableOfContents

Suggestions

Graphs I Plan to Add

Recently Added: Info Coming Soon

Inherited from NetworkX

Families of Graphs

Named Graphs

Currently Implemented in Graph Database

Class Docstrings

A collection of constructors of common graphs.

USES:
    A list of all graphs and graph structures in this database is available via tab completion.
    Type "graphs." and then hit tab to see which graphs are available.

    The docstrings include educational information about each named graph with the hopes that this
    database can be used as a reference.

PLOTTING:
    All graphs (i.e., networks) have an associated SAGE graphics object, which you can display:
        
        sage: G = WheelGraph(15)
        sage: p = G.plot()
        sage: is_Graphics(p)
        True

    When creating a graph in SAGE, the default positioning of nodes is determined using the spring-layout
    algorithm.  Often, it is more efficient to pre-set the positions in a dictionary.  Additionally, we can use
    this position dictionary to display the graph in an intuitive manner, whereas the spring-layout would 
    fail if the graph is not very symmetric.  For example, consider the Petersen graph with default node
    positioning vs. the Petersen graph constructed by this database:

        sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9],\
                5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]})
        sage.: petersen_spring.show()
        sage: petersen_database = graphs.PetersenGraph()
        sage.: petersen_database.show()
    
    For all the constructors in this database (except the random and empty graphs), the position dictionary
    is filled, instead of using the spring-layout algorithm.

ORGANIZATION:
    The constructors available in this database are organized as follows:
        Basic Structures:
            - EmptyGraph
            - CycleGraph
            - StarGraph
            - WheelGraph
        Named Graphs:
            - PetersenGraph
        Families of Graphs:
            - CompleteGraph
            - CompleteBipartiteGraph
            - RandomGNP
            - RandomGNPFast

AUTHORS:
    -- Robert Miller (2006-11-05): initial version - empty, random, petersen
    -- Emily Kirkman (2006-11-12): basic structures, node positioning for all constructors
    -- Emily Kirkman (2006-11-19): docstrings, examples
    
TODO:
    [] more named graphs
    [] thorough docstrings and examples
    [] set properties (as they are implemented)
    [] add query functionality for large database

Basic Structures

Barbell Graph

Info

Plotting

Code

 pos_dict = {}
        
 for i in range(n1):
     x = float(cos((pi/4) - ((2*pi)/n1)*i) - n2/2 - 1)
     y = float(sin((pi/4) - ((2*pi)/n1)*i) - n2/2 - 1)
     j = n1-1-i
     pos_dict[j] = [x,y]
 for i in range(n1+n2)[n1:]:
     x = float(i - n1 - n2/2 + 1)
     y = float(i - n1 - n2/2 + 1)
     pos_dict[i] = [x,y]
 for i in range(2*n1+n2)[n1+n2:]:
     x = float(cos((5*pi/4) + ((2*pi)/n1)*(i-n1-n2)) + n2/2 + 2)
     y = float(sin((5*pi/4) + ((2*pi)/n1)*(i-n1-n2)) + n2/2 + 2)
     pos_dict[i] = [x,y]
        
 import networkx
 G = networkx.barbell_graph(n1,n2)
 return graph.Graph(G, pos=pos_dict, name="Barbell graph")

Examples

 # Construct and show a barbell graph
 # Bar = 4, Bells = 9
 sage: g = graphs.BarbellGraph(9,4)
 sage: g.show()

attachment here

Bull Graph

Info

Plotting

Code

 pos_dict = [[0,0],[-1,1],[1,1],[-2,2],[2,2]]
 import networkx
 G = networkx.bull_graph()
 return graph.Graph(G, pos=pos_dict, name="Bull Graph")

Examples

 # Construct and show a bull graph
 sage: g = graphs.BullGraph()
 sage: g.show()

attachment here

Circular Ladder Graph

Info

Plotting

Code

 pos_dict = {}
 for i in range(n):
     x = float(cos((pi/2) + ((2*pi)/n)*i))
     y = float(sin((pi/2) + ((2*pi)/n)*i))
     pos_dict[i] = [x,y]
 for i in range(2*n)[n:]:
     x = float(2*(cos((pi/2) + ((2*pi)/n)*(i-n))))
     y = float(2*(sin((pi/2) + ((2*pi)/n)*(i-n))))
     pos_dict[i] = [x,y]
 import networkx
 G = networkx.circular_ladder_graph(n)
 return graph.Graph(G, pos=pos_dict, name="Circular Ladder graph")

Examples

 # Construct and show a circular ladder graph with 26 nodes
 sage: g = graphs.CircularLadderGraph(13)
 sage: g.show()

attachment here

 # Create several circular ladder graphs in a SAGE graphics array
 sage: g = []
 sage: j = []
 sage: for i in range(9):
 ...    k = graphs.CircularLadderGraph(i+3)
 ...    g.append(k)
 ...
 sage: for i in range(3):
 ...    n = []
 ...    for m in range(3):
 ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment here

Cycle Graphs

Info

Plotting

Code

 import networkx as NX
 pos_dict = {}
 for i in range(n):
     x = float(functions.cos((pi/2) + ((2*pi)/n)*i))
     y = float(functions.sin((pi/2) + ((2*pi)/n)*i))
     pos_dict[i] = [x,y]
 G = NX.cycle_graph(n)
 return graph.Graph(G, pos=pos_dict, name="Cycle graph on %d vertices"%n)

Examples

The following examples require NetworkX (to use default):

 sage: import networkx as NX

Compare the constructor speeds.

 time n = NX.cycle_graph(3989); spring3989 = Graph(n)

 time posdict3989 = graphs.CycleGraph(3989)

Compare the plotting speeds.

 sage: n = NX.cycle_graph(23)
 sage: spring23 = Graph(n)
 sage: posdict23 = graphs.CycleGraph(23)

 time spring23.show()

attachment:cycle_spr23.png

 time posdict23.show()

attachment:cycl_pd23.png

View many cycle graphs as a SAGE Graphics Array.

With the position dictionary filled:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    k = graphs.CycleGraph(i+3)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:cycle_pd_array.png

With the spring-layout algorithm:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    spr = NX.cycle_graph(i+3)       
 ...    k = Graph(spr)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:cycle_spr_array.png

Diamond Graph

Info

Plotting

Code

 pos_dict = [[0,1],[-1,0],[1,0],[0,-1]]
 import networkx
 G = networkx.diamond_graph()
 return graph.Graph(G, pos=pos_dict, name="Diamond Graph")

Examples

 # Construct and show a diamond graph
 sage: g = graphs.DiamondGraph()
 sage: g.show()

attachment here

Empty Graphs

Info

Plotting

Code

 return graph.Graph()

Examples

Add one vertex to an empty graph.

 sage: empty1 = graphs.EmptyGraph()
 sage: empty1.add_vertex()
 sage: empty1.show()

attachment:empty1.png

Use for loops to build a graph from an empty graph.

 sage: empty2 = graphs.EmptyGraph()
 sage: for i in range(5):
 ...    empty2.add_vertex() # add 5 nodes, labeled 0-4
 ...
 sage: for i in range(3):
 ...    empty2.add_edge(i,i+1) # add edges {[0:1],[1:2],[2:3]}
 ...
 sage: for i in range(4)[1:]:
 ...    empty2.add_edge(4,i) # add edges {[1:4],[2:4],[3:4]}
 ...
 sage: empty2.show()

attachment:empty2.png

Grid2d Graphs

Info

Plotting

Code

 pos_dict = {}
 for i in range(n1):
     y = -i
     for j in range(n2):
         x = j
         pos_dict[i,j] = [x,y]
 import networkx
 G = networkx.grid_2d_graph(n1,n2)
 return graph.Graph(G, pos=pos_dict, name="2D Grid Graph")

Examples

 # Construct and show a grid 2d graph
 # Rows = 5, Columns = 7
 sage: g = graphs.Grid2dGraph(5,7)
 sage: g.show()

attachment here

House Graph

Info

Plotting

Code

This has been updated! Change!

 pos_dict = [[-1,0],[1,0],[-1,1],[1,1],[0,2]]
 import networkx
 G = networkx.house_graph()
 return graph.Graph(G, pos=pos_dict, name="House Graph")

Examples

 # Construct and show a house graph
 sage: g = graphs.HouseGraph()
 sage: g.show()

attachment here

House X Graph

Info

Plotting

Code, has been updated!

 pos_dict = [[-1,0],[1,0],[-1,1],[1,1],[0,2]]
 import networkx
 G = networkx.house_x_graph()
 return graph.Graph(G, pos=pos_dict, name="House Graph")

Examples

 # Construct and show a house X graph
 sage: g = graphs.HouseXGraph()
 sage.: g.show()

attachment here

Krackhardt Kite Graph

Info

References

Plotting

Code

 pos_dict = [[-1,4],[1,4],[-2,3],[0,3],[2,3],[-1,2],[1,2],[0,1],[0,0],[0,-1]]
 import networkx
 G = networkx.krackhardt_kite_graph()
 return graph.Graph(G, pos=pos_dict, name="Krackhardt Kite Graph")

Examples

 # Construct and show a Krackhardt kite graph
 sage: g = graphs.KrackhardtKiteGraph()
 sage.: g.show()

attachment here

Ladder Graph

Lollipop Graph

Path Graph

Star Graphs

Info

Plotting

Code

 import networkx as NX
 pos_dict = {}
 pos_dict[0] = [0,0]
 for i in range(n+1)[1:]:
     x = float(functions.cos((pi/2) + ((2*pi)/n)*(i-1)))
     y = float(functions.sin((pi/2) + ((2*pi)/n)*(i-1)))
     pos_dict[i] = [x,y]
 G = NX.star_graph(n)
 return graph.Graph(G, pos=pos_dict, name="Star graph on %d vertices"%(n+1))

Examples

The following examples require NetworkX (to use default):

 sage: import networkx as NX

Compare the constructor speeds.

 time n = NX.star_graph(3989); spring3989 = Graph(n)

 time posdict3989 = graphs.StarGraph(3989)

Compare the plotting speeds.

 sage: n = NX.star_graph(23)
 sage: spring23 = Graph(n)
 sage: posdict23 = graphs.StarGraph(23)

 time spring23.show()

attachment:star_spr23.png

 time posdict23.show()

attachment:star_pd23.png

View many star graphs as a SAGE Graphics Array. With the position dictionary filled:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    k = graphs.StarGraph(i+3)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:star_array_pd.png

With the spring-layout algorithm:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    spr = NX.star_graph(i+3)       
 ...    k = Graph(spr)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:star_array_spr.png

Wheel Graphs

Info

Plotting

Code

 import networkx as NX
 pos_dict = {}
 pos_dict[0] = [0,0]
 for i in range(n)[1:]:
     x = float(functions.cos((pi/2) + ((2*pi)/(n-1))*(i-1)))
     y = float(functions.sin((pi/2) + ((2*pi)/(n-1))*(i-1)))
     pos_dict[i] = [x,y]
 G = NX.wheel_graph(n)
 return graph.Graph(G, pos=pos_dict, name="Wheel graph on %d vertices"%n)

Examples

The following examples require NetworkX (to use default):

 sage: import networkx as NX

Compare the constructor speeds.

 time n = NX.wheel_graph(3989); spring3989 = Graph(n)

 time posdict3989 = graphs.WheelGraph(3989)

Compare the plotting speeds.

 sage: n = NX.wheel_graph(23)
 sage: spring23 = Graph(n)
 sage: posdict23 = graphs.WheelGraph(23)

 time spring23.show()

attachment:wheel_spr23.png

 time posdict23.show()

attachment:wheel_pd23.png

View many wheel graphs as a SAGE Graphics Array. With the position dictionary filled:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    k = graphs.WheelGraph(i+3)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:wheel_array_pd.png

With the spring-layout algorithm:

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    spr = NX.wheel_graph(i+3)       
 ...    k = Graph(spr)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:wheel_array_spr.png

Named Graphs

Petersen

Info

Plotting

only has 10 vertices and 14 edges.

Code

 pos_dict = {}
 for i in range(5):
     x = float(functions.cos(pi/2 + ((2*pi)/5)*i))
     y = float(functions.sin(pi/2 + ((2*pi)/5)*i))
     pos_dict[i] = [x,y]
 for i in range(10)[5:]:
     x = float(0.5*functions.cos(pi/2 + ((2*pi)/5)*i))
     y = float(0.5*functions.sin(pi/2 + ((2*pi)/5)*i))
     pos_dict[i] = [x,y]
 P = graph.Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9],\
            5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]},\
            pos=pos_dict, name="Petersen graph")
 return P

Examples

Petersen Graph as constructed in this class:

 sage: petersen_database = graphs.PetersenGraph()
 sage: petersen_database.show()

attachment:petersen_pos.png Petersen Graph plotted using the spring layout algorithm:

 sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9],\
                    5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]})
 sage: petersen_spring.show()

attachment:petersen_spring.png

Graph Families

Complete Graphs

Info

Plotting

Code

 import networkx as NX
 pos_dict = {}
 for i in range(n):
     x = float(functions.cos((pi/2) + ((2*pi)/n)*i))
     y = float(functions.sin((pi/2) + ((2*pi)/n)*i))
     pos_dict[i] = [x,y]
 G = NX.complete_graph(n)
 return graph.Graph(G, pos=pos_dict, name="Complete graph on %d vertices"%n)

Examples

The following examples require NetworkX (to use default):

 sage: import networkx as NX

Compare the constructor speeds.

 time n = NX.complete_graph(1559); spring1559 = Graph(n)

 time posdict1559 = graphs.CompleteGraph(1559)

Compare the plotting speeds.

 sage: n = NX.complete_graph(23)
 sage: spring23 = Graph(n)
 sage: posdict23 = graphs.CompleteGraph(23)

 time spring23.show()

attachment:complete_spr23.png

 time posdict23.show()

attachment:complete_pd23.png

View many Complete graphs as a SAGE Graphics Array. With the position dictionary filled:

 sage: g = []
 sage: j = []
 sage: for i in range(9):
 ...    k = graphs.CompleteGraph(i+3)
 ...    g.append(k)
 ...
 sage: for i in range(3):
 ...    n = []
 ...    for m in range(3):
 ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:complete_array_pd.png

With the spring-layout algorithm:

 sage: g = []
 sage: j = []
 sage: for i in range(9):
 ...    spr = NX.complete_graph(i+3)       
 ...    k = Graph(spr)
 ...    g.append(k)
 ...
 sage: for i in range(3):
 ...    n = []
 ...    for m in range(3):
 ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:complete_array_spr.png

Complete Bipartite Graphs

Info

Plotting

Code

 pos_dict = {}
 c1 = 1 # scaling factor for top row
 c2 = 1 # scaling factor for bottom row
 c3 = 0 # pad to center if top row has 1 node
 c4 = 0 # pad to center if bottom row has 1 node
 if n1 > n2:
     if n2 == 1:
         c4 = (n1-1)/2
     else:
         c2 = ((n1-1)/(n2-1))
 elif n2 > n1:
     if n1 == 1:
         c3 = (n2-1)/2
     else:
         c1 = ((n2-1)/(n1-1))
 for i in range(n1):
     x = c1*i + c3
     y = 1
     pos_dict[i] = [x,y]
 for i in range(n1+n2)[n1:]:
      x = c2*(i-n1) + c4
      y = 0
      pos_dict[i] = [x,y]
 G = NX.complete_bipartite_graph(n1,n2)
 return graph.Graph(G, pos=pos_dict, name="Complete bipartite graph on %d vertices"%(n1+n2))

Examples

The following examples require NetworkX (to use default):

 sage: import networkx as NX

Compare the constructor speeds.

 time n = NX.complete_bipartite_graph(389,157); spring_big = Graph(n)

 time posdict_big = graphs.CompleteBipartiteGraph(389,157)

Compare the plotting speeds.

 sage: n = NX.complete_bipartite_graph(11,17)
 sage: spring_med = Graph(n)
 sage: posdict_med = graphs.CompleteBipartiteGraph(11,17)

 time spring_med.show()

attachment:compbip_spr_med.png

 time posdict_med.show()

attachment:compbip_pd_med.png

View many Complete Bipartite graphs as a SAGE Graphics Array. With the position dictionary filled:

 sage: g = []
 sage: j = []
 sage: for i in range(9):
 ...    k = graphs.CompleteBipartiteGraph(i+1,4)
 ...    g.append(k)
 ...
 sage: for i in range(3):
 ...    n = []
 ...    for m in range(3):
 ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:compbip_array_pd.png

With the spring-layout algorithm:

 sage: g = []
 sage: j = []
 sage: for i in range(9):
 ...    spr = NX.complete_bipartite_graph(i+1,4)       
 ...    k = Graph(spr)
 ...    g.append(k)
 ...
 sage: for i in range(3):
 ...    n = []
 ...    for m in range(3):
 ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:compbip_array.spr.png

Random Graph Generators

RandomGNP

Info

Plotting

Code

 import networkx as NX
 G = NX.gnp_random_graph(n, p, seed)
 return graph.Graph(G)

Examples

Compare the speed of RandomGNP and RandomGNPFast: Sparse Graphs

 time regular_sparse = graphs.RandomGNP(1559,.22)

 time fast_sparse =  graphs.RandomGNPFast(1559,.22)

Dense Graphs

 time regular_dense = graphs.RandomGNP(1559,.88)

 time fast_dense = graphs.RandomGNP(1559,.88)

Plot a random graph on 12 nodes with p = .71

 sage: gnp = graphs.RandomGNP(12,.71)
 sage: gnp.show()

attachment:rand_reg.png

View many random graphs using a SAGE Graphics Array

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    k = graphs.RandomGNP(i+3,.43)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:rand_array_reg.png

RandomGNPFast

Info

Plotting

Code

 import networkx as NX
 G = NX.fast_gnp_random_graph(n, p, seed)
 return graph.Graph(G)

Examples

Compare the speed of RandomGNP and RandomGNPFast: Sparse Graphs

 time regular_sparse = graphs.RandomGNP(1559,.22)

 time fast_sparse =  graphs.RandomGNPFast(1559,.22)

Dense Graphs

 time regular_dense = graphs.RandomGNP(1559,.88)

 time fast_dense = graphs.RandomGNP(1559,.88)

Plot a random graph on 12 nodes with p = .71

 sage: fast = graphs.RandomGNPFast(12,.71)
 sage: fast.show()

attachment:rand_fast.png

View many random graphs using a SAGE Graphics Array

 sage: g = []
 sage: j = []
 sage: for i in range(16):
 ...    k = graphs.RandomGNPFast(i+3,.43)
 ...    g.append(k)
 ...
 sage: for i in range(4):
 ...    n = []
 ...    for m in range(4):
 ...        n.append(g[4*i + m].plot(node_size=50, vertex_labels=False))
 ...    j.append(n)
 ...
 sage: G = sage.plot.plot.GraphicsArray(j)
 sage: G.show()

attachment:rand_array_fast.png