Implementation of the "Laakso Graph" in Python

Question

I would like to implement the "Laakso graph", a recursive graph that generates a fractal pattern, utilizing the networkX Python package.

The Laakso graph $L_k$ is defined recursively over the positive integers.

$L_1$ is simply two nodes joined by an edge.

Then $L_i$ is built from $L_{i-1}$ by replacing part of each edge in $L_{i-1}$ with a copy of the standard 4-cycle graph. (Equivalently, replacing each full edge with a copy of $L_2$). Here is a figure of $L_2$ and $L_3$ (albeit with directed edges, which I don't care about).

I don't have much coding experience (I am a mathematician by training), and honestly, have been using help from ChatGPT to create Python code for implementing different kinds of graphs.

However, this graph is not well-known, and the element of recursion is causing some difficulties in correctly implementing.

Essentially I want to be able to call some function, parameterized by $k$, that creates the $k$-level Laakso graph.

Implementing $L_1$ is trivial, and $L_2$ isn't hard either. But I'm not sure the best way to write the code so that the next level graph always gets the right number of nodes, and the edges in the right places.

Edit: In particular, I am confused about relabeling nodes when you are creating the new ones on the next level. For instance, if we are trying to replace the edge (1,2) with a copy of L_2, we need to add 4 new nodes 3,4,5,6 and a few new edges. But then what happens to the original nodes with those labels? Maybe there is a way to index the new nodes by the edge they are replacing, so that we can insert new nodes in such a way where if edge (1,2) is "edge 1" then the new nodes replacing edge 1 are 1.1, 1.2, 1.3, 1.4. I already feel like this is getting too complicated, but maybe it has to in order to implement this correctly.

Edit 2: Another figure for clarity.

Answer 1

I believe that the following implementation works. I've decided to label the nodes with strings encoding the edge in which the node is being placed. See script and generated image below.

Note: With inspiration from Paul's approach, I've refactored the code slightly and made everything more readable. If only the abstract graph is desired, then the references to pos and pos_new as well as the blocks for finding and setting node positions can simply be removed.

# script to get the Laakso graph L_k
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

k = 3
expansion_motif = [
    (0, 1),
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5)
]
relative_positions = 0.25 * np.array([
    [ 0, 0],
    [ 0, 1],
    [-1, 2],
    [ 1, 2],
    [ 0, 3],
    [ 0, 4]
])

def get_next(G,pos):
    res = nx.Graph()
    pos_new = {}
    for a,b in G.edges:
        # generate node labels
        labels = [a] + [f"[{a}{b}]{i}" for i in range(4)] + [b]
        
        # add edges to graph
        for i,j in expansion_motif:
            res.add_edge(labels[i],labels[j])
        
        # find node positions
        start,end = pos[a],pos[b]
        dx,dy = end - start
        rot = np.array([[dy,-dx],[dx,dy]])
        points = start + relative_positions@rot
        
        # set node positions
        pos_new.update(zip(labels,points))
    return res,pos_new


G = nx.Graph()
G.add_edge('0','1')
pos = {'0':np.array([0,0]),'1':np.array([0,1])}

for j in range(k-1):
    G,pos = get_next(G,pos)

plt.figure(figsize = (10,10))
nx.draw(G, with_labels = True, node_color = 'orange',pos = pos)

Resulting drawing:

Also, here's a figure of L_4. It was generated by running the above script for k = 4, but replacing the nx.draw line with the following block of code:

for k,v in pos.items():
    a,b = v
    pos[k] = np.array([-b,a])
plt.figure(figsize = (10,10))
nx.draw(G, pos = pos, node_size = 10)
plt.gca().set_aspect('equal')

Here's a similar figure for L_6, with node_size = 0 instead.

Answer 2

Just a clean-up of @BenGrossmann's brilliant answer to conform with standard networkx graph generator syntax.

#!/usr/bin/env python

"""
Construct a fractal Laakso graph order k.
"""

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

relative_positions = 0.25 * np.array([
    [ 0, 0],
    [ 0, 1],
    [-1, 2],
    [ 1, 2],
    [ 0, 3],
    [ 0, 4]
])
expansion_motif = [
    (0, 1),
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 4),
    (4, 5)
]

def expand(edges):
    for start_point, end_point in edges:
        dx, dy = end_point - start_point
        rotation = np.array([[dy, -dx], [dx, dy]])
        points = start_point + relative_positions @ rotation
        for ii, jj in expansion_motif:
            yield((points[ii], points[jj]))


def laakso_graph(k, create_using=nx.Graph):
    # create Laakso graph
    edges = [(np.array([0, 0]), np.array([0, 1]))]
    for _ in range(1, k):
        edges = list(expand(edges))

    # convert to standard nx.Graph
    positions, inverse = np.unique(np.array(edges).reshape((-1, 2)), return_inverse=True, axis=0)
    g = nx.from_edgelist(inverse.reshape((-1, 2)), create_using)
    nx.set_node_attributes(g, dict(enumerate(positions)), name="pos")
    return g


if __name__ == "__main__":

    g = laakso_graph(4)
    pos = nx.get_node_attributes(g, "pos")

    fig, ax = plt.subplots()
    nx.draw(g, pos, node_color="gray", edge_color="black", node_size=1, width=0.1, ax=ax)
    ax.set_aspect("equal")
    plt.show()