Click here to Skip to main content
15,895,746 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
I have this graph and I want to name each subgraph


What I have tried:

Python
<pre lang="Python"> <pre>import matplotlib.pyplot as plt
    import networkx as nx
    G = nx.from_numpy_array(x)  #x matrix
    #G.add_nodes_from(new_list)
    lab= dict(zip(G.nodes, new_list)) #pour nommée les noeuds
    threshold = 0.2

# filter out all edges above threshold and grab id's
    long_edges = list(filter(lambda e: e[2] <= threshold, (e for e in G.edges.data('weight'))))
    le_ids = list(e[:2] for e in long_edges)

# remove filtered edges from graph G
    G.remove_edges_from(le_ids)
    nx.draw(G,node_size=500,arrowsize=200,node_color='green', edge_color='red',font_size=10, labels=lab,
            with_labels=True)
    plt.show(300)
    print("number of edges is:",G.number_of_edges())
    print("number of nodes is:",G.number_of_nodes())
    print("lengh of the graphe is :",len(G))
    components = []
    for graph in nx.connected_components(G):
        components.append([graph, len(graph)]) 
    print("the components:",components) 
    print(nx.info(G))
Posted
Updated 28-Apr-22 1:26am
Comments
Richard Deeming 28-Apr-22 5:04am    
Name them Pugh, Pugh, Barney McGrew, Cuthbert, Dibble, and Grubb. :)

Seriously, nobody can tell you how to do something if you can't clearly and precisely explain what it is you're trying to do.

1 solution

I don't write Python, so I don't know if this networkx library has a function for finding subgraphs. If not, here's what I would do. The subgraphs will end up being numbered 1...n, where n is the number of nodes in the graph.
for i from 0 to n-1
  node[i].subgraph = 0  # subgraph assigned to node i
u = n  # number of nodes not yet reached
s = 0  # number of the current subgraph

while u > 0
  i = the first node whose node[i].subgraph is 0
  s = s + 1
  node[i].subgraph = s

  # find all nodes that belong to the new subgraph
  added = false

  repeat
    for i from 0 to n-1
      if node[i].subgraph is 0
        for each node j that is adjacent to node[i]
          if node[j].subgraph is s
            node[i].subgraph = s
            added = true
            u = u - 1
  until added is false
This can be improved by replacing u with the set of unreached nodes. When a node is assigned to a subgraph, remove it from the set. The algorithm stops when the set is empty.
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900