Skip to content

Instantly share code, notes, and snippets.

@xZise
Created November 16, 2014 22:16
Show Gist options
  • Save xZise/43407277407c4aa33dd9 to your computer and use it in GitHub Desktop.
Save xZise/43407277407c4aa33dd9 to your computer and use it in GitHub Desktop.
BFS for iw prefix path
def interwiki_prefix_path(self, site, max_depth=2):
# all sites already checked
visited = set()
old_queue = [(self, [])]
new_queue = []
for depth in range(max_depth):
print('D{}'.format(depth))
print('Q{}'.format(old_queue))
for checked_site, path in old_queue:
print('-' * 30)
print('S{} P{}'.format(checked_site, path))
try:
prefix = checked_site.interwiki_prefix(site)
except KeyError:
for prefix, cached in checked_site._iw_sites.items():
print('P{} S{} L{}'.format(prefix, cached[0], cached[1]))
if cached[1] and cached[0] not in visited:
old_queue += [(cached[0], path + [prefix])]
visited.add(cached[0])
else:
return path + [prefix]
old_queue.sort(key=lambda e: 0 if e[0].family != self.family else 1)
old_queue, new_queue = new_queue, []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment