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.bay...@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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
