邻接矩阵到抽象单复形的转换

Question

我有一个由邻接矩阵表示的图，我想把它转换成一个抽象的简单复形（即所有顶点、边、三角形、四面体的列表…），以便在图上进行一些拓扑计算。但是，我有一些困难，使算法非常正确。我在网上查了一下，找不到任何能说明这一点的东西。在

换句话说，代码所做的就是列出所有边（例如，a和b之间的一条边将是ab，因此该列表看起来像[ab, bc, ad...]。然后我们需要找到所有三角形。所以，从一个随机边开始，比如ab并将其添加到一个字符串中。然后与深度优先搜索类似，我们向队列中添加一个包含a或b的所有其他边的列表。我们试着把它们加到绳子上。如果在3次迭代之后，字符串由重复项组成（也就是说，它看起来像abbcca），然后将abc添加到我的三角形列表中，弹出堆栈并重试。在

类似地，对于3维（四面体），我们做一些类似的事情并查看我们的三角形列表[abc, bcd, bce...]。我们使用abc并将共享ab、bc或{}的所有三角形添加到队列中，并尝试将这些三角形附加到字符串中。如果，经过4次迭代，我们只有重复的，那么我们知道有一个四面体。在

继续追求想要的多个维度。在

但是，代码没有按预期工作，我真的卡住了。在

现在我只是在二维中工作，尝试得到三角形，然后简单地添加逻辑来处理更高的值。在

    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

我在一个有5个顶点的图的玩具箱上运行

^{pr2}$

给定这个输入，它只返回一个空列表，来自tenttriangle的print语句给了我一个很长的列表

dc
dcae
dcaecd
dcaecb
dcaedb
dcaebc
dcaebd
dcba
dcbacd
dcea
dceacd
dceacb
dceadb
dceabc
//...abbreviated the long list 

所以，它不会在应该停止的时候停止，不会添加到三角形列表中，只是周围都不起作用。在

任何和所有的帮助将不胜感激！在

Answer 1

这里有一些工作代码。它保留了您的基本思想，但通过保留和重用上一级中每个单纯形的共享邻居列表对其进行了一点细化。在

在寻找包含单纯形S的下一次单形时，我们选择一个随机顶点V和子样本S-V。要找到S的邻域，只需查找V和S-V的邻域并取交集。交集中的每个元素N给出一个新的单纯形S+N

我们利用set和dict容器进行快速查找、交集和重复清除。在

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)

样本输出：

^{pr2}$