python - 将邻接矩阵转换为抽象单纯复形

Question

我有一个由邻接矩阵表示的图，我想将其转换为一个抽象的单纯复形(即所有顶点、边、三角形、四面体的列表......)以便做一些拓扑图上的计算。但是，我在使算法完全正确时遇到了一些麻烦。我在网上查了一下，找不到任何能做到这一点的东西。

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

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

继续尝试尽可能多的维度。

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

现在我只是在 2-dimensional 中工作并尝试获得三角形并且将简单地添加逻辑以稍后处理更高的。

    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 

因此，它不会在应该停止的时候停止，不会添加到三角形列表中，而且周围的一切都不起作用。

我们将不胜感激任何帮助!

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)

示例输出:

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