note
LanX
"graph
isomorphism
graph
Your description is confusing.<P>
Comparing the "shape" sound like a isomorphism test. In this case be aware that the "[google://graph isomorphism problem]" is NP-complete.<P>
Then you say your nodes are already named and have "children". General graphs have no children they have neighbours. So maybe you are speaking of trees or [wp://Partially_ordered_set|lattice]s (which have a bottom and a top element).<P>
But names and other properties should simplify the comparison it can be easier to normalize both graph according those weights and consequently ordering the nodes. <P>
This depends on the memory representation, e.g. when taking an [wp://incidence matrix] of both graphs you can order rows and columns according to the associated weights (e.g. first row/column representing the "top node" and so on). Graphs with the same incidence matrix after permutation are isomorphic.<P>
Of course this becomes more complicated when having a nontrivial [wp://automorphism] group in large graphs which is the reason for the mentioned [wp://NP-complete]ness.<P>
In short there is no general <u>fast</u> solution for arbitrary graphs when they get big, but <i>"[http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases|a number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions]"</i><P>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-708738">
<p>Cheers Rolf
</div></div><P>
UPDATE:added links
865880
865880