Search code examples
pythonalgorithmtreegraph-theory

Plotting balls of the Diestel-Leader graphs

(I'm sorry if the question involves too much Mathematics, that's the bane of Mathematical programmation !)

My goal is to visualize finite radii balls in the Diestel-Leader graph DL(p,q). Here is an article by W. Woess which describes with pictures the construction (starting from page 3). I will however give it here with less mathematics to capture the idea.

It is constructed by taking two infinite trees Tp and Tq, each of respective valence p+1 and q+1. We consider height functions h:Tp→Z and h':Tq→Z, meaning that each vertex x with height k has exactly one parent vertex with height k-1 and exactly p (resp. q) children with height k+1.

Now, the vertex set of DL(p,q) is defined to be {(x,y)∈Tp×Tq : h(x)+h'(y)=0}, and two vertices (x,y) and (x',y') are adjacent in DL(p,q) if and only if x and x' are adjacent in Tp and y and y' are adjacent in Tq.

It turns out DL(p,q) is not a tree ! Balls whose radii are greater than 4 always have non-contractible loops.

I am fixing arbitrary elements o∈Tp and o'∈Tq whose heights are zero, and I am willing to plot the sub-graph of DL(p,q) consisting of elements whose distance to (o,o') is at most a certain radius R (that is the ball of radius R). This means that I must find all elements of distance at most R to o in Tp, and of distance at most R to o' in Tq, and then somehow get the adjacencies between couples of such vertices.

Also, I am mainly concerned about the case p=2 and q=3, that is DL(2,3). However, an algorithm in the general case would be more than welcome !

So far, I first tried finding a representation for elements in Tp. I tried implementing the representation given in the paragraph (2.1) Tree and sequences. in the article I linked, but even that seemed doomed. Then, I thought about taking a vertex at height -R, and represent all its children up to the generation R (that is, I would have 2R+1 generations of vertices). To represent a child of a vertex, this corresponds to labelling all the downwards edges with an integer from 0 to p-1. I first used a dec2base conversion algorithm :

def dec2base(x,b):
    if(x==0): return "0"
    digits = []
    while(x>0):
        x,r = divmod(x,b)
        digits.append(str(r))
    return "".join(reversed(digits))

Then, I simply looped through all possibles lists, and stored all vertices in a list :

def Tree(p,R):
    vertices = []
    for h in range(2*R+1):
        for k in range(p**h):
            vertices.append((dec2base(k,p),h-R))
    return vertices

This returns a list of elements of the form ("1201",-1), where the string is the path to take from the vertex at height -R, and the integer is the height. of the vertex. However, there are two issues :

  • I am generating too many vertices. Vertices generated by this method are distant at most 2R+1 to the origin, but it can happen that they are distant more than R.

  • This doesn't generate adjacencies. In structures like the one presented in this blog article, we need to feed adjacencies, but I think with this method, it's easier to generate an adjacency function (where you feed two vertices and it tells you whether they are adjacent or not) rather than a list of all such values (i.e. an adjacency matrix for instance).

With this in mind, I find it even harder to then plot the Diestel-Leader graph... I'm clueless on this one, and it's been too many years since I last manipulated graphs/trees structures.

Could anyone give me a helping hand please ?

P.S. : I took as an example, but I am not restrincting myself to any particular language, especially if one allows for an easier implementation !

Update

I think I made up a simple way to represent elements of the tree Tp that also takes the height function into account. A picture being worth much more than words, here it is :

I circled the origin vertex o∈Tp. In my picture, I took p=3 and R=3. I start with the (only) vertex x distant R from o and whose height is h(x)=-R. I label it "", and I append a "0", a "1" or a "2" to the end of a string representing a vertex to represent its children.

The height of a vertex x represented by a string of length L is given by the relation h(x)=L-R. This may be convenient when trying to generate DL(p,q). However, the catch is I wasn't able to implement an algorithm to generate the ball of radius R in the tree by this method... I tried a recursive algorithm, but I didn't see what to pass as arguments...

Now, I have managed to implement the recursion to generate the ball of radius R in Tp ! Here is how it looks (the exact same as the hand-drawn picture) :

My code for this is the following :

import networkx as nx
import matplotlib.pyplot as plt

def T(p,R):
    T = GraphVisualization()
    def addChildren(vertex,gen):
        if(gen>0):
            for k in range(p):
                T.addEdge(vertex,vertex+str(k))
                addChildren(vertex+str(k),gen-1)
    o = R*str(p-1)
    addChildren(o,R)
    for k in range(1,R+1):
        addChildren(o[:(R-k)],R-k)
    T.addEdge("0",str(p-1))
    T.visualize()

Note that this is very far from being optimal, as I generate several edges a lot of times. But I don't mind if the code is not optimized, I just want it working to visualize the balls !

Solution

  • It turns out I was very close to finishing ! It boiled down to writing the definition of the edge set for the Diestel-Leader graph :

    E[DL(p,q)]={(e1,e2)∈E[Tp]×E[Tq] : h(i(e1))+h'(i(e2))=h(t(e1))+h'(t(e2))=0}

    with i(e) denoting the initial vertex of the edge e and t(e) the terminal edge. Therefore, I simply looped through all edges of both trees and checked for that condition :

    def height(v,R):
    if(v=="0"): return -R
    return len(v)-R

def DL(p,q,R):
    Tp = T(p,R)
    Tq = T(q,R)
    G = GraphVisualization()
    for e1 in Tp.visual:
        for e2 in Tq.visual:
            ie1, te1 = e1[1], e1[0]
            ie2, te2 = e2[0], e2[1]
            if(height(ie1,R)+height(ie2,R)==0 and height(te1,R)+height(te2,R)==0):
                G.addEdge(ie1+","+ie2,te1+","+te2)
    G.visualize()

    Vertices in the Diestel-Leader graph G are represented by strings of the form "XXX,YYY", with "XXX" being the string representing a vertex in Tp and "YYY" being the string representing a vertex in Tq.

    Here is the picture of the ball of radius 2 in DL(2,3) (centered at "11,22") :