将邻接矩阵转换为抽象单纯复合体

Question

我有一个由邻接矩阵表示的图，我想将其转换为抽象单纯复合体（即所有顶点、边、三角形、四面体等的列表），以便对图进行一些拓扑计算。但是，我在编写算法时遇到了一些困难。我在网上搜索后没有找到完全符合要求的内容。

简单来说，代码的作用是生成所有边的列表（例如，a和b之间的边将是ab，因此列表看起来像[ab, bc, ad...]）。然后我们需要找到所有的三角形。所以，从一个随机的边开始，比如ab，并将其添加到字符串中。类似于深度优先搜索，我们将所有其他具有a或b的边的列表添加到队列中。我们尝试将它们附加到字符串中。如果在3次迭代后，字符串由重复项组成（即看起来像abbcca），则将abc添加到我的三角形列表中，弹出堆栈并重试。

同样地，在三维空间（四面体）中，我们做类似的事情，并查看我们的三角形列表[abc，bcd，bce...]。我们取abc并添加共享ab、bc或ac的所有三角形到我们的队列中，并尝试将这些三角形附加到字符串中。如果在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个顶点构成的图的玩具案例，其给定方式如下：

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.]]

鉴于输入仅返回一个空列表并且tempTriangle中的打印语句给出了一个很长的列表

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

所以，它在应该停止时并没有停止，没有添加到三角形列表中，总之就是不起作用。

非常感谢任何帮助！

- LivingRobot

---

你的代码有什么问题？ - internet_user

已添加输入/输出。谢谢！ - LivingRobot

我不明白count最初是如何传递到AdjacencyToASC()函数中的，同时i在哪里定义了？ - DrBwts

i 是之前的一个愚蠢错误。我将其更改以反映更准确的代码和测试用例场景。稍后我使用 AdjacencyToASC(edges, 0, edges[0], triangles, "") 调用该函数，其中 triangles 是一个空列表。 - LivingRobot

Answer 1

以下是一些可工作的代码。它保留了你的基本思路，但通过保留和重用每个上一个维度中各单体所共享的邻居列表对其进行了微调。

在查找包含单体S的下一个维数的单体时，我们选择一个随机顶点V和子单体S-V。为了找到S的邻居，我们简单地查找V和S-V的邻居并取交集。交集中的每个元素N都会产生一个新的单体S+N。

我们利用集合和字典容器进行快速查找、交集和重复清除。

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)

样例输出：

'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'}]

- Paul Panzer

---

哦，我的天啊！非常感谢！！你是最棒的！这真的非常聪明。谢谢。 - LivingRobot