0
415
ViewsGenerar todos los dígrafos de un tamaño dado hasta el isomorfismo
Estoy tratando de generar todos los gráficos dirigidos con un número determinado de nodos hasta el isomorfismo del gráfico para poder introducirlos en otro programa de Python. Aquí hay una implementación de referencia ingenua usando NetworkX, me gustaría acelerarla:
from itertools import combinations, product import networkx as nx def generate_digraphs(n): graphs_so_far = list() nodes = list(range(n)) possible_edges = [(i, j) for i, j in product(nodes, nodes) if i != j] for edge_mask in product([True, False], repeat=len(possible_edges)): edges = [edge for include, edge in zip(edge_mask, possible_edges) if include] g = nx.DiGraph() g.add_nodes_from(nodes) g.add_edges_from(edges) if not any(nx.is_isomorphic(g_before, g) for g_before in graphs_so_far): graphs_so_far.append(g) return graphs_so_far assert len(generate_digraphs(1)) == 1 assert len(generate_digraphs(2)) == 3 assert len(generate_digraphs(3)) == 16El número de tales gráficos parece crecer bastante rápido y está dado por esta secuencia OEIS . Estoy buscando una solución que pueda generar todos los gráficos hasta 7 nodos (alrededor de mil millones de gráficos en total) en un tiempo razonable.
Representar un gráfico como un objeto NetworkX no es muy importante; por ejemplo, me parece bien representar un gráfico con una lista de adyacencia o usar una biblioteca diferente.
1 answers
Answer question0
En lugar de usar nx.is_isomorphic para comparar dos gráficos G1 y G2, también podría generar todos los gráficos que son isomorfos a G1 y verificar si G2 está en este conjunto. Al principio, esto suena más engorroso, pero le permite no solo verificar si G2 es isomorfo a G1, sino también si algún gráfico es isomorfo a G1, mientras que nx.is_isomorphic siempre comienza desde cero al comparar dos gráficos.
Para facilitar las cosas, cada gráfico se almacena simplemente como una lista de aristas. Dos grafos son iguales (no isomorfos) si el conjunto de todas las aristas es el mismo. Asegurarse siempre de que la lista de aristas sea una tupla ordenada hace que == pruebe exactamente esa igualdad y haga que las listas de aristas se puedan modificar.
import itertools def all_digraphs(n): possible_edges = [ (i, j) for i, j in itertools.product(range(n), repeat=2) if i != j ] for edge_mask in itertools.product([True, False], repeat=len(possible_edges)): # The result is already sorted yield tuple(edge for include, edge in zip(edge_mask, possible_edges) if include) def unique_digraphs(n): already_seen = set() for graph in all_digraphs(n): if graph not in already_seen: yield graph already_seen |= { tuple(sorted((perm[i], perm[j]) for i, j in graph)) for perm in itertools.permutations(range(n)) }En comparación con las variantes de la solución anterior, esto da los siguientes tiempos en mi máquina:
Todo esto parece bastante prometedor, pero ya para 6 nodos, mis 16 GiB de memoria no son suficientes y el sistema operativo finaliza el proceso de Python. Estoy seguro de que puede combinar este código con la generación de gráficos en lotes para cada outdegree_sequence como se detalla en la respuesta anterior. Esto le permitiría a uno vaciar lo que ya se already_seen después de cada lote y reduciría drásticamente el consumo de memoria.