Библиотека для работы с графом большого размера

Требуется разработать библиотеку для работы с графом большого размера на чистом Си++ (в дальнейшем планируется использовать её как под виндами, так и под юниксом). Большой размер означает до сотен тысяч вершин и до десятков миллионов рёбер. Библиотека должна позволять производить лишь основные операции с графами - добавление/удаление вершин/рёбер, поиск вершины, проверка наличия ребра между заданными вершинами. Библиотека не должна быть многопоточной.

Естественно, она должна работать с файлами на диске, кешировать/подкачивать данные.

Есть определённые соглашения по стилю программирования, так как работа представляет собой часть более крупного проекта. Потребуется разбираться в чужом коде и согласовывать подробности своей работы со мной.

Я пока не уверен, сколько это должно стоить и сколько занять времени, так что присылайте предложения.