Как найти все уникальные перестановки множества элементов над графом - PullRequest
Новая
       34

Как найти все уникальные перестановки множества элементов над графом

3 голосов
/ 24 февраля 2020

У меня есть проблема материаловедения, которая, я уверен, может быть решена с помощью networkx, но я не уверен, как.

Сначала я хотел бы найти все уникальные комбинации из 3 элементов с заменой. Это я уже сделал с помощью itertools следующим образом: 

elements = ["Mg","Cu","Zn"]
combinations = list(itertools.combinations_with_replacement(elements, 3))

Для каждой из этих комбинаций я хотел бы найти все уникальные перестановки на простом графе. Граф имеет три узла и три ребра, где каждый узел связан с двумя другими узлами. Важно отметить, что ребра имеют расстояние 1, но одно ребро имеет расстояние 2. По сути, как прямоугольный треугольник.

например, что-то вроде Node1 <-Distance = 1-> Node2 <-Distance = 2-> Node3 <-Distance = 1-> Node1

Так что для комбинации ["Mg", " Cu "," Cu "] должно быть две уникальные перестановки:

a ) Mg (сайт1) -1- Cu (сайт2) -1- Mg (сайт3) -2- Mg (сайт1)
b ) Mg (сайт1) -1- Mg (сайт2) -1- Cu (сайт3) -2- Mg (сайт1)
c) Cu (сайт1) -1- Mg (сайт2) -1- Mg (сайт3) -2- Cu (сайт1) (аналогично b )

ПРИМЕЧАНИЕ. Я не уверен в том, как лучше определить график, это может быть что-то вроде: 

import networkx as nx
FG = nx.Graph()
FG.add_weighted_edges_from([(1, 2, 1), (2, 3, 1), (3, 1, 2)])

1 Ответ

1 голос
/ 26 февраля 2020

Критерий уникальности, который вы хотите использовать, называется изоморфизм графов . В NetworkX есть подмодуль: networkx.algorithms.isomorphism . Вы можете указать, как именно ваши узлы / ребра графов должны рассматриваться как «равные» с node_match/edge_match параметрами. Вот пример: 

import networkx as nx

FG1 = nx.Graph()
FG1.add_node(1, element='Cu')
FG1.add_node(2, element='Cu')
FG1.add_node(3, element='Mg')
FG1.add_weighted_edges_from([(1, 2, 1), (2, 3, 1), (3, 1, 2)])

FG2 = nx.Graph()
FG2.add_node(1, element='Cu')
FG2.add_node(2, element='Mg')
FG2.add_node(3, element='Cu')
FG2.add_weighted_edges_from([(1, 3, 1), (2, 3, 1), (1, 2, 2)])

nx.is_isomorphic(
    FG1,
    FG2,
    node_match=lambda n1, n2: n1['element'] == n2['element'],
    edge_match=lambda e1, e2: e1['weight'] == e2['weight']
)

True

Если вы переименуете какой-либо элемент или измените вес ребра, графики станут неизоморфными c (с этими параметрами). Именно так вы можете найти уникальные графы - множество неизоморфных c графов. Обратите внимание, что проблема изоморфизма графов очень сложна в вычислительном отношении, поэтому ее не следует использовать даже для графов среднего размера.

Но ваша задача имеет так много ограничений, что использование графов не является необходимым. Если у вас есть только 3 элемента в «молекуле», у вас будет только 3 типа комбинаций элементов: 

1-1-1

1-1-2

1-2-3

Для каждого из них вы можете рассчитать и указать количество уникальных комбинаций:

1-1-1: один - 1=1-1

1-1-2: два - 1=1-2 и 1-1=2

1-2-3: три - 1=2-3, 1-2=3 и 1-2-3(=1)

Таким образом, вы можете просто умножить каждую комбинацию itertools на количество возможных комбинаций: 

number_of_molecular_combinations = 0
for c in combinations:
    number_of_molecular_combinations += len(set(c))
print(number_of_molecular_combinations)

18

This Метод будет работать намного быстрее, чем обработка графиков, но его можно использовать только в случае очень строгих ограничений, таких как у вас.

...