Scaling Graph Algorithms to Large Graphs

MAX - FLOW (Ford-Fulkerson Edmonds-Karp Algorithm)

• Works for integral values of edge capacities
• Vertex numbering starts from 1
• Outputs max-flow value to terminal

Optimization

Maximum possible flow in each augmenting path found (Minimum of the edge capacitites in the path) is calculated during the path detection itself, instead of doing it after the path is returned. This does away with the traversal of the adjacency list multiple times (as many times as the length of the path) to get the capacities of each edge in the path.

• Input generated by running generator file (./generator-max_flow )
• Input file passed as command-line argument (./max_flow )
• Input format:
  First line : number_of_vertices(n) number_of_edges
  Next m lines : edge_from edge_to edge_capacitiy
  Last line : source_vertex sink_vertex

---

BIPARTITE MATCHING (Hopcraft-Karp Algorithm)

• Finds maximum matching in the graph and prints to terminal

• Vertex numbering starts from 1

• Edge weight is assumed to be 1 for each edge

• Input generated by running generator file (./generator-bipartite )

• Input file passed as command-line argument (./bipartite )

• Input format:
  First line : number_of_vertices_in_LHS(m) number_of_vertices_in_RHS(n) number_of_edges(e)
  Next e lines : edge_from edge_to