I have a directed graph, which can be cyclic, where each node contains a value.
Nodes are not labeled, and different nodes can contain the same value.
The outgoing edges of a node are ordered, or labeled, (1, 2, 3, ... N), where N is the number of outgoing edges from the node. (That is, it's a k-ary tree, if such a term can be used for a cyclic structure).
For each node in the graph, I produce a description of that node using the algorithm below. Nodes are considered the "same" (equivalent) if they end up having the same description.
My motivation is that I'd like to produce a hash value from the description which will be the same for nodes where their value and the subgraph reachable from the node are (recursively) the same... however, if the descriptions are the same, the hash will be the same, so we don't need to worry about the hash.
I describe the data structure reachable from the node in this simple way:
Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are labeled.
Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include in the hash the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.
For example, for a tree with nodes containing values A, B, C, and D:
I calculate describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and describe the values and edges this way:
0: A [1 2 3] 1: B  2: C  3: D 
Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).
And similarly, to calculate the description for C:
0: C  1: A [2 0 3] 2: B  3: D 
As another example:
both nodes get the same description, because the algorithm produces the same description when run for each node.
Now, I'm assuming I haven't just solved the isomorphism problem for labeled graphs ;-)
Thus I'm guessing this algorithm describes some special case of graph isomorphism easier to solve than the general problem... or, it's not a solution to graph isomorphism because we're comparing nodes not graphs... or the algorithm is flawed doesn't produce the result I think it does! :-)
But I don't know enough computer science to be able to tell which nodes exactly would be characterized as the "same" or "different" by this algorithm.
It might be that different nodes (different in the usual way that you'd typically characterize the isomorphism of labeled graphs) are nonetheless "close enough" for my purposes that I don't mind that they get the same description.
And, if this simple algorithm does produce the result I want, I'd be eager to know if a more efficient algorithm exists. But I can't ask that question without being able to specify what the simple algorithm does do.
Or, if I did understand what equivalence relation the algorithm produced, I might see that the algorithm was indeed flawed for my purposes.
Can you help?