Extract largest biconnected component

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Extract largest biconnected component

Lietz, Haiko

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

 

 

Dr. Haiko Lietz

GESIS - Leibniz Institute for the Social Sciences

Department of Computational Social Science

Unter Sachsenhausen 6-8, 50667 Köln, Germany

Tel: + 49 (0)221 / 47694 - 223

eMail: [hidden email]

Web: http://www.gesis.org

 


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Lietz, Haiko

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:[hidden email]] Im Auftrag von Lietz, Haiko
Gesendet: Dienstag, 5. Juni 2018 14:38
An: '[hidden email]'
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
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Tiago Peixoto
Administrator
In reply to this post by Lietz, Haiko
Am 05.06.2018 um 13:38 schrieb Lietz, Haiko:
> 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?

They are the biconnected component labels, as the documentation says.

> And how can I use this property map to extract the **largest** bicomponent?

Just look at the label that occurs most often.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Tiago Peixoto
Administrator
In reply to this post by Lietz, Haiko
Am 06.06.2018 um 10:44 schrieb Lietz, Haiko:
> bicomp, articulation, nc = label_biconnected_components(G, eprop=weight)

Read the documentation carefully. The `eprop` parameter is used to specify
the _output_ property map where the labels will be stored. This is only
there if you want to re-use a property map, instead of creating a new one.
It has nothing to do with weights.

> 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?
It seems the label 16 occurs most often. Just extract the vertices with
edges labeled 16.

Best,
Tiago

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Lietz, Haiko
In reply to this post by Lietz, Haiko
Hi Tiago,

Yes, your approach works in my case, and below I give the code.

But imagine a graph consisting of a 4-clique and a 5-ring overlapping in one node:

edgelist = np.array([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [0, 4], [4, 5], [5, 6], [6, 7], [0, 7]])
G = Graph(directed=False)
G.add_edge_list(edgelist)

In this case your proposed method to extract the vertices with edges labeled the most frequent number doesn't work. Is there a universal recipe?

This is the way to extract the largest bicomponent in a working example:

# create graph
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]])
G = Graph(directed=False)
G.add_edge_list(edgelist)
# extract largest bicomponent
bicomp, articulation, nc = label_biconnected_components(G)
l = []
for i in list(bicomp.a == 16):
    l.append(bool(i))
edge_filter = G.new_edge_property('bool')
edge_filter.a = l
G.set_edge_filter(edge_filter)
m = label_largest_component(G)
G = GraphView(G, vfilt=m)
G.num_vertices()

Best

Haiko
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Lietz, Haiko
In reply to this post by Lietz, Haiko
> But imagine a graph consisting of a 4-clique and a 5-ring overlapping in one node:
>
> ...
>
> In this case your proposed method to extract the vertices with edges labeled the most frequent number doesn't work. Is there a universal recipe?

I mean, I can check the size of each bicomponent and then pick the largest one. I guess that's the universal recipe?

Haiko

_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: Extract largest biconnected component

Tiago Peixoto
Administrator
Am 11.06.2018 um 09:37 schrieb Lietz, Haiko:
>> In this case your proposed method to extract the vertices with edges labeled the most frequent number doesn't work. Is there a universal recipe?
>
> I mean, I can check the size of each bicomponent and then pick the largest one. I guess that's the universal recipe?

I suppose. I can't think of any other reasonable definition of "largest"...

--
Tiago de Paula Peixoto <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>