import random


def weighted_maximum_cut(g):
    """ Weighted version of maximum cut problem solution using local search.
    Each edge has a weight, we need to find the cut which maximizes the total
    sum of the edges crossed by the cut.

    Complexity: O(exp(n))

    Params:
        g: object, instance of src.graph.Graph, represents an undirected
            weighted graph.

    Returns
        tuple, format (left_vertex_set, right_vertex_set)
            left_vertex_set: list, of vertices composing the left side of the cut.
            right_vertex_set: list, of vertices composing the right side of the cut.
    """
    # 1. Randomly pick a point where to split the set into two lists.
    vertices = g.get_vertices()
    split_point = random.randint(0, len(vertices)-1)
    left = vertices[:split_point]
    right = vertices[split_point:]

    # 2. Start searching for a better solution using local search.
    while True:
        possible_switches = []
        for v in vertices:
            # Cost of edges incident on v that _don't_ cross the cut (A,B)
            cost_dv = 0
            # Cost of edges incident on v that _do_ cross the cut (A, B)
            cost_cv = 0

            v_in_left = v in left
            for i in g.incident(v):
                i_in_left = i in left
                if i_in_left and v_in_left:
                    cost_dv += g.get_edge_value((v, i))
                elif i_in_left and not v_in_left:
                    cost_cv += g.get_edge_value((v, i))
                elif not i_in_left and v_in_left:
                    cost_cv += g.get_edge_value((v, i))
                elif not i_in_left and not v_in_left:
                    cost_dv += g.get_edge_value((v, i))
            if cost_dv > cost_cv:
                possible_switches.append(v)
        if len(possible_switches) == 0:
            break
        else:
            # The reason whey we pick a candidate v at random and not the v
            # that maximizes Cv and Dv is to avoid local optimum.
            v = random.choice(possible_switches)
            if v in left:
                left.remove(v)
                right.append(v)
            else:
                right.remove(v)
                left.append(v)

    return (left, right)