0
$\begingroup$

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473

To summarize, in an unknown strongly connected, directed graph in which all vertices have out-degree 2 (so from a vertex, we either go $a$ or $b$), we are placed on one of the vertices (we do not know which, as we don't even know the graph), and have to find the exit, which is one of the vertices (of course we do not know this either). We must find a sequence of $a$, $b$ that guarantees our getting out.

Now, the way to solve this (https://math.stackexchange.com/a/4887473/1098363) was very well written under my previous question, so let me quote it:

There are only finitely many possible labyrinths on n vertices, where the data defining a labyrinth includes all of the edges, the start vertex, and the target vertex. Say there are $M$ labyrinths, and name them $L_1,L_2,\dots,L_M$ . Given a labyrinth $L$ and an arbitrary vertex $v$ of $L$ , let $sol(L, v)$ be a sequence of $a$ and $b$ which, starting from $v$ , takes you to the exit of $L$ .

Let $w_1=sol(L_1,v_1)$ , where $v_1$ is the start vertex of $L_1$ . The first part of the solution path will be $w_1$ .

Let $v_2$ be the vertex you end up on after following the path $w_1$ on the labyrinth $L_2$ . Then, let $w_2=sol(L_2,v_2)$ . The second portion of the solution path is $w_2$ ; as long as the true labyrinth is $L_2$ , then we will be done after completing $w_1+w_2$ .

Let $v_3$ be the vertex you end up on after following the concatenation of paths $w_1+w_2$ on the labyrinth $L_3$ . Then, let $w_3=sol(L_3,v_3)$ . The third portion of the solution path is $w_3$ .

We continue in this fashion. Assuming that $w_k$ has been defined, we let $v_{k+1}$ be the result of following the path $w_1+w_2+\dots+w_k$ on $L_{k+1}$ , and then define $w_{k+1}=sol(L_{k+1},v_{k+1})$ .

Finally, the solution path which works on any labyrinth is $w_1+\dots+w_M$

And this makes perfect sense, it is probably not the shortest such sequence, and that is fine. I have to write the code that outputs this sequence of $a$ and $b$, and this seems like a daunting task.

I believe the task can be split up into multiple parts:

Step 1: generate the graphs: This seems hard, do i do it the irreducible matrix way or is there something that relies more on programming that is easier? Should I do adjacency list or matrix?

Step 2: make a path finding function: Depending on the format of the graphs I belive this should be fairly easy with BFS or DFS

Step 3: execute the iteration: This seems pretty difficult. After enumerating these graphs I also have to have a function that keeps track of where in the graph we are, based on the previous sum of $w_i$ then do the BFS or DFS to the terminal and save that sequence and move on to the next graph

Is this plan correct programming-wise? Can someone help me especially with Step 1, as I don't know how this could easily be done?

(I also had this post but it was much less concrete: Graph labyrinth solving sequence)

$\endgroup$

1 Answer 1

0
$\begingroup$

Step 1. Firstly, adjacency list is preferable, since the graph is very sparse. Even if you don't care about memory and running time, using list is more convenient in this specific problem, since you need do distinguish a-arc and b-arc. In list (which is a pair for each vertex) you may think that the first outgoing arc is a and the second is b.

Secondly, to generate all graphs you may use a pure (recursive) brute force, selecting all possible head vertices in each pair of outgoing arcs. After creating a graph you need to check its strong connectivity only, since every vertex has exactly two outgoing arcs, already with proper labels.

This part has plenty of optimizations giving a constrained search instead of brute force. First of all note that you don't need all labeled graph for the same unlabeled. That's why you can make a constraint that every arc goes either to one of already non-isolated vertices or to the first isolated. Note that the only isolated vertex for which you add outgoing arcs is the first one, because every such vertex is definitely not reachable from any of previous. (Thus for a strong connectivity check you need to check only that the first vertex is reachable from any other since every vertex is reachable from the first one.) Also note that for $n > 1$ there should not be two self-loops for any vertex.

Step 2. Note that you need to solve the problem for every vertex $v_1, v_2, \ldots, v_n$ of the graph $G$. A possible approach is the following. Let $t$ be the terminal vertex. Suppose that $v_1$ is the starting vertex and find a $(v_1, t)$-path $P_1$ and corresponding sequence $S_1$ of a and b's. (Generally BFS is better here in sense of path length, however DFS is also suitable.) Now suppose that $v_2$ is the starting vertex. Remember that you already have moves in $S_1$. So firstly make all moves of $S_1$ starting from $v_2$ leading to other vertex $u_2$. If $t$ is not visited yet, find $(u_2, t)$-path $P_2$ and append corresponding a and b's to $S_1$ to get a sequence $S_2$. Repeat the same for every other vertex.

Step 3. There is no need to store all graphs. If you store the sequence itself you may iterate it for the current triple of graph $G$, starting vertex $v$ and terminal vertex $t$. I would insert step 2 call into the graph-generating function for every terminal vertex $t$. The longer sequence you have the higher chance that you will not need to append anything else.

However if you want to generate graphs firstly and create a sequence afterwards, then you need to store for each pair of starting and terminal vertices of each graph the actual state (which is a vertex where we come after making all moves) and update all states each time after augmenting the sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.