[Tutor] "Path tree"
Peter Otten
__peter__ at web.de
Tue Aug 15 03:56:44 EDT 2017
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)
More information about the Tutor
mailing list