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. But, they are slower.

In [1]:
using Laplacians
using LightGraphs
In [21]:
a = grid2(1000) # Laplacians style graph
lg = Graph(a)   # LightGraphs style
Out[21]:
{1000000, 1998000} undirected graph
In [22]:
@time is_connected(lg)
Out[22]:
true
0.450431 seconds (44 allocations: 31.890 MB)
In [23]:
@time isConnected(a)
Out[23]:
true
0.142486 seconds (8 allocations: 15.259 MB)

Let's subsample, and test out the speed of connected components routines.

In [24]:
as = subsampleEdges(a,0.5);
lgs = Graph(as)
Out[24]:
{1000000, 998947} undirected graph
In [27]:
@time c = components(as);

  0.061239 seconds (8 allocations: 15.259 MB)
In [28]:
@time lgc = connected_components(lgs);

  0.437358 seconds (572.18 k allocations: 73.131 MB)

Let's check if they give the same answers.

In [29]:
vecToComps(c)
Out[29]:
98859-element Array{Array{Int64,1},1}:
 [1]                                                                                              
 [2,1001,1002,2001,2002,3001]                                                                     
 [3,4,1004]                                                                                       
 [5]                                                                                              
 [6]                                                                                              
 [7]                                                                                              
 [8,1008,1009]                                                                                    
 [9]                                                                                              
 [10]                                                                                             
 [11,12,13,14,15,16,17,18,23,1003  …  13024,13025,13026,13027,13028,13029,14009,14015,14016,14027]
 [19,20,21]                                                                                       
 [22]                                                                                             
 [24,25,26]                                                                                       
 ⋮                                                                                                
 [999966]                                                                                         
 [999970]                                                                                         
 [999974,999975,999976]                                                                           
 [999977,999978]                                                                                  
 [999985]                                                                                         
 [999986]                                                                                         
 [999987]                                                                                         
 [999988,999989]                                                                                  
 [999990,999991]                                                                                  
 [999995]                                                                                         
 [999996]                                                                                         
 [999997]
In [30]:
lgc
Out[30]:
98859-element Array{Array{Int64,1},1}:
 [1]                                                                                              
 [2,1001,1002,2001,2002,3001]                                                                     
 [3,4,1004]                                                                                       
 [5]                                                                                              
 [6]                                                                                              
 [7]                                                                                              
 [8,1008,1009]                                                                                    
 [9]                                                                                              
 [10]                                                                                             
 [11,12,13,14,15,16,17,18,23,1003  …  13024,13025,13026,13027,13028,13029,14009,14015,14016,14027]
 [19,20,21]                                                                                       
 [22]                                                                                             
 [24,25,26]                                                                                       
 ⋮                                                                                                
 [999966]                                                                                         
 [999970]                                                                                         
 [999974,999975,999976]                                                                           
 [999977,999978]                                                                                  
 [999985]                                                                                         
 [999986]                                                                                         
 [999987]                                                                                         
 [999988,999989]                                                                                  
 [999990,999991]                                                                                  
 [999995]                                                                                         
 [999996]                                                                                         
 [999997]

To be sure that we are not being unfair in running time, let's time the vecToComps, too.

In [31]:
@time v = vecToComps(c);

  0.032858 seconds (98.90 k allocations: 16.559 MB)
In [ ]: