Resolving Dependencies and Incompatibilities Deterministically

Question

Problem Description

I'm working in Python and I've been having a problem designing something to handle the following (abstracted) system:

I have some objects (lets call them Nodes) that can be in states. These corresponds to physical objects in real life. One node can be in multiple states. Additionally, each state can act on one or more nodes. For example:

# Create nodes
A = Node("A")
B = Node("B")
# Apply states to A
Blue(A)
Red(A)
# Apply states to B
Blue(B)
# Apply states to both A and B
BlueConnection(A,B)
BlueConnection(B,A) # Not necessarily the same thing, sometimes order matters!

Each state might have some states that it requires or some states that prevent it. For example:

Blue(A)
Green(A)
Blue(B)
RedConnection(A,B) # Invalid! RedConnection requires all nodes to be red.
BlueConnection(A,B) # Also invalid! BlueConnection won't work if any of the nodes are green.

EDIT: These restrictions correspond to some real life physical restrictions. For a more concrete example:

A = Node("A")
Grounded(A)
Flying(A) # Invalid! A can't be standing on the ground and flying at the same time.
B = Node("B")
FlyingEast(B) #Invalid! B can't be flying East if it's not Flying.

It's possible to remove states. If this causes other state to no longer meet their requirements, those states would be automatically removed as well.

Blue(A)
Blue(B)
BlueConnection(A,B)
# Use a static method of State to remove Blue from A
State.remove(Blue, A) # Also automatically removes BlueConnection(A,B), since BlueConnection requires both nodes to be blue.

Finally, we'll write "Transitions", which are a group of state changes. Users will select transitions to do what they want to do. Each of these transitions corresponds to a physical process. Users cannot applying States individually, only Transitions.

def FeelingBlue(A, B):
    '''
    A and B must not be Green.
        (Assume this is somehow enforced and this transition isn't available
        to the user if either is green.)
    '''
    Blue(A)
    Blue(B)
    BlueConnection(A,B)

EDIT: To clarify, I will be writing all the transitions. Hence, I'm not trying to solve my problems for all possible transitions, I just want an algorithm that will find 'bad' transitions and tell me to remove them.

What I Want to Do

I want a nice way to do the following (in Python, I'm not worried about a GUI for now):

1. Applying a State to some Node(s)
   • If this would make the configuration invalid because some old states are incompatible with the new state, those old states should be removed
2. Removing a State from some Node(s)
   • If this would make the configuration invalid because some states are incompatible with the new state, those old states should be removed
3. Each Transition should only have one valid output
   • What I don't want is a situation where multiple different removals could all lead to acceptable, but different, States being assigned to the nodes.

My Problems

I'm not sure whether it's possible to guarantee condition 3. The main issue I see is that one removal could lead to another, which could lead to another, which could lead to another. It seems like this has the potential to lead to situations where the order in which I resolve these removals could lead to different results.

As a possible alternative, I've also considered making it so that States can't be removed if an existing State requires it. That would mean I'd have to watch out for dependency cycles. How would I manage those cycles and ensure that no combination of transitions could lead to such a cycle?

This whole thing feels a bit like a graph theory problem that someone smarter than me has probably already written a paper about, but the closest thing I can find is dependency graphs.

EDIT: Hans-Martin Mosner has shown how fulfilling 3 is impossible if there is a requirement of the form 'choose 2 of 3'. If we were to restrict ourselves to requirements where ALL requirements must be met (no using 'choose x of y') and ALL incompatibilities must be avoided, would it be possible to fulfill condition 3?

Answer 1

Here's a simple concrete "real-life" example for a state conflict ambiguity not even involving multiple objects:

A Project can be in states Good, Cheap, and Fast. Any two are allowed together, but not all three.

Now you have ProjectA that's Good and Cheap. User wants to set state Fast which would violate the constraint.

An algorithm could choose one of these conflict resolutions:

• remove state Good
• remove state Cheap
• remove both states

The third option would be unambiguous but destroys most previously asserted information.

If you prefer one of the first resolutions, you need criteria to select which state should be removed. A very simple method would be to put the states in a list, appending only at the end so that older states are before younger states. After adding one or more new states, you enumerate the list and remove all states that are in conflict. Note that you need to be careful because you're removing elements while enumerating.

This naive algorithm has a complexity of $O(n^2)$ if I'm not mistaken. It's probably possible to find a better way of implementing its effect.