def get_frontier(graph, explored_vertices):
    """ Computes the edges on the frontier of a graph, given
    the already explored vertices, ie. the edges where the tail was explored
    and the head was not yet explored.

    Args:
        graph: data structure holding graph data.
        explored_vertices: a list of vertex names

    Returns:
        A list of tuples representing vertices (tail, head, value).
    """
    frontier = set()
    for vertex in explored_vertices:
        for other in graph.neighbours(vertex):
            if other not in explored_vertices:
                value = graph.get_edge_value((vertex, other))
                frontier.add((vertex, other, value))
    return frontier