Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.
If we give a node in Graph A, how to find the corresponding one in Graph B?
Finally, we need to find all the node mappings.
Of course, there can be more than one possible mapping. We need to find the similarity (ranking) percentage.
How to design such an algorithm?
The graphs are Control-flow Graphs (Call Graph) extracted from program binaries. However, due to compiler difference (optimization, inline, etc.), the graphs can be a little different.
To be more clear, as shown in the figure below, we also need to find the matching like B and B',B1' ("->" means a node match):
A -> A'
B -> (B' , B1')
C -> C'
D -> D'
E -> E'
F -> F'
As this is not a sub-graph matching, I cannot find good library APIs or algorithms.