You're viewing the front-end.social public feed.

Federated feed Local feed

Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 9:51 AM
I need an algorithm. Given: a dynamically generated graph (you have to visit a node to calculate the list of its neighbours, at a cost), and a starting node, I want to find out:
* Whether every node can reach this starting node.
* With an early exit as soon as a counter-example is found, optimised for finding the counter-example as soon as possible (for instance, a dead end is an easy early exit).
* With a limit on the complexity, IE, if it takes too long to calculate, give up.
Any ideas?
💬 1🔄 0⭐ 0

Replies

Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 9:54 AM
The expected nature of the graph is such that if the graph is complex, a counter-example should be easy to find, and if there is no counter-example, the graph should be fairly simple.
💬 1🔄 0⭐ 0
Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 2:02 PM
I think I figured it out: I can use https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm, and exit early the first time it triggers the case to create a new strongly connected component. What I am looking for is graphs that have a single strongly connected component with the root at the starting node.
💬 1🔄 0⭐ 0
Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 3:33 PM
Ended up with this little code to do it. Much cleaner than earlier attempts to solve this problem.
💬 1🔄 0⭐ 0
Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 3:33 PM
The actual problem being solved being: Is a solitaire-like game lost? This turns out to be a pretty throny problem to solve. It's easy to see when there are no more moves available to make, but the tricky part is that you might have moves you can still make but they do not progress the game. And you also do not want to reveal to the player that they have no path to success too early, because that is just unsatisfying.
💬 1🔄 0⭐ 0
Dag Ågren ↙︎↙︎↙︎WAHa_06x36@mastodon.social
Jul 16, 2026, 3:35 PM
So it turns out the correct way to think of it is: Game states and moves can be thought of as nodes and edges in a directed graph. However, what is interesting is not individual states, but strongly connected components of this graph. Each strongly connected component represents a set of states that can easily move to each other, so they are functionally a single state.
Instead of finding out if there is a single available game state left, we find out if there is a single component left.
💬 0🔄 0⭐ 0