Extracting order of client server from a dictionary using python

Question

I have a dictionary like below which for example, for the first item means 5 is the customer of 2. and in the last item, as you can see, 2 is the customer of 4 and 4 is also the customer of item 3.

customer_provider_dic= {'2':['5'],'1':['2'],'3':['4'],'4':['2']}

I am trying to extract all chains of customer of these items. The output will be like this:

[2,5]
[1,2,5]
[3,4,2,5]
[4,2,5]

I really confused how can I extracts these chains. Any suggestion for the flowchart or the steps I should follow.

Are you sure this is the correct output? Because `[2,5]` and `[3,4]` are clearly going from server to customer, but `[1,2,4,3]` is going the opposite direction, and `[4,2,1]` seems to be reversing direction in the middle. So, if that _is_ the right output, you're going to have to explain what "chain" means here, because it's not obvious. — abarnert, Jul 06 '18 at 00:07
You need to implement topological sort to get what you are looking for. — Anoop, Jul 06 '18 at 00:08
Why are the dict values lists? Will there ever be more than 1 item in those lists? — PM 2Ring, Jul 06 '18 at 00:16
@PM2Ring yes the value of lists could be more than one item. I will edit the title of my question too. Excuse me for my bad English. — Shahrooz Pooryousef, Jul 06 '18 at 00:22
Ok. In that case the solution is a bit more complex, since multiple list items means that there will be branching chains. BTW, the last line of your output `[4,2,3]` isn't correct. — PM 2Ring, Jul 06 '18 at 00:24
@PM2Ring yes it is a little complex. I am thinking about an algorithm for it since today morning until now:( but nothing. Can you please help me:) I really have confused! — Shahrooz Pooryousef, Jul 06 '18 at 00:36

PM 2Ring · Accepted Answer · 2018-07-06T03:11:42.097

First, here's a solution that works if all the lists contain exactly one item.

def simple_chain(graph, key):
    chain = [key]
    while True:
        lst = graph.get(key)
        if lst is None:
            # There's nothing left to add to the chain
            break
        key = lst[0]
        if key in chain:
            # We've found a loop
            break
        chain.append(key)
    return chain

customer_provider = {
    '2': ['5'], '1': ['2'], '3': ['4'], '4': ['2'],
}

data = customer_provider
for k in data:
    print(simple_chain(data, k))

output

['2', '5']
['1', '2', '5']
['3', '4', '2', '5']
['4', '2', '5']

The general solution is a little harder. We can create all the chains using a recursive generator. The code below works, but it's not very efficient, since it makes the same sub-chains multiple times.

The basic strategy is similar to the previous version, but we need to loop over all the keys in each list, and make a new chain for each one.

To fully understand how this code works you need to be familiar with recursion and with Python generators. You may also find this page helpful: Understanding Generators in Python; there are also various Python generators tutorials available online.

def make_chains(graph, key, chain):
    ''' Generate all chains in graph that start at key.
        Stop a chain when graph[key] doesn't exist, or if
        a loop is encountered.
    '''
    lst = graph.get(key)
    if lst is None:
        yield chain
        return
    for k in lst:
        if k in chain:
            # End this chain here because there's a loop
            yield chain
        else:
            # Add k to the end of this chain and
            # recurse to continue the chain
            yield from make_chains(graph, k, chain + [k])

customer_provider = {
    '2': ['5'], '1': ['2'], '3': ['4'], '4': ['2'],
}

pm_data = {
    '2': ['5'], '1': ['2'], '3': ['4', '6'], 
    '4': ['2'], '6': ['1', '5'],
}

#data = customer_provider
data = pm_data

for k in data:
    for chain in make_chains(data, k, [k]):
        print(chain)

If we run that code with data = customer_provider it produces the same output as the previous version. Here's the output when run with data = pm_data.

['2', '5']
['1', '2', '5']
['3', '4', '2', '5']
['3', '6', '1', '2', '5']
['3', '6', '5']
['4', '2', '5']
['6', '1', '2', '5']
['6', '5']

The yield from syntax is a Python 3 feature. To run this code on Python 2, change

yield from make_chains(graph, k, chain + [k])

to

for ch in make_chains(graph, k, chain + [k]):
    yield ch

Prior to Python 3.6 dict does not retain the insertion order of keys, so for k in data can loop over the keys of data in any order. The output lists will still be correct, though. You may wish to replace that loop with

for k in sorted(data):

to get the chains in order.

thank you for your answer. the simple_chain function is fine, I tried to use make_chains function, I am getting this error yield from make_chains(graph, k, chain + [k]) ^ SyntaxError: invalid syntax — Shahrooz Pooryousef, Jul 06 '18 at 02:52
@ShahroozPooryousef I guess you're still using Python 2, since `yield from` only works in Python 3. But it's very easy to adapt that code to Python 2, I'll update my answer in a few minutes. — PM 2Ring, Jul 06 '18 at 03:02

Extracting order of client server from a dictionary using python

1 Answers1