Подсчет треугольников в шестиугольнике

Question

Я сейчас борюсь с проблемой. У меня есть проблема, которая связана с сопоставлением и теорией графов. Я дал текстовые данные, которые являются отношениями вершин. Мне нужно найти количество треугольников в этом графике в соответствии с данными текстовых данных. Я приложил поясняющее изображение.

Я пытался добавить веса, но это не сработало. Я пытался найти их, используя грубую силу. Вот мой код:

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

Извините за эту долгую проблему. Надеюсь, у вас есть время ответить. Спасибо.

Answer 1

Я читаю ваш PDF и алгоритм "forward" кажется приятным и простым.

После создания "adjacency data structure" отдых легко, потому что есть псевдокод.

Я поставил код, но не знаю, дает ли он правильные результаты.

Я держу каждый треугольник как кортеж с углами в алфавитном порядке c, чтобы потом было проще сравнивать дубликаты. Используя 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 рядом с этим изображением есть несколько ошибок.