What particularly puzzles me: Using my example graph I nowhere see the right
answer in the gt output:
edgelist = np.array([[ 0, 1], [ 0, 3], [ 0, 5], [ 0, 9], [ 1, 2], [ 1,
4], [ 1, 5], [ 1, 8], [ 1, 16], [ 1, 17], [ 1, 23], [ 3, 5], [ 3, 19], [ 5,
6], [ 5, 9], [ 5, 11], [ 5, 13], [ 6, 7], [ 6, 10], [ 8, 12], [ 8, 21], [ 9,
15], [ 9, 22], [11, 13], [13, 14], [13, 21], [15, 20], [15, 24], [17, 18]])
edgeweights = np.array([2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1,
1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1])
G = Graph(directed=False)
G.add_edge_list(edgelist)
weight = G.new_edge_property('int')
weight.a = edgeweights
graph_draw(G, edge_pen_width=weight, vertex_text=G.vertex_index,
output_size=(300, 300))
Visual inspection shows that the largest bicomponent is the set of 9 vertices
{0, 1, 3, 5, 8, 9, 11, 13, 21}.
bicomp, articulation, nc = label_biconnected_components(G, eprop=weight)
print(bicomp.a)
> [16 16 16 16 0 1 16 16 12 14 15 16 11 4 16 16 16 2 3 10 16 7 8 16 9
> 16 5 6 13]
print(articulation.a)
> [0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0]
nc
> array([ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13],
> dtype=uint64)
How do I recover the largest component?
Also, my example is a weighted graph, but the method is agnostic of edge
weights. So what can eprop be used for?
Best wishes
Haiko
Von: graph-tool [mailto:[email protected]] Im Auftrag von Lietz,
Haiko
Gesendet: Dienstag, 5. Juni 2018 14:38
An: '[email protected]'
Betreff: [graph-tool] Extract largest biconnected component
Hi all,
There is a function to label the edges of biconnected components in a graph:
https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.label_biconnected_components
I'm struggling to interpret the output of the example given there. comp.a is an
edge property map with integers labeling edges. But what are those values?
And how can I use this property map to extract the *largest* bicomponent?
Is it about binarizing the map and using it in G.set_edge_filter()?
Many thanks in advance, list
Haiko
_______________________________________________
graph-tool mailing list
[email protected]
https://lists.skewed.de/mailman/listinfo/graph-tool
