如何在图表中找到 "triangle of friends"？

Question

我有朋友的名字，我正在寻找朋友的三角形，如果有的话。示例（姓名相邻的为好友，第一行第一个数字代表人数，第二个数字代表好友数）：

6 7
mirko slavko
slavko janko
janko mirko
slavko luka
luka mirjana
mirjana ivana
ivana luka

在这个例子中，janko - mirko - slavko 是一个三角形，mirjana - luka - ivana 是另一个三角形。

我写了一个代码，它生成一个代表这个图的二维列表。

L = [input().split() for i in range (n)]
H=[]
for i in range(n):
    for j in range(2):
        if L[i][j] not in H:
            H.append(L[i][j])
H.sort()

for number, name in enumerate(H):
    for i in range (n):
        for j in range(2):
            L[i][j]=L[i][j].replace(name, str(number))
        
    
matrix = [[0 for i in range(m)] for j in range(m)]

for i, j in L:
    matrix[int(i)][int(j)]=matrix[int(j)][int(i)]=1

图表是这样的（名字按字母顺序排列，每一行每一列代表一个名字，1代表有友谊，0代表这两个人不是朋友）：

[0, 0, 1, 1, 0, 0]  
[0, 0, 0, 0, 1, 1]  
[1, 0, 0, 1, 0, 1]  
[1, 0, 1, 0, 0, 0]  
[0, 1, 0, 0, 0, 1]  
[0, 1, 1, 0, 1, 0]

我的问题是如何用代码找到三角形？？

Answer 1

最简单的方法是

创建一个字典，其键为人名，值为该人的集朋友。确保如果 A 在 B 的朋友集中，则 B 也在 A 的朋友集中。
对每一对人A和B，看friends[A].intersect(friends[B])是否为空

Answer 2

clique problem 的大多数形式都很困难，最通用的解决方案是 NP 完全的。因此，假设输入表示有效，O(N**3) 可能是您可以做的最好的事情，并且由于您已经制作了二维矩阵，所以您已经完成了大部分工作。

friends = [
     [0,1,1,0],
     [1,0,1,1],
     [1,1,0,0],
     [0,1,0,0]]
n = 4

for i in range(n):
    for j in range(i+1, n):
        if not friends[i][j]:
            continue
        for k in range(j+1, n):
            if friends[i][k] and friends[j][k]:
                print('friends!')
                print(i,j,k)

如何在图表中找到 "triangle of friends"？

How to find a "triangle of friends" in a graph?

python

graph-theory

social-networking

triangle-count