/* See boag_graph.h */ /* Last edited on 2018-02-13 01:04:40 by stolfilocal */ #define _GNU_SOURCE #include #include #include #include #include #include #include #include #define boag_graph_vertices_MAX ((uint64_t)1000000000) /* Max number of vertices (possible booklets, {NB^NT}. */ #define boag_graph_edges_MAX ((uint64_t)1000000000) /* Max number of edges (incompatible booklet pairs, {NV*ND}. */ int64_t boag_graph_full_vertex_degree(int32_t NT, int32_t NB, int32_t K); /* Returns the degree {ND} of each vertex in the full incompatibility graph; that is, the number of distinct booklets that share more than {K} question blocks with the given booklet. */ /* IMPLEMENTATIONS */ int64_t boag_graph_num_vertices(int32_t NT, int32_t NB) { /* Check for too many vertices by computing {p = floor(boag_graph_vertices_MAX/(NB^NT))}: */ uint64_t p = boag_graph_vertices_MAX; for (uint32_t e = 0; e < NT; e++) { p = p/((uint64_t)NB); } demand(p > 0, "too many vertices in incompatibility graph"); /* Number of vertices is OK: */ return ipow(NB, NT); } int64_t boag_graph_full_vertex_degree(int32_t NT, int32_t NB, int32_t K) { int64_t ND = 0; uint64_t max = INT64_MAX; /* Max value of next sum term. */ for (int32_t r = K+1; r < NT; r++) { /* Compute number of ways that a booklet may have exactly {r} shared blocks: */ uint64_t nch = comb(NT, r); /* Ways to choose {r} topics to share. */ uint64_t pwr = upow(NB-1, NT-r); /* Ways to differ in the other {NT-r} topics. */ demand(max/pwr > 0, "too many edges per vertex"); int64_t ninc = (int64_t)(nch*pwr); /* Number of booklets with exactly {r} shared. */ ND += ninc; max -= ninc; } return ND; } boag_graph_t *boag_graph_new(int32_t NT, int32_t NB, int32_t K) { fprintf(stderr, "creating graph for %d topics, %d blocks per topic, and max %d shared blocks...\n", NT, NB, K); boag_graph_t *G = notnull(malloc(sizeof(boag_graph_t)), "no mem"); G->NT = NT; G->NB = NB; G->K = K; int64_t NV = boag_graph_num_vertices(NT, NB); /* Number of possible exam booklets. */ G->NV = NV; int64_t ND = boag_graph_full_vertex_degree(NT, NB, K); /* Number of incompatible booklets for each booklet. */ G->ND = ND; fprintf(stderr, "graph will have %ld vertices of degree %ld\n", NV, ND); /* Allocate the tables: */ G->val = notnull(malloc(NV*sizeof(bool_t)), "no mem"); G->vdg = notnull(malloc(NV*sizeof(int64_t)), "no mem"); /* Initialize all vertices as valid, with full degree */ for(int64_t ix = 0; ix < NV; ix++) { G->val[ix] = TRUE; G->vdg[ix] = ND; } fprintf(stderr, "graph created\n"); return G; } void boag_graph_free(boag_graph_t *G) { free(G->vdg); free(G->val); free(G); } void boag_graph_initialize_edges(boag_graph_t *G); /* On entry, assumes that {G} and {H} hav been fully allocated and initialized, except that it lacks all edges. Assumes in particular that, for every vertex {ix}, {G.fst[ix+1] - G.fst[ix] == G.ND}, and that {G.val[ix]} is true, but {G.vdg[ix]} is zero. On exit, {G} will have all edges, and {H} will be equal to {G}. */ void boag_graph_enum_incompat_booklets(boag_graph_t *G, int64_t ix, boag_graph_neighbor_proc_t *proc) { int32_t NT = G->NT; int32_t NB = G->NB; int32_t K = G->K; int64_t NV = G->NV; /* Expand {ix} to a block choice vector: */ int32_t qv[NT]; boag_booklet_index_to_vector(NT, NB, NV, ix, qv); auto void enum_incompat(int32_t r); /* On entry, assumes that {t[0..NT-1]} is some permutation of {0..NT-1}, {r} is a number between 0 and {NT-1}. The topic indices {t[0..r-1]} must be in increasing order. The procedure enumerates all booklets that are distinct from {qv} but make the same block choices as {qv} in at least {K+1} topics, including topics {t[0..r-1]}. The procedure calls {proc(ixb)} on the index {ixb} of every such booklet. The procedure rearranges the vector {t} while working, but the original perm should be restored on exit. */ auto void enum_diff(int32_t s); /* On entry, assumes that {t[0..NT-1]} is some permutation of {0..NT-1}, {s} is a number between {K+1} and {NT}, and {qvb[0..s-1]} are possible block choices for topics {t[0..s-1]}. The procedure enumerates all booklets that make block choices {qvb[t[0..s-1]]} on topics {t[0..s-1]}, and are distinct from {qv} in all other topics topics. The procedure calls {proc(ixb)} on the index {ixb} of every such booklet. The procedure modifies {qvb} only for topics other than {t[0..s-1]}. It does not modify the perm {t[0..NT-1]}. */ /* Create a vector {t[0..NT]} initialized with the trivial perm or {0..NT-1}. */ int32_t t[NT]; /* Topics vector. */ for (uint32_t r = 0; r < NT; r++) { t[r] = r; } int32_t qvb[NT]; /* Work vector for {enum_diff}. */ enum_incompat(0); return; /* INTERNAL IMPLEMENTATIONS: */ void enum_incompat(int32_t r) { assert((r >= 0) && (r < NT)); if (r > K) { /* At this point {qvb[t[i]] = qv[t[i]]} for {i} in {0..r-1}. */ /* Enumerate all booklets that match those, and differ from {qv} in the remaining topics. */ enum_diff(r); } if (r < NT-1) { /* Try to fix another topic to be like {qv}: */ for (int32_t i = r; i < NT; i++) { /* Check whether appending {t[i]} to {t[0..r-1]} will keep it sorted: */ if ((r == 0) || (t[i] > t[r-1])) { /* Swap {t[i]} with {t[r]} (it will keep {t[0..r]} sorted): */ { int32_t z = t[i]; t[i] = t[r]; t[r] = z; } /* Fix choice for {t[r]} to be the same as in the original booklet, and recurse: */ qvb[t[r]] = qv[t[r]]; enum_incompat(r+1); /* Swap back {t[i]} with {t[r]} to restore original perm: */ { int32_t z = t[i]; t[i] = t[r]; t[r] = z; } } } } } void enum_diff(int32_t s) { assert((s > K) && (s <= NT)); /* At this point {qvb[t[i]] is fixed} for {i} in {0..s-1}. */ if (s == NT) { /* Only one booklet, process it: */ int64_t ixb; boag_booklet_index_from_vector(NT, NB, NV, qvb, &ixb); proc(ixb); } else { /* Enumerate all possible choices for {qvb[t[s]], and recurse: */ int32_t ts = t[s]; assert((ts >= 0) && (ts < NT)); int32_t qvs = qv[ts]; assert((qvs >= 1) && (qvs <= NB)); for (uint32_t b = 1; b <= NB; b++) { if (b != qv[ts]) { qvb[ts] = b; enum_diff(s+1); } } } } } void boag_graph_invalidate_vertex(boag_graph_t *G, int64_t ix) { int64_t NV = G->NV; /* Vertex count in full graph. */ int64_t ND = G->ND; /* Vertex degree in full graph. */ /* Paranoia: */ assert((ix >= 0) && (ix < NV)); demand(G->val[ix], "vertex is not currently valid"); assert(G->NH > 0); int64_t dix = G->vdg[ix]; assert((dix >= 0) && (dix <= ND)); /* Invalidate the vertex: */ G->val[ix] = FALSE; G->vdg[ix] = -1;/* No longer relevant. */ G->NH--; /* Decrement degrees of valid neighbors: */ int64_t ndec = 0; /* Number of valid neighbors found. */ auto void dec_degree(int64_t ixb); /* Decrements the degree of vertex {ixb}, if still valid. No-op if it is invalid. */ boag_graph_enum_incompat_booklets(G, ix, &dec_degree); assert(ndec == dix); return; /* INTERNAL IMPLEMENTATIONS: */ void dec_degree(int64_t ixb) { assert((ix >= 0) && (ix < NV)); if (G->val[ixb]) { int64_t dixb = G->vdg[ixb]; assert((dixb > 0) && (dixb <= ND)); G->vdg[ixb]--; ndec++; } } }