I have a graph as represented by an adjacency matrix and I would like to convert that into an abstract simplicial complex (that is, a list of all vertices, edges, triangles, tetrahedrons...) in order to do some topology computations on the graph. However, I'm having some trouble getting the algorithm quite right. I looked online and couldn't find anything that quite did this.
In words, what the code does is makes a list of all edges (for example, an edge between a and b would be ab so the list would look like [ab, bc, ad...]. We then need to find all triangles. So, start with a random edge, say ab and add it to a string. Then similar to a depth-first-search, we add to a queue a list of all other edges that have either a or b in them. We try appending them to the string. If, after 3 iterations, the string is comprised of duplicates (that is, it looks like abbcca) then add abc to my list of triangles, pop the stack and try again.
Similarly, for 3 dimensions (tetrahedrons) we do something similar and look at our list of triangles [abc, bcd, bce...]. We take abc and add all triangles that share EITHER ab, bc, or ac to our queue and try appending those triangles to the string. If, after 4 iterations we have only duplicates then we know that there's a tetrahedron.
Keep going for as many dimensions as wanted.
But, the code is not working as desired and I'm really stuck.
Right now I'm just working in 2-dimensions and trying to get triangles and will simply add logic to handle higher later.
def DFS(edges, count, node, triangles, tempTriangle):
print(tempTriangle)
visited, stack = set(), [node]
tempTriangle = tempTriangle.strip(" ")
if count > 2:
return
elif len(tempTriangle) % 3 == 0 and deleteDuplicates(tempTriangle) == "":
print("Triangle: ", oneTimeLetters(tempTriangle))
triangles.append(oneTimeLetters(tempTriangle))
tempTriangle = ""
neighbors = [x for x in edges if hasIntersection(node, x) == False and strIntersection(tempTriangle, x) != x]
for y in neighbors:
if y not in visited:
visited.add(y)
tempTriangle = tempTriangle + y
if count > 2:
count = 0
node = (edges - visited)[0]
DFS(edges, 0, node, triangles, "")
DFS(edges, count+1, y, triangles, tempTriangle)
tempTriangle = tempTriangle[:len(tempTriangle)-2]
visited.pop()
def deleteDuplicates(word):
letterList = set()
for c in word:
if c in letterList:
word = word.replace(c, "")
letterList.add(c)
return word
def oneTimeLetters(word):
letterList = set()
for c in word:
if c in letterList:
word = word.replace(c, "")
letterList.add(c)
return ''.join(letterList)
def hasIntersection(a, b):
return not set(a).isdisjoint(b)
def strIntersection(s1, s2):
out = ""
for c in s1:
if c in s2 and not c in out:
out += c
return out
I'm running this on the toy case of a graph with 5 vertices given by
Edges = ['cd', 'da', 'eb', 'cb', 'dc', 'ea', 'db', 'ac', 'ca', 'bd', 'ba', 'be', 'ad', 'bc', 'ab', 'ae']
Adjacency matrix =
[[ 0. 1. 1. 1. 1.]
[ 1. 0. 1. 1. 1.]
[ 1. 1. 0. 1. 0.]
[ 1. 1. 1. 0. 0.]
[ 1. 1. 0. 0. 0.]]
Given that input it just returns an empty list and the print statement from tempTriangle gives me a long list of things
dc
dcae
dcaecd
dcaecb
dcaedb
dcaebc
dcaebd
dcba
dcbacd
dcea
dceacd
dceacb
dceadb
dceabc
//...abbreviated the long list
So, it doesn't stop when supposed to, doesn't add to the triangles list and just all around doesn't work.
Any and all help would be greatly appreciated!
Here is some working code. It keeps your basic idea but refines it a bit by keeping and reusing the list of shared neighbors of each simplex in the previous degree.
When finding the next degree simplices containing a simplex S, we choose a random vertex V and the subsimplex S-V. To find the neighbors of S we simply look up those of V and S-V and take the intersection. Each element N in the intersection gives a new simplex S+N.
We take advantage of set and dict containers for fast lookup, intersection and duplicate purging.
def find_cliques(edges, max_sz=None):
make_strings = isinstance(next(iter(edges)), str)
edges = {frozenset(edge) for edge in edges}
vertices = {vertex for edge in edges for vertex in edge}
neighbors = {vtx: frozenset(({vtx} ^ e).pop() for e in edges if vtx in e)
for vtx in vertices}
if max_sz is None:
max_sz = len(vertices)
simplices = [set(), vertices, edges]
shared_neighbors = {frozenset({vtx}): nb for vtx, nb in neighbors.items()}
for j in range(2, max_sz):
nxt_deg = set()
for smplx in simplices[-1]:
# split off random vertex
rem = set(smplx)
rv = rem.pop()
rem = frozenset(rem)
# find shared neighbors
shrd_nb = shared_neighbors[rem] & neighbors[rv]
shared_neighbors[smplx] = shrd_nb
# and build containing simplices
nxt_deg.update(smplx|{vtx} for vtx in shrd_nb)
if not nxt_deg:
break
simplices.append(nxt_deg)
if make_strings:
for j in range(2, len(simplices)):
simplices[j] = {*map(''.join, map(sorted, simplices[j]))}
return simplices
# demo
from itertools import combinations
edges = set(map(''.join, combinations('abcde', 2)))
random_missing_edge = edges.pop()
simplices = find_cliques(edges)
from pprint import pprint
pprint(random_missing_edge)
pprint(simplices)
Sample output:
'ae'
[set(),
{'d', 'a', 'e', 'c', 'b'},
{'be', 'ab', 'cd', 'bd', 'ad', 'ac', 'ce', 'bc', 'de'},
{'bce', 'abc', 'acd', 'bcd', 'cde', 'abd', 'bde'},
{'abcd', 'bcde'}]