List:General Discussion« Previous MessageNext Message »
From:Joe Conway Date:March 2 2008 2:28am
Subject:Re: [GENERAL] Efficiently storing a directed graph
View as plain text  
Kelly Jones wrote:
> I have a directed graph (nodes and edges) that I want to store
> "efficiently": given two nodes, I want to quickly find the shortest
> path between them. The graph is NOT acyclic (it's not a tree), is
> fairly "sparse" (about 10000 edges for 2500 nodes), and changes
> occasionally.
> 
> I know PostgreSQL/MySQL can store graphs (as one table of nodes and
> one table of edges that reference the nodes), but I think finding the
> shortest path between two nodes is quite inefficient that way.
> 
> I know PostgreSQL/MySQL have special "plugins" (like PostGIS for
> PostgreSQL) for specific problems. Is there a directed graph plugin?

Perhaps use PL/R plus one of the R packages available here:
   http://cran.stat.ucla.edu/web/packages/
   (e.g. http://cran.stat.ucla.edu/web/packages/igraph/index.html)
to enable data storage in Postgres and data processing in R.

R:
   http://www.r-project.org/

PL/R:
   http://www.joeconway.com/plr/

HTH,

Joe
Thread
Efficiently storing a directed graphKelly Jones1 Mar
  • Re: Efficiently storing a directed graphPeter Brawley2 Mar
  • Re: Efficiently storing a directed graphmgainty2 Mar
    • Re: Efficiently storing a directed graphPeter Brawley2 Mar
  • Re: [GENERAL] Efficiently storing a directed graphJoe Conway2 Mar