How to find all unique permutations of a set of elements over a graph

user_7723544 0
Viewed 442

I have a material science problem which I am reasonably sure can be solved using networkx, but I'm not sure how.

Firstly I would like to find all unique combinations of 3 elements, with replacement. This I have already done with itertools as follows:

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

For each of these combinations, I would like to find all unique permutations over a simple graph. The graph has three nodes and three edges, where each node is connected to two other nodes. Importantly, the edges have a distance of 1, but one of the edges has a distance of 2. Basically, like a right-angle triangle.

e.g. something like Node1 <-Distance=1-> Node2 <-Distance=2-> Node3 <-Distance=1-> Node1

So for the combination ["Mg", "Cu", "Cu"] there should be two unique permutations:

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) (This is the same as b)

NOTE: I'm not sure of the best way to define the graph, it could be something like:

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

The uniqueness criteria you want to use is called graph isomorphism. NetworkX has a submodule for it: networkx.algorithms.isomorphism. You can specify how exactly your nodes/edges of graphs should be treated as "equal" with node_match/edge_match parameters. Here is the example:

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

If you will rename any element or change any edge weight, graphs will become non-isomorphic (with those parameters). It is how you can find unique graphs - the set of non-isomorphic graphs. Note, that graph isomorphism problem is very computational-heavy so you should not use it even for medium-sized graphs.

But your task has so many restrictions that graphs usage is not necessary. If you have only 3 element in a "molecule", you will have only 3 types of element combinations:

1-1-1

1-1-2

1-2-3

For each of them you can calculate and state the number of unique combinations:

1-1-1: One - 1=1-1

1-1-2: Two - 1=1-2 and 1-1=2

1-2-3: Three - 1=2-3, 1-2=3 and 1-2-3(=1)

So you can just multiply each itertools-combination to the number of possible combinations:

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

18

This method will work FAR faster than graph processing but is usable only in the case of very strong restrictions, like yours.

user_112277810
Related