Add breadth first search for graphs

[czgdp1807]

Description of the problem

As graphs are now added to the master branch we can start adding graph algorithms. For a start we will move ahead with breadth first search(BFS). We look forward to add two versions of the algorithm,

1. Serial BFS: Standard BFS using FIFO queue. Open for anyone as it is pretty easy.
2. Parallel BFS: Much harder as there are various papers presenting different versions of implementation. We plan to use the following papers,
   i. http://supertech.csail.mit.edu/papers/pbfs.pdf (not used in the implementation)
   ii. https://people.eecs.berkeley.edu/~aydin/sc11_bfs.pdf (not used in the implementation)

Example of the problem

References/Other comments

[Impranjal]

hey ,can i work on this issue?

[czgdp1807]

Hi, You can work on the serial BFS. Feel free to start the work in a PR. May be we can create a new file, algorithms.py in graphs for all the graph related algorithms.

[Jain-Aditya]

Hi @czgdp1807 I would, like to work on this issue. The API would simply take adjacency list as input and will return the bfs as output, as far as I understand?

[czgdp1807]

Feel free to work on the serial version of BFS. Use the Queue of PyDataStructs in your implementation.

[czgdp1807]

IMO, BFS should be customized enough to perform some operations related to or on the Node we visit it. For example, if we want to check is there exists a path from the source node to the destination node then BFS should stop as soon as it encounters the destination node. Or may be just forming a BFS tree or storing the level of a node in the BFS tree.
The API can be,

breadth_first_search(source_node, operation, *args, **kwargs)

operation can be the name of another function which will be called inside breadth_first_search like, operation(curr_node, *args, *kwargs) whenever we will visit a node. It will help in customising the traversal according to the problem statement encountered by the end user. Any thoughts on this?
In addition we can fix the return values of the operation to either True or False. If it's the latter BFS will keep on running otherwise it should halt.

[czgdp1807]

This has given me the idea of adding n-ary trees as BFS is also the same kind. An issue can be opened for the same.

[czgdp1807]

breadth_first_search(source_node, operation, *args, **kwargs)

Something better would be,

breadth_first_search(graph, source_node, operation, *args, **kwargs)

Inside the above function we can call the following for different implementations of graphs,

getattr(module, "_breadth_first_search_" + implementation)(graph, source_node, operation, *args, **kwargs)

The above will allow doing the stuff without modifying the definition of breadth_first_search. Let me know of any improvements.
See, https://softwareengineering.stackexchange.com/questions/351389/dynamic-dispatch-from-a-string-python for more details of dynamic dispatch of functions.

[czgdp1807]

Below is the final API for BFS(both serial and parallel) which I have thought of,

Serial
breadth_first_search(graph, source_node, operation, *args, **kwargs) - It will just transfer the task to functions specific to graph implementation(minor changes are required in Graph for that purpose).
_breadth_first_search_adjacency_list(graph, source_node, operation, *args, **kwargs) - Performs serial breadth first search on adjacency list implementation of graphs.
_breadth_first_search_adjacency_matrix(graph, source_node, operation, *args, **kwargs) - Intuitive from above.

Parallel
breadth_first_search_parallel(graph, source_node, num_threads, operation, *args, **kwargs) - Transfer task to implementation specific functions. It will use a maximum of num_threads to do the computation parallely.
_breadth_first_search_parallel_adjacency_list(graph, source_node, num_threads, operation,*args, **kwargs) - Performs parallel breadth first search on adjacency list implementation of graphs.
_breadth_first_search_adjacency_matrix(graph, source_node, num_threads, operation, *args, **kwargs) - Intuitive from above.

operation is a function which is applied on every node. It should return True if the BFS is to be continued once the computation inside operation is done otherwise, False. The arguments to this function can be specified in args, kwargs. A call like operation(curr_node, *args, **kwargs) will be made when applying the function.

P.S. I will make a PR by tomorrow if no contributor is interested to implement the above APIs.