display | more...

Topological sort and reference counting may seem two very different things in Computer Science. In fact they're almost the same. Not only does the field manage to invent its own new name for an extant topic ("topological sort" instead of "completing a partial order to a total order"), it manages to give a repeat performance!

Freeing of resources with reference counting is really just an online version of topological sort. Indeed, suppose we have some data structure with pointers pointing between objects. Clearly the destruction order for the structure that reference counting gives is a total order which extends the pointers' partial order, except that the object holding the pointer gets freed before the pointed-to object (if this really bothers you, think of the reference counted structure with the pointers reversed). But it's even worse than that: it's easy to see that all that the topological sort algorithm does is maintain a reference count for each element. Elements with a 0 reference count are "freed" by outputting them and decrementing the counts of their dependents, and the process is repeated. It's just reference counting all over again!

By now it should not be too surprising that both techniques share the same failure mode. Reference counting is unable to free any circular data structures. And topological sorting fails precisely if the input relation is not a partial order. But the only way a relation can fail to be a partial order is if it contains some cycle (and if it contains a cycle it's not a partial order). So both techniques fail for the same inputs. And since they're really the same algorithm, they both fail the same way: some cycle in the input cannot be freed/output, as no "first" element can be found.

Log in or register to write something here or to contact authors.