python - 计算六边形中的三角形

问题描述

我现在正在努力解决一个问题。我有一个与匹配和图论有关的问题。我已经给出了顶点关系的文本数据。我需要根据给定的文本数据找到该图中三角形的数量。我附上了一张解释图片。

我尝试过添加权重，但没有奏效。我试图通过蛮力找到它们。这是我的代码：


path = r"triangles.txt"
file = open(path,"r+")
f1 = file.readlines()
splitted_list = []
a = []
b = []
c = []
d = []
e = []
f = []
g = []
h = []
j = []
k = []

for i in f1:
    splitted_list.append(i.strip().split("-"))

elements = [a,b,c,d,e,f,g,h,j,k]
values = ["a","b","c","d","e","f","g","h","j","k"]
for i in range(10):
    for t in values:
        for j in splitted_list:
            for k in range(len(j)):
                if t in j:
                    if j[k] not in elements[i] and j[k] !=t:
                        elements[i].append(j[k])

#expected output
# a = ["b","c","f","j","d","g","k","e"]
# b = ["a","c","d","e","f","h","k","j"]
# c = ["b","f","j","a","d","e"]
# d = ["a","g","k","e","c","b"]
# e = ["a","b","c","d","g","h","j","k"]
# f = ["b","h","k","j","c","a"]
# g = ["d","a","k","e","h","j"]
# h = ["g","f","b","e","k","j"]
# j = ["b","f","c","a","h","g","e","k"]
# k = ["j","e","g","d","a","h","f","b"]

#output
a =['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k']
#all the elements are also have the same value 
#a=b=c=d=e=f=g=h=j=k

另一个问题是我应该怎么做才能计算三角形？我认为我应该使用 count 来获取三个节点之间的每个关系，这也是一种蛮力。你有一个简单的方法吗？

我附上了一份关于在大图上计算三角形的手稿，如果它可以帮助任何人解决这个问题。 https://i11www.iti.kit.edu/extra/publications/sw-fclt-05_t.pdf

对不起这个长期的问题。希望你有时间回答。谢谢。

标签： pythonalgorithmgraph-theory

解决方案

我读了你的 PDF，算法"forward"看起来很简单。

创建"adjacency data structure"休息后很容易，因为有伪代码。

我输入了代码，但我不知道它是否给出了正确的结果。

我将每个三角形都保留为元组，并按字母顺序排列角点，以便以后比较重复项更容易。使用set()它会自动删除重复项。

顺便说一句：在评论中我使用名称“邻域矩阵”，但我正在考虑类似“邻接数据结构”的东西

text = '''a-b
a-c-f-j
a-d-g-k
a-e
b-c-d-e
b-f-h-k
b-j
e-g-h-j
e-k
j-k'''

# --- create Adj ---

Adj = dict()

lines = []

for row in text.strip().split('\n'):
    all_items = set(row.split('-'))
    lines.append(all_items)
    for item in all_items:
        if item not in Adj:
            Adj[item] = set()
        rest = all_items - set(item)
        Adj[item].update(rest)
        #Adj[item].update(all_items)
        #Adj[item].remove(item)

print('--- nodes ---')
nodes = sorted(Adj.keys())
print(nodes)

print('--- lines ---')
for line in lines:
    print(line)

print('--- Adj ---')
for key in sorted(Adj.keys()):
    print(key, list(sorted(Adj[key])))


# --- create triangles ---

triangles = list()
A = {x:set() for x in nodes} # create empty A(v)

for s in nodes:
    for t in Adj[s]:
        if s < t:
            for v in A[s] & A[t]:
                # check if nodes not on one line
                is_line = False
                for line in lines:
                    if s in line and t in line and v in line:
                        is_line = True
                        break
                if not is_line:
                    triangles.append(tuple(sorted( (s,v,t) )))
                    #print(*triangles[-1])
            A[t].add(s)

# --- count triangles ---

print('--- number of triangles ---')
print(len(triangles))
#print(len(set(triangles)))

# --- show triangles in alphabetic order ---

print('--- triangles ---')
for triangle in sorted(triangles):
    print(*triangle)

我使用其他示例：

带对角线的矩形：

text = '''a-b
a-c
a-d
b-c
b-d
c-d
'''

PDF 中的示例：

text = '''a-b
a-c
a-d
a-e
b-c
b-d
d-e
'''

PDF 显示 2 个三角形，但此图中有 3 个三角形

a b c
a b d
a d e

我认为 PDF 在这张图片附近的表格中几乎没有错误。

python - 计算六边形中的三角形

问题描述

解决方案

推荐阅读