Bottom Page

• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 A generic breadth first traversal function Gribouillis Posts: 2,047 Threads: 18 Joined: Jan 2018 Reputation: 184 Likes received: 489 #1 Jul-07-2019, 06:51 AM (This post was last modified: Jul-07-2019, 06:51 AM by Gribouillis. Edited 7 times in total.) The function `breadth_first()` defined below generates the nodes of a directed graph in breadth first order. Repeated nodes are ignored: only the first occurrence is generated. ```from collections import deque from itertools import chain from more_itertools import unique_everseen __version__ = '2019.07.07.1' def consume(d, start, neighbors): yield (start,) while d: yield neighbors(d.popleft()) def breadth_first(start, neighbors): """Generates nodes of a directed graph in level order. Arguments: * start : an arbitrary initial element (any hashable object) * neighbors : a function such that neighbors(item) is a sequence of the item's neighbors in the graph. Returns: A sequence of nodes in level order. Duplicate nodes are ignored: only the first occurrence is generated. """ d = deque() for item in unique_everseen( chain.from_iterable(consume(d, start, neighbors))): yield item d.append(item) if __name__ == '__main__': D = { 1: [2, 3, 4], 2: [5, 6], 4: [7, 8], 5: [9, 10, 4], 7: [11, 12], } for x in breadth_first(1, lambda n: D.get(n, ())): print(x, end=' ') print() `````Output:1 2 3 4 5 6 7 8 9 10 11 12``Edit: A small improvement of version 2019.07.07 is to postpone the call to neighbors() as much as possible. Skaperen, rootVIII, snippsat And 1 others like this post perfringo Da Bishop Posts: 1,139 Threads: 5 Joined: Jun 2018 Reputation: 117 Likes received: 256 #2 Jul-11-2019, 12:54 PM Just for historical reference I add link to Guido van Rossum essay Python Patternsâ€”Implementing Graphs I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame. rootVIII Not Blown Up Yet Posts: 59 Threads: 24 Joined: Aug 2018 Reputation: 1 Likes received: 5 #3 Jul-12-2019, 12:26 AM ah more_itertools is pretty neat « Next Oldest | Next Newest »

Top Page

 Possibly Related Threads... Thread Author Replies Views Last Post general tree traversal cwilson1 2 1,227 Jun-19-2018, 03:46 PM Last Post: cwilson1

Forum Jump:

Users browsing this thread: 1 Guest(s)