[Haskell-cafe] OT: representations for graphs

[Jamie Brandon]

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 <jamiiecb at googlemail.com> 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.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
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bdd.pdf
Type: application/pdf
Size: 292465 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20081219/f54bd8fd/bdd-0001.pdf