Oops, that url probably isnt accessible outside the department. I've attached a copy to this email, hopefully the mailing list doesnt strip attachments. On Fri, Dec 19, 2008 at 6:45 PM, Jamie Brandon wrote:

In model checking, transition matrices (ie weighted adjacency matrices) are often represented by binary decision diagrams. They're a very compact way of representing sparse or regular vectors/matrices (where graphs can be thought of as adjacency matrices). Theres some good lecture notes on them here:

http://web.comlab.ox.ac.uk/teaching/materials08-09/probabilistic/19-symbolic...

If you skip to page 42 theres a table comparing memory use with traditional sparse representations.

Jamie

On Fri, Dec 19, 2008 at 5:07 PM, Bayley, Alistair wrote:

...

(OT, but I'm hoping some of you might have some ideas on this anyway...)

I was wondering what alternative representations there are for graphs, or maybe if there might be a way to derive one/some from some insightful observations. For the purposes of storing and exmaining (querying) graphs in an SQL database.

For example, a tree (so, a specialised sub-class of graph) can be represented by a three models, that I know of: - adjacency-list (the most common) - materialised-path (a denormalisation of adjacency-list) - nested-sets

Nested-sets (and materialised-path) works for trees because the graph is - directed (so we know which nodes are parents or children) - acyclic (there's a definite root, and leaves) - every child has a single parent (so no diamond shapes - does this property have a name?)

Nested-sets works well with SQL databases for querying, at the expense of updates. Adjacency-list is easier to update, but some queries suck, or are downright impossible in normal SQL.

We can use the adjacency-list model for graphs too, but it has the same query deficiencies as for trees. I'd like some sort of alternative to adjacency-list, like nested-sets, that would work better for querying at the expense of updates.

Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe