Labeled Acyclic Mexican Standoffs

LAMS.py

import itertools
# 1, 3, 25, 443, 13956

def generate_graphs(n):
    """ Generate all directed graphs for n vertices """
    all_possible_edges = [(i, j) for i in range(n) for j in range(n) if i != j]
    for edges in itertools.product([False, True], repeat=len(all_possible_edges)):
        graph = {i: [] for i in range(n)}
        for edge, edge_exists in zip(all_possible_edges, edges):
            if edge_exists:
                graph[edge[0]].append(edge[1])
        yield graph

def is_acyclic(graph):
    def dfs(vertex, visited, rec_stack):
        visited[vertex] = True
        rec_stack[vertex] = True

        for neighbour in graph[vertex]:
            if not visited[neighbour]:
                if dfs(neighbour, visited, rec_stack):
                    return True
            elif rec_stack[neighbour]:
                return True

        rec_stack[vertex] = False
        return False

    visited = [False] * len(graph)
    rec_stack = [False] * len(graph)
    
    for node in range(len(graph)):
        if not visited[node]:
            if dfs(node, visited, rec_stack):
                return False

    return True



def in_degree(graph, vertex):
    return sum(vertex in edges for edges in graph.values())

def filter_in_degree_two_or_less(graphs):
    filtered_graphs = []
    for graph in graphs:
        if all(in_degree(graph, v) <= 2 for v in graph):
            filtered_graphs.append(graph)
    return filtered_graphs

def list_dags(n):
    for graph in generate_graphs(n):
        if all(in_degree(graph, v) <= 2 for v in graph) and is_acyclic(graph):
            yield graph



def graph_to_dot(graph, cluster_index, vertex_offset):
   
    dot_str = f"    subgraph cluster{cluster_index} {{\n"
    dot_str += "        style=filled;\n"
    dot_str += "        color=lightgrey;\n"
    dot_str += "        label=\"Graph {}\";\n".format(cluster_index)
    for vertex, edges in graph.items():
        adjusted_vertex = vertex + vertex_offset
        if not edges:  # Include isolated vertices
            dot_str += f"        {adjusted_vertex};\n"
            dot_str += f"        {adjusted_vertex}[label=\"{vertex}\"];\n"
        for edge in edges:
            adjusted_edge = edge + vertex_offset
            dot_str += f"        {adjusted_vertex} -> {adjusted_edge};\n"
            dot_str += f"        {adjusted_vertex}[label=\"{vertex}\"];\n"
            dot_str += f"        {adjusted_edge}[label=\"{edge}\"];\n"

    dot_str += "    }\n"
    return dot_str

def write_graphs_to_dot_file(graphs, filename):
    with open(filename, 'w') as file:
        file.write("digraph G {\n")
        vertex_offset = 0
        for cluster_index, graph in enumerate(graphs):
            file.write(graph_to_dot(graph, cluster_index, vertex_offset))
            vertex_offset += len(graph)  # Increment vertex offset for next subgraph
        file.write("}\n")

# Example usage
n = 4
all_dags = list(list_dags(n))
write_graphs_to_dot_file(all_dags, "dags.dot")


# Example usage
n = 10  # Small number due to computational complexity

for i in range(n):
    print(sum(1 for _ in list_dags(i)))