python dict key order based on values - recursive solution

Question

(In python 3.6) How do I output a list of the dictionary keys in which the order of the list is based on the dictionary value dependencies? For example, if I have a dictionary of software programs with values that indicate other programs upon which it is dependent:

packages = { 'B7': ['R3'], 
             'R3': ['timestmp', 'Abbot', '9K'],
             'tempor': ['cavie', 'sandals', 'B7'],
             'Abbot': ['Duns'],
             'timestmp': [],
             'Duns': [] }

I would return a list with each item ordered based on the programs necessary to install. So I would install 'timestmp' before 'R3'.

>>> get_download_order(packages)
['timestmp', 'Duns', 'Abbot', '9K', 'R3', 'B7', 'cavie', 'sandals', 'tempor']

# The list doesn't have to result in this exact order 
# as long as the download order of packages will work.

For a non-recursive solution, I was thinking of doing a tree with children, and identify the parent, then you could traverse the tree. But apparently, there is a recursive solution, and I cannot figure it out.

Dani Mesejo · Answer 1 · 2018-09-20T21:07:22.343

Your problem is known as topological sort, from the Wikipedia:

In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

In your particular case the vertex of the graph are the packages and the edges are the dependencies. You can solve the problem using Kahn's algorithm (no recursion), an implementation below:

def toposort(graph):
    # init the indegree for each noe
    nodes = graph.keys() | set([node for adjacents in graph.values() for node in adjacents])
    in_degree = {node: 0 for node in nodes}

    # compute the indegree
    for k, adjacents in graph.items():
        for node in adjacents:
            in_degree[node] += 1

    # init the heap with the nodes with indegree 0 and priority given by key
    heap = [node for node, degree in in_degree.items() if degree == 0]

    top_order = []
    while heap:  # heap is not empty
        node = heap.pop()  # get the element with highest priority and remove from heap
        top_order.append(node)  # add to topological order
        for adjacent in graph.get(node, []):  # iter over the neighbors of the node
            in_degree[adjacent] -= 1
            if in_degree[adjacent] == 0:  # if the node has in_degree 0 add to the heap with priority given by key
                heap.append(adjacent)

    return top_order


packages = {'B7': ['R3'],
            'R3': ['timestmp', 'Abbot', '9K'],
            'tempor': ['cavie', 'sandals', 'B7'],
            'Abbot': ['Duns'],
            'timestmp': [],
            'Duns': []}

reverse = {}
for key, nodes in packages.items():
    for node in nodes:
        reverse.setdefault(node, []).append(key)


print(toposort(reverse))

Output

['timestmp', '9K', 'sandals', 'Duns', 'Abbot', 'R3', 'B7', 'cavie', 'tempor']

Note

For the proposed solution to work it needs the reversed graph, that is what the following lines do:

reverse = {}
for key, nodes in packages.items():
    for node in nodes:
        reverse.setdefault(node, []).append(key)

Also note that the order is not unique, for instance in your example both 'timestmp' and 'Duns' could be the first package to install, given that they don't have any dependencies.

Further

A discussion of Kanh's algorithm along with implementations: topological sorting.
A recursive solution can be done using (a recursive) Depth-First Search (DFS) to solve the topological sort, you can find a good discussion of a recursive DFS here.
For using DFS for solving Topological sorting see this.

This solution fails if there are no dependencies, as you can verify by setting `packages = {"B7": [], "R3": []}` (it returns an empty list). — Sten L, May 11 '19 at 14:50

Sten L · Answer 2 · 2019-05-11T15:32:57.627

Adapted from this answer:

from typing import List, Dict, Set

def topological_sort(graph: Dict[str, List[str]]) -> List[str]:
    result: List[str] = []
    seen: Set[str] = set()

    def recursive_helper(node: str) -> None:
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        if node not in result:
            result.append(node)

    for key in graph.keys():
        recursive_helper(key)
    return result


packages = {'B7': ['R3'],
            'R3': ['timestmp', 'Abbot', '9K'],
            'tempor': ['cavie', 'sandals', 'B7'],
            'Abbot': ['Duns'],
            'timestmp': [],
            'Duns': []}

print(topological_sort(packages))

Output

['timestmp', 'Duns', 'Abbot', '9K', 'R3', 'B7', 'cavie', 'sandals', 'tempor']

This also works without dependencies:

packages = {"B7": [], "R3": []}
print(topological_sort(packages))

Output

['B7', 'R3]

python dict key order based on values - recursive solution

2 Answers2

Output

Output