python - 如何在图上找到一组元素的所有唯一排列

Question

我有一个 Material 科学问题，我有理由确信可以使用 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(site1) -1- Cu(site2) -1- Mg(site3) -2- Mg(site1)
b) Mg(site1) -1- Mg(site2) -1- Cu(site3) -2- Mg(site1)
c) Cu(site1) -1- Mg(site2) -1- Mg(site3) -2- Cu(site1) (与 b 相同)

注意:我不确定定义图表的最佳方式，它可能类似于:

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

Answer 1

您要使用的唯一性标准称为 graph isomorphism . 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

如果您要重命名任何元素或更改任何边权重，图形将变得非同构(使用这些参数)。这是您找到独特图的方式 - 非同构图的集合。请注意，图同构问题的计算量很大，因此即使是中型图也不应该使用它。

但是您的任务有很多限制，因此不需要使用图表。如果“分子”中只有 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-combination 乘以可能的组合数:

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

18

这种方法的工作速度比图形处理快得多，但只有在非常严格的限制的情况下才可用，比如你的。