[OT] Just curious: What's this algorithm's name?

[Nick Sabalausky]

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?