Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.8k
Add gomory-hu article#1308
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
base:main
Are you sure you want to change the base?
Uh oh!
There was an error while loading.Please reload this page.
Conversation
Visit the preview URL for this PR (for commitc278efa): https://cp-algorithms--preview-1308-w9guphnj.web.app (expires 2024-07-18T13:40:14.892553068Z) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Hi, thanks for the suggestion! Could you please address the comments in the review?
| ## Definition | ||
| The gomory-hu tree of an undirected graph $G$ with capacities consists of a weighted tree that condenses information from all the *s-t cuts* for all s-t vertex pairs in the graph. Naively, one must think that $O(|V|^2)$ flow computations are needed to build this data structure, but actually it can be shown that only $|V| - 1$ flow computations are needed. Once the tree is constructed, we can get the minimum cut between two vertices *s* and *t* by querying the minimum weight edge in the unique *s-t* path. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| Thegomory-hu tree of an undirected graph $G$ with capacitiesconsists ofa weighted tree thatcondenses information from all the*s-t cuts* for all s-t vertex pairs in thegraph. Naively, one must think that $O(|V|^2)$ flow computations are needed tobuild this data structure, but actually itcan be shown that only $|V| - 1$ flow computations are needed. Oncethe treeisconstructed, we can gettheminimum cut between two vertices*s* and*t* by querying the minimum weight edge in the unique*s-t* path. | |
| TheGomory–Hu tree of an undirected graph $G$ with capacitiesisa weighted treesuchthatfor any pair of vertices $s$ and $t$, the weight of theminimum edge on the path between $s$ and $t$ is equal tothe value of the minimum cut between $s$ and $t$. Itcan be shown that only $|V| - 1$ flow computations are needed to constructthe tree, whichisan improvement overthenaive $O(|V|^2)$ algorithm of finding maximum flow between each pair of vertices. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Generally, it would be nice to explain why this tree is well-defined (e.g. why it always exists), if possible.
| We can say that two cuts $(X, Y)$ and $(U, V)$ *cross* if all four set intersections $X \cap U$, $X \cap V$, $Y \cap U$, $Y \cap V$ are nonempty. Most of the work of the original gomory-hu method is involved in maintaining the noncrossing condition. The following simpler, yet efficient method, proposed by Gusfield uses crossing cuts to produce equivalent flow trees. | ||
| Lets assume the vertices are 0-indexed for the next section | ||
| The algorithm is composed of the following steps: | ||
| 1. Create a (star) tree $T'$ on $n$ nodes, with node 0 at the center and nodes 1 through $n - 1$ at the leaves. | ||
| 2. For $i$ from 1 to $n - 1$ do steps 3 and 4 | ||
| 3. Compute the minimum cut $(X, Y)$ in $G$ between (leaf) node $i$ and its (unique) neighbor $t$ in $T'$. Label the edge $(i, t)$ in $T'$ with the capacity of the $(X, Y)$ cut. | ||
| 4. For every node $j$ larger than $i$, if $j$ is a neighbor of $t$ and $j$ is on the $i$ side of $(X, Y)$, then modify $T'$ by disconnecting $j$ from $t$ and connecting $j$ to $i$. Note that each node $j$ larger than $i$ remains a leaf in $T'$ | ||
| It is easy to see that at every iteration, node $i$ and all nodes larger than $i$ are leaves in $T'$, as required by the algorithm. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
The way it is written now, it's very hard to seewhy the algorithm works this way. For example, crossing cuts are defined, but it is not explained why it is a property of interest that can be useful and helpful. It's not even clear how (non-)crossing curs are connected with the algorithm itself.
I assume the algorithm strives to maintain some kind of invariant that intermediate states provide a correct upper bound on the cut between any pair of vertices, and the bound is tight when the vertex is "finalised", but I don't see any natural explanation to why it's actually true?
| ## Complexity | ||
| The algorithm total complexity is $\mathcal{O}(V*MaxFlow)$, wich means that the overall complexity depends on the algorithm that was choosen to find the maximum flow. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| The algorithm total complexity is $\mathcal{O}(V*MaxFlow)$, wich means that the overall complexity depends on the algorithm that waschoosen to find the maximum flow. | |
| The algorithm total complexity is $\mathcal{O}(V)$ times the complexity of a single maximum flow call, wich means that the overall complexity depends on the algorithm that waschosen to find the maximum flow. |
| The algorithm total complexity is $\mathcal{O}(V*MaxFlow)$, wich means that the overall complexity depends on the algorithm that was choosen to find the maximum flow. | ||
| ### Implementation | ||
| This implementation considers the Gomory-Hu tree as a struct with methods: |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| This implementation considers the Gomory-Hu tree as a struct with methods: | |
| Below, we implement the Gomory-Hu tree as a`struct` with methods: |
| - The method *solve* returns a list that contains for each index $i$ the cost of the edge connecting $i$ and its parent, and the parent number. | ||
| - Note that the algorithm doesn't produce a *cut tree*, only an *equivalent flow tree*, so one cannot retrieve the two components of a cut from the tree $T'$. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
What is a cut tree? What is an equivalent flow tree? Neither are properly defined...
| - Note that the algorithm doesn't produce a *cut tree*, only an *equivalent flow tree*, so one cannot retrieve the two components of a cut from the tree $T'$. | ||
| ```{.cpp file=gomoryhu} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Was this implementation tested on any problem? If possible, it'd be nice to add some tests to the implementation, seehere.
| @@ -0,0 +1,100 @@ | |||
| # Gomory Hu Tree | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| #Gomory Hu Tree | |
| --- | |
| tags: | |
| - Original | |
| --- | |
| #Gomory-Hu Tree |
| @@ -189,6 +189,7 @@ search: | |||
| - [Flows with demands](graph/flow_with_demands.md) | |||
| - [Minimum-cost flow](graph/min_cost_flow.md) | |||
| - [Assignment problem](graph/Assignment-problem-min-flow.md) | |||
| - [All-pairs minimum cut - Gomory Hu](graph/gomory_hu.md) | |||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
| - [All-pairs minimum cut -Gomory Hu](graph/gomory_hu.md) | |
| - [Gomory-Hu tree](graph/gomory_hu.md) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Please also add it to the list of new articles inREADME.
Preview the changes for PR#1308 athttps://gh.cp-algorithms.com/1308/ (current version:2c09148). |
No description provided.