A game based on the Havel-Hakimi algorithm
jacquerie.github.io
A game based on the Havel-Hakimi algorithm
1–10 of 28 posts
Re: A game based on the Havel-Hakimi algorithm
#2A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
Re: A game based on the Havel-Hakimi algorithm
#3This is nice! I got stuck and gave up when there got to be nodes with 6s on them, but that's just because I'm in class.
Given that the only reason to select an edge right now is to delete it, perhaps the delete action could be mapped to a click, rather than a click plus a backspace. Also, a reset level button would be nice.
Re: A game based on the Havel-Hakimi algorithm
#4A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
Or connect the node with the highest degree with the node with the lowest degree.
Re: A game based on the Havel-Hakimi algorithm
#5A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
Or connect the node with the highest degree with the node with the lowest degree.
I just tried this and several times the highest degree was already connected with the lowest degree, so I either had to pick another highest degree node (if there was a tie), pick the next highest degree and connect it with the lowest degree, or pick the next lowest degree and connect it with the highest degree. They all seemed to work out okay.
I find it interesting that yours appears simpler on the face of it, but has more edge cases. Seems like mine would be simpler if you were actually writing out the steps properly.
Re: A game based on the Havel-Hakimi algorithm
#6A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greedy algorithm falls down is a field of many nodes with the same degree, where the greedy algorithm doesn't give information about which two to connect. I think the problem is a bit deeper than it seems in the first few iterations.
Re: A game based on the Havel-Hakimi algorithm
#7A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
This is in fact the Havel-Hakimi algorithm.
Re: A game based on the Havel-Hakimi algorithm
#8A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
A naive greedy algorithm will eventually find a situation where the two nodes with the highest degrees are already connected. Another place where a simple greedy algorithm falls down is a field of many nodes with the same degree, where the greedy algorithm doesn't give information about which two to connect. I think the problem is a bit deeper than it seems in the first few iterations.
You're correct, I didn't specify it well enough.
Pick the node with the highest unassigned degree, connect it to the other unconnected nodes with the highest unassigned degrees (where unassigned degree is the difference between the target degree and the degree of edges we've assigned in previous iterations)
I don't fully understand your second point. If there isn't a requirement to create a connected graph it can pick arbitrarily between nodes of equal unassigned degrees.
[1] My brain is too tired to come up with a better term than unassigned
Re: A game based on the Havel-Hakimi algorithm
#9A greedy algorithm seems to be successful with the graphs in this game. Pick the node with the highest degree, connect it to the other nodes with the highest degrees, repeat.
Or connect the node with the highest degree with the node with the lowest degree.
Not only that but also connect the highest with greatest connectivity to the lowest with greatest connectivity to avoid "orphan" nodes.
Re: A game based on the Havel-Hakimi algorithm
#10Pretty fun game. Clever way to scout internships as well. Hah!