1

I have a subgraph with some connected components as follows:

enter image description here

I'm using 

bicomponents = list(nx.biconnected_components(T))

to identify all the connected components in the subgraph. I need to remove the whole connected component and contract that component to a vertex and get a new leaf. For example, I need to remove the component {28,30,31} and introduce a new vertex 51 (I have n= 50 vertices, so new one will be 51) and join with 29 to get a new leaf.

Can someone help me to do that?

ccc
  • 574
  • 2
  • 9
  • 22

1 Answers1

2

To contract the biconnected components, we will first relabel the nodes in each component so that they have the same label, then remove the self-loops.

Construct the label mapping

label_mapping = {}
for idx, node_component in enumerate(filter(lambda s: len(s) > 2, nx.biconnected_components(g)), start=len(g) + 1):
    for node in node_component:
        if node not in label_mapping:
            label_mapping[node] = idx

Here I made two assumptions: We discard trivial biconnected components (hence the filter, which can be easily removed if undesired), and if a node belongs to two biconnected components (cut vertex), we don't contract these two components into a single node, but keep two nodes for two components. If this is not the desired behaviour, we need to merge the components having a common node, whose solution is in this question.

Contract the components

h = nx.relabel_nodes(g, label_mapping)
h.remove_edges_from(h.selfloop_edges())
ducminh
  • 1,312
  • 1
  • 8
  • 17