with the following new elements:

      - Tuple (col, color) with column and color index for the current node

      - A list of tuples indicating the edges between the current node and its

        parents.

    """

    row = []

    colors = {}

    newcolor = 1

    for (rev, dagparents) in dag:

        # Compute row and nextrow

        if rev not in row:

            row.append(rev)  # new head

            colors[rev] = newcolor

            newcolor += 1

        col = row.index(rev)

        addparents = [p for p in dagparents if p not in row]

        # Add unknown parents to nextrow

        tmprow = row[:]

        # Stop looking for non-existing ancestors

        nextrow = []

        for r in tmprow:

            if r > nullrev or r in dagparents:

                nextrow.append(r)

        # Set colors for the parents

        color = colors.pop(rev)

        for i, p in enumerate(addparents):

            if not i:

                colors[p] = color

            else:

                colors[p] = newcolor

                newcolor += 1

        # Add edges to the graph

        edges = []

        for ecol, ep in enumerate(row):

            if ep in nextrow:

                edges.append((ecol, nextrow.index(ep), colors[ep]))

            elif ep == rev:

                for p in dagparents:

                    edges.append((ecol, nextrow.index(p), colors[p] if len(dagparents) > 1 else color))