def contract(graph, edge):
    """ Composes a new vertex from the ends of the given edge.

    All the resulting self-loop edges are removed.

    Args:
        graph: a data structure containg all data and operations.
        edge: a tuple of format (tail, head, value)

    Returns:
        The graph after contracting value.
    """
    (tail, head, value) = graph.split_edge(edge)
    super_vertex = '{start}_{end}'.format(start=tail, end=head)

    # Remove individual vertices and add super-vertex.
    graph.rename_vertex(tail, super_vertex)
    graph.rename_vertex(head, super_vertex)

    return graph