Issues with Recursive Digraph Construction and Missing Loops in Python Code

Question

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.

In "we take two copies of G_1, add a new vertex, and connect them with new edges." what does "them" refer to? Do you mean 'connect the new vertex to the two copies of Gn-1'? If Gn-1 has multiple vertices do you connect the new vertex to every copied vertex? — ravenspoint
– ravenspoint, Commented Mar 24 at 12:28
Hello @ravenspoint, thank you for this point. The sentence refers to the two copies of G_1 and the new vertex: the new vertex is not connected to every vertex in the copies, just to specific key vertices. I added some examples to my post — Mark
– Mark, Commented Mar 25 at 13:21
"to specific key vertices." Which? How does the algorithm choose which vertices to connect? Random? Something else? You still have ambiguous 'them' in your specification — ravenspoint
– ravenspoint, Commented Mar 25 at 13:56
According to your definition, two vertices in G_2 have self-loops, while one does not. Therefore, for your problem 1, why is it necessary for every vertex to have self-loops? Am I misunderstanding your definition? For Problem 2, your primary concern is how to visualize correctly, isn’t it? — Fabian Stiewe
– Fabian Stiewe, Commented Mar 25 at 17:34
Another remark: I don't understand why you build G_3 the way you did in the figure. Why did you add an edge from 1 to 7 instead of adding it from 3 to 5 ? — m.raynal - bye toxic community
– m.raynal - bye toxic community, Commented Mar 26 at 13:05

Jens Timmerman · Accepted Answer · 2025-03-27 13:07:03Z

2

+25

When you're adding your new vertex, you're not adding the self loop,

You create 2 copies with a self loop but never add it to the new vertex. As you can see it's always the even vertex that get's added without self loop.

Just add it after you add the new vertex using

new_vertex = offset  
G.add_node(new_vertex)  
G.add_edge(offset, offset)  # Self-loop for new_vertex

If these self loops don't need to be there, only the copied ones need to have a self loop, then I don't see any problem? Al copied vertexes have a self loop, all added vertexes after the copy operation don't.

I don't have a lot of experience with the networkx library, but using dot and Graphviz in python you can easily create directed graphs that look nice, and add extra constraints

https://graphviz.readthedocs.io/en/stable/manual.html

you can convert a networkx graph to a pydot graph with

graph = networkx.drawing.nx_pydot.to_pydot(my_networkx_graph)

e.g.


  def draw_G(n):
      G = construct_G(n)
      graph = nx.drawing.nx_pydot.to_pydot(G)
      graph.write_png('output.png')

results in

edited Mar 27 at 13:07

answered Mar 27 at 10:46

Jens Timmerman

9,9912 gold badges45 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mark Mar 29 at 17:20

Hi, thank you for your answer. Sorry but I didn't understand how to modify the code, could you write me the modified code please?

Jens Timmerman Apr 10 at 16:07

@Mark you just replace the def draw_G function with the one I wrote, if you're having trouble doing that I believe you might want to follow an intro to python course.

Collectives™ on Stack Overflow

Issues with Recursive Digraph Construction and Missing Loops in Python Code

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related