3

What are some more interesting graph data structures for working with networks? I am interested in structures which may offer some particular advantage in terms of traversing the network, finding random nodes, size in memory or for insertion/deletion/temporary hiding of nodes for example.

Note: I'm not so much interested in database like designs for addressing external memory problems.

zenna
  • 9,006
  • 12
  • 73
  • 101
  • Not a duplicate, but you might find some good stuff here. http://stackoverflow.com/questions/500607/what-are-the-lesser-known-but-cool-data-structures – Mike Jan 25 '11 at 16:58

2 Answers2

2

One of my personal favorites is the link/cut tree, a data structure for partitioning a graph into a family of directed trees. This lets you solve network flow problems asymptotically faster than more traditional methods and can be used as a more powerful generalization of the union/find structure you may have heard of before.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
1

I've heard of Skip Graphs ( http://www.google.com/search?ie=UTF-8&oe=UTF-8&sourceid=navclient&gfns=1&q=skip+graphs ), a probabilistic graph structure that is - as far as I know - already in use in some peer-to-peer applications.

These graphs are kind of self-organizing and their goal is to achieve a good connectivity and a small diameter. There is a distributed algorithm that tries to achieve such graphs: http://www14.informatik.tu-muenchen.de/personen/jacob/Publications/podc09.pdf

phimuemue
  • 34,669
  • 9
  • 84
  • 115