Immutable graph libraries and alternative structures

Hi
I know there has been more than one go at writing graph libraries. I
have a single specific usage intended for which I need immutable graph
structures of fairly modest size (a few hundred to about 4000 nodes).
I'm looking for advice on suitable libraries.
The other unusual thing about my graphs are they are typically highly
disconnected - representing activities of vehicles and drivers (it's a
VRP problem) across a period of time. Edges are activities and drivers
and vehicles do not normally interact with other drivers and vehicles
- so I get lots of chains of activities that are almost (but not
quite) lists. Branches do occur - when drivers swap to another vehicle
for example, or when the driver takes a break while someone else
offloads the truck.
The graphs are also directed and not cyclic.

So I'm looking for a library that will support that sort of structure
efficiently and immutably - though I'm not unhappy doing one by hand.

I do know about Graph4Scala (am actively looking at it) but I wondered
if there were any suggested alternatives or suggested best ways of
using it given my particular requirements.

Thanks

Tim