시작하기무료로 시작하기

열린 삼각형 찾기

이제 열린 삼각형을 찾아보겠습니다! 열린 삼각형은 친구 추천 시스템의 기반이 됩니다. 예를 들어, "A"가 "B"를 알고, "A"가 "C"도 안다면, "B"와 "C"도 서로 알 가능성이 높습니다.

이 연습은 강의의 일부입니다

Python으로 시작하는 네트워크 분석

강의 보기

연습 안내

  • 이웃과의 관계에서 어떤 노드가 열린 삼각형에 속하는지 판별하는 함수 node_in_open_triangle()를 작성하세요. 매개변수는 G와 n 두 개입니다.
    • for 루프에서 가능한 모든 삼각관계 조합을 순회하세요.
    • 노드 n1과 n2 사이에 간선이 없으면(즉, 서로 연결되어 있지 않으면) in_open_triangle을 True로 설정하고, 해당 if에서 빠져나와 in_open_triangle을 반환하세요.
  • 이 함수를 사용해 T에 존재하는 열린 삼각형의 개수를 세세요.
    • for 루프에서 T의 모든 노드를 순회하세요.
    • 현재 노드 n이 열린 삼각형에 속하면 num_open_triangles를 증가시키세요.

실습형 인터랙티브 연습

이 예제를 이 샘플 코드를 완성하여 풀어보세요.

from itertools import combinations

# Define node_in_open_triangle()
def node_in_open_triangle(G, n):
    """
    Checks whether pairs of neighbors of node `n` in graph `G` are in an 'open triangle' relationship with node `n`.
    """
    in_open_triangle = False

    # Iterate over all possible triangle relationship combinations
    for n1, n2 in ____:

        # Check if n1 and n2 do NOT have an edge between them
        if not ____:

            in_open_triangle = ____

            break

    return ____

# Compute the number of open triangles in T
num_open_triangles = 0

# Iterate over all the nodes in T
for n in ____:

    # Check if the current node is in an open triangle
    if ____:

        # Increment num_open_triangles
        ____ += 1

print(num_open_triangles)
코드 편집 및 실행