A modern Music Player Daemon based on Rockbox open source high quality audio player
tsiry-sandratraina.com
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * Routine for finding loops in graphs, reusable across multiple
3 * puzzles.
4 *
5 * The strategy is Tarjan's bridge-finding algorithm, which is
6 * designed to list all edges whose removal would disconnect a
7 * previously connected component of the graph. We're interested in
8 * exactly the reverse - edges that are part of a loop in the graph
9 * are precisely those which _wouldn't_ disconnect anything if removed
10 * (individually) - but of course flipping the sense of the output is
11 * easy.
12 *
13 * For some fun background reading about all the _wrong_ ways the
14 * Puzzles code base has tried to solve this problem in the past:
15 * https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/findloop/
16 *
17 * The specific variant of Tarjan's algorithm we use is the one from
18 * https://mathstodon.xyz/@abacabadabacaba@infosec.exchange/113113280480134188
19 */
20
21#include "puzzles.h"
22
23struct findloopstate {
24 int depth, shallowest_reachable, subtree_size;
25 int parent, component_root;
26 int prev, next;
27};
28
29struct findloopstate *findloop_new_state(int nvertices)
30{
31 return snewn(nvertices, struct findloopstate);
32}
33
34void findloop_free_state(struct findloopstate *state)
35{
36 sfree(state);
37}
38
39bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v)
40{
41 /*
42 * In the DFS-built forest, all edges are either are from parent
43 * to child or from child to ancestor.
44 *
45 * Back-edges to ancestors must be parts of loops. In order to
46 * detect whether a parent-to-child edge is part of a loop, we
47 * check if any ancestor is reachable from that child's subtree.
48 */
49 if (pv[u].parent == v && pv[u].shallowest_reachable >= pv[u].depth)
50 return false;
51 if (pv[v].parent == u && pv[v].shallowest_reachable >= pv[v].depth)
52 return false;
53 return true;
54}
55
56static bool findloop_is_bridge_oneway(
57 struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
58{
59 if (pv[u].parent != v)
60 return false;
61 if (pv[u].shallowest_reachable < pv[u].depth)
62 return false;
63
64 if (u_vertices)
65 *u_vertices = pv[u].subtree_size;
66 if (v_vertices) {
67 int r = pv[u].component_root;
68 *v_vertices = pv[r].subtree_size - pv[u].subtree_size;
69 }
70
71 return true;
72}
73
74bool findloop_is_bridge(
75 struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
76{
77 return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) ||
78 findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices));
79}
80
81bool findloop_run(struct findloopstate *pv, int nvertices,
82 neighbour_fn_t neighbour, void *ctx)
83{
84 int u, v, w;
85 bool any_loop = false;
86
87 /*
88 * We run a DFS to split the graph into disjoint spanning trees.
89 * This construction guarantees that every edge either descends
90 * to a new child never visited before or goes to an ancestor.
91 * Tracking which ancestors are linked from which subtrees lets
92 * us detect all loops efficiently.
93 *
94 * Here we don't use recursion, instead holding the entire DSF
95 * state in the findloopstate struct. The loop below visits each
96 * node exactly twice: before and after visiting its subtree.
97 *
98 * The first time we visit a node, we take care of marking its
99 * children with their position in the tree and when they're
100 * scheduled to be visited. The second time we update the parent
101 * with statistics about the subtree.
102 *
103 * The order of nodes is managed using a doubly-linked list.
104 * The first time a node is visited, we add its children before it
105 * in the list and set the pointer to go through them first. The
106 * second time we move to the next node in the list, which is a
107 * sibling or a parent, or if we're at the root of the connected
108 * component will be a node in the next component. (All the nodes
109 * of the graph always appear in the list)
110 * A linked list is used to handle the case where the same child
111 * appears in two levels, to allow us to efficiently remove it from
112 * its previous position.
113 *
114 * The algorithm tracks whether we're at the first or the second
115 * visit at a node using the depth property. It's set to a negative
116 * value on initialization, and to the depth in the connected
117 * component's tree on the first visit.
118 * It detects a new connected component using the parent pointer,
119 * it's always set to a real node in the search, and is negative for
120 * new trees.
121 *
122 * In the first visit, we go over the node's children, moving them
123 * in the list and setting their parent pointer. Edges going to
124 * ancestors are noted in the shallowest_reachable field.
125 * In the second visit, we adjust the subtree_size and
126 * shallowest_reachable fields of the parent.
127 *
128 * Variables:
129 * u = the current node under examination
130 * v = the node to go to in the next iteration
131 * w = neighbour iterator
132 */
133
134 for (u = 0; u < nvertices; u++) {
135 pv[u].depth = -1;
136 pv[u].shallowest_reachable = nvertices;
137 pv[u].subtree_size = 1;
138 pv[u].parent = -1;
139 pv[u].component_root = u;
140 pv[u].prev = u - 1;
141 pv[u].next = (u == nvertices - 1) ? -1 : u + 1;
142 }
143
144 debug(("------------- new find_loops, nvertices=%d\n", nvertices));
145
146 v = 0;
147 while (v != -1) {
148 u = v;
149 if (pv[u].depth < 0) {
150 /* Our first visit to the node (on the way down the search) */
151 if (pv[u].parent < 0) {
152 debug((" new component: processing %d\n", u));
153 pv[u].depth = 0;
154 pv[u].component_root = u;
155 } else {
156 debug((" processing %d\n", u));
157 pv[u].depth = pv[pv[u].parent].depth + 1;
158 pv[u].component_root = pv[pv[u].parent].component_root;
159 }
160
161 /* Schedule visits to the neighbors, and then back here */
162 v = u;
163 for (w = neighbour(u, ctx); w >= 0; w = neighbour(-1, ctx)) {
164 if (w == pv[u].parent)
165 continue;
166 if (pv[w].depth < 0) {
167 debug((" adding edge %d-%d to tree\n", u, w));
168 pv[w].parent = u;
169 /* Remove the neighbour from the linked list */
170 if (pv[w].prev >= 0)
171 pv[pv[w].prev].next = pv[w].next;
172 if (pv[w].next >= 0)
173 pv[pv[w].next].prev = pv[w].prev;
174 /* Add it to the start of the list */
175 pv[w].prev = pv[v].prev;
176 pv[w].next = v;
177 if (pv[v].prev >= 0)
178 pv[pv[v].prev].next = w;
179 pv[v].prev = w;
180 /* Mark this as the next node to visit */
181 v = w;
182 } else {
183 debug((" found back-edge %d-%d\n", u, w));
184 pv[u].shallowest_reachable =
185 min(pv[u].shallowest_reachable, pv[w].depth);
186 any_loop = true;
187 }
188 }
189 } else {
190 debug((" wrapping up %d. |subtree| = %d, min(reachable) = %d\n",
191 u, pv[u].subtree_size, pv[u].shallowest_reachable));
192 if (pv[u].parent >= 0) {
193 if (pv[u].shallowest_reachable >= pv[u].depth) {
194 debug((" bridge: %d-%d\n", u, pv[u].parent));
195 }
196 pv[pv[u].parent].subtree_size += pv[u].subtree_size;
197 pv[pv[u].parent].shallowest_reachable =
198 min(pv[pv[u].parent].shallowest_reachable,
199 pv[u].shallowest_reachable);
200 }
201 v = pv[u].next;
202 }
203 }
204
205 return any_loop;
206}