[Python] Issues with Recursive Digraph Construction and Missing Loops in Python Code

I'm trying to write code to recursively generate directed graphs as described in the following process:

• For G_1, we start with a single vertex with a self-loop.
• For G_2, we take two copies of G_1, add a new vertex, and connect them with new edges.
• For G_3 and higher, we repeat the process, taking two copies of G_{n-1}, adding a new vertex, and connecting them with three new edges.

The process should be recursive, and I'm using Python with the networkx library to represent and visualize the graphs. Here's the code I wrote so far:

import networkx as nx
import matplotlib.pyplot as plt

def construct_G(n):
if n == 1:
G = nx.DiGraph()
G.add_node(1)
G.add_edge(1, 1) # Self-loop
return G

G_n_minus_1 = construct_G(n - 1)
G = nx.DiGraph()
G.add_nodes_from(G_n_minus_1.nodes)
G.add_edges_from(G_n_minus_1.edges)

offset = 2**(n-1)
G_renamed = nx.relabel_nodes(G_n_minus_1, lambda x: x + offset)
G.add_nodes_from(G_renamed.nodes)
G.add_edges_from(G_renamed.edges)

new_vertex = offset
G.add_node(new_vertex)

G.add_edge(1, 2**n - 1)
G.add_edge(offset + 1, new_vertex)
G.add_edge(new_vertex, offset - 1)

return G

def draw_G(n):
G = construct_G(n)
pos = nx.spring_layout(G, seed=42)
plt.figure(figsize=(8, 6))
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, arrowsize=10)
plt.title(f"Digraph G_{n}")
plt.show()

# Example: Draw the digraph G_4
draw_G(2)


Problem 1:
The code is missing self-loops for some vertices, which should be present according to the definition. I can't figure out how to add these loops for these vertices in the graph. (The presence of vertices with loops ultimately depends on the copying mechanism underlying the recursive definition of the graph. In fact, the loop that starts at step n=1 is copied and propagates from step to step.)

Problem 2:
When the value of n is greater than 2, the graph's vertices and edges overlap. The graph looks correct for n = 2, but for higher values of n, the nodes and edges are superimposed, making it difficult to visualize.

Any suggestions on how to fix these issues?

Updates.

I added some figures:



for G_1,



for G_2,



for G_3.

Continue reading...