1

I've been struggling with finding a solution to what seems to be a relatively simple problem.

Given a graph g:

g = {'A': ['B', 'C'],
     'B': ['A', 'C'],
     'C': ['D'],
     'D': [],
     }

One can find all paths using this solution (which I found here):

def paths(graph, v):
    path = [v]                  # path traversed so far
    seen = {v}                  # set of vertices in path
    def search():
        dead_end = True
        for neighbour in graph[path[-1]]:
            if neighbour not in seen:
                dead_end = False
                seen.add(neighbour)
                path.append(neighbour)
                yield from search()
                path.pop()
                seen.remove(neighbour)
        if dead_end:
            yield list(path)
    yield from search()

paths(g,'A')

>>  [['A', 'B', 'C', 'D'], ['A', 'C', 'D']]

To make matters more complex, I would like to find all paths in g but when the lists become nested. For example, take g to be

g2 = {'A': [['B', 'C'],['D']],
     'B': [['A'], ['C']],
     'C': [['D']],
     'D': [[]]}

The solution I am looking for would be 

[ [['A', 'B', 'C', 'D'], ['A', 'C', 'D']], ['A', 'D'] ]

where the first two paths are grouped together (i. e., in total I want to get two paths). However the above function is not sufficient. I have tried adapting this code to my problem but I have not been successful.

The actual graphs I am working with are quite a bit larger and many of the elements in the dictionary are these nested lists, so the number of paths may grow rather large rather quickly.

I hope this example makes sense. Any help would be greatly appreciated.

Community
  • 1
  • 1
chewbaccabacca
  • 11
  • 2
  • 1
    Is there any reason not to just flatten the lists? would `{'A': ['B', 'C', 'D']}` give the desired result in your example? If not, how does it differ. – TemporalWolf Mar 28 '17 at 16:42

1 Answers1

0
>>> {key:[ele for lst in value for ele in lst] for key, value in g2.iteritems()}
{'A': ['B', 'C', 'D'], 'C': ['D'], 'B': ['A', 'C'], 'D': []}

It appears to me that flattening the lists would solve your problem.

Or, without a dict & list comprehension:

result = {}
for key, value in g2.iteritems():
    result[key] = []
    for lst in value:
        for ele in lst:
            result[key].append(ele)

If you want to sort the result via the original graph g2:

# Sort by 2nd value in list
res = []
for lst in g2['A']:
    res.append([])
    for reslst in res:
        if reslst[1] in lst:
            res[-1].append(reslst)
    if len(res[-1]) == 0:
        res.pop()

[[['A', 'B', 'C', 'D'], ['A', 'C', 'D']], [['A', 'D']]]
Community
  • 1
  • 1
TemporalWolf
  • 7,727
  • 1
  • 30
  • 50