I am looking for (or attempting to design) a technique for matching nodes from very similar graphs based on the structure of the graph*. In the examples below, the top graph has 5 nodes, and the bottom graph has 6 nodes. I would like to match the nodes from the top graph to the nodes in the bottom graph, such that the "0" nodes match, and the "1" nodes match, etc. This seems logically possible, because I can do it in my head for these simple examples. Now I just need to express my intuition in code. Are there any established algorithms or patterns I might consider?
(* When I say based on the structure of the graph, I mean the solution shouldn't depend on the node labels; the numeric labels on the nodes are only for demonstration.)
UPDATE: It has been correctly pointed out that using the structure alone, most of these graphs can't be solved with 100% accuracy. I've added some thoughts to each graph.
I'm also interested in the performance of any potential solutions. How well will they scale? Could I merge graphs with millions of nodes?
In more complex cases, I recognize that the best solution may be subject to interpretation. Still, I'm hoping for a "good" way to merge complex graphs.
(These are directed graphs; the thicker portion of an edge represents the head.)
This graph is a cycle with 1 node "attached to the outside." After attaching a second node to the outside it's not possible to determine whether the new node (node 5) is attached to node 1 or 3. The 4 nodes composing the cycle can't be perfectly matched either. Nodes 1 and 5 can be swapped in the bottom graph without changing the structure. Thus, you can only guess with 50/50 accuracy which is the new node. This graph has symmetry in 2 dimensions and can be mirrored without changing the structure. Meaning you can swap several nodes without changing the structure. This last graph is the only one for which you can identify the new node with 100% accuracy.
Thanks Kirk Broadhurst, for pointing this out.