shithub: puzzles

Info  •  Files  •  Log  •  Branches

findloop: alternative query function.

This one tells you if a graph edge _is_ a bridge (i.e. it has inverted
sense to the existing is_loop_edge query). But it also returns
auxiliary data, telling you: _if_ this edge were removed, and thereby
disconnected some connected component of the graph, what would be the
sizes of the two new components?

The data structure built up by the algorithm very nearly contained
enough information to answer that already: because we assign
sequential indices to all the vertices in a traversal of our spanning
forest, and any bridge must be an edge of that forest, it follows that
we already know the size of _one_ of the two new components, just by
looking up the (minindex,maxindex) values for the vertex at the child
end of the edge.

To determine the other subcomponent's size, we subtract that from the
size of the full component. That's not quite so easy because we don't
already store that - but it's trivial to annotate every vertex's data
with a pointer back to the topmost node of the spanning forest in its
component, and then we can look at the (minindex,maxindex) pair of
that. So now we know the size of the original component and the size
of one of the pieces it would be split into, so we can just subtract.

--- a/findloop.c

+++ b/findloop.c

@@ -14,7 +14,7 @@

 #include "puzzles.h"

 struct findloopstate {

-    int parent, child, sibling;

+    int parent, child, sibling, component_root;

     bool visited;

     int index, minindex, maxindex;

     int minreachable, maxreachable;

@@ -57,6 +57,33 @@

     return !(pv[u].bridge == v || pv[v].bridge == u);

 }

+static bool findloop_is_bridge_oneway(

+    struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)

+{

+    int r, total, below;

+

+    if (pv[u].bridge != v)

+        return false;

+

+    r = pv[u].component_root;

+    total = pv[r].maxindex - pv[r].minindex + 1;

+    below = pv[u].maxindex - pv[u].minindex + 1;

+

+    if (u_vertices)

+        *u_vertices = below;

+    if (v_vertices)

+        *v_vertices = total - below;

+

+    return true;

+}

+

+bool findloop_is_bridge(

+    struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)

+{

+    return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) ||

+            findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices));

+}

+

 bool findloop_run(struct findloopstate *pv, int nvertices,

                   neighbour_fn_t neighbour, void *ctx)

 {

@@ -94,6 +121,7 @@

              */

             pv[v].sibling = pv[root].child;

             pv[root].child = v;

+            pv[v].component_root = v;

             debug(("%d is new child of root\n", v));

             u = v;

@@ -116,6 +144,7 @@

                             pv[w].child = -1;

                             pv[w].sibling = pv[u].child;

                             pv[w].parent = u;

+                            pv[w].component_root = pv[u].component_root;

                             pv[u].child = w;

                         }

--- a/puzzles.h

+++ b/puzzles.h

@@ -591,6 +591,18 @@

 bool findloop_is_loop_edge(struct findloopstate *state, int u, int v);

 /*

+ * Alternative query function, which returns true if the u-v edge is a

+ * _bridge_, i.e. a non-loop edge, i.e. an edge whose removal would

+ * disconnect a currently connected component of the graph.

+ *

+ * If the return value is true, then the numbers of vertices that

+ * would be in the new components containing u and v are written into

+ * u_vertices and v_vertices respectively.

+ */

+bool findloop_is_bridge(

+    struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices);

+

+/*

  * Helper function to sort an array. Differs from standard qsort in

  * that it takes a context parameter that is passed to the compare

  * function.