cutset = nx.minimum_edge_cut(G)
for e in cutset:
G.remove_edge(*e)
size1, size2 = map(len, nx.connected_components(G))
answer = size1 * size2At least it spit out the right answer after a while.
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.https://cseweb.ucsd.edu/classes/sp11/cse202-a/lecture8-final...
Max-Flow runs on directed graphs. These are undirected graphs.
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.
"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...
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