[SERVER-55675] Improve libdeps analyzer critical edges to find all min cuts Created: 31/Mar/21 Updated: 17/Oct/23 Resolved: 17/Oct/23 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Major - P3 |
| Reporter: | Daniel Moody | Assignee: | [DO NOT ASSIGN] Backlog - Server Development Platform Team (SDP) (Inactive) |
| Resolution: | Won't Do | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Assigned Teams: |
Server Development Platform
|
| Participants: |
| Description |
|
The libdeps analyzer critical edges feature finds a minimum cut between two nodes. It will currently only find the first min cut closet to the input target node. It would be an improvement if it found all min cuts from target to source. |
| Comments |
| Comment by Daniel Moody [ 31/Mar/21 ] |
|
One idea I had was if you take the min cut, then add dummy nodes and edges between min cut edges then take the min cut again and see if a min cut of the same length as the original is output, then that would be a new min cut. The process could be repeated for each new min cut. |