Breadth-first search

The purpose of this assignment is to get you comfortable working with graph structures and to implement a breadth-first search function to traverse the graph and find the shortest path between nodes.

In search/graph.py:

• Define the function bfs that takes in a graph, start node, and optional node and:
  • If no end node is provided, returns a list of nodes in order of breadth-first search traversal from the given start node
  • If an end node is provided and a path exists, returns a list of nodes in order of the shortest path to the end node
  • If an end node is provided and a path does not exist, returns None
• Be sure that your code can handle possible edge cases, e.g.:
  • running bfs traversal on an empty graph
  • running bfs traversal on an unconnected graph
  • running bfs from a start node that does not exist in the graph
  • running bfs search for an end node that does not exist in the graph
  • any other edge cases you can think of

In test/test_bfs.py:

• Write unit tests for breadth-first traversal and breadth-first search
• You may use the two networks provided in the data folder or create your own for testing
• Test at least 2 possible edge cases (listed above)
• Include a test case that fails and raises an exception

Breadth First Search (BFS) is a graph search method that traverses nodes on a graph given a start node in a "layer first" fashion. This method of traversal allows for shortest path determination (in conjugation with dijkstra algorithm). Here, I wrote an implementation of both BFS and shortest path search using NetworkX package.