From the dialogues that you reported, it looks
like the xs version of the package got built
and installed OK. I'm not sure why
the t/weak.t test still reported that the xs version was
needed - perhaps a make distclean is needed
before rerunning perl Makefile.PL. In any case,
does this fix the original problem with the Graph
module?