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

Question

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

4

我有一个材料科学问题，我相信可以使用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)])

- Daniel Marchand

你在代码中如何精确地定义这个图形？ - Green Cloak Guy

1

我不知道该如何定义它，只要有任何一种方法可以给我三个节点并编码正确的距离，那对我来说都是可以的。 - Daniel Marchand

1

我添加了一种可能的生成图形的方式。 - Daniel Marchand

“简单图”不能有从一个节点到自身的边-但是在您的示例中，节点Mg每次都会有一条指向自身的边。请澄清。 - kaya3

你可以将其视为Mg1和Mg2，想象一下类似于H2O的东西，其中有两个不同的原子，'H'但是属于相同的元素。 - Daniel Marchand

@DanielMarchand 但是你的输入是 ["Mg", "Cu", "Cu"]，为什么有两个不同的 Mg 节点呢？ - kaya3

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vurmux · Accepted Answer

您想要使用的唯一性标准称为图同构。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']
)

如果您重新命名任何元素或更改任何边权重，图形将变得不同构（在这些参数下）。这是您可以找到唯一图形的方法-非同构图形集合。请注意，图同构问题非常计算密集，因此即使对于中等规模的图形，也不应使用它。

但是您的任务有很多限制，使用图表并不必要。如果“分子”中只有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。