I have names of people that are friends and I am looking for triangles of friends, if there are any. Example (names next to each other classify as friends, in the first row the first number represents the number of people and the second number represents number of friendships):
6 7
mirko slavko
slavko janko
janko mirko
slavko luka
luka mirjana
mirjana ivana
ivana luka
In this example, janko - mirko - slavko is one and mirjana - luka - ivana is an another triangle.
I wrote a code which generates a 2d list which represents this graph.
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
the graph looks like this (names are sorted alphabeticly, each row and column represent a name, 1 represents that a friendship exists, 0 represent that these two people aren't friends):
[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]
My question is how to find a triangle with code??
Most forms of the clique problem are difficult, the most general solutions are NP complete. Therefore O(N**3) is probably the best you can do assuming the input representation is efficient, and since you already made the 2d matrix you are most of the way there.
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)