import random


class Graph:
    def __init__(self, connected_nodes):
        self.structure = connected_nodes[:]  # list of sets

    def __repr__(self):
        structure = map(lambda s: "{" + ", ".join([f'v{x}' for x in s]) + "}", self.structure)
        return "\n".join([f'v{i}: {s}' for i, s in enumerate(structure)])

    def list_of_edges(self):
        edge_list = []
        for i, s in enumerate(self.structure):
            edge_list.extend([(i, x) for x in s])
        return edge_list

    def number_of_symmetries(self):
        def backtracking(count=0, mapping_vertex=0):
            if mapping_vertex >= n:
                if mapping_structure == self.structure:
                    if 0 < count < 4:
                        print(f'Example {count - 1}:\n' +
                              "\n".join(f'{v1} -> {v2}' for v1, v2 in enumerate(mapping)) +
                              "\n")
                    return count + 1
                return count
            for vertex in list(unmapped_vertices):
                unmapped_vertices.remove(vertex)
                mapping.append(vertex)
                adjacent = set(range(mapping_vertex)) & self.structure[mapping_vertex]
                mapping_structure[vertex] = set(map(lambda x: mapping[x], adjacent))
                for adj_vertex in adjacent:
                    mapping_structure[mapping[adj_vertex]].add(vertex)
                if len(mapping_structure[mapping_vertex] - self.structure[mapping_vertex]) == 0:
                    count = backtracking(count, mapping_vertex + 1)
                for adj_vertex in adjacent:
                    mapping_structure[mapping[adj_vertex]].remove(vertex)
                mapping_structure[vertex] = set()
                mapping.pop()
                unmapped_vertices.add(vertex)
            return count

        n = len(self.structure)
        unmapped_vertices = set(range(n))
        mapping = []
        mapping_structure = [set()] * n
        return backtracking()


class GraphGenerator:
    @staticmethod
    def _randomly_assigned(_):
        return bool(random.randint(0, 1))

    @staticmethod
    def _randomly_assigned_with_density(density):
        return random.uniform(0.0, 1.0) <= density

    @staticmethod
    def _all_edges(number_of_vertices):
        for v1 in range(number_of_vertices - 1):
            for v2 in range(v1 + 1, number_of_vertices):
                yield v1, v2

    @staticmethod
    def generate(number_of_vertices, density=None):
        if number_of_vertices < 0:
            raise NegativeVertexCountError
        structure = [set() for _ in range(number_of_vertices)]
        randomly_assigned = GraphGenerator._randomly_assigned
        if density is not None:
            randomly_assigned = GraphGenerator._randomly_assigned_with_density
        for v1, v2 in GraphGenerator._all_edges(number_of_vertices):
            if randomly_assigned(density):
                structure[v1].add(v2)
                structure[v2].add(v1)
        return Graph(structure)

    @staticmethod
    def generate_full(number_of_vertices):
        if number_of_vertices < 0:
            raise NegativeVertexCountError
        return Graph([set(range(number_of_vertices)) - {v} for v in range(number_of_vertices)])

    @staticmethod
    def generate_tree(number_of_vertices):
        if number_of_vertices < 0:
            raise NegativeVertexCountError
        structure = [set() for _ in range(number_of_vertices)]
        remaining_vertices = list(range(number_of_vertices))
        assigned_vertices = []
        v1 = remaining_vertices.pop(random.randrange(len(remaining_vertices)))
        v2 = remaining_vertices.pop(random.randrange(len(remaining_vertices)))
        assigned_vertices.append(v1)
        assigned_vertices.append(v2)
        structure[v1].add(v2)
        structure[v2].add(v1)
        while remaining_vertices:
            v1 = remaining_vertices.pop(random.randrange(len(remaining_vertices)))
            v2 = assigned_vertices[random.randrange(len(assigned_vertices))]
            assigned_vertices.append(v1)
            structure[v1].add(v2)
            structure[v2].add(v1)
        return Graph(structure)

    @staticmethod
    def petersen_graph():
        return Graph([{2, 3, 5}, {3, 4, 6}, {0, 4, 7}, {0, 1, 8}, {1, 2, 9},
                      {0, 6, 9}, {1, 5, 7}, {2, 6, 8}, {3, 7, 9}, {4, 5, 8}])


class NegativeVertexCountError(Exception):
    """Exception raised when user enters negative number of vertices"""
    def __init__(self):
        super().__init__("Parameter number_of_vertices cannot be negative")


if __name__ == '__main__':
    # Testing 1
    print("Test graph:")
    test_graph = Graph([
        {1, 2, 3},
        {0, 2},
        {0, 1, 3},
        {0, 2}
    ])
    print(str(test_graph) + "\n")
    print("Number of symmetries: " + str(test_graph.number_of_symmetries()))
    
    print("\n----------------------\n")
    
    print("Petersen graph:")
    petersen_graph = GraphGenerator.petersen_graph()
    print(str(petersen_graph) + "\n")
    print("Number of symmetries: " + str(petersen_graph.number_of_symmetries()))
    
    print("\n----------------------\n")
    
    print("Test full graph:")
    test_graph = GraphGenerator.generate_full(9)
    print(str(test_graph) + "\n")
    print("Number of symmetries: " + str(test_graph.number_of_symmetries()))
    
    print("\n----------------------\n")
    
    print("Test random graph with density:")
    test_graph = GraphGenerator.generate(10, density=0.3)
    print(str(test_graph) + "\n")
    print("Number of symmetries: " + str(test_graph.number_of_symmetries()))
    
    print("\n----------------------\n")
    
    print("Test random tree:")
    test_graph = GraphGenerator.generate_tree(10)
    print(str(test_graph) + "\n")
    print("Number of symmetries: " + str(test_graph.number_of_symmetries()))