[Tutor] "Path tree"

[Peter Otten]

Martin A. Brown wrote:

> The image:
> 
>> http://imgur.com/a/CwA2G
> 
> To me, this looks like a 'graph', which is a more general data
> structure -- it does not look like a 'tree' (in the computer-science
> meaning of the term, anyway).

> import networkx as nx

While Martin's solution is certainly more robust it may also be instructive 
to see it done "by hand":

edges = [
    (1, 2),
    (2, 5),
    (2, 3),
    (3, 4),
    (5, 7),
    (5, 6),
    (6, 8),
# remove the comment to see what happens 
# when there is more than one path between two nodes
#    (1, 8), 
]

graph = {}

# make a lookup table node --> neighbours
for a, b in edges:
    graph.setdefault(a, []).append(b)
    graph.setdefault(b, []).append(a)
print(graph)

def connect(start, end, path, graph):
    path += (start,)
    if start == end:
        # we found a connection
        yield path
    neighbours = graph[start]

    # try all neighbours, but avoid cycles to nodes already in the path
    for node in neighbours:
        if node not in path:
            # recurse to find connection from neigbour to end
            yield from connect(node, end, path, graph)

for path in connect(4, 8, (), graph):
    print(path)