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 Generators Class is to implement constructors for many common graphs, as well as thorough docstrings that can be used for reference. The graph generators will grow as the Graph Theory Project does. So please check back for additions and feel free to leave requests in the suggestions section. We currently have 30 constructors of named graphs and basic structures. Most of these graphs are constructed with a preset dictionary of x-y coordinates of each node. SAGE graphs all have an associated graphics object, and examples of plotting options are shown on the graphs below.

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.

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

Inherited from NetworkX

Families of Graphs

Named Graphs

Currently Implemented in Graph Database

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_this = graphs.PetersenGraph()
 sage: petersen_this.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)

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 ADD SAGE LIST OF GRAPHS HERE INSTEAD

 # 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:

ADD LIST HERE

 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: ADD LIST HERE

 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.

update to with list

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:

update with list

 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.

update with list

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:

update with list

 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