Я сравниваю большой набор сетевых диаграмм для изоморфизма, где большинство графиков не должно быть изоморфным (например, 0-20% изоморфны чему-либо в списке, например).
Я пробовал следующий подход.
graphs = [] # A list of networkx graphs
unique = [] # A list of unique graphs
for new in graphs:
for old in unique:
if nx.is_isomorphic(new, old[0]):
break
else:
unique.append([new])
Это позволило мне получить гораздо более быстрый сокращенный набор, но я все еще считаю его слишком медленным для идеального использования. Есть ли более быстрый алгоритм для решения этого типа проблемы (сравнение пар транзитивных коммутативных свойств) или способ распространить этот алгоритм на многоядерную настройку (работает на 20-ядерном компьютере).
Я уже фильтрую эти наборы данных на основе количества узлов/ребер, мы можем предположить, что функция nx.is_isomorphic не может быть выполнена быстрее с помощью любых типов фильтрации операций. Я также не могу легко менять инструменты прямо сейчас, поэтому использование скомпилированного пакета не является вариантом.
Дополнительная информация:
Графики, как правило, составляют примерно 16-20 узлов с общим количеством 24-48 ребер, существует много взаимосвязи, поэтому каждый node имеет примерно 8 ребер. Каждое ребро также помечено, но в нем используется только 2-3 типа ребер.
