'Liu\'s algorithm, for pre-determination of the Elimination Tree of
the given matrix, used in row-based symbolic Cholesky factorization.
Examples
>>> from sympy.matrices import SparseMatrix
>>> S = SparseMatrix([
... [1, 0, 3, 2],
... [0, 0, 1, 0],
... [4, 0, 0, 5],
... [0, 6, 7, 0]])
>>> S.liupc()
([[0], [], [0], [1, 2]], [4, 3, 4, 4])
References
Symbolic Sparse Cholesky Factorization using Elimination Trees,
Jeroen Van Grondelle (1999)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.7582'

def liupc(self):

    R = [[] for r in range(self.rows)]
    for (r, c, _) in self.row_list():
        if (c <= r):
            R[r].append(c)
    inf = len(R)
    parent = ([inf] * self.rows)
    virtual = ([inf] * self.rows)
    for r in range(self.rows):
        for c in R[r][:(-1)]:
            while (virtual[c] < r):
                t = virtual[c]
                virtual[c] = r
                c = t
            if (virtual[c] == inf):
                parent[c] = virtual[c] = r
    return (R, parent)
