how to sort a list of dependencies

Question

Is there any pythonic way to sort a unordered list of links into a dependency-sorted list?

Given the following unordered_linked_list:

unordered_linked_list = [
    {id: "DE3", pred: "FE8"}, 
    {id: "FE8", pred: None}, 
    {id: "79E", pred: "DE3"}, 
    {id: "52D", pred: "79E"},
    ...
]

Which should result in

ordered_list = ["FE8", "DE3", "79E", "52D"]

Do you want something like `sorted([d['id'] for d in unordered_linked_list])` (which would be `[0, 1, 2, 3]`)? — jonrsharpe, Aug 18 '15 at 15:11
bad example indeed. The id should be string. I updated the question — sonix, Aug 18 '15 at 15:17

yurib · Accepted Answer · 2015-08-18T19:03:04.547

in general, sorting dependencies is done with topological sort. however, this specific case is simple enough (exactly one incoming and outgoing edge for each item) that full topological sort isn't required.

instead of a linked list, what you have is a list of links. so just restructure it in to something that resembles a linked list and traverse it:

# transform into a source:target dictionary
links = {d['pred'] if d['pred'] else 'root':d['id'] for d in unordered_linked_list}

# follow links and print
source = 'root'
while source in links:
    print links[source]
    source = links[source]

score 1 · Answer 2 · answered Aug 18 '15 at 15:34

Try this:

unordered_linked_list = [
    {'id': "DE3", 'pred': "FE8"}, 
    {'id': "FE8", 'pred': None}, 
    {'id': "79E", 'pred': "DE3"}, 
    {'id': "52D", 'pred': "79E"},
]

def traverse(links):
    preds = dict()
    for item in links:
        preds[item['pred']] = item['id']
    item = None
    items = []
    while item in preds:
        item = preds[item]
        items.append(item)
    return items

>>> traverse(unordered_linked_list)
['FE8', 'DE3', '79E', '52D']

thanks that solution also works! – sonix Aug 20 '15 at 07:13 — sonix, Aug 20 '15 at 07:13

how to sort a list of dependencies

2 Answers2