[Haskell-cafe] OT: representations for graphs

[Jamie Brandon]

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.pdf

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
<Alistair.Bayley at invesco.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>