Nothing important, just something I'm curious about: At least a couple times recently I've come across a certain pattern for dealing with directed graphs (ones that may have cycles). It seems general enough that I'm surprised I don't seem to recognize it (but then again, it has been years since I've formally studied algorithms - I only have vague recollections of names like "Prim's"). A brief search didn't seem to turn up anything that jumped out at me as being a match.
Here's what it's for: Suppose you have a directed graph, which may have cycles, and you want to compute something for each node. But the final result for each node is dependent on the final results for each of the nodes it points to. (It may sound like this would just cause an endless "feedback loop" ie infinite recursion whenever there's a cycle, but there are applications of this where that isn't a problem. Ie, in cases where the computation stops recursing when it gets back to itself.) A basic example: You have a graph. Various strings can be computed for each node (based on the data stored in the node). Additionally, for each node, all N edges are numbered from 1 to N. For each node "X", you want to compute a single set of unique strings: All the strings computed from node X, plus all the strings computed from all the nodes reachable from node X using *only* even-numbered edges (ie, "edge % 2 == 0"). The way that's done: There's two main phases: 1. "Spontaneously generate" a partial result for each node X. This partial result is *only* the strings generated from node X itself. It does not attempt to include any strings from the other nodes reachable from X. Additionally, while you're at each node X, you generate a "propagation graph": Ie, make note of which edges are even-numbered and will therefore need to be traversed. 2. "Propagate" the results. For each node X, add in (propagate) any new strings that come directly from the nodes you noted in the "propagation graph" (ie, the edges you already identified as matching "edge % 2 == 0"). Repeat this step 2 until you can go through the entire graph without propagating any new strings. Granted, that specific example can be simplified somewhat since "follow only even-numbered edges" just happens to be trivial without actually creating a propagation graph. But anyways, that's the basic idea. There's at least two uses of this algorithm when building LALR parse tables for LALR parsing: For one, it's used to generate all the lookahead information (which is where I got much of the terminology). And I've recently realized that, unless I'm mistaken, it also appears to be needed when determining what terminals can be the "first" terminal in a nonterminal's derivation (which is, in turn, more necessary information for computing the lookahead information). Even though I don't remember ever encountering this particular algorithm anywhere besides generating LALR parse tables, I have a feeling there are other practical applications of it. So anyone know offhand what this graph-processing algorithm is called? Or is it just too basic a usage of graphs for it to even have a name?