Addendum: Code for bridging numbers

Hey everyone,

So I mentioned in my final lattice graphs post that I'd put up how I generated the bridging numbers. The way I did it is using Python3 (specifically, Anaconda). I took some open-source code from Quora and modified it a little to suit my own needs. A link to the original code source is here and my modified code is below. I'll then go on to talk you through how it works.

def main():
    nodeToNodes = dict()
    nodeToNodes['A'] = ['B', 'D', 'E']
    nodeToNodes['B'] = ['A', 'C', 'F']
    nodeToNodes['C'] = ['B', 'D', 'H']
    nodeToNodes['D'] = ['A', 'C', 'G']
    nodeToNodes['E'] = ['A', 'I', 'J']
    nodeToNodes['F'] = ['B', 'K', 'L']
    nodeToNodes['G'] = ['D', 'P', 'O']
    nodeToNodes['H'] = ['C', 'N', 'M']
    nodeToNodes['I'] = ['E', 'T', 'U']
    nodeToNodes['J'] = ['E', 'T', 'K']
    nodeToNodes['K'] = ['F', 'J', 'S']
    nodeToNodes['L'] = ['F', 'S', 'f']
    nodeToNodes['M'] = ['H', 'R', 'a']
    nodeToNodes['N'] = ['H', 'O', 'R']
    nodeToNodes['O'] = ['G', 'N', 'Q']
    nodeToNodes['P'] = ['G', 'Q', 'Z']
    nodeToNodes['Q'] = ['O', 'P', 'o']
    nodeToNodes['R'] = ['N', 'M', 'p']
    nodeToNodes['S'] = ['K', 'L', 'l']
    nodeToNodes['T'] = ['I', 'J', 'j']
    nodeToNodes['U'] = ['I', 'V', 'l']
    nodeToNodes['V'] = ['U', 'W', 'u']
    nodeToNodes['W'] = ['V', 'X', 'd']
    nodeToNodes['X'] = ['W', 'Y', 'c']
    nodeToNodes['Y'] = ['X', 'Z', 'v']
    nodeToNodes['Z'] = ['P', 'Y', 'm']
    nodeToNodes['a'] = ['M', 'b', 'r']
    nodeToNodes['b'] = ['a', 'c', 's']
    nodeToNodes['c'] = ['X', 'b', 'd']
    nodeToNodes['d'] = ['W', 'c', 'e']
    nodeToNodes['e'] = ['d', 'f', 't']
    nodeToNodes['f'] = ['L', 'e', 'g']
    nodeToNodes['g'] = ['f', 'h', 't']
    nodeToNodes['h'] = ['g', 'i', 'q']
    nodeToNodes['i'] = ['S', 'h', 'p']
    nodeToNodes['j'] = ['T', 'k', 'o']
    nodeToNodes['k'] = ['j', 'l', 'n']
    nodeToNodes['l'] = ['U', 'k', 'u']
    nodeToNodes['m'] = ['Z', 'n', 'v']
    nodeToNodes['n'] = ['k', 'm', 'o']
    nodeToNodes['o'] = ['Q', 'j', 'n']
    nodeToNodes['p'] = ['R', 'i', 'q']
    nodeToNodes['q'] = ['h', 'p', 'r']
    nodeToNodes['r'] = ['a', 'q', 's']
    nodeToNodes['s'] = ['b', 'r', 'v']
    nodeToNodes['t'] = ['e', 'g', 'u']
    nodeToNodes['u'] = ['V', 'l', 't']
    nodeToNodes['v'] = ['Y', 'm', 's']
    out = getAllSimplePaths('A', 'C', nodeToNodes)
    out.sort(key=len, reverse=True)
    for i in out:
        if len(i) <= 10:
            print(str(len(i)-2) + ": " + str(i[1:len(i)-1]))
 
#
# Return all distinct simple paths from "originNode" to "targetNode".
# We are given the graph in the form of a adjacency list "nodeToNodes".
#
def getAllSimplePaths(originNode, targetNode, nodeToNodes):
    return helpGetAllSimplePaths(targetNode,
                                 [originNode],
                                 set(originNode),
                                 nodeToNodes,
                                 list())
 
#
# Return all distinct simple paths ending at "targetNode", continuing
# from "currentPath". "usedNodes" is useful so we can quickly skip
# nodes we have already added to "currentPath". When a new solution path
# is found, append it to "answerPaths" and return it.
#    
def helpGetAllSimplePaths(targetNode,
                          currentPath,
                          usedNodes,
                          nodeToNodes,
                          answerPaths):
    lastNode = currentPath[-1]
    if lastNode == targetNode:
        answerPaths.append(list(currentPath))
    else:
        for neighbor in nodeToNodes[lastNode]:
            if neighbor not in usedNodes:
                currentPath.append(neighbor)
                usedNodes.add(neighbor)
                helpGetAllSimplePaths(targetNode,
                                      currentPath,
                                      usedNodes,
                                      nodeToNodes,
                                      answerPaths)
                usedNodes.remove(neighbor)
                currentPath.pop()
    return answerPaths
 
if __name__ == '__main__':
    main()

---

The Explanation

Firstly, we need to set up our lattice. There are two ways I've done this: the "good enough" method and the "better, more complicated and riskier" method. I'll talk about both.

The "Good Enough"  method approximates our infinite lattice by taking a slice around our two penadjacent nodes that's up to a certain distance away. We want this distance to be large enough that we capture all the bridging numbers of our lattice, but small enough so we don't spend too long calculating.

I have tended to, for the calculation of the B¹ series up to n=6, include around 6n nodes in the calculation. This is a largely arbitrary value and is greatly influenced by the geometry of the lattice. It is important to include as many complete cycles as possible, and to prioritise smaller cycles over larger ones.

The next step is to label the nodes {A, B, C...} and to then put them in the code (lines 3-50 above). We do this by assigning dictionary key entries to each node, with the corresponding list values being the nodes that that vertex connects to. As an example, in the code above, try working it backwards. What lattice am I encoding? Hint: I'm using the second method! Speaking of...

The "Better and riskier" method involves wrapping the lattice around to form a looping surface that mimics the infinite surface. This is usually more accurate, but there are three caveats that one has to be aware of: 

1. Looping round produces many, many more paths, so calculations will take much longer

2. It is vitally important that the correct connectivity is maintained, as this will produce errors if the connectivity is wrong

3. One must be aware of pseudoloops- loops that pass from one edge to the other without returning through that edge, and as such don't actually return to the endpoint we want. This is important if you consider the same path taken on a lattice with more copies before looping- the two vertexes that are connected won't be the same! It's hard to explain this simply, but it's a quirk that is easy to miss so paths must be checked.

Generally I have used method 1 for calculations. I have tried method 2 a few times, but the increase in computation time (several hours vs several minutes) is simply not worth the negligible accuracy increase when the numbers are small!

Finally, we set our start and end nodes in the code (line 51 above), then run it. The program, as far as I can tell, first creates a list of paths- starting at the end node, it looks at all those connected to it, then all those not already listed in each chain that are connected to that latest node in each chain, etc etc, until each chain hits the starting node. The original code then prints all chains in the order they appear in the list- not length order. My addendum (lines 52-55) simply sorts the list in reverse size order (longest chain first), then prints the size of the chain (minus the start and end nodes), then the whole chain, if it's less than some threshold value (line 54).

The code is inefficient, clunky, and could be majorly improved. However it gets the job done in a few minutes, so I'm not complaining! 

We may see more code on the blog in future. But for now, adventure awaits! 

-Wolfie <3