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

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]:
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]:
In [78]:
Plots.plot(E.vectors[:,8],label="v8",marker=5)
xlabel!("Vertex Number")
ylabel!("Value in Eigenvector")

Out[78]:
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 [ ]: