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)]=matrica[int(j)][int(i)]=1

for i in range(m):
    for j in range(m):
        if matrix[i][j]==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??

CodePudding user response：

The dead simple method would be

1. Create a dictionary whose key is the people's names, and the value is the set of friends of that person. Make sure that if A is in the set of friends of B, that B is also in the set of friends of A.

2. For each pair of people A and B, see if friends[A].intersect(friends[B]) is empty.

CodePudding user response：

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)