Biconnected components algorithm is slow #281
Description
The biconnected components algorithm is very slow on larger graphs, compared to connected components and other graph packages.
For example, take the following code
import sys
import igraph as ig
import graph_tool as gt
import graph_tool.topology as gtt
import time
gfile = sys.argv[1]
G = ig.Graph.Read(gfile, format="edges")
st = time.time()
comps = G.components()
print(f"igraph strongly connected elapsed = {time.time()-st}")
st = time.time()
comps = G.biconnected_components()
print(f"igraph biconnected elapsed = {time.time()-st}, num bicomps = {len(comps)}")
G = gt.load_graph_from_csv(gfile, directed=True, csv_options={'delimiter': '\t'})
st = time.time()
comp, art, hist = gtt.label_biconnected_components(G)
print(f"graph_tool biconnected elapsed = {time.time()-st}, num bicomps = {len(hist)}")On the Amazon graph from SNAP, I get the following results:
igraph strongly connected elapsed = 0.1865100860595703
igraph biconnected elapsed = 6.894217014312744, num bicomps = 7849
graph_tool biconnected elapsed = 0.1410079002380371, num bicomps = 7849
On the web-Google graph from SNAP, I get the following results:
igraph strongly connected elapsed = 1.2485511302947998
igraph biconnected elapsed = 1056.809671163559, num bicomps = 175274
graph_tool biconnected elapsed = 0.5269908905029297, num bicomps = 175274