Show HN: Dynamic graph connectivity data structure

https://github.com/mikolalysenko/dynamic-forest

by 33a • 12 years ago

25 3 12 years ago

I'd like to know more about the use-case and advantages here. Anyone have professional experience with the cost/difficulty of maintaining spanning forests?

33a• 12 years ago

The advantage of using the library is that you would be able to answer connectivity queries and traverse the connected components of the graph efficiently.

EDIT: If you want an example application, suppose you have a physics simulation with a bunch of connected rigid bodies. You would like to be able to quickly test if two boxes are connected by links to the same body or to detect if after breaking a joint the resulting body becomes disconnected into two different pieces. Using a data structure like this would be faster than brute force searching over the graph of all bodies every time you change a link by connecting/disconnecting two bodies.

sherbet• 12 years ago

There are several well-known space and time efficient data-structures that answer membership/connectivity queries.

The main drawback has typically been that whilst they can be made to be incremental (e.g. the addition of vertices or edges) quite easily, they don't retain enough information to be made fully dynamic (addition AND removal of vertices and edges) without prohibitively increasing the space complexity required.

This data-structure, however, has particularly good time/space properties that make it interesting to anyone working on large-scale graph-analytical problems with a temporal component.

Show HN: Dynamic graph connectivity data structure

Related Stories