MulaiMulai sekarang secara gratis

Menemukan segitiga terbuka

Sekarang mari kita beralih ke pencarian segitiga terbuka! Ingat bahwa ini menjadi dasar dari sistem rekomendasi teman; jika "A" mengenal "B" dan "A" mengenal "C", maka kemungkinan "B" juga mengenal "C".

Latihan ini adalah bagian dari kursus

Pengantar Analisis Jaringan di Python

Lihat Kursus

Petunjuk latihan

  • Tulis fungsi node_in_open_triangle() yang memiliki dua parameter — G dan n — dan menentukan apakah suatu simpul berada dalam segitiga terbuka dengan para tetangganya.
    • Dalam loop for, iterasi semua kemungkinan kombinasi relasi segitiga.
    • Jika simpul n1 dan n2 tidak memiliki sisi di antara keduanya, setel in_open_triangle menjadi True, keluar dari pernyataan if, dan kembalikan in_open_triangle.
  • Gunakan fungsi ini untuk menghitung jumlah segitiga terbuka yang ada di T.
    • Dalam loop for, iterasi semua simpul di T.
    • Jika simpul saat ini n berada dalam segitiga terbuka, tingkatkan num_open_triangles.

Latihan interaktif praktis

Cobalah latihan ini dengan menyelesaikan kode contoh berikut.

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)
Edit dan Jalankan Kode