Ответ 1
Как уже упоминалось, если вы хотите остаться в Python + Networkx, вы можете использовать could_be_isomorphic для фильтрации ваших графиков.
Проблема заключается в том, что этот метод ожидает, что 2 графика будут входными, а не миллионными. Если вы сравниваете каждую пару графиков с этим методом, это займет очень много времени.
Рассматривая исходный код could_be_isomorphic, он сравнивает степень, треугольник и количество последовательностей клик для обоих графиков. Если они не равны, графики не могут быть изоморфными.
Вы можете упаковать этот отпечаток в функцию, сортировать свои графики в соответствии с этим отпечатком и группировать их с помощью itertools.groupby. Будет огромное большинство одиноких графиков. Несколько графиков, имеющих одни и те же отпечатки пальцев, можно проверить на изоморфизм.
Использование списка из 100 000 случайных графов:
many_graphs = [nx.fast_gnp_random_graph(random.randint(16, 22), 0.2) for _ in range(100000)]
Было всего 500 отпечатков пальцев, которые были разделены по меньшей мере на 2 графа. Если вы добавите информацию о типах краев, будет еще меньше общих отпечатков пальцев.
Здесь приведен пример с 3000 графиками, каждый из которых имеет от 10 до 14 узлов:
import networkx as nx
from itertools import groupby
import random
many_graphs = [nx.fast_gnp_random_graph(
random.randint(10, 14), 0.3) for _ in range(3000)]
def graph_fingerprint(g):
order = g.order()
d = g.degree()
t = nx.triangles(g)
c = nx.number_of_cliques(g)
props = [[d[v], t[v], c[v]] for v in d]
props.sort()
# TODO: Add count of edge types.
return(props)
sorted_graphs = sorted(many_graphs, key=graph_fingerprint)
for f, g in groupby(sorted_graphs, key=graph_fingerprint):
similar_graphs = list(g)
n = len(similar_graphs)
if n > 1:
print("Found %d graphs which could be isomorphic." % n)
for i in range(n):
for j in range(i + 1, n):
g1, g2 = similar_graphs[i], similar_graphs[j]
if g1 != g2 and nx.is_isomorphic(g1, g2):
print(" %s and %s are isomorphic!" %
(nx.generate_graph6(g1,header=False), nx.generate_graph6(g2,header=False)))
Он находит 4 изоморфных пары менее чем за 1s:
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Id?OGG_C? and [email protected][email protected]? are isomorphic!
Found 6 graphs which could be isomorphic.
I?OWcGG?G and [email protected]_ are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
I_uI???JG and II??QDNA? are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
[email protected] and [email protected]`dS? are isomorphic!
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Вот 2 последних изоморфных графа. "IDOCCY @GG":
и "IOGC @\dS?":
Вот 2 графика, которые имеют один и тот же отпечаток, но не изоморфны:
Отпечаток пальца может выполняться параллельно. Сортировка и группировка должны выполняться на 1 ЦП, но проверка изоморфизма для каждой группы может выполняться в разных ЦП.