Cellular automata over a graph?

Is anybody aware of a project that has created a cellular automata-like system, but where the grid is replaced by a directed graph? In other words, each node has a state plus a list of neighboring nodes, and a rule for computing the next state as a function of those two things. Many relaxation-based graph layout algorithms are based on a data structure like this, but the rules are usually hand-crafted. In contrast, a cellular automata-style system would view the rules as being configurable.

I've been thinking about using evolutionary algorithms to play around with source code. One of the most natural ways of doing this, to my mind, is to use a system like the one I just described. The directed graph would be the program AST, enriched with edges representing function references, variable references, and type references. My main open question right now is how to represent the node state and transition rules (these two things being intimately related). The state needs to be simple so that it is easily manipulable by the transition rules, yet it also needs to be sophisticated so that it can encode interesting information.

I'm currently thinking of having a fixed number of state variables per node, but allowing each state variable to hold a set of values. That way you can get rich information (any number of values), with a simple interface (insert, remove, and query-membership). The state transition algorithm might be different for each node type. The instruction set would include SIMD instructions for working with all the edges of a given type, or all the values in a set, at once.

If anybody is aware of any other projects working on applying evolutionary algorithms applied to directed graphs, please let me know. (Genetic Programming doesn't count; it uses a DAG to represent the phenotype, not the environment.)