MultiThreaded Graph Library (MTGL) from Sandia National Laboratories.
From the webpage:
The MultiThreaded Graph Library (MTGL) is a collection of algorithms and data structures designed to run on shared-memory platforms such as the massively multithreaded Cray XMT, or, with support from the Qthreads library, on Symmetric Multiprocessor (SMP) machines or multi-core workstations. The software and API is modeled after the Boost Graph Library, though the internals differ in order to leverage shared memory machines.
The MTGL is copyrighted and released under a Berkeley open source license. If you are a developer, you may get the most recent unreleased version of the MTGL (after logging in) by clicking the “Browse Source” tab at the top of this page, then clicking on “trunk,” and finally clicking on the “zip archive” link. See below for the MTGL 1.0 release, which will have various improvements and will not include deprecated/experimental code.
This was cited and used in the “High-performance Computing Applied to Semantic Databases” article that I covered in Is That A Graph In Your Cray?
As of 2/15/2012, version 1.1 is available.
You may not have time on a Cray but if you have a multi-core workstation this library may spark some creative thoughts!