CODEWITHSUNDEEP
pythonpython-3.xlistdictionary
asd
asd

Reputation: 183

How to Create paths by dictionary inputs through python (DAG)

I have a dict like this

dag_list= [{'sA': 'sB'}, {'sA': 'sC'}, {'sB': 'sD'}]

and I want the output something like below

sA -> sB -> sD -> sC
sA -> sC -> sB -> sD

what I have tried so far:

 for i in range(0,len(dag_list)):
            for j in range(i+1,len(dag_list)):
                for k in dag_list[j].keys():
                       if dag_list[i][k]==k:
                           print(dag_list[i],k)

Upvotes: 1

Views: 181

Answers (2)

Ajax1234
Ajax1234

Reputation: 71461

A slightly shorter recursive approach:

dag_list= [{'sA': 'sB'}, {'sA': 'sC'}, {'sB': 'sD'}]
dl = [j for k in dag_list for j in k.items()]
def paths(d, c = []):
   if not (k:=[b for a, b in dl if a == d]):
      yield c+[d]
   else:
      yield from [j for l in k for j in paths(l, c+[d])]

r = [j for k in {a for a, _ in dl if all(x != a for _, x in dl)} for j in paths(k)]

Output:

[['sA', 'sB', 'sD'], ['sA', 'sC']]

Upvotes: 1

LazyBum Q
LazyBum Q

Reputation: 255

Here's code, but to understand it you should know how recursions work:

dag_list= [{'sA': 'sB'}, {'sA': 'sC'}, {'sB': 'sD'}]
not_end_points = {list(pair)[0] for pair in dag_list}
dag_tree = {point: [
                    to 
                    for pair in dag_list 
                        for from_,to in pair.items() 
                            if from_ == point] 
            for point in not_end_points}
# {'sB': ['sD'], 'sA': ['sB', 'sC']}

def get_paths(start):                              
    res = []                                   
    ways = dag_tree[start]                         
    for way in ways:                           
        if way in dag_tree:                
            res.extend( [ f'{start} -> {this}'  for this in get_paths(way)] )      
        else:                              
            res.append(f'{start} -> {way}')
    return res
def print_paths(start):
    print(*get_paths(start), sep='\n')
    
print_paths('sA')
# sA -> sB -> sD
# sA -> sC

It's really hard to explain it here. Make sure your paths are not looped, like: sA -> sC -> sB -> sA -> sC -> sB -> sA -> sC..... You will get a RecursionError if it is.

Upvotes: 1

Related Questions