Create a tree data using networkx in python

Question

I am trying to create a tree that has 1111 nodes and is organized such that node 1 has 10 children (2 to 11), node 2 has 10 children (12 to 21) and so on... such that each node had 10 children with 1 node at the root level, having 10 child nodes, each child node has 10 children, and each of these 100 nodes have 10 child nodes each this having 1000 leaf nodes. The total number of nodes is 1111.

import networkx as nx
G = nx.Graph()
L1 = [1]
L2 = [x for x in range(2,12)]
L3 = [x for x in range(12,112)]
L4 = [x for x in range(112,1112)]

G.add_node(1)
G.add_nodes_from(L1)
G.add_nodes_from(L2)
G.add_nodes_from(L3)
G.add_nodes_from(L4)

Now I want to add edges using G.add_edges_from([(x,y) for x in L1 for y in L2]) which is OK for the first level but how do I do it for the other levels?

Answer 1

You can generalize the creation of the graph to an arbitrary depth and an arbitrary number of children for each internal node.

If you start numbering the levels from 0 -- that is the root node represents level 0 -- then each level contains n^level nodes.
n is the number of children on each internal node.

Therefore you can identify the indices of the first and last node on each level.
For instance in your case with n = 10 the last nodes for levels 0, 1, 2, 3 are
10⁰ = 1,
10⁰ + 10¹ = 11,
10⁰ + 10¹ + 10² = 111,
10⁰ + 10¹ + 10² + 10³ = 1111.

To find the indices of the children for a given node you take the index of the last node on that level and add an offset.
If the given node is the first (leftmost) node on that level the offset is 0.
If its the last node on that level the offset is (n^level - 1) * n.
Then (n^level - 1) is the number of predecessor nodes on that level.
In general the offset is calculated as [number of predecessor nodes on that level] * n.

This notion is covered in the code as offset = ulim + i * n + 1.
I have added 1 to be able to loop in the following from 0 - (n-1) instead of from 1 - n.

import networkx as nx

n = 10  # the number of children for each node 
depth = 3 # number of levels, starting from 0

G = nx.Graph()
G.add_node(1) # initialize root

ulim = 0
for level in range(depth): # loop over each level
  nl = n**level # number of nodes on a given level
  llim = ulim + 1 # index of first node on a given level 
  ulim = ulim + nl # index of last node on a given level
  for i in range(nl): # loop over nodes (parents) on a given level
    parent = llim + i
    offset = ulim + i * n + 1 # index pointing to node just before first child
    for j in range(n): # loop over children for a given node (parent)
      child = offset + j
      G.add_node(child)
      G.add_edge(parent, child)

      # show the results
      print '{:d}-{:d}'.format(parent, child),
    print ''
  print '---------'

---

For depth = 3 and n = 3 this is the output:

1-2 1-3 1-4 
---------
2-5 2-6 2-7 
3-8 3-9 3-10 
4-11 4-12 4-13 
---------
5-14 5-15 5-16 
6-17 6-18 6-19 
7-20 7-21 7-22 
8-23 8-24 8-25 
9-26 9-27 9-28 
10-29 10-30 10-31 
11-32 11-33 11-34 
12-35 12-36 12-37 
13-38 13-39 13-40 
---------

Answer 2

Figured out the answer

import networkx as nx
G = nx.Graph()
L1 = [1]
L2 = [x for x in range(2,12)]
L3 = [x for x in range(12,112)]
L4 = [x for x in range(112,1112)]


G.add_node(1)
G.add_nodes_from(L1)
G.add_nodes_from(L2)
G.add_nodes_from(L3)
G.add_nodes_from(L4)
G.add_edges_from([(x,y) for x in L1 for y in L2])
temp2 = []
temp = []
temp2.extend(L4)
temp.extend(L3)
for i in range(1,11,1):
    G.add_edges_from([x,temp.pop()] for x in L2)
    G.add_edges_from([y,temp2.pop()] for y in L3)

print G.nodes()
print G.edges()
print G.number_of_nodes()
print G.number_of_edges()
print G.neighbors(1)

try:
    diameter_of_myGraph =nx.shortest_path_length(G)
    #print diameter_of_myGraph
except nx.NetworkXNoPath:
    print 'No path'

try:
    avg_distance_of_myGraph =nx.average_shortest_path_length(G)
    print avg_distance_of_myGraph
except nx.NetworkXNoPath:
    print 'No path'