Good morning everyone,
I have tried to do the following but I don't get what I need to get.
I have the following graph.
import networkx as nx
G_pc = nx.Graph()
nodos=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
G_pc.add_nodes_from(nodos)
borde=[(0,13),(0,14),(1,17),(2,18),(3,13),(4,17),(5,17),(5,13),(6,12),(6,15),(7,14),(8,11),(8,13) ,(9,14),(10,16),(10,18),(11,16),(12,14)]
G_pc.add_edges_from(borde)
peso=[(0,13,20.5589012853715),(0,14,25.4177434046609),(1,17,36.2618645532395),(2,18,16.8703999582542),(3,13,34.3863683718127) ,(4,17,30.0351171023635),(5,17,33.9822809344501),(5,13,18.0200934317999),(6,12,39.2422565435151), (6,15,22.2532908062227),(7,14,19.4260879503034),(8,11,41.3183215038238),(8,13,34.278901568112),(9,14,33.7961759649886),(10,16,23.5517464403996),(10,18,28.1699993580065),(11,16,15.6238382977572),(12,14,36.8538761297749)]
G_pc.add_weighted_edges_from(peso)
nx.draw_networkx(G_pc)
What I'm trying to get is if I'm on node 13, I'll pull all the nodes below node 13 assuming node 0 is the start:
13 : (3,5,17,1,4,8,11,16,10,18,2)
If I'm on node 5:
5: (17,1,4)
If I'm on node 8:
8: (11,16,10,18,2)
So on for all nodes.
Thank you very much.
The first thing would be to convert your graph into a tree, since you are really talking about a tree-like structure by considering a "root" node (0) from which branches "descend".
I'm not very familiar with the library
networkx
, so I don't know if it has any tree-specific functions (I looked at the documentation and couldn't find it). However, it does have a method to convert your entire graph to a dictionary of lists, which you can then work on to reduce it to a tree, using recursion. Look:If we use the method
nx.to_dict_of_lists()
we get the following data structure:Which tells us, for each node, what its list of neighbors is. It is almost what we needed, but no, since, for example, among the list of neighbors of 13 appears 0, which we do not want to consider because it would be "father" and you are only interested in "children".
This method basically visits the nodes of the graph starting from zero, in a "depth search". That is, as soon as it sees that one of the children of node 0 is 13, it will next look at the children of 13 (via recursion). It marks the nodes that it has already visited to avoid entering them again in the lists of children.
In short, it generates a dictionary similar to the one seen before, but in which the "parents" have been eliminated in each list of nodes, leaving only the "children". Look at the result:
Here you can see how 0 has 13 and 14 as children, and the children of 13 are 3, 5 and 8 (0 no longer appears because it would be its "father"). Nodes without children (such as 3) do not appear in this dictionary.
If we now want to get the list of descendants of 13 (i.e. its children, plus its children's children, etc.) we can write another recursive function that does a deep traversal of this new representation of the tree:
To this function you pass the tree (that is, the dictionary that we just generated with the other function) and the node that you want to start with. Returns you the entire list of descendants of that node (not counting itself). Thus, if you pass it 0 (which is the default value for that parameter) it will return the list of all nodes except 0.
Let's try if it works:
It seems to produce in all cases the result you were looking for.