DAdaveFNbuck·Aug 8, 2017
Check the bfs code at https://github.com/OmkarPathak/pygorithm/blob/b7a5c1cda3b945...:
# breadth first search algorithm
def search(graph, startVertex):
# Take a list for stoting already visited vertexes
if startVertex not in graph or graph[startVertex] is None or graph[startVertex] == []:
return None
# create a list to store all the vertexes for BFS and a set to store the visited vertices
visited, queue = set(), [startVertex]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
It returns None if there is a bad input or if the start node is a leaf. That's very weird, as None would seem to indicate an error but searching from a leaf
Read the rest
is not normally an error. You should return a set just containing the start vertex if you start on a leaf. This doesn't need to be a special case.
The initial guard also checks whether graph[startNode] is None, but this is never checked when looking up other nodes in the graph. Whether you check this should be consistent.
The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. This makes the bfs implementation have quadratic worst-case complexity rather than the linear complexity it should have. The Python standard library has a deque class that can be used to fix this, and it would be more instructive and more correct to use that. This also means the time complexity function is wrong.
So 2 clear bugs and 1 weird and probably unnecessary check in the bfs implementation. Also, the implementation has no comments to explain how it works, why it has the time complexity it does, or how you might tweak it to accomplish different goals.
I don't see how someone who didn't already know BFS could learn from this. There's nothing here that teaches the algorithm, and the implementation is weirdly flawed.
On top of all this, the package claims to teach all major algorithms but only contains a handful of sorting and searching algorithms. It doesn't even have a UI to help people discover and learn about the algorithms it does teach. You just have to know which ones are there and import them, then run a bunch of commands to print out the source code. This UI is worse than just browsing the source on GitHub, and that's much worse than just looking the algorithms up on Wikipedia or reading a textbook.
I really don't get why someone would share this on HN in its current state. It looks like what you'd throw together for sample data before you started working on your algorithm teaching package.