In [1]:

    

using Laplacians


    

    




INFO: Recompiling stale cache file /Users/spielman/.julia/lib/v0.4/Laplacians.ji for module Laplacians.
INFO: Building PyCall
INFO: No system-wide Python was found; got the following error:
could not spawn `'' -c "import distutils.sysconfig; print(distutils.sysconfig.get_config_var('VERSION'))"`: no such file or directory (ENOENT)
using the Python distribution in the Conda package






    




Fetching package metadata: ....
Solving package specifications: .........

# All requested packages already installed.
# packages in environment at /Users/spielman/.julia/v0.4/Conda/deps/usr:
#
numpy                     1.11.0                   py27_1  






    




INFO: PyCall is using /Users/spielman/.julia/v0.4/Conda/deps/usr/bin/python (Python 2.7.11) at /Users/spielman/.julia/v0.4/Conda/deps/usr/bin/python, libpython = /Users/spielman/.julia/v0.4/Conda/deps/usr/lib/libpython2.7.dylib
INFO: Recompiling stale cache file /Users/spielman/.julia/lib/v0.4/PyCall.ji for module PyCall.
INFO: Recompiling stale cache file /Users/spielman/.julia/lib/v0.4/PyPlot.ji for module PyPlot.

In [7]:

    

include("../src/akpw.jl")


    

    
Out[7]:





sortIJVind3 (generic function with 1 method)

In [6]:

    

# this should produce 22.9374025974026
srand(1)
a = grid2(1100)
t = akpwU(a)
sum(compStretches(t,a))/nnz(a)


    

    
Out[6]:





22.9374025974026

In [7]:

    

# this should produce 32.47723881214327
#a = grid2(1100)
t = akpw(a)
sum(compStretches(t,a))/nnz(a)


    

    
Out[7]:





32.47723881214327

In [8]:

    

#= this should produce 
  0.835222 seconds (3.65 M allocations: 272.523 MB, 17.63% gc time)
  0.900887 seconds (5.59 M allocations: 365.142 MB, 22.07% gc time) 
Out[7]:
1x2 Array{Float64,2}:
 6.76587  6.80419
=#
a = wtedChimera(60100,22)
f(t) = sum(compStretches(t,a))/nnz(a)
@time t5 = akpw(a);
@time t2 = akpw(a, ver=2);
[f(t5) f(t2)]


    

    




  0.655519 seconds (3.65 M allocations: 272.555 MB, 19.86% gc time)
  0.692783 seconds (3.37 M allocations: 331.863 MB, 20.80% gc time)






    
Out[8]:





1x2 Array{Float64,2}:
 6.76587  6.80419

In [206]:

    

a = wtedChimera(100200,96)
#a=a*a
(ai,aj,av) = findnz(a)
ijva = IJVindList(ai,aj,av);
ijva = ijva[randperm(length(ijva))];


    

In [207]:

    

@time l2 = sortIJVind2(ijva);


    

    




  0.266035 seconds (2.91 M allocations: 131.291 MB, 39.36% gc time)

In [208]:

    

@time l1 = sortIJVind(ijva);


    

    




  0.041412 seconds (16 allocations: 27.520 MB, 11.22% gc time)

In [216]:

    

@time l3 = sortIJVind3(ijva);


    

    




  0.368634 seconds (3.81 M allocations: 117.113 MB, 5.57% gc time)

In [191]:

    

mean(l3 .== l1)


    

    
Out[191]:





1.0

In [196]:

    

byi(x::IJVind) = x.v
o = ord(isless, byi, false, Forward)
sort!(l3, 1, 6, InsertionSort, o)
l3[1:10]


    

    
Out[196]:





10-element Array{IJVind,1}:
 IJVind(32598,1,0.9067137036834374,4) 
 IJVind(44543,1,2.3894079663505914,6) 
 IJVind(20429,1,2.4094448913018938,2) 
 IJVind(38770,1,8.883586375668639,5)  
 IJVind(22246,1,14.90457453538139,3)  
 IJVind(1,1,17.173896797551638,1)     
 IJVind(45931,1,3.09280818142043,7)   
 IJVind(49411,1,6.951494918391464,8)  
 IJVind(51996,1,8.1280478246751,9)    
 IJVind(57396,1,0.9580306176358113,10)

In [ ]:

    




    

In [24]:

    

include("testTrees.jl")


    

    
Out[24]:





testTrees (generic function with 1 method)

In [27]:

    

out = testTrees3(500,100);


    

    




st0 : [1.076 0.848 0.96 0.989 0.998 1.002 1.008 1.024 1.079 1.134 1.243 1.827]
st2 : [0.998 0.758 0.93 0.956 0.976 0.992 1.0 1.006 1.015 1.028 1.045 1.253]
stp : [1.863 0.887 1.112 1.258 1.365 1.52 1.654 1.769 1.966 2.244 2.536 11.323]
stold : [1.269 0.772 0.923 0.993 1.024 1.074 1.153 1.186 1.256 1.333 1.486 8.645]
t0 : [1.645 0.143 0.52 1.04 1.333 1.436 1.537 1.635 1.725 1.897 2.177 6.925]
t2 : [1.908 0.21 0.903 1.191 1.277 1.324 1.412 1.547 1.728 2.084 3.626 8.562]
tp : [0.685 0.052 0.214 0.331 0.351 0.387 0.431 0.454 0.515 0.587 0.93 8.382]
told : [1.136 0.164 0.504 0.789 0.863 0.909 0.967 1.084 1.207 1.324 1.549 4.715]

In [198]:

    

for i in 1:10000
    a = wtedChimera(10,i)
    tr = akpwish(a,ver=5)
    if !isConnected(tr)
        println(i)
        break
    end
end


    

    




108

In [154]:

    

vstat = function(x)
    x = sort(x)
    n = length(x)
    n5 = div(n,5)
    [mean(x) minimum(x) x[n5:n5:(4*n5)]' maximum(x)]
end
vstat(x)


    

    
Out[154]:





1x7 Array{Float64,2}:
 0.495792  0.00395628  0.200624  0.410043  0.558465  0.728353  0.986281

In [157]:

    

include("testTrees.jl")
out = testTrees2(401,400)


    

    




st4 : [1.0379418262746154 0.7079790208934582 0.9708660820683037 0.9965430965924408 1.017162022145891 1.0875901292824974 1.58885610948498]
st5 : [1.0379418262746154 0.7079790208934582 0.9708660820683037 0.9965430965924408 1.017162022145891 1.0875901292824974 1.58885610948498]
t4 : [0.9090763142120248 0.0592528840812208 0.4297130690625479 0.6028311890086586 0.78294698577274 0.9499543558245857 7.199459040415482]
t5 : [0.9258012754477519 0.06542346702649612 0.42238050353267237 0.571452324839979 0.7142970679258375 0.8675812969508102 8.737101312462725]






    
Out[157]:





([0.00133195,0.00311736,0.00192787,0.0117338,0.00486461,0.00287441,0.0126692,0.00249084,0.0011676,0.00826691  …  0.00192805,0.00127704,0.00172139,0.00178234,0.00152866,0.00608663,0.0026548,0.00448506,0.00330081,0.00093498],[0.00106346,0.00131842,0.00262381,0.00898276,0.0031729,0.0121299,0.00226282,0.00118291,0.000858469,0.0231958  …  0.00242223,0.00115838,0.0013224,0.00124492,0.00143403,0.00422536,0.00748991,0.00234868,0.0013384,0.000724155],[0.000591048,0.00288484,0.00343407,0.000974171,0.00285162,0.00207982,0.00150208,0.011491,0.00060576,0.00298697  …  0.00163232,0.0015729,0.00123611,0.000989406,0.0012904,0.00288752,0.00242948,0.0011356,0.00177255,0.000663229],[1.06824,1.53542,2.80651,1.2405,2.19607,1.58781,2.31276,2.61023,1.75752,2.2293  …  6.01892,6.14323,5.60324,1.24131,1.54946,2.59558,2.98174,5.68036,3.7824,1.43644],[1.06698,1.50911,2.81806,1.26098,2.32005,1.83571,2.4832,3.5634,1.68421,2.29407  …  6.1495,6.2431,5.43398,1.2971,1.57569,3.00004,2.2966,5.69701,3.67526,1.57088],[1.06698,1.50911,2.81806,1.26098,2.32005,1.83571,2.4832,3.5634,1.68421,2.29407  …  6.1495,6.2431,5.43398,1.2971,1.57569,3.00004,2.2966,5.69701,3.67526,1.57088])

In [149]:

    

@time a = wtedChimera(601000,20)
f(t) = sum(compStretches(t,a))/nnz(a)
@time t6 = akpwish(a,ver=6)
@time t5 = akpwish(a,ver=5)
@time t2 = akpwish(a,ver=2)

println([f(t6) f(t5) f(t2)])


    

    




 18.925009 seconds (6.67 M allocations: 2.806 GB, 11.24% gc time)
175.429663 seconds (1.37 G allocations: 42.546 GB, 9.97% gc time)
 27.088778 seconds (43.81 M allocations: 3.347 GB, 8.51% gc time)
 55.230688 seconds (64.29 M allocations: 10.447 GB, 10.45% gc time)
[5.581439086460352 8.647818700715248 1.4246992782852712]

In [127]:

    

@time a = wtedChimera(601000,20)
f(t) = sum(compStretches(t,a))/nnz(a)
@time t5 = akpwish(a,ver=5)
@time t4 = akpwish(a,ver=4)
@time t2 = akpwish(a,ver=2)
@time t3 = akpwish(a,ver=3)
@time tp = randishPrim(a)
@time tk = randishKruskal(a)
@time told = akpw(a)
println([f(t5) f(t4) f(t2) f(t3) f(tp) f(tk) f(told)])


    

    




 14.442564 seconds (6.67 M allocations: 2.806 GB, 9.99% gc time)
 16.859458 seconds (43.81 M allocations: 3.347 GB, 7.52% gc time)
 17.613216 seconds (43.81 M allocations: 2.921 GB, 10.01% gc time)
 47.777039 seconds (64.29 M allocations: 10.447 GB, 9.78% gc time)
 40.977286 seconds (63.91 M allocations: 10.442 GB, 13.23% gc time)
  6.535373 seconds (5.89 M allocations: 793.532 MB, 7.02% gc time)
  5.576942 seconds (5.89 M allocations: 541.336 MB, 8.00% gc time)
 16.174762 seconds (18.64 M allocations: 2.236 GB, 11.46% gc time)
[8.647818700715248 8.647818700715248 1.4246992782852712 1.4246992782852712 7.054708832793151 3.083938594033725 5.829988682828951]

In [98]:

    

n = 300

st0 = Array(Float64,0)
st2 = Array(Float64,0)
st4 = Array(Float64,0)
st5 = Array(Float64,0)
stp = Array(Float64,0)
stk = Array(Float64,0)
stold = Array(Float64,0)

t0 = Array(Float64,0)
t2 = Array(Float64,0)
t4 = Array(Float64,0)
t5 = Array(Float64,0)
tp = Array(Float64,0)
tk = Array(Float64,0)
told = Array(Float64,0)



for i in 1:10
    a = wtedChimera(n,i)
    f(t) = sum(compStretches(t,a))/nnz(a)
    
    try
    
    tic()
    tr = akpwish(a,ver=0)
    at0 = toq()
    ast0 = f(tr)

    tic()
    tr = akpwish(a,ver=2)
    at2 = toq()
    ast2 = f(tr)

    tic()
    tr = randishKruskal(a)
    atk = toq()
    astk = f(tr)
    
    print(n, " ", i, " : ")
    
    print(ast0, " ")
    push!(t0,at0)
    push!(st0,ast0)

    print(ast2, " ")
    push!(t2,at2)
    push!(st2,ast2)
    
    print(astk, " ")
    push!(tk,atk)
    push!(stk,astk)
    
        
    catch
        println("bad on wtedChimera ", n, " ", i)
    end


end
       

mist = minimum([st0 st2 stk],2)
f = 1.3

stats(v) = [mean(v./mist) median(v./mist) maximum(v./mist) mean(v .== mist) mean(v .> f*mist)]

println(stats(st0))
println(stats(st2))
println(stats(stk))


    

    




300 1 : 1.2552462726508418 1.219609670585416 1.4794178794893695 300 2 : 1.9022687328926449 2.4407677992948216 3.094762686406375 300 3 : 1.5909187247375338 1.5665448491620906 1.9338570146507208 300 4 : 2.0093761911516346 1.9273041698920927 9.047492054596425 300 5 : 2.40716864787057 2.479460887395707 10.287064023612757 300 6 : 2.832868093196327 2.306097132328284 8.217359957102657 300 7 : 2.4292723822619737 2.3921857087893263 4.365510550035845 300 8 : 2.614324990772121 2.210799709731024 4.212493528666549 300 9 : 1.2775062342886405 1.2156699466540988 2.1519561661174835 300 10 : 2.437098281670821 2.415483723999455 4.478273954537306 





    




LoadError: invalid redefinition of constant f
while loading In[98], in expression starting on line 66

In [99]:

    

st0 = Array(Float64,0)
st2 = Array(Float64,0)
st4 = Array(Float64,0)
st5 = Array(Float64,0)
stp = Array(Float64,0)
stk = Array(Float64,0)
stold = Array(Float64,0)

t0 = Array(Float64,0)
t2 = Array(Float64,0)
t4 = Array(Float64,0)
t5 = Array(Float64,0)
tp = Array(Float64,0)
tk = Array(Float64,0)
told = Array(Float64,0)


    

    
Out[99]:





0-element Array{Float64,1}

In [101]:

    

a = wtedChimera(301,8)
    f(t) = sum(compStretches(t,a))/nnz(a)

    tic()
    tr = akpwish(a,ver=0)
    at0 = toq()
    ast0 = f(tr)

    tic()
    tr = akpwish(a,ver=2)
    at2 = toq()
    ast2 = f(tr)

    tic()
    tr = akpwish(a,ver=4)
    at4 = toq()
    ast4 = f(tr)

    tic()
    tr = akpwish(a,ver=5)
    at5 = toq()
    ast5 = f(tr)

    tic()
    tr = randishKruskal(a)
    atk = toq()
    astk = f(tr)
    
    tic()
    tr = randishPrim(a)
    atp = toq()
    astp = f(tr)
    
    tic()
    tr = akpw(a)
    atold = toq()
    astold = f(tr)


    

    




LoadError: BoundsError: attempt to access 1166-element Array{IJVind,1}:
 IJVind(120,1,1.0,1)                    
 IJVind(161,1,1.0,2)                    
 IJVind(220,1,1.0,3)                    
 IJVind(61,3,1.0,12)                    
 IJVind(116,3,1.0,13)                   
 IJVind(242,3,1.0,14)                   
 IJVind(10,4,1.0,15)                    
 IJVind(221,4,1.0,16)                   
 IJVind(56,5,1.0,17)                    
 IJVind(57,5,1.0,18)                    
 IJVind(67,5,1.0,19)                    
 IJVind(243,5,1.0,20)                   
 IJVind(268,5,1.0,21)                   
 ⋮                                      
 IJVind(288,278,0.6942308211336234,1083)
 IJVind(13,288,0.6942308211336234,1114) 
 IJVind(14,288,0.6942308211336234,1115) 
 IJVind(30,288,0.6942308211336234,1116) 
 IJVind(91,288,0.6942308211336234,1118) 
 IJVind(155,288,0.6942308211336234,1119)
 IJVind(250,288,0.6942308211336234,1120)
 IJVind(260,288,0.6942308211336234,1121)
 IJVind(278,288,0.6942308211336234,1122)
 IJVind(113,299,0.6942308211336234,1157)
 IJVind(170,299,0.6942308211336234,1158)
 IJVind(232,299,0.6942308211336234,1159)
  at index [1167]
while loading In[101], in expression starting on line 20

 in akpwSub5 at /Users/spielman/.julia/v0.4/Laplacians/src/akpw.jl:820
 in akpwish at /Users/spielman/.julia/v0.4/Laplacians/src/akpw.jl:309

In [17]:

    

st1 = Array(Float64,0)
st2 = Array(Float64,0)
st3 = Array(Float64,0)
stold = Array(Float64,0)

tic()
for i in 1:100
    a = chimera(9003,i)
    

    t1 = akpwU(a)
    push!(st1, sum(compStretches(t1,a)) / nnz(a) )

    
    t2 = akpwU(a,x->(1/(log(x+1))))
    push!(st2, sum(compStretches(t2,a)) / nnz(a) )

    t3 = akpwU(a,x->(1/(2*exp(sqrt(log(x))))))
    push!(st3, sum(compStretches(t3,a)) / nnz(a) )
    
    told = akpw(a)
    push!(stold, sum(compStretches(told,a)) / nnz(a) )

end

toc()

mi = minimum([st1 st2 st3 stold],2)
f = 1.3

stats(v) = [mean(v./mi) median(v./mi) maximum(v./mi) mean(v .== mi) mean(v .> f*mi)]

println(stats(st1))
println(stats(st2))
println(stats(st3))
println(stats(stold))


    

    




elapsed time: 21.269472164 seconds
[1.0961555823867704 1.0466196318413168 1.647743032903734 0.23 0.06]
[1.1226533411178823 1.0799355492840592 1.6319599245523357 0.19 0.12]
[1.103145953657218 1.045913656800645 1.7059369677411094 0.26 0.09]
[1.0671200059055066 1.024100904665599 1.5526848258993176 0.41 0.03]

In [45]:

    

st5 = Array(Float64,0)



tic()
for i in 1:1000
    a = chimera(90001,i)
    


    t5 = akpwU(a,x->(1/(2*log(x))))
    push!(st5, sum(compStretches(t5,a)) / nnz(a) )
    

end

toc()

mi = minimum([st1 st2 st3 st4 stold],2)
f = 1.3

stats(v) = [mean(v./mi) median(v./mi) maximum(v./mi) sum(v .== mi) sum(v .> f*mi)]

println(stats(st5))


    

    




elapsed time: 910.560501799 seconds
[1.573597519040565 1.0461617743183793 14.377468072115894 0.0 375.0]

In [265]:

    

stnew = Array(Float64,0)
stp = Array(Float64,0)
stold = Array(Float64,0)

timenew = 0
timep = 0
timeold = 0

tic()
for i in 1:10000
    a = wtedChimera(100,i)
    
    tic()
    tnew = akpwish(a)
    timenew += toq()
    push!(stnew, sum(compStretches(tnew,a)) / nnz(a) )

    
    tic()
    tp = randishPrim(a)
    timep += toq()
    push!(stp, sum(compStretches(tp,a)) / nnz(a) )    
    
    
    tic()
    told = akpw(a)
    timeold += toq()
    push!(stold, sum(compStretches(told,a)) / nnz(a) )

end

toc()

mi = minimum([stnew stp stold],2)
f = 1.3

stats(v) = [mean(v./mi) median(v./mi) maximum(v./mi) mean(v .== mi) mean(v .> f*mi)]

println(stats(stnew))
println(stats(stp))

println(stats(stold))

@show timenew
#@show timep
@show timeold


    

    




elapsed time: 27.71791812 seconds
[1.0329578609017473 1.0 3.044104883278004 0.7095 0.0197]
[1.6135367739645807 1.469106526640427 28.08383656108187 0.0498 0.6663]
[1.2163115202866204 1.1025249769393954 19.70007674391376 0.287 0.2417]
timenew = 5.759704107000006
timeold = 2.818882684999991






    
Out[265]:





2.818882684999991

In [228]:

    

findmax(stnew./stold)


    

    
Out[228]:





(1.76998356630378e6,8785)

In [270]:

    

function complsst(sz::Int, nruns::Int)
stnew = Array(Float64,0)
stp = Array(Float64,0)
stold = Array(Float64,0)

timenew = 0
timep = 0
timeold = 0

tic()
    for i in 1:nruns
        a = wtedChimera(sz,i)
    
    tic()
    tnew = akpwish(a)
    timenew += toq()
    push!(stnew, sum(compStretches(tnew,a)) / nnz(a) )

    
    tic()
    tp = randishPrim(a)
    timep += toq()
    push!(stp, sum(compStretches(tp,a)) / nnz(a) )    
    
    
    tic()
    told = akpw(a)
    timeold += toq()
    push!(stold, sum(compStretches(told,a)) / nnz(a) )

end

toc()

mi = minimum([stnew stp stold],2)
f = 1.3

stats(v) = [mean(v./mi) median(v./mi) maximum(v./mi) mean(v .== mi) mean(v .> f*mi)]

println(stats(stnew))
println(stats(stp))

println(stats(stold))

@show timenew
@show timep
@show timeold
    
end


    

    
Out[270]:





complsst (generic function with 2 methods)

In [271]:

    

complsst(1000,1001)


    

    




elapsed time: 17.150495434 seconds
[1.0418868935278642 1.0 2.063921384429326 0.6423576423576424 0.027972027972027972]
[1.8091368111270818 1.6859720039258068 17.965155972271987 0.026973026973026972 0.7962037962037962]
[1.63454126490793 1.0650356796731735 180.1090874544127 0.36663336663336665 0.17782217782217782]
timenew = 4.540195051999999
timep = 1.138203373000002
timeold = 2.6787831649999965






    
Out[271]:





2.6787831649999965

In [272]:

    

complsst(10010,101)


    

    




elapsed time: 19.092920961 seconds
[1.0416746135444168 1.0 2.0882087764326913 0.693069306930693 0.039603960396039604]
[1.8542378843254879 1.8077424267467397 3.5754658615660317 0.0 0.8514851485148515]
[1.288608045611944 1.0679218834395716 11.214703437036851 0.3069306930693069 0.18811881188118812]
timenew = 5.405975421999999
timep = 1.6513358239999993
timeold = 3.728321181000001






    
Out[272]:





3.728321181000001

In [274]:

    

Profile.clear()


    

In [22]:

    

a = chimera(1000000,2);


    

In [27]:

    

include("../src/akpw.jl")
tnew = akpwish(chimera(50,1))
@time tnew = akpwish(a)
sum(compStretches(tnew,a)) / nnz(a)


    

    




  5.650605 seconds (40.30 M allocations: 1.521 GB, 12.87% gc time)






    
Out[27]:





8.156200827707035

In [23]:

    

include("../src/akpw.jl")
tnew = akpwish(chimera(50,1))
@time tnew = akpwish(a)
sum(compStretches(tnew,a)) / nnz(a)


    

    




  7.619553 seconds (40.38 M allocations: 1.596 GB, 8.47% gc time)






    
Out[23]:





8.156200827707035

In [24]:

    

told = akpw(chimera(50,1))
@time told = akpw(a)
sum(compStretches(told,a)) / nnz(a)


    

    




  7.216852 seconds (3.42 M allocations: 852.313 MB, 2.85% gc time)






    
Out[24]:





8.118114503973283

In [25]:

    

tp = akpw(chimera(50,1))
@time tp = randishPrim(a)
sum(compStretches(tp,a)) / nnz(a)


    

    




  5.191788 seconds (4.00 M allocations: 657.081 MB, 10.26% gc time)






    
Out[25]:





14.73372423665601