News for hackers. Stuff that matters.
Re:Solving the minimum cut problem for undirected graphs by ryandv on Wednesday April 17, 2024 @01:26PM (#40067676)
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

[1] https://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handou...

[2] https://dl.acm.org/doi/pdf/10.5555/313559.313872

Re:Solving the minimum cut problem for undirected graphs by d0mine on Wednesday April 17, 2024 @01:49PM (#40067951)
Here'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
Re:Solving the minimum cut problem for undirected graphs by ryandv on Wednesday April 17, 2024 @02:29PM (#40068447)
Elegant. 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.

Re:Solving the minimum cut problem for undirected graphs by guiambros on Wednesday April 17, 2024 @11:59PM (#40072818)
Same! 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.
Re:Solving the minimum cut problem for undirected graphs by tylerhou on Wednesday April 17, 2024 @05:16PM (#40070126)
Sorry 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...

Re:Solving the minimum cut problem for undirected graphs by ColinWright on Wednesday April 17, 2024 @05:27PM (#40070226)
Unless 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.

Re:Solving the minimum cut problem for undirected graphs by eutectic on Wednesday April 17, 2024 @06:42PM (#40070854)
Also, the problem is to find a global min-cut, which requires all-pairs max flow.
Re:Solving the minimum cut problem for undirected graphs by gloria_mundi on Wednesday April 17, 2024 @08:54PM (#40071853)
Not 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.
Re:Solving the minimum cut problem for undirected graphs by armanboyaci on Wednesday April 17, 2024 @08:21PM (#40071626)
You 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'.
Re:Solving the minimum cut problem for undirected graphs by papercrane on Wednesday April 17, 2024 @05:19PM (#40070155)
Since 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.

Re:Solving the minimum cut problem for undirected graphs by nikanj on Wednesday April 17, 2024 @08:26PM (#40071662)
I 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"
Re:Solving the minimum cut problem for undirected graphs by vismit2000 on Thursday April 18, 2024 @01:11AM (#40073171)
Just 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/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... [2] https://github.com/vismit2000/compCode-II/blob/master/Advent...