-1

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?

  • 1 & 2 are trivial, since state changes only affect the direct connections of a node (which simply need to be removed when a node gets a non-corresponding color, no graph traversal required). But for 3, if that condition will be fulfilled depends simply on the specific transitions allowed and has nothing to do how you are going to implement it. I am under the impression this is an attempt to not tell us too much about the real problem (maybe because its confidental), but by doing so, the real requirements were not properly transformed into this quite abstract description... – Doc Brown May 13 at 6:14
  • 1
    ... which makes this a form of an XY problem. I recommend to consider if you can give us a description which is nearer to the problem you really want to solve. – Doc Brown May 13 at 6:16
  • @DocBrown Thanks for the feedback; unfortunately there's some confidentiality involved. I tried to add some more details and a more concrete example. Please let me know if I'm still being unclear. – Qudit May 13 at 6:36
0

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.

| improve this answer | |
  • Thanks for the example. As an addendum, would it be possible to fulfill condition 3 if I didn't include any requirements/incompatibilities of the form 'choose x of y'? I think in this scenario it might be the fact we can have (Good, Cheap) OR (Cheap,Fast) OR (Good, Fast) that causes the issue. If we restrict those "OR"s then is this solvable? – Qudit May 13 at 6:39
  • It's only possible to answer this when you have a complete list of states and their cross-incompatibilities. As long as your language remains vague, you can't expect precise answers. – Hans-Martin Mosner May 13 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.