Berrys_Algorithm.py

# Function to find all minimal separators of a graph
def find_minimal_separators(G):
    separators = []
    visited_separators = {}
    
    # Initial iteration
    for v in G.vertices():           
        N_v = set(G.neighbors(v))
        S = N_v.union({v})
        G_S = G.copy()
        G_S.delete_vertices(S)
        
        connected_components = G_S.connected_components()
        
        for H in connected_components: 
            N_v = set(G.neighbors(H[0]))
            for vertex in H: 
                N_v = N_v.union(set(G.neighbors(vertex)))
            nh = N_v.difference(H)
            separators.append(list(nh))
    
    # Remove duplicates from the separators list
    separators = list({tuple(sorted(s)) for s in separators})
    
    print("after initialization, list of minimal separators: ", separators)
    
    # Iteration to get all minimal separators
    for entry in separators:
        if not visited_separators.get(tuple(sorted(entry)), False):
            continue
        visited_separators[tuple(sorted(entry))] = True  # Mark separator as visited
        for x in entry:
            Sx = set(entry).union(G.neighbors(x))
            G_Sx = G.copy()
            G_Sx.delete_vertices(Sx)
            
            connected_components = G_Sx.connected_components()
            
            for H in connected_components:
                N_v = set(G.neighbors(H[0]))
                for vertex in H:
                    N_v = N_v.union(set(G.neighbors(vertex)))
                nh = N_v.difference(H)
                separators.append(list(nh))
    
    print("final separators: ", separators)
    
    return separators

# Example usage:
# Create a graph (replace this with your actual graph)
G = Graph({1: [2], 2: [1, 3], 3: [2, 4], 4: [5, 3], 5: [4, 6]})
separators = find_minimal_separators(G)
print("final separators: ", separators)