A Gomory-Hu tree serves as a condensed depiction of the minimum cut values between each pair of nodes within an undirected graph. This tree proves to be highly effective in resolving network flow, min-cut, and connectivity-related challenges. Within the Gomory-Hu tree, every edge signifies a minimum cut separating two nodes in the initial graph. Navigating this tree allows for the straightforward identification of the minimum cut between any pair of vertices.
Applications of Gomory-Hu
- Network Flow Problem: Finding a bottleneck in flow networks .
- Graph Partitioning: Optimal ways to partition graphs for being processed in parallel.
- Clustering: Clustering algorithms are used to group a set of data points into clusters, where the distance in-between-points-to-point concerns structure.
Gomory-Hu Tree Explained
Definition and Properties
A split between two nodes in a graph is defined by the minimal set of edges that, when removed, disconnect the two nodes. The cost associated with this disconnection is determined by the total weight of the edges within this specific set, indicating the minimum weight needed to isolate the two nodes effectively.
Gomory-Hu Tree Structure:
- Gomory- Hu Tree T is A tree with n leaves where each leaf nodes corresponds to a vertex in G.
- Each edge in TT corresponds to a minimum cut value that separates the two sets of vertices represented by leaves from sub-trees starting at each end of such an edge.
- The weight of an edge (u,v)(u, v) in the Gomory-Hu tree indicates at least cut capacity between vertices corresponding with leaves from two subtrees rooted within uu and vv.
Algorithm for construction
The Gomory-Hu tree is constructed using the following steps:
- Initial setup: Start with an undirected graph, GG, and arbitrary selection of a vertex r as the root of the Gomory-Hu tree.
- Maximum flow computation: For every vertex in GG (except r): From rr to vvRun a flow algorithm, like Edmonds-Karp, to compute the maximum flow from r to v. After that, realize this maximum flow signifies the capacity of the minimum cut separating r from v.
- From rr to vvRun a flow algorithm, like Edmonds-Karp, to compute the maximum flow from r to v.
- After that, realize this maximum flow signifies the capacity of the minimum cut separating r from v.
- For each pair (r,v), add an edge to the Gomory-Hu tree, which is weighted by the computed minimum cut.
- Repeat the same for subgraphs defined by the minimum cuts recursively until all vertices are included.
Tree construction:
Applications:
The major applications of the Gomory-Hu tree can be illustrated as follows:
- Network design: In telecommunications and computer networks, Gomory-Hu trees allow designers to recognize specific connections and optimize the reliability of the network.
- Image segmentation: The Gomory-Hu tree enables the further segmentation of an image by calculating the weakest separability of the image into distinct regions or sectors.
- Clustering algorithms: The Structure of the Gomory-Hu tree can aid in the derivation of hierarchical clustering, with clusters corresponding to the minimum cuts that separate those groups of data points.
- Robustness analysis: In reliability engineering, a Gomory-Hu tree can assist in the robustness analysis of networks and systems against failures by evaluating minimum cuts.
Example:
//Program to implement the Gomory-Hu Tree Construction in C++
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <queue>
using namespace std;
class Gomory_Hu_Tree {
public:
Gomory_Hu_Tree(int num) : num(num), parent(num), minimumCut(num, vector<int>(num, 0)) {}
void addEdge(int u1, int v1, int value) {
adjacent[u1].emplace_back(v1, value);
adjacent[v1].emplace_back(u1, value);
}
void build_Method() {
for (int i = 1; i < num; ++i) {
int cut = minCutValue(0, i);
parent[i] = cut;
// The tree is updated with new cut value.
updateMinCuts(0, i, cut);
}
}
void printTree_values() {
for (int i = 1; i < num; ++i) {
cout << "The Edge from " << parent[i] << " to " << i << " having cut value is " << minimumCut[0][i] << endl;
}
}
private:
int num;
vector<vector<pair<int, int>>> adjacent = vector<vector<pair<int, int>>>(100);
vector<int> parent;
vector<vector<int>> minimumCut;
int minCutValue(int src, int dest) {
//The max flow
vector<int> parent(num, -1);
vector<int> value(num, 0);
value[src] = numeric_limits<int>::max();
queue<int> que;
que.push(src);
while (!que.empty()) {
int u1= que.front();
que.pop();
for (auto& edges : adjacent[u1]) {
int v1 = edges.first;
int cap = edges.second;
if (parent[v1] == -1 && cap > 0) {
parent[v1] = u1;
value[v1] = min(value[u1], cap);
if (v1== dest) {
return value[v1];
}
que.push(v1);
}
}
}
return 0;
}
void updateMinCuts(int src, int dest, int cval) {
minimumCut[src][dest] = cval;
// Updating Graph Structure
}
};
int main() {
int number= 5; // declaring the number of veritices
Gomory_Hu_Tree tree(number);
// Adding edges (u, v, val)
tree.addEdge(0, 1, 15);
tree.addEdge(0, 7, 5);
tree.addEdge(1, 2, 15);
tree.addEdge(1, 4, 9);
tree.addEdge(2, 4, 10);
tree.addEdge(3, 2, 5);
tree.build_Method();
tree.printTree_values();
return 0;
}
Output:
The Edge from 15 to 1 having cut value is 15
The Edge from 15 to 2 having cut value is 15
The Edge from 5 to 3 having cut value is 5
The Edge from 9 to 4 having cut value is 9
Explanation:
Data members:
- Number: Number of vertices in the graph.
- Parent: A vector that stores the parent nodes for each vertex in the tree .
- MinimumCut: A 2D vector to store the minimum cut values between pairs of vertices.
- Adjacent: Adjacency list representation of the graph where each vertex points to a list of pairs (neighbor, capacity).
- Constructor: It initializes the number of vertices and setup the parent and minimumCut structures.
- Methods: addEdge(int u1, int v1, int value):
- Adds a bidirectional edge with a capacity from vertex u1 to vertex v1.
- build_Method: It builds the Gomory-Hu tree. The algorithm finds the minimum cut values between a root node (which will be vertex 0) and all other vertices and in each iteration, updates the tree structure.
- printTree_values: Outputs the edges of the Gomory-Hu tree and their corresponding cut values.
- minCutValue(int src, int dest): It calculates the minimum cut value from source src to sink dest, using BFS for maximum flow.
- updateMinCuts(int src, int dest, int cval): Updates the minimumCut matrix with the cut value found.
- Adding Edges: The addEdge creates a two-way link between two vertices supplied with fixed capacity which makes it easy do build the graph on-the-fly.
- Building the Tree: The build_Method computes minimum cuts for each vertex against the root. It modifies the parent relationships and minimum cut values in the tree.
- Finding Minimum Cut: The minCutValue implementation uses a BFS to find the max-flow from src to dest, which is defined by the edges' capacities. The minCutValue function returns the min-cut value-the maximum flow from the source to the destination.
- Updating Minimum Cuts: The updateMinCuts will update the minimum cuts stored in the minimumCut matrix for a given source and destination.
- Initialization: It creates a GomoryHuTree instance with five vertices.
- Adding Edges: Adding multiple edges of specific capacities to the graph.
- Building the Tree: Calling build_Method to build a Gomory-Hu tree based on the edges added.
- Printing the Tree: Prints out the results, indicating the edges in the Gomory-Hu tree and their cut values.
The Main Methods:
Main function:
Conclusion:
Here is a basic C++ code snippet designed to generate the Gomory-Hu Tree, which serves as an effective method for identifying all minimum cuts between vertex pairs within any connected and undirected graph. The code defines a class that encapsulates essential attributes such as the number of vertices, a parent vector for tree structure, a matrix for storing minimum cut values, and a graph represented as an adjacency list. Key functionalities might involve functions for adding edges with capacities, which facilitate the construction of the Gomory-Hu tree by computing minimum cut values through Breadth-First Search (BFS) and displaying the edge along with its assigned weight in the cuts forest.
In a sequential manner, the software builds a tree containing five nodes, establishes connections between them, and showcases the resulting tree. The tree's visualization is presented in a single line, following principles of graph theory.
