How to spread changes in oriented graph?

Question

Hello, I have oriented graph. Graph can be strongly connected. Every vertex can have a set of anything, for example letters. The set is user editable.

Every vertex makes intersection of sets in previous vertices (only one step back).

But now, there is problem: When I update set of one vertex, the change should expand to all vertices and uptate their intersection of sets of previous vertices.

How to do every vertex have correct intersection after update of any vertex? Restriction: algorithm must avoid to stick in infinity. ...

Any idea how to solve it?. EDIT:

Example - red vertix changes, and it is needed to spread change of intersecions of all vertices:

Answer 1

Looks like a BFS would do it:

1. Memorize the set of the vertex which has changed.
2. Now start a breadth first search from the changed vertex
3. For each adjacent vertex change the corresponding set according to the set from (1)
4. Mark vertex as visited
5. Repeat 1-4 for each adjacent vertex until no more unvisited vertices exist

Maybe your real problem lies in the intersection of sets. That you would be point (3) here. You should add an example to make the problem clearer.

Answer 2

You could split the changes into subtractive and additive changes. Anything subtractive can be removed in one pass using the method MicSim described. Anything additive, however, might propagate all the way through any cycles that you have.

For additive changes, do the updates the same way but ignore any inputs that haven't been updated yet. This will cause you to overpopulate the graph, as you're not computing all the intersections. But then if you go back for a second pass, you'll clean up all the changes. (You might need to keep sweeping through until there are no more changes; I'm not entirely sure.)

I suppose if you don't care to keep track of what was added and what was subtracted--only that there was a change--you just do an initial sweep where update-needing but un-updated nodes don't get intersected, and then keep sweeping through until everything settles down. Since intersection can only remove elements, this is guaranteed to complete.

Answer 3

Do BFS as suggested by MicSim, stop after an iteration that hasn't changed any vertices.