|
|
Graph Theory in Sage
William Stein
August 2010
|
|
|
|
Outline
|
|
1. Creating Graphs
|
|
Creating graphs using the Graph function
From a dictionary:
Graph(
|
|
g = Graph({0:[1,2,3], 2:[4], 3:[4], 7:[]}); g
Graph on 6 vertices Graph on 6 vertices |
g.edges()
[(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None), (3, 4, None)] [(0, 1, None), (0, 2, None), (0, 3, None), (2, 4, None), (3, 4, None)] |
g.vertices()
[0, 1, 2, 3, 4, 7] [0, 1, 2, 3, 4, 7] |
g.show(graph_border=True)
|
|
With labeled edges:
g = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}})
|
|
g.edges()
[(0, 1, 'x'), (0, 2, 'z'), (0, 3, 'a'), (2, 5, 'out')] [(0, 1, 'x'), (0, 2, 'z'), (0, 3, 'a'), (2, 5, 'out')] |
g.plot(edge_labels=True, graph_border=True) # plotting of labels looks bad...
|
|
Make a graph from a graph6 string:
g.graph6_string()
'DsG' 'DsG' |
Graph('DsG').show(graph_border=True)
|
|
Loops and multiple edges:
g = Graph({0:[1,2,3], 1:[1,1], 2:[4,4], 3:[4]})
g.show(graph_border=True)
|
|
|
|
Creating graphs using the catalogue of graph creation functions
graphs. # put cursor after dot and press [tab] key
|
|
graphs.PetersenGraph().plot()
|
|
graphs.BullGraph().show(graph_border=True)
|
|
@interact
def f(r=(2..4), h=(1..6)):
g = graphs.BalancedTree(r,h)
g.show(graph_border=True)
Click to the left again to hide and once more to show the dynamic interactive window |
g = graphs.RandomGNP(20, .6); print g
g.show(graph_border=True)
Graph on 20 vertices Graph on 20 vertices |
|
|
|
|
Adjacency and Incidence Matrices
- 'adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the number of edges {i,j}
- 'incidence_matrix' - a Sage matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1
M = matrix(3, [0,2,1, 1,0,0, 1,1,0])
show(M)
g = Graph(M, format='adjacency_matrix')
g.plot(graph_border=True)
|
I = g.incidence_matrix(); I
[-1 -1 -1] [ 0 1 1] [ 1 0 0] [-1 -1 -1] [ 0 1 1] [ 1 0 0] |
Graph(I, format='incidence_matrix').show(graph_border=True)
|
|
(Note: If you introduce a loop, then the last step of the above example doesn't work. See trac 9713.)
|
|
|
|
Generating all Graphs on n vertices, etc.:
In the following example, we plot all 11 graphs on 4 vertices:
G = list(graphs(4)); len(G)
11 11 |
v = [g.plot(graph_border=True, vertex_size=30, vertex_labels=False) for g in G]
|
|
graphics_array(v, 4, 3)
|
|
|
|
|
Database of Graphs
Sage comes with a query-able database of graphs
Q = GraphQuery(display_cols=['graph6','num_vertices','degree_sequence'],
num_edges=['<=',5],min_degree=1)
|
|
Q.show(with_picture=True)
|
|
|
The database contains all graphs on up to 7 vertices.
Q = GraphQuery(display_cols=['graph6','num_vertices','degree_sequence'],
num_vertices=['=',7],min_degree=1)
Q.number_of()
378 378 |
Q = GraphQuery(display_cols=['graph6','num_vertices','degree_sequence'],
num_vertices=['=',8],min_degree=1)
Q.number_of()
0 0 |
|
|
2. Displaying Graphs
We will plot a graph with a double loop and multiple edges in various ways. First we define the graph:
g = Graph({0:[1,2,3], 1:[1,1], 2:[4,4], 3:[4]})
|
|
g
Looped multi-graph on 5 vertices Looped multi-graph on 5 vertices |
We plot it using the default plotting function, which is random (try it multiple times) and uses the "spring layout" algorithm.
Note that the output is a PNG image. You can click and save it.
g.plot()
|
|
g.plot(graph_border=True)
|
|
You can also save the plot to a pdf file, which is suitable for inclusion in a LaTeX document:
\documentclass{article}
\usepackage{graphicx}
\begin{document}
\includegraphics[width=.5\textwidth]{graph}
\end{document}
g.plot(graph_border=True).save('graph.pdf')
|
|
Next we illustrate the HTML5 (Canvas 2d) graph editor, which Rado Kirov recently wrote and contributed to Sage. WARNING: the current version included in Sage silently and without warning discards loops and multiple edges. Watch out. NOTE: Rado is rapidly improving the graph editor, and there is a much better version in the works (see http://www.math.uiuc.edu/~rkirov2/js-graph-editor/showcase.html).
g = Graph({0:[1,2,3],1:[0],2:[0,4,4],3:[0,4],4:[2,2,3,6],5:[6],6:[4,8,5],7:[],8:[6]}); g.set_pos({0:[79,139],1:[45.27151527862789,44.88265969424094],2:[183.85254060219972,296.9070676267539],3:[284.36195631877837,145.64958169162242],4:[226,193],5:[256.01483524384605,301.85568288000184],6:[242.25396569173387,239.90403365361175],7:[273,221],8:[293.10633756827343,303.8332652508823]}); graph_editor(g);
|
|
show(g)
|
|
|
|
Plotting using the Circular Layout, which places all the vertices on a circle (in some order):
g.plot(layout='circular', graph_border=True).show(figsize=[3,3])
|
|
g = Graph({0:[1,2,3], 1:[1,1], 2:[4,4], 3:[4]})
g.plot(layout='circular', graph_border=True).show(figsize=[3,3])
|
|
|
|
There is also a special plotting mode for trees.
g = graphs.BalancedTree(2,3)
g.plot()
|
|
g.plot(layout='tree')
|
|
|
|
If a graph has a planar embedding, you can plot it in the plane:
g = graphs.DodecahedralGraph(); g.plot()
|
|
g.is_planar(set_pos=True)
True True |
g.plot()
|
|
|
|
You can also plot graphs using LaTeX:
You can also plot graphs using LaTeX (WARNING: this doesn't work for me under OS X with a very complete LaTeX install -- other packages are needed as mentioned in the error message.).
g = Graph({0:[1,2,3], 1:[1,1], 2:[4,4], 3:[4]})
latex(g)
\begin{tikzpicture}
%
\definecolor{col_a0}{rgb}{1.0,1.0,1.0}
\definecolor{col_a1}{rgb}{1.0,1.0,1.0}
\definecolor{col_a2}{rgb}{1.0,1.0,1.0}
\definecolor{col_a3}{rgb}{1.0,1.0,1.0}
\definecolor{col_a4}{rgb}{1.0,1.0,1.0}
%
%
\definecolor{col_lab_a0}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a2}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a3}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a4}{rgb}{0.0,0.0,0.0}
%
%
\definecolor{col_a0-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a0-a2}{rgb}{0.0,0.0,0.0}
\definecolor{col_a0-a3}{rgb}{0.0,0.0,0.0}
\definecolor{col_a1-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a1-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a2-a4}{rgb}{0.0,0.0,0.0}
\definecolor{col_a2-a4}{rgb}{0.0,0.0,0.0}
\definecolor{col_a3-a4}{rgb}{0.0,0.0,0.0}
%
%
\GraphInit[vstyle=Normal]
%
\SetVertexMath
%
\SetVertexNoLabel
%
\renewcommand*{\VertexLightFillColor}{col_a0}
\Vertex[x=2.0744cm,y=3.5104cm]{a0}
\renewcommand*{\VertexLightFillColor}{col_a1}
\Vertex[x=0.0cm,y=5.0cm]{a1}
\renewcommand*{\VertexLightFillColor}{col_a2}
\Vertex[x=3.1633cm,y=0.0cm]{a2}
\renewcommand*{\VertexLightFillColor}{col_a3}
\Vertex[x=4.1562cm,y=4.6589cm]{a3}
\renewcommand*{\VertexLightFillColor}{col_a4}
\Vertex[x=5.0cm,y=1.3477cm]{a4}
%
%
\AssignVertexLabel{a}{5}{
\color{col_lab_a0}{$0$},
\color{col_lab_a1}{$1$},
\color{col_lab_a2}{$2$},
\color{col_lab_a3}{$3$},
\color{col_lab_a4}{$4$}
}
%
%
\renewcommand*{\EdgeColor}{col_a0-a1}
\Edge(a0)(a1)
\renewcommand*{\EdgeColor}{col_a0-a2}
\Edge(a0)(a2)
\renewcommand*{\EdgeColor}{col_a0-a3}
\Edge(a0)(a3)
\renewcommand*{\EdgeColor}{col_a1-a1}
\Edge(a1)(a1)
\renewcommand*{\EdgeColor}{col_a1-a1}
\Edge(a1)(a1)
\renewcommand*{\EdgeColor}{col_a2-a4}
\Edge(a2)(a4)
\renewcommand*{\EdgeColor}{col_a2-a4}
\Edge(a2)(a4)
\renewcommand*{\EdgeColor}{col_a3-a4}
\Edge(a3)(a4)
%
%
\end{tikzpicture}
\begin{tikzpicture}
%
\definecolor{col_a0}{rgb}{1.0,1.0,1.0}
\definecolor{col_a1}{rgb}{1.0,1.0,1.0}
\definecolor{col_a2}{rgb}{1.0,1.0,1.0}
\definecolor{col_a3}{rgb}{1.0,1.0,1.0}
\definecolor{col_a4}{rgb}{1.0,1.0,1.0}
%
%
\definecolor{col_lab_a0}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a2}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a3}{rgb}{0.0,0.0,0.0}
\definecolor{col_lab_a4}{rgb}{0.0,0.0,0.0}
%
%
\definecolor{col_a0-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a0-a2}{rgb}{0.0,0.0,0.0}
\definecolor{col_a0-a3}{rgb}{0.0,0.0,0.0}
\definecolor{col_a1-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a1-a1}{rgb}{0.0,0.0,0.0}
\definecolor{col_a2-a4}{rgb}{0.0,0.0,0.0}
\definecolor{col_a2-a4}{rgb}{0.0,0.0,0.0}
\definecolor{col_a3-a4}{rgb}{0.0,0.0,0.0}
%
%
\GraphInit[vstyle=Normal]
%
\SetVertexMath
%
\SetVertexNoLabel
%
\renewcommand*{\VertexLightFillColor}{col_a0}
\Vertex[x=2.0744cm,y=3.5104cm]{a0}
\renewcommand*{\VertexLightFillColor}{col_a1}
\Vertex[x=0.0cm,y=5.0cm]{a1}
\renewcommand*{\VertexLightFillColor}{col_a2}
\Vertex[x=3.1633cm,y=0.0cm]{a2}
\renewcommand*{\VertexLightFillColor}{col_a3}
\Vertex[x=4.1562cm,y=4.6589cm]{a3}
\renewcommand*{\VertexLightFillColor}{col_a4}
\Vertex[x=5.0cm,y=1.3477cm]{a4}
%
%
\AssignVertexLabel{a}{5}{
\color{col_lab_a0}{$0$},
\color{col_lab_a1}{$1$},
\color{col_lab_a2}{$2$},
\color{col_lab_a3}{$3$},
\color{col_lab_a4}{$4$}
}
%
%
\renewcommand*{\EdgeColor}{col_a0-a1}
\Edge(a0)(a1)
\renewcommand*{\EdgeColor}{col_a0-a2}
\Edge(a0)(a2)
\renewcommand*{\EdgeColor}{col_a0-a3}
\Edge(a0)(a3)
\renewcommand*{\EdgeColor}{col_a1-a1}
\Edge(a1)(a1)
\renewcommand*{\EdgeColor}{col_a1-a1}
\Edge(a1)(a1)
\renewcommand*{\EdgeColor}{col_a2-a4}
\Edge(a2)(a4)
\renewcommand*{\EdgeColor}{col_a2-a4}
\Edge(a2)(a4)
\renewcommand*{\EdgeColor}{col_a3-a4}
\Edge(a3)(a4)
%
%
\end{tikzpicture}
|
Here is an example of the sort of thing that will be possible (due to very recent work of Rob Beezer):
|
|
Here is another nice example of a Cayley graph using LaTeX:
|
|
Finally, given any graph, you can export it to GraphViz and plot it there. GraphViz has some very sophisticated graph plotting algorithms. Note that GraphViz isn't part of Sage because it is released under a GPL-incompatible license.
g = Graph({0:[1,2,3], 1:[1,1], 2:[4,4], 3:[4]})
g = graphs.DodecahedralGraph()
g.graphviz_to_file_named('/tmp/sage.dot')
os.system('open -a GraphViz /tmp/sage.dot') # will only work on OS X after installing graphviz.
0 0 |
|
|
You can also create 3d plots in Sage:
g = graphs.IcosahedralGraph()
show(g.plot3d(engine='tachyon')) # weird -- see trac 9716
|
g.plot3d()
|
|
|
|
3. Computations About a Graph
Given a graph g, there are an absolutely enormous number of things you can compute about it in Sage.
g = graphs.DodecahedralGraph(); g
Dodecahedron: Graph on 20 vertices Dodecahedron: Graph on 20 vertices |
g. # press the [tab] key to see 248 methods
|
|
g.genus()
0 0 |
g.cliques_maximal()
[[0, 1], [0, 10], [0, 19], [2, 1], [2, 3], [2, 6], [3, 4], [3, 19], [4, 5], [4, 17], [5, 6], [5, 15], [6, 7], [7, 8], [7, 14], [8, 1], [8, 9], [9, 10], [9, 13], [11, 10], [11, 12], [11, 18], [12, 13], [12, 16], [13, 14], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19]] [[0, 1], [0, 10], [0, 19], [2, 1], [2, 3], [2, 6], [3, 4], [3, 19], [4, 5], [4, 17], [5, 6], [5, 15], [6, 7], [7, 8], [7, 14], [8, 1], [8, 9], [9, 10], [9, 13], [11, 10], [11, 12], [11, 18], [12, 13], [12, 16], [13, 14], [14, 15], [15, 16], [16, 17], [17, 18], [18, 19]] |
g.chromatic_number()
3 3 |
g.chromatic_polynomial()
x^20 - 30*x^19 + 435*x^18 - 4060*x^17 + 27393*x^16 - 142194*x^15 + 589875*x^14 - 2004600*x^13 + 5673571*x^12 - 13518806*x^11 + 27292965*x^10 - 46805540*x^9 + 68090965*x^8 - 83530946*x^7 + 85371335*x^6 - 71159652*x^5 + 46655060*x^4 - 22594964*x^3 + 7171160*x^2 - 1111968*x x^20 - 30*x^19 + 435*x^18 - 4060*x^17 + 27393*x^16 - 142194*x^15 + 589875*x^14 - 2004600*x^13 + 5673571*x^12 - 13518806*x^11 + 27292965*x^10 - 46805540*x^9 + 68090965*x^8 - 83530946*x^7 + 85371335*x^6 - 71159652*x^5 + 46655060*x^4 - 22594964*x^3 + 7171160*x^2 - 1111968*x |
g.eulerian_circuit()
False False |
g.hamiltonian_cycle().plot()
|
|
Many (but not all) of these functions come from NetworkX, which is the canonical Python graph theory library, which Sage includes and builds upon.
N = g.networkx_graph(); N
<networkx.classes.graph.Graph object at 0x110414f90> <networkx.classes.graph.Graph object at 0x110414f90> |
N. # [tab] key -- not much
|
|
import networkx
|
|
networkx.
|
|
networkx.closeness_centrality(N)
{0: 0.37999999999999995, 1: 0.37999999999999995, 2: 0.37999999999999995,
3: 0.37999999999999995, 4: 0.37999999999999995, 5: 0.37999999999999995,
6: 0.37999999999999995, 7: 0.37999999999999995, 8: 0.37999999999999995,
9: 0.37999999999999995, 10: 0.37999999999999995, 11:
0.37999999999999995, 12: 0.37999999999999995, 13: 0.37999999999999995,
14: 0.37999999999999995, 15: 0.37999999999999995, 16:
0.37999999999999995, 17: 0.37999999999999995, 18: 0.37999999999999995,
19: 0.37999999999999995}
{0: 0.37999999999999995, 1: 0.37999999999999995, 2: 0.37999999999999995, 3: 0.37999999999999995, 4: 0.37999999999999995, 5: 0.37999999999999995, 6: 0.37999999999999995, 7: 0.37999999999999995, 8: 0.37999999999999995, 9: 0.37999999999999995, 10: 0.37999999999999995, 11: 0.37999999999999995, 12: 0.37999999999999995, 13: 0.37999999999999995, 14: 0.37999999999999995, 15: 0.37999999999999995, 16: 0.37999999999999995, 17: 0.37999999999999995, 18: 0.37999999999999995, 19: 0.37999999999999995}
|
|
|
Graph Automorphism Groups: This is something not in NetworkX, which Robert Miller implemented (over several months of hard work).
g.automorphism_group()
Permutation Group with generators [(2,8)(3,9)(4,13)(5,14)(6,7)(10,19)(11,18)(12,17), (1,8,7,14,15,16,17,18,19,20)(2,9,6,13,5,12,4,11,3,10), (1,19)(2,3)(4,6)(7,17)(8,18)(9,11)(12,13)(14,16)] Permutation Group with generators [(2,8)(3,9)(4,13)(5,14)(6,7)(10,19)(11,18)(12,17), (1,8,7,14,15,16,17,18,19,20)(2,9,6,13,5,12,4,11,3,10), (1,19)(2,3)(4,6)(7,17)(8,18)(9,11)(12,13)(14,16)] |
h = copy(g)
gamma = SymmetricGroup(20).random_element()
h.relabel(gamma)
h.is_isomorphic(g)
True True |
h.is_isomorphic(graphs.RandomGNP(20, .1))
False False |
g
Dodecahedron: Graph on 20 vertices Dodecahedron: Graph on 20 vertices |
|
|