Pushing Boxes, help me solve this graph problem!

52 Views Asked by At

Given a directed, acyclic graph with nodes representing boxes/objects at rest and edges that point to neighbouring boxes/objects in direct contact. Each node will be assigned a number that represents an external force exerted on the box/object. Positive forces will flow in edge direction and negative against edge direction, that is to say, boxes can only be pushed by another box, but not pulled. Forces are one-dimensional.

You can imagine that depending on the forces and how the boxes are connected, forces will add up or cancel out.

How can I find the resulting forces to determine which parts of the graph start moving, and which will remain at rest?

See drawing for illustration: https://i.stack.imgur.com/Snil4.jpg