human
Complete this python program:
def is_same_graph(var1, var2, givens=None, debug=False):
assistant
#Here is the Python program you requested.

    """Return True iff Variables `var1` and `var2` perform the same computation.
    By \performing the same computation\, we mean that they must share the same
    graph, so that for instance this function will return False when comparing
    (x * (y * z)) with ((x * y) * z).
    The current implementation is not efficient since, when possible, it
    verifies equality by calling two different functions that are expected to
    return the same output. The goal is to verify this assumption, to
    eventually get rid of one of them in the future.
    Parameters
    var1
    The first Variable to compare.
    var2
    The second Variable to compare.
    givens
    Similar to the `givens` argument of `theano.function`, it can be used
    to perform substitutions in the computational graph of `var1` and
    `var2`. This argument is associated to neither `var1` nor `var2`:
    substitutions may affect both graphs if the substituted variable
    is present in both.
    debug : bool
    If True, then an exception is raised when we are in a situation where
    the `equal_computations` implementation cannot be called.
    This parameter is intended to be used in tests only, to make sure we
    properly test both implementations.
    Examples
    var1    var2    givens  output
    x + 1   x + 1   {}      True
    x + 1   y + 1   {}      False
    x + 1   y + 1   {x: y}  True
    """
    if (givens is None):
        givens = {}
    global equal_computations, is_same_graph_with_merge
    if (equal_computations is None):
        from theano.gof.opt import is_same_graph_with_merge
        from theano.scan_module.scan_utils import equal_computations
    if (not isinstance(givens, dict)):
        givens = dict(givens)
    rval1 = is_same_graph_with_merge(var1=var1, var2=var2, givens=givens)
    use_equal_computations = True
    if givens:
        ok = True
        in_xs = []
        in_ys = []
        inputs_var = list(map(inputs, ([var1], [var2])))
        all_vars = [set(variables(v_i, v_o)) for (v_i, v_o) in ((inputs_var[0], [var1]), (inputs_var[1], [var2]))]
        def in_var(x, k):
            return (x in all_vars[(k - 1)])
        for (to_replace, replace_by) in iteritems(givens):
            inside = dict(((v, [in_var(v, k) for k in (1, 2)]) for v in (to_replace, replace_by)))
            if (inside[to_replace][0] and (not inside[to_replace][1]) and inside[replace_by][1] and (not inside[replace_by][0])):
                in_xs.append(to_replace)
                in_ys.append(replace_by)
            elif (inside[to_replace][1] and (not inside[to_replace][0]) and inside[replace_by][0] and (not inside[replace_by][1])):
                in_xs.append(replace_by)
                in_ys.append(to_replace)
            else:
                ok = False
                break
        if (not ok):
            if debug:
                raise AssertionError('When    `debug`    is    True    we    want    to    make    sure    we    are    also    using    the    `equal_computations`    implementation')
            use_equal_computations = False
    else:
        in_xs = None
        in_ys = None
    if use_equal_computations:
        rval2 = equal_computations(xs=[var1], ys=[var2], in_xs=in_xs, in_ys=in_ys)
        assert (rval2 == rval1)
    return rval1