Gomory-Hu Tree

Muti-Terminal Network Flow problem can be solved trivially by doing $\binom{n}{2}$ flow computations. Gomory-Hu Tree reduces that to $n-1$ flow computations. Thus, improving Time Complexity by factor of $\mathcal{O(n)}$.

A Gomory-Hu Tree (1961) is an undirected, weighted tree on the vertices of a given graph such that each edge in the tree represents a minimum separating cut in the underlying graph with respect to its incident vertices.
Property:

1. Min-Cut between two vertices on the tree also corresponds to a Min-Cut between those vertices in the underlyng graph.
2. Min-Cut value between two vertices is equal cheapeast tree edge on the unique path between the vertices (Corollary to 1).

Dynamic Gomory-Hu Tree (Tanja Hartmann and Dorothea Wagner, 2013) aims to re-use previously computed cuts to prevent complete re-construction of the whole tree when an edge-weights changes in the underlying graph. This, further improves the Execution Time for a dynamic graph.

How to Run (Scripts)

• Use Ubuntu/Linux/WSL Terminal.
• Argument 1 is compulsory and path is relative to "Implementation/" directory.
• Paths to [brute.cpp] and [gen.cpp] are relative to "Implementation/Test/" directory.
• Default for [number_of_iterations = 100] [brute = brute.cpp] [gen = gen.cpp].
• Keep same input and output format for <code.cpp> [brute.cpp] and use that for Testcase generator.
• Benchmarks - ./bench.sh <code.cpp> [number_of_iterations] [brute.cpp] [gen.cpp]
  • Output is appended to "benchmark-<code>-<brute>-<gen>.csv".
  • If all iterations are done then Choose (y/n) for logarithmic plotting of that .csv file.
  • Use Plotter.py to plot (takes relative path to .csv file as input).
• Stress Test - ./bash.sh <code.cpp> [brute.cpp] [gen.cpp]
  • Any Testcase for which output of both codes is different is printed.
  • Ctrl+C to stop script.
    
    

Performance

Static Gomory-Hu Tree

Dynamic Gomory-Hu Tree

Single Update

Multiple Updates

Implementation

• My Report
• Static_GomoryHu_Tree.cpp Based on Very Simple Methods for All Pairs Network Flow Analysis (Website).
• Equivalent_Flow_Tree_gusfield.cpp Based on Very Simple Methods for All Pairs Network Flow Analysis (Website).
• Dynamic_GomoryHu_Tree.cpp Based on Dynamic Gomory-Hu Tree Construction -- fast and simple (Website).
  
  

Test Codes

• Dinic.cpp - Algorithm used to compute maxflow (treated as a blackbox).
• brute.cpp - Runs maxflow algorithm for each $\binom{n}{2}$ pairs of vertices.
• reusing_Static_GomoryHu_Tree.cpp - Reconstructs Gomory-Hu Tree from scratch for each edge update.
• gen.cpp - Generates Testcases (Random Graphs) for Static and SingleUpdate Dynamic Gomory-Hu Tree.
• Multiple Updates (MU):
  • Testing Dynamic Gomory-Hu Tree against Multiple Updates per Graph.
  • benchMU.sh - ./benchMU.sh [code.cpp] [number_of_iterations] [gen.cpp]
  • Dynamic_GomoryHu_Tree_MU.cpp - Prints the time requried for Each Update.
  • gen_MU.cpp - Generates Random Graph with Multiple Update Testcases.
  • PlotterMU.py - Plots mean %age of time required for each subsequent update w.r.t Initial Tree construction time.
    
• Example:
  
  
  

Application

Image Segmentation

How to Run:

• Go to UCRT64 terminal(or whichever compiler is being used) and install opencv using - pacman -S mingw-w64-ucrt-x86_64-opencv
• Add the following commands when calling the compiler - -std=c++20 -O3 -Wl,--stack,1073741824
• Add the following commands when calling the linker - -lopencv_core -lopencv_imgcodecs -lopencv_highgui -lopencv_imgproc
• Include the folder include/opencv4 in C++ includes.

Image segmentation is done based on an Unsupervised-Flow-based-Hierarchical-Clustering-Algorithm as mentioned in this paper.

The given code is an implementation of the algorithm mentioned in the above paper.

In the images folder are the segmented images produced after running the algorithm.

Image	Pixels	Execution Time (in sec)
basic3.png	$100 \times 100 = 10^4$	0
login.png	$170 \times 94 = 1.6 \times 10^4$	1
paint.png	$465 \times 287 = 1.3 \times 10^5$	32
paint1.png	$617 \times 317 = 2 \times 10^5$	267
paint2.png	$480 \times 331 = 1.6 \times 10^5$	175
sample2.png	$400 \times 788 = 3.1 \times 10^5$	109

NOTE: HyperParameters - sigma, cMAX, FACTOR, WINDOW affect both final clusters and Execution Time (Time required for Clustering), whereas MIN_SIZE (minimum no. of pixels that should be present in a cluster) affects only the final cluster.