We test out the LightGraph package, to see how easy it is to use with ours, and to compare its speed. It is easy to make a LightGraphs data type. You just put in the adjacency matrix. Since this also works for directed graphs, it could be nice to use their directed graph routines. Their connected components seems slower, but their dijkstra is often faster!
In [1]:
using Laplacians
using LightGraphs
In [21]:
a = grid2(1000) # Laplacians style graph
lg = Graph(a) # LightGraphs style
Out[21]:
In [22]:
@time is_connected(lg)
Out[22]:
In [23]:
@time isConnected(a)
Out[23]:
Let's subsample, and test out the speed of connected components routines.
In [24]:
as = subsampleEdges(a,0.5);
lgs = Graph(as)
Out[24]:
In [27]:
@time c = components(as);
In [28]:
@time lgc = connected_components(lgs);
Let's check if they give the same answers.
In [29]:
vecToComps(c)
Out[29]:
In [30]:
lgc
Out[30]:
To be sure that we are not being unfair in running time, let's time the vecToComps, too.
In [31]:
@time v = vecToComps(c);
In [105]:
nexp = 100
tLap = zeros(nexp)
tLG = zeros(nexp)
tLapW = zeros(nexp)
tLGW = zeros(nexp)
Out[105]:
In [106]:
for i in 1:nexp
a = chimera(1000000,i)
tic()
len, pa = shortestPaths(a,100);
t = toq()
tLap[i] = t
println("graph $i : time $t")
end
In [107]:
for i in 1:nexp
a = chimera(1000000,i)
lg = Graph(a)
tic()
x = dijkstra_shortest_paths(lg, 100);
t = toq()
tLG[i] = t
println("graph $i : time $t")
end
In [108]:
for i in 1:nexp
a = wtedChimera(1000000,i)
tic()
len, pa = shortestPaths(a,100);
t = toq()
tLapW[i] = t
println("graph $i : time $t")
end
In [109]:
for i in 1:nexp
a = wtedChimera(1000000,i)
lg = Graph(a)
tic()
x = dijkstra_shortest_paths(lg, 100);
t = toq()
tLGW[i] = t
println("graph $i : time $t")
end
In [111]:
mean(tLap)
Out[111]:
In [112]:
mean(tLG)
Out[112]:
In [113]:
mean(tLapW)
Out[113]:
In [114]:
mean(tLGW)
Out[114]:
In [121]:
i = 6
Out[121]:
In [131]:
Profile.clear()
i = i + 1
@profile chimera(100000,i);
ProfileView.view()
Out[131]:
In [136]:
a1 = grownGraph(1000,2);
@time a11 = productGraph(a1,a1);
nnz(a11)
Out[136]:
In [138]:
@time a11 = productGraph(a1,a1);
In [141]:
@time a10 = generalizedNecklace(a1,a1,2);
In [143]:
@time a0 = joinGraphs(a11,a10,100);
In [150]:
@time (ai,aj,av) = findnz(a11);
n = size(a11)[1]
@time ax = sparse(ai,aj,av,n,n);
In [155]:
@time rt = randishKruskal(a11);
In [156]:
@time rt = randishPrim(a11);
In [157]:
a = wtedChimera(50);
In [159]:
x = minimum(a.nzval)
Out[159]:
In [160]:
a.nzval = a.nzval / x;
minimum(a.nzval)
Out[160]:
In [161]:
n
Out[161]:
In [ ]: