Re: graphs in PostgreSQL

On Thu, 13 Oct 2005, Ivan Yu. Zolotukhin wrote:

> Hello,
>
> I'm trying to organize storage and processing of a graph (pretty spare,
> 100,000 vertices and 5,000,000 edges) with PostgreSQL.
>
> I have two main problems:
> - standart problem of finding all shortest paths between two given vertices;
> - search thru vertices' properties with ordering by path lengths from
> given vertix.
>
> So, basically, I need to decide what additional data (some preprocessed
> data about a graph or indexes) I need to store, how to store it, and how
> maintain it when graph changes.
>
> It seems that the second problem (ordering by path length) requires to
> store all path lengths between all vertices pairs (roadmap), that is
> very expensive to maintain.
>

You might look at PostGIS, as it seems you essentially want to store
spatial data and this is a better tool for this purpose than the native
Postgresql spatial datatypes.

Brent Wood