import copy


def get_fillin_graph2(old_graph, peo):
    """
    Provided a graph and an order of its indices, returns a
    triangulation of that graph corresponding to the order.

    The algorithm is copied from
    "Simple Linear Time Algorithm To Test Chordality of Graph"
    by R. E. Tarjan and M. Yannakakis

    Parameters
    ----------
    old_graph : nx.Graph or nx.MultiGraph
                graph to triangulate
    peo : elimination order to use for triangulation

    Returns
    -------
    nx.Graph or nx.MultiGraph
                triangulated graph
    """
    # Ensure PEO is a list of ints
    peo = list(map(int, peo))
    peo_to_conseq = dict(zip(peo, range(len(peo))))

    number_of_nodes = len(peo)
    graph = copy.deepcopy(old_graph)

    # Safeguard check. May be removed for partial triangulation
    assert number_of_nodes == graph.number_of_nodes()

    index = [0 for ii in range(number_of_nodes)]
    f = [0 for ii in range(number_of_nodes)]

    for ii in range(number_of_nodes):
        w = peo[ii]
        idx_w = peo_to_conseq[w]
        f[idx_w] = w
        index[idx_w] = ii
        neighbors = list(graph[w])
        lower_neighbors = [v for v in neighbors
                           if peo.index(v) < ii]
        for v in lower_neighbors:
            x = v
            idx_x = peo_to_conseq[x]
            while index[idx_x] < ii:
                index[idx_x] = ii
                # Check that edge does not exist
                # Tensors added here may not correspond to cliques!
                # Their names are made incompatible with Tensorflow
                # to highlight it
                if (x, w) not in graph.edges(w):
                    tensor = {'name': 'C{}'.format(w),
                              'indices': (w, ) + tuple(neighbors),
                              'data_key': None}
                    graph.add_edge(
                        x, w,
                        tensor=tensor)
                x = f[idx_x]
                idx_x = peo_to_conseq[x]
            if f[idx_x] == x:
                f[idx_x] = w
    return graph