Always validate that all nodes of the graph exist

Hello jeremy, 

Please review the following commits I made in branch 'nick-fixit'.

7dd91c20281b50ee9d7f218fc50dc0eb0e3b2a8a (2013-03-23 03:58:32 -0400)
Always validate that all the nodes of the graph exist. This helped find some other holes in this logic.

R=jeremy