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:
[ Parent
| on HN ]
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.