def dictdict_to_listdict(dictgraph):
    """Transforms a dict-dict graph representation into a
    adjacency dictionary representation (list-dict)

    :param dictgraph: dictionary mapping vertices to dictionary
           such that dictgraph[u][v] is weight of arc (u,v)
    :complexity: linear
    :returns: tuple with graph (listdict), name_to_node (dict), node_to_name (list)
    """
    n = len(dictgraph)                            # vertices
    node_to_name = [name for name in dictgraph]   # bijection indices <-> names
    node_to_name.sort()                           # to make it more readable
    name_to_node = {}
    for i in range(n):
        name_to_node[node_to_name[i]] = i
    sparse = [{} for _ in range(n)]               # build sparse graph
    for u in dictgraph:
        for v in dictgraph[u]:
            sparse[name_to_node[u]][name_to_node[v]] = dictgraph[u][v]
    return sparse, name_to_node, node_to_name