Also, I like storing my data in mysql for other reasons so I don't want to switch everything wholesale to a graph database, but I wonder if I should be loading the graphical part of the data into something in memory, like a graph cache, that I can easily query rather than having to do all the recursive programming myself. Does something like that exist, a simple free library that acts as an in-memory graph db?
I suspect you want to extract a few basic functions from what you've already written, and then combine them for new features. The posibilities are not endless, there's only so many things you are likely to want to do on a graph, and the vast majority (like TFA) are not useful to you
Here are some common operations:
* list everythign reachable from a given node, depth first order
* list everythign reachable from a given node, breadth first order
* make the reverse graph (edges point the other way)
* find the strongly connected component a node is in (a more general way of identifying loops)
Then you can build more complex queries out of those, rather than coding them every time. e.g.
> show only the part of the graph that leads to this category of nodes
get the reverse graph, for each node in the category, find everything reachable in the reverse graph, and union them together in one set
> display the graph while hiding everything downstream of node X
get the set of everything downstream, then list everything depth first, skipping stuff in the set.
It's not super efficient, but I don't think you care.
It doesn’t sound like too much work to create your own in-memory cache - if you even need it...
Graph dbs are more for searching for patterns in your data. In your case it sounds more like you just want to traverse the graph and display a subset of it.
The idea, roughly, is that corresponding to each node of the original tree (or forest), in the (resulting) binary tree, the left child denotes “first child [in original tree]” and the right child denotes “next sibling [in original tree]”. In TAOCP there are 15 pages about this idea (including exercises) (plus 4 pages of solutions). In this paper here, the author calls it the Knuth transform, and extends that idea to a larger class of graphs. (This is all in the first paragraph of the paper, but just posting this here in case the context is helpful to someone, as I didn't know all this before just now.)
"Seven Trees in One" by Andreas Blass.
HTML dom has the necessary links. Let's you do dfs without a stack.