Algorithms

def is_prime(number):
    if number < 2:
        return False
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            return False
    return True

def Euclidean(a, b):
    r = b % a
    if r == 0:
        return a
    return Euclidean(r, a)

def gcd(a, b):
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            return i

from math import gcd

def lcm(a, b):
    for i in range(max(a, b), (a*b)+1):
        if i % a == 0 and i % b == 0:
            return i

def lcm_with_gcd(a, b):
    return a*b // gcd

from math import lcm

from collections import defaultdict
from math import comb

# Make Graph
"""
Graph data maybe like this;
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'C', 'D'},
    'C': {'A', 'B', 'D', 'E'},
    'D': {'B', 'C', 'E', 'F'},
    'E': {'C', 'D'},
    'F': {'D'}
}
"""
graph = defaultdict(set)

# make a undirected graph
for u, v in wires:  # 'wires' seems a directed graph.
    graph[u].add(v)
    graph[v].add(u)

# Node Degree
n_g = {}
for u in graph:
    n_g[u] = len(graph[u])

# Clustering Coefficient
c_g = {}
for u in graph:
    c_g[u] = 0
    for v in graph[u]:
        c_g[u] += len(graph[v])
    c_g[u] /= max(1, comb(len(graph[u]), 2))

node_degree = sorted(n_g, key=lambda x: n_g[x], reverse=True)
clstr_coeff = sorted(c_g, key=lambda x: c_g[x], reverse=True)

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set()
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)
    return len(visited)  # Count # of nodes of a graph

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return len(visited)  # Count # of nodes of a graph