Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Solving Decanting Problems by Graph Theory

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

Classic decanting problems present some jugs with water and ask for a method to get from one state to another by pouring water from one jug to another. There is no source or sink; all water must remain in the system.

[more]

This Demonstration shows how graph theory can solve the problem; it focuses on the case of three jugs with decreasing integer capacities , , , where each jug in the initial and final states has an integer volume of water. A legal pour is one that empties the source jug or fills the target. Selecting the "hardest case" box causes the start and finish to correspond to a path that is the longest for the particular capacities selected. The total water in the initial state of the three jugs must be set, as that defines the graph. You set the initial and final states by moving the purple and yellow disks, respectively. The final position is always moved to the nearest reachable state; those states are shown by large red or green disks. The smaller red and green disks and the small blue disks are states that are unreachable from the initial state.

The graphic shows a graph that represents the states, with the shortest path from the initial to final state given as a sequence of arrows.

[less]

Contributed by: Stan Wagon (March 2015)
Macalester College
Open content licensed under CC BY-NC-SA

Snapshots

Details

By viewing the possible states as vertices in a graph, with directed edges for legal moves from state to state, the decanting problem is simply that of finding a path (better, the shortest path) from the initial state to the final. Note that any edge must go to a state that has at least one jug that is empty or full.

Barycentric coordinates (also called trilinear coordinates) allow the states to be viewed as discrete points in an equilateral triangle. Edges in the graph can travel in three directions parallel to the sides of the triangle, and must always travel to the end of the line chosen. In this representation, states on the triangle's boundary (red) have at least one empty jug; states on the boundary of the polygon containing the graph, but not on the triangle's boundary, are states with at least one full jug and no empty jug (these are green); and states in the interior of the polygon are states with neither an empty nor a full jug. The smaller blue vertices are not reachable from the start position.

Snapshot 1: The interesting case of . The hardest problem here is to go from to .

Snapshot 2: The case of and passage from to . In this example, some boundary points are unreachable from .

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send