Take a look at the Graph modules. Chances are you're reinventing wheels;)

Update
Oops, missed that you already knew about Graph. It is definitely the place to look. Even if it does fully not solve your problem, you will have useful building blocks, i.e. data structures, common algorithms etc.