Similarity Score for Chemical Structures / Graphs

Hi,

I've a question concerning the similarity between let's say topological
data.
In particular I'm working with directed graphs that I want to compare
to each other. I would like to get something like a score of their
similarity, e.g. two identical graphs have a score of 0.0 and two
random graphs have a score of 1.0. I know that this problem also
evolves in comparing chemical structures. I've found an equation like
the following:

score = number-of-identical-nodes - p*(fragments-1)

where 'p' is a freely chosen coefficient and which obviously produces a
higher score for identical graphs (that would be ok, too). Now the
problem is, that my graphs do have fragments on their own, so that
those fragments schould be part of the equation. I tried to add the two
graphs' average number of fragments and so on, but that didn't really
work. Does anybody have an idea or pointer for me?

Thank you in advance!

p.s.: Sorry, long message...