Exercise

Finding open triangles

Let us now move on to finding open triangles! Recall that they form the basis of friend recommendation systems; if "A" knows "B" and "A" knows "C", then it's probable that "B" also knows "C".

Instructions

100 XP
  • Write a function node_in_open_triangle() that has two parameters - G and n - and identifies whether a node is present in an open triangle with its neighbors.
    • In the for loop, iterate over all possible triangle relationship combinations.
    • If the nodes n1 and n2 do not have an edge between them, set in_open_triangle to True, break out from the if statement and return in_open_triangle.
  • Use this function to count the number of open triangles that exist in T.
    • In the for loop, iterate over all the nodes in T.
    • If the current node n is in an open triangle, increment num_open_triangles.