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

Question

我有一个材料科学问题，我有理由相信可以使用networkx解决，但我不确定如何解决。

首先，我想找到3个元素的所有独特组合，并进行替换。我已经用itertools完成了如下操作：

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

对于这些组合中的每一个，我都想在一个简单的图上找到所有唯一的排列。该图有三个节点和三条边，其中每个节点都连接到另外两个节点。重要的是，这些边的距离为1，但是其中一个边的距离是2。基本上，就像一个直角三角形。

例如类似Node1&lt-距离=1->Node2&lt-距离=2->Node3&lt-距离=1->Node1

因此，对于组合["Mg"，"Cu"，"Cu]应该有两个独特的排列：

a(Mg(site1(-1-Cu(site2(-1-Mg(site3(-2-Mg

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

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

Answer 1

要使用的唯一性标准称为图同构。NetworkX有一个子模块：NetworkX.algorithms同构。您可以指定如何使用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:One-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

此方法的工作速度将比图形处理快得多，但仅在非常严格的限制情况下可用，如您的方法。