CODEWITHSUNDEEP
pythonnetworkxigraph
mathfux
mathfux

Reputation: 5949

tagging connected components using networkx

Using igraph I'm able to assign unique id of connected component for each node:

import igraph 
def tag_components(vertices, edges):
    graph = igraph.Graph()
    graph.add_vertices(vertices)
    graph.add_edges(edges)
    graph_tags = graph.clusters().membership
    return graph_tags
print(tag_components([0,1,2,3,4,5], [[1,2],[2,4],[3,5]]))

It outputs [0, 1, 1, 2, 1, 2] which means that are 3 connected components indexed 0, 1, 2 consistent of node groups [0], [1, 2, 4], [3, 5]. How can I achieve the same output using networkx?

I expect something like:

def tag_components_nx(vertices, edges):
    G = nx.Graph()
    G.add_nodes_from(vertices)
    G.add_edges_from(edges)
    ...
    return graph_tags

Update

I have a satisfactory answer already and I wonder if networkx has more sophisticated methods than connected_components suitable for my problem

Upvotes: 1

Views: 731

Answers (1)

abc
abc

Reputation: 11939

Starting from the output of nx.connected_components you can build the desired output format.

Example.

>>> g.nodes()
NodeView((0, 1, 2, 3, 4, 5))
>>> g.edges()
EdgeView([(1, 2), (2, 4), (3, 5)])
>>> idx_components = {u:i for i,node_set in enumerate(nx.connected_components(g)) for u in node_set}
>>> res = [idx_components[u] for u in vertices]
>>> res
[0, 1, 1, 2, 1, 2]

Upvotes: 2

Related Questions