I wrote a miniature Ruby gem to topologically sort a Directed Acyclic Graph (DAG), which is useful when you have a bunch of things that depend on each other (e.g. tasks), and you want to put them in a linear order.
Writing the test suite got me thinking about how to find all the topologically distinct directed acyclic graphs with number of vertices V
and edges E
. My current algorithm goes like this:
Start with some large number n
of toothpicks and marshmallows.
Call the children.
Try to finish before all the marshmallows are gone.
Here is what we ended up with for all graphs of V = 4
:
Itâ€™s not bad I think, but is a method known that works even without children? Are there any graphs I missed?
(Full disclosure: I redid this photo a couple days later with better-colored toothpicks, so now you can tell which way they point. Marshmallows may be crunchier than they appear.)
blog comments powered by Disqus Prev: An nginx HTTP-to-HTTPS Redirect Mystery, and Configuration Advice Next: Temporal Databases Annotated Bibliography