[sf-perl] [sfpug] Practical theory: graphs

[David Fetter]

On Wed, Dec 14, 2005 at 10:47:40PM -0800, Quinn Weaver wrote:
> Hi, all,
> 
> I'm looking for a practical, lay book on graph theory, especially
> one that describes how to represent graphs in RDBMSs.
> 
> I fear I am stuck with something by Date, but... Do people have any
> other recommendations?

Sure :)

First, a few refs on graph theory in general:
http://en.wikipedia.org/wiki/Graph_theory
The references there include a book from Springer in PDF form :)

The problem of is one representing graphs in RDBMSs is at the outer
edge of theory right now, so you'll be doing some pretty serious
coding to make it happen.  The kind of graph where the most has
already happened as far as RDBMSs go is a tree.

http://www.grzm.com/fornow/archives/2004/07/10/static_hierarchies
http://www.mrnaz.com/static/articles/trees_in_sql_tutorial/
http://www.sai.msu.su/~megera/postgres/gist/ltree/

> I specifically don't want formal proofs of mathematical properties
> of graphs.  What I want is something more emic: What can you
> represent with x kind of graph?  What are its properties?  What are
> the algorithms for traversing (or otherwise processing it)?  In
> short, what is it good for?

A lot of the general questions about graphs are essentially
mathematical in nature and end up with phrases like "NP-hard" or
"NP-complete."

> If anyone can come up with this, I owe them a huge debt of
> gratitude. :)

HTH :)

Cheers,
D
-- 
David Fetter david at fetter.org http://fetter.org/
phone: +1 415 235 3778

Remember to vote!