Pouring water between two jugs to get a certain amount in one of the jugs

I wrote a solution for a jug problem (given two jugs of water of different sizes find the steps needed to get specific amount of water in one of the jugs). I'm hoping for some input on my code. How can I make it better? More readable?

Optional - Is there a faster or more efficient solution I should look into?

```
#!/usr/bin/env python

import graph
import heapq

def build_gallon_graph(g, jug1, jug2, jug1_size, jug2_size):
"""Build a graph for solving a jug problem. Recursive function.

Arguments:
g -- graph.Graph() object.
jug1 -- Amount of water in a first jug.
jug2 -- Amount of water in a second jug.
jug1_size -- Size of the first jug.
jug2_size -- Size of the second jug.
"""
# Fill jug 1.
if jug1 0 and jug2 0 and jug1 0:
new_jug1, new_jug2 = 0, jug2
_add_connection(g, jug1, jug2, new_jug1, new_jug2,
jug1_size, jug2_size)

# Empty jug 2.
if jug2 > 0:
new_jug1, new_jug2 = jug1, 0
_add_connection(g, jug1, jug2, new_jug1, new_jug2,
jug1_size, jug2_size)

def _connection_exists(g, jug1, jug2, new_jug1, new_jug2):
if (new_jug1, new_jug2) not in g.vertices or (jug1, jug2) not in g.vertices:
return False
if g.vertices[(new_jug1, new_jug2)] in g.vertices[(jug1, jug2)].neighbors:
return True
if g.vertices[(jug1, jug2)] in g.vertices[(new_jug1, new_jug2)].neighbors:
return True
return False

def _add_connection(
g, jug1, jug2, new_jug1, new_jug2, jug1_size, jug2_size):
if not _connection_exists(g, jug1, jug2, new_jug1, new_jug2):
g.add_edge((jug1, jug2), (new_jug1, new_jug2))
build_gallon_graph(g, new_jug1, new_jug2, jug1_size, jug2_size)

def find_correct_order_of_actions(g, start, finish):
"""This is based on Dijkstra's shortest path alogirthm."""
g.vertices[start].distance = 0
queue = [(v.distance, v) for v in g.vertices.values()]
heapq.h

• Dijkstra's algorithm is an unnecessary complication when all the edges have the same cost. A simple breadth first search could be used instead.

• Building the graph in breadth first order would allow you to set the predecessors on the same pass. Then you would be able to answer different queries directly by following the predecessors from the final state, as long as the jug sizes and start state are the same. If you only need to answer a single query you could even stop building the graph as soon as you produce the target node.

-
This calculation

# Pour jug 1 to jug 2.
if jug1 > 0 and jug2 < jug2_size:
    new_jug1 = jug1 - jug2_size + jug2
    if new_jug1 < 0:
        new_jug1 = 0
    new_jug2 = jug2 + jug1 if jug1 + jug2 <= jug2_size else jug2_size

could be written in a simpler way:

# Pour jug 1 to jug 2.
measure = min(jug1, jug2_size - jug2)
if measure > 0:
    new_jug1 = jug1 - measure
    new_jug2 = jug2 + measure

-
In build_gallon_graph the same call to _add_connection repeats many times. One way to avoid that would be to refactor into a generator:

def transitions(jug1, jug2, jug1_size, jug2_size):

    # Fill jug 1.
    if jug1  0:
        yield jug1 - measure, new_jug2 = jug2 + measure

    # Pour jug 2 to jug 1.
    measure = min(jug1_size - jug1, jug2)
    if measure > 0:
        yield jug1 + measure, new_jug2 = jug2 - measure

    # Empty jug 1.
    if jug1 > 0:
        yield 0, jug2

    # Empty jug 2.
    if jug2 > 0:
        yield jug1, 0

def build_gallon_graph(g, jug1, jug2, jug1_size, jug2_size):
    for new_jug1, new_jug2 in transitions(jug1, jug2, jug1_size, jug2_size):
        _add_connection(g, jug1, jug2, new_jug1, new_jug2,
                        jug1_size, jug2_size)

StackExchange Code Review Q#78586, answer score: 5