Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
from collections import (
OrderedDict,
deque,
)
g = OrderedDict()
g["root"] = ["a", "b", "c"]
g["a"] = ["e","f","g"]
g["e"] = []
g["f"] = ["w"]
g["g"] = []
g["w"] = []
g["b"] = ["d"]
g["d"] = ["j"]
g["j"] = []
g["c"] = ["h", "i"]
g["h"] = ["x"]
g["i"] = []
g["x"] = []
# Reference post:
# https://www.educative.io/edpresso/how-to-implement-depth-first-search-in-python
# strategy recursion.
def flatten_graph2(node_id, graph):
"""
Given a node_id and graph (or tree),
return a list of every descendant node_id, depth first.
"""
flat_graph = []
def dfs(node, graph):
flat_graph.append(node)
for child in graph[node]:
dfs(child, graph)
dfs(node_id, graph)
return flat_graph
# Reference post:
# http://kmkeen.com/python-trees/2010-09-18-08-55-50-039.html
# strategy queue.
def flatten_graph(node_id, graph):
"""
Given a node_id and graph (or tree),
return a list of every descendant node_id, depth first.
"""
flat_graph = []
to_crawl = deque([node_id])
while to_crawl:
current_id = to_crawl.pop()
flat_graph.append(current_id)
children_ids = graph[current_id]
# reverse so that we extend the queue in the expected order.
children_ids.reverse()
to_crawl.extend(children_ids)
return flat_graph
flat_graph = flatten_graph2("root", g)
print(flat_graph)
flat_graph = flatten_graph("root", g)
print(flat_graph)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment