Toolkit for TCS 2018 - Drawing Graphs using Laplacian Eigenvectors

Jupyter Notebook for Spectral Methods module of course using the tools developed by Dan Spielman. References and sources:

Table of Contents

  1. Line Graphs

  2. Grid Graphs

  3. Platonic Solids

In [69]:
using Laplacians
using LinearAlgebra
using Statistics
using Plots
using SparseArrays
using FileIO
using JLD2
using Random

Line Graphs

In [70]:
M = path_graph(8)
Out[70]:
8×8 SparseMatrixCSC{Float64,Int64} with 14 stored entries:
  [2, 1]  =  1.0
  [1, 2]  =  1.0
  [3, 2]  =  1.0
  [2, 3]  =  1.0
  [4, 3]  =  1.0
  [3, 4]  =  1.0
  [5, 4]  =  1.0
  [4, 5]  =  1.0
  [6, 5]  =  1.0
  [5, 6]  =  1.0
  [7, 6]  =  1.0
  [6, 7]  =  1.0
  [8, 7]  =  1.0
  [7, 8]  =  1.0
In [71]:
Matrix(M)
Out[71]:
8×8 Array{Float64,2}:
 0.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0
 1.0  0.0  1.0  0.0  0.0  0.0  0.0  0.0
 0.0  1.0  0.0  1.0  0.0  0.0  0.0  0.0
 0.0  0.0  1.0  0.0  1.0  0.0  0.0  0.0
 0.0  0.0  0.0  1.0  0.0  1.0  0.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0  1.0  0.0
 0.0  0.0  0.0  0.0  0.0  1.0  0.0  1.0
 0.0  0.0  0.0  0.0  0.0  0.0  1.0  0.0
In [72]:
L=Matrix(lap(M))
Out[72]:
8×8 Array{Float64,2}:
  1.0  -1.0   0.0   0.0   0.0   0.0   0.0   0.0
 -1.0   2.0  -1.0   0.0   0.0   0.0   0.0   0.0
  0.0  -1.0   2.0  -1.0   0.0   0.0   0.0   0.0
  0.0   0.0  -1.0   2.0  -1.0   0.0   0.0   0.0
  0.0   0.0   0.0  -1.0   2.0  -1.0   0.0   0.0
  0.0   0.0   0.0   0.0  -1.0   2.0  -1.0   0.0
  0.0   0.0   0.0   0.0   0.0  -1.0   2.0  -1.0
  0.0   0.0   0.0   0.0   0.0   0.0  -1.0   1.0
In [73]:
E = eigen(Matrix(L))
println(E.values)
[0.0, 0.152241, 0.585786, 1.23463, 2.0, 2.76537, 3.41421, 3.84776]
In [74]:
E.vectors[:,1]
Out[74]:
8-element Array{Float64,1}:
 0.3535533905932733 
 0.35355339059327345
 0.35355339059327356
 0.35355339059327306
 0.3535533905932737 
 0.3535533905932742 
 0.3535533905932746 
 0.3535533905932742 
In [75]:
v2 = E.vectors[:,2]
Out[75]:
8-element Array{Float64,1}:
  0.49039264020161544
  0.4157348061512732 
  0.27778511650980175
  0.09754516100806479
 -0.09754516100806364
 -0.27778511650980087
 -0.4157348061512728 
 -0.4903926402016143 
In [76]:
plot(v2,marker=5,legend=false)
xlabel!("vertex number")
ylabel!("value in eigenvector")
Out[76]:
2 4 6 8 -0.4 -0.2 0.0 0.2 0.4 vertex number value in eigenvector
In [77]:
Plots.plot(E.vectors[:,2],label="v2",marker = 5)
Plots.plot!(E.vectors[:,3],label="v3",marker = 5)
Plots.plot!(E.vectors[:,4],label="v4",marker = 5)
Plots.plot!(E.vectors[:,1],label="v1",marker = 5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[77]:
2 4 6 8 -0.4 -0.2 0.0 0.2 0.4 Vertex Number Value in Eigenvector v2 v3 v4 v1
In [78]:
Plots.plot(E.vectors[:,8],label="v8",marker=5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")
Out[78]:
2 4 6 8 -0.4 -0.2 0.0 0.2 0.4 Vertex Number Value in Eigenvector v8
In [79]:
using PyPlot: pygui
pygui(false)
plot_graph(M,E.vectors[:,2],E.vectors[:,3])
Out[79]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x1554fcac8>

Grid Graphs

In [80]:
M = grid2(6,5)
L = lap(M)
E = eigen(Matrix(L))
V = E.vectors[:,2:3]
println(E.values)
[-1.1678e-307, 0.267949, 0.381966, 0.649915, 1.0, 1.38197, 1.38197, 1.64992, 2.0, 2.38197, 2.38197, 2.61803, 2.88598, 3.0, 3.38197, 3.38197, 3.61803, 3.61803, 3.73205, 3.88598, 4.11402, 4.38197, 4.61803, 4.61803, 5.11402, 5.61803, 5.61803, 6.35008, 6.61803, 7.35008]
In [81]:
pygui(false)
plot_graph(M,V[:,1],V[:,2])
Out[81]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x15575d828>
In [82]:
M = grid3(5,5,5)
L = lap(M)
E = eigen(Matrix(L))
V = E.vectors[:,2:3]
println(E.values)
[4.06786e-16, 0.381966, 0.381966, 0.381966, 0.763932, 0.763932, 0.763932, 1.1459, 1.38197, 1.38197, 1.38197, 1.76393, 1.76393, 1.76393, 1.76393, 1.76393, 1.76393, 2.1459, 2.1459, 2.1459, 2.61803, 2.61803, 2.61803, 2.76393, 2.76393, 2.76393, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.1459, 3.1459, 3.1459, 3.38197, 3.38197, 3.38197, 3.61803, 3.61803, 3.61803, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.1459, 4.38197, 4.38197, 4.38197, 4.38197, 4.38197, 4.38197, 4.38197, 4.38197, 4.38197, 5.0, 5.0, 5.0, 5.0, 5.0, 5.0, 5.23607, 5.23607, 5.23607, 5.38197, 5.38197, 5.38197, 5.38197, 5.38197, 5.38197, 5.38197, 5.38197, 5.38197, 5.61803, 5.61803, 5.61803, 6.23607, 6.23607, 6.23607, 6.23607, 6.23607, 6.23607, 6.38197, 6.38197, 6.38197, 6.61803, 6.61803, 6.61803, 6.61803, 6.61803, 6.61803, 6.61803, 6.61803, 6.61803, 7.23607, 7.23607, 7.23607, 7.61803, 7.61803, 7.61803, 7.61803, 7.61803, 7.61803, 7.61803, 7.61803, 7.61803, 7.8541, 8.61803, 8.61803, 8.61803, 8.8541, 8.8541, 8.8541, 9.8541, 9.8541, 9.8541, 10.8541]
In [83]:
pygui(false)
plot_graph(M,V[:,1],V[:,2])
Out[83]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x1558de4e0>
In [84]:
x = E.vectors[:,2]
y = E.vectors[:,3]
z = E.vectors[:,4]
pygui(true)
plot_graph(M, x, y, z; setaxis=false)
Out[84]:
1-element Array{PyCall.PyObject,1}:
 PyObject <mpl_toolkits.mplot3d.art3d.Line3D object at 0x155ba1c88>

Platonic Solids

Examples include Dodecahedron (dodec.txt), Icosahedron (isoca.txt), Octahedron (octa.txt), Cube (cube.txt) and Tetrahedron (tetra.txt)

In [85]:
M = readIJV("icosa.txt")
Out[85]:
12×12 SparseMatrixCSC{Float64,Int64} with 60 stored entries:
  [2 ,  1]  =  1.0
  [5 ,  1]  =  1.0
  [6 ,  1]  =  1.0
  [9 ,  1]  =  1.0
  [10,  1]  =  1.0
  [1 ,  2]  =  1.0
  [7 ,  2]  =  1.0
  [8 ,  2]  =  1.0
  [9 ,  2]  =  1.0
  [10,  2]  =  1.0
  [4 ,  3]  =  1.0
  [5 ,  3]  =  1.0
  ⋮
  [8 , 10]  =  1.0
  [12, 10]  =  1.0
  [3 , 11]  =  1.0
  [4 , 11]  =  1.0
  [5 , 11]  =  1.0
  [7 , 11]  =  1.0
  [9 , 11]  =  1.0
  [3 , 12]  =  1.0
  [4 , 12]  =  1.0
  [6 , 12]  =  1.0
  [8 , 12]  =  1.0
  [10, 12]  =  1.0
In [86]:
E = eigen(Matrix(lap(M)))
println(E.values)
[9.76996e-15, 2.76393, 2.76393, 2.76393, 6.0, 6.0, 6.0, 6.0, 6.0, 7.23607, 7.23607, 7.23607]
In [87]:
x = E.vectors[:,2]
y = E.vectors[:,3]
pygui(false)
plot_graph(M, x, y; setaxis=false)
Out[87]:
1-element Array{PyCall.PyObject,1}:
 PyObject <matplotlib.lines.Line2D object at 0x156830278>
In [88]:
z = E.vectors[:,4]
pygui(true)
plot_graph(M, x, y, z; setaxis=false)
Out[88]:
1-element Array{PyCall.PyObject,1}:
 PyObject <mpl_toolkits.mplot3d.art3d.Line3D object at 0x15807ac18>
In [ ]:

In [ ]: