Match the vertices of two identical labelled graphs

user_7351617 0
Viewed 21

I have a rather simple problem to define but I did not find a simple answer so far.

I have two graphs (ie sets of vertices and edges) which are identical. Each of them has independently labelled vertices. Look at the example below: enter image description here

How can the computer detect, without prior knowledge of it, that 1 is identical to 9, 2 to 10 and so on?

Note that in the case of symmetry, there may be several possible one to one pairings which give complete equivalence, but just finding one of them is sufficient to me.

This is in the context of a Python implementation. Does someone have a pointer towards a simple algorithm publicly available on the Internet? The problem sounds simple but I simply lack the mathematical knowledge to come up to it myself or to find proper keywords to find the information.

EDIT: Note that I also have atom types (ie labels) for each graphs, as well as the full distance matrix for the two graphs to align. However the positions may be similar but not exactly equal.

graph python
2 Answers

This is known as the graph isomorphism problem, and probably very hard; although the exactly details of how hard are still subject of research.

(But things look better if you graphs are planar.)

user_13462760

So, after searching for it a bit, I think that I found a solution that works most of the time for moderate computational cost. This is a kind of genetic algorithm which uses a bit of randomness, but it is practical enough for my purposes it seems. I didn't have any aberrant configuration with my samples so far even if it is theoretically possible that this happens.

Here is how I proceeded:

  1. Determine the complete set of 2-paths, 3-paths and 4-paths
  2. Determine vertex types using both atom type and surrounding topology, creating an "identity card" for each vertex

Do the following ten times:

  1. Start with a random candidate set of pairings complying with the allowed vertex types
  2. Evaluate how much of 2-paths, 3-paths and 4-paths correspond between the two pairings by scoring one point for each corresponding vertex (also using the atom type as an additional descriptor)
  3. Evaluate all other shortlisted candidates for a given vertex by permuting the pairings for this candidate with its other positions in the same way
  4. Sort the scores in descending order
  5. For each score, check if the configuration is among the excluded configurations, and if it is not, take it as the new configuration and put it into the excluded configurations.
  6. If the score is perfect (ie all of the 2-paths, 3-paths and 4-paths correspond), then stop the loop and calculate the sum of absolute differences between the distance matrices of the two graphs to pair using the selected pairing, otherwise go back to 4.

Stop this process after it has been done 10 times

  1. Check the difference between distance matrices and take the pairings associated with the minimal sum of absolute differences between the distance matrices.
user_73516170
Related