Graph Algorithm Research Internship

During my internship under the guidance of Professor Rupesh Nasre from the Indian Institute of Technology, Madras, I had the opportunity to work on several graph algorithms. This experience enhanced my understanding of algorithmic theory and allowed me to translate concepts to Python concepts. I also did a time-complexity analysis of algorithms, helping me understand their efficiency and scalability.

Most datasets were sourced from Stanford-SNAP, a collection of large datasets, and the time module was used to measure the time taken for the algorithms to run.

Gale-Shapley Algorithm

Gale-Shapley Algorithm, also known as the Stable Matching Algorithm, is used to find a match between two sets without violating the stability criteria. Despite being quadratic, it is fairly efficient for medium-sized sets.

Dijkstra's Algorithm

Dijkstra's Algorithm is used for finding the shortest path between two nodes in a graph. It is widely used in network routing and pathfinding. I implemented the algorithm in Python, using a greedy approach to iteratively explore the node with the least distance.

Max-Flow Computation

The Ford-Fulkerson algorithm computes the maximum flow in a flow network by iteratively finding augmenting paths from the source node to the sink node and updating the residual capacities. This is done until no more augmenting paths are found (and the flow is maximised).

I implemented the algorithm using a Breadth First Search approach to find the shortest augmenting path.

My implementation had a time complexity of O(f * E), where f is the maximum flow and E is the number of edges in the graph.