Counting triangles in a hexagon

Question

I am struggling with a problem right now. I have a problem which is related to matching and graph theory. I have given text data which is the relation of the vertexes. I need to find the number of triangles in that graph according to the given text data. I have attached an explanation image.

I have tried add weights but it did not work. I have tried to find them by using brute force. Here is my code:

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

Another problem is what should I do to count the triangles? I thought I should use count to get every relation between three nodes which is also a brute force. Do you have an easy method for this?

I have attached a manuscript about counting triangles on big graphs if it would help anyone to figure out this problem. https://i11www.iti.kit.edu/extra/publications/sw-fclt-05_t.pdf

Sorry for this long problem. Hope you have time to answer. Thanks.

Answer 1

I read your PDF and algorithm "forward" seems nice and easy.

After creating "adjacency data structure" rest is easy because there is pseudo code.

I put code but I don't know if it gives correct results.

I keep every triangle as tuple with corners in alphabetic order so later it is easer to compare duplications. Using set() it automatically removes duplications.

BTW: in comments I uses name "neighborhood matrix" but I was thinking about something like "adjacency data structure"

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)

---

I use other examples:

rectangle with diagonals:

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

Example from PDF:

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

PDF shows 2 triangles but there are 3 triangles in this graph

a b c
a b d
a d e

I think PDF has few mistakes in table near this image.