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):
- 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
- 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
- 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.
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?