3 ms·
The min-cut problem was in fact the last problem for Advent of Code 2023 [0]. Many algorithms were too big-brained for me, but I was able to find "A Simple Min-
by ryandv 3y ago
The min-cut problem was in fact the last problem for Advent of Code 2023 [0]. Many algorithms were too big-brained for me, but I was able to find "A Simple Min-Cut Algorithm" [1] which was relatively easy to understand. It uses maximum adjacency search [2] to traverse the graph in descending order of the number of incident edges from each vertex to all previously visited vertices, possibly factoring in their weights; the last two visited vertices are then merged, and the cut separating the last vertex visited from the rest of the graph is stored.
The process repeats until all but two vertices have been merged; the smallest cut found in each iteration, by sum of weights of edges that need to be severed to separate the last vertex from the rest of the graph, induces a min-cut for the entire graph; since vertices have been merged together you will need to map from edges incident to the merged vertex back to edges incident to all vertices "contained" in that merged vertex.
The advantage of implementing maximum adjacency search is that it can also be used to traverse and count components of the resulting cut graph to verify it has indeed been partitioned in two.
Something like that anyway. It's been a little while.
[0] https://adventofcode.com/2023/day/25 https://adventofcode.com/2023/day/25
[1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/stoerwagner-mincut.pdf https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...
[2] https://dl.acm.org/doi/pdf/10.5555/313559.313872 https://dl.acm.org/doi/pdf/10.5555/313559.313872
- d0mine 3y agoHere's solution using networkx Python module: cutset = nx.minimum_edge_cut(G) for e in cutset: G.remove_edge(*e) size1, size2 = map(len, nx.connected_components(G)) answer = size1 * size2
- ryandv 3y agoElegant. For whatever reason I elected to roll my own graph implementation in my own solution, with predictably terrible performance characteristics: using adjacency lists (instead of matrices) and BTreeSets to model "merged" vertices was not the greatest idea in hindsight.. At least it spit out the right answer after a while.
- guiambros 3y agoSame! I felt it'd be above my IQ-level, so networkx-ed it. Here's another obvious solution: pos = nx.spring_layout(G) nx.draw_networkx_nodes(G, pos) nx.draw_networkx_edges(G, pos) nx.draw_networkx_labels(G, pos, font_size=10, font_color="white") plt.show() Thankfully it was my fastest solution (after day 1). After 25 days, I wasn't in the mood of spending hours post-xmas dinner solving convoluted riddles.
- tylerhou 3y agoSorry if I am missing something, but why not run max-flow? Max-flow is simple to implement; basically just DFS/BFS in a loop. Also, a more advanced variant with better runtime, scaling max-flow, is not too much harder. https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final.pdf https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final...
- ColinWright 3y agoUnless I'm missing something (which is entirely possible, I have a cold and might not be thinking straight) ... Max-Flow runs on directed graphs. These are undirected graphs.
- eutectic 3y agoAlso, the problem is to find a global min-cut, which requires all-pairs max flow.
- gloria_mundi 3y agoNot actually all-pairs max flow, you can fix the source and consider all possible sinks. In the AoC problem we also know that the min-cut is 3, so we can abort the flow algorithm as soon as we have found a 4-flow.
- armanboyaci 3y agoYou can compute the max-flow of an undirected graph. The edges have capacities and in the undirected case you assume that capacity can be used in both 'directions'.
- papercrane 3y agoSince the AoC specifies the min-cut for you I found it was simpler to take advantage of that. I picked two random vertices and found the shortest path between them 3 times, cutting each vertex after each iteration. If after doing that I couldn't find a path between the two vertices then I had successfully partitioned the graph in two. Otherwise that meant I picked two vertices in the same partition and I reset the graph and randomly picked a different vertex. Ended up being very quick to run, and easy to implement.
- nikanj 3y agoI visualized the AoC graph with graphviz and identified the minimum cut using good ol' mark 1 eyeball. Humans have an incredibly efficient algorithm for identifying "this blob is only connected to that blob with these two lines"
- vismit2000 3y agoJust FYI, it was possible to solve Advent of Code 2023 - Day 25 using a cool Linear Algebra trick as well. "Fiedler vector"[1] - Algebraic connectivity (without networkx): https://www.reddit.com/r/adventofcode/comments/18qbsxs/comment/keubcfd/ https://www.reddit.com/r/adventofcode/comments/18qbsxs/comme... I also used networkx during the contest to solve and visualize[2] but it was good to learn the Linear Algebra approach also afterwards from the Reddit solution thread. [1] https://en.wikipedia.org/wiki/Algebraic_connectivity?useskin=vector#Partitioning_a_graph_using_the_Fiedler_vector https://en.wikipedia.org/wiki/Algebraic_connectivity?useskin... [2] https://github.com/vismit2000/compCode-II/blob/master/Advent-of-Code/2023/day25.py#L14 https://github.com/vismit2000/compCode-II/blob/master/Advent...