graph-script.py

import networkx as nx
from collections import defaultdict
import itertools
import planarity

def graph_from_adj(adj):
    G = nx.Graph()
    for (src, edges) in enumerate(adj):
        for dest in edges:
            G.add_edge(src, dest)
    return G

def get_graphs(
    adj,
    cur_index=0,
    seen_graphs=None,
):
    if seen_graphs is None:
        seen_graphs = defaultdict(list)

    graph_size = len(adj)
    if cur_index == graph_size:
        yield adj
        return

    def index_of_degree_zero(adj):
        for i in range(cur_index, graph_size):
            if len(adj[i]) == 0:
                return i
        return None

    # If the current node is missing k neighbors, we can limit our connections
    # to neighborless nodes by only considering the first k.
    num_we_need = 3 - len(adj[cur_index])
    ind_zero = index_of_degree_zero(adj)
    first_neighborless_node = max(graph_size if ind_zero is None else ind_zero, cur_index + 1)
    end_index = min(first_neighborless_node + num_we_need, graph_size)

    # Is there a fully disconnected subgraph?
    if cur_index > 0:
        if all(len(adj[i]) == 3 for i in range(0, cur_index)):
            if all(len(adj[i]) == 0 for i in range(cur_index, graph_size)):
                return

    for combo in itertools.combinations(range(cur_index + 1, end_index), num_we_need):
        if any(len(adj[i]) == 3 for i in combo):
            return

        for partner in combo:
            adj[cur_index].append(partner)
            adj[partner].append(cur_index)

        # # Check for a node of degree zero with a node of nonzero degree after it.
        # do_it = True
        # ind_zero = index_of_degree_zero(adj, cur_index+1)
        # if ind_zero is not None:
        #     if ind_zero < combo[-1]:
        #         do_it = False

        G = graph_from_adj(adj)
        similar_graphs = seen_graphs[cur_index]

        if planarity.is_planar(G):
            if not any(nx.is_isomorphic(G, old_graph) for old_graph in similar_graphs):
                similar_graphs.append(G)
                yield from get_graphs(adj, cur_index + 1, seen_graphs)

        for partner in reversed(combo):
            assert adj[cur_index][-1] == partner
            assert adj[partner][-1] == cur_index
            adj[cur_index].pop()
            adj[partner].pop()

for x in get_graphs([[] for _ in range(12)]):
    print(x)