/* Last edited on 2018-02-13 00:48:10 by stolfilocal */

/* ---------------------------------------------------------------------- */
/* {boag_graph} */

  { 
    int64_t ND;     /* Degree of each vertex in the complete graph. */
    int64_t NE;     /* Number of edges (ordered distinct incompatible booklet pairs). */
    int64_t *fed;   /* Index of first edge in complete graph out of each vertex. */
    int64_t *nbr;   /* Indices of neighboring vertices of each vertex. */

  }
  /* The edges of {G} out of vertex {ix} are stored in the vector {nbr[0..NE-1]}
    in positions {fst[ix] .. fst[ix+1]-1}. Namely, edge number {j} out
    of vertex {ix} goes to vertex {nbr[fst[ix]+j]}, for any {j} in
    {0..ND-1}. Note that {fst} has {NV+1} positions, {fst[NV] = NE}, and
    {fst[ix+1]-fst[ix] = ND} for every vertex index {ix}. */

int64_t boag_graph_num_edges(int64_t NV, int64_t ND);
  /* Returns the total number {NE} of edges in the incompatibility graph,
    given the number {NV} of vertices and the degee {ND} of each vertex.
    The result is just {NV*ND}, but the procedure will bomb out if the number
    is excessive. */ 
    
boag_graph_t *boag_graph_new(int32_t NT, int32_t NB, int32_t K)
  { 
    int64_t NE = boag_graph_num_edges(NV, ND);  /* Number of incompatibility pairs. */
    G->NE = NE;

    G->fst = notnull(malloc((NV+1)*sizeof(int64_t), "no mem");
    G->nbr = notnull(malloc(NE*sizeof(int64_t), "no mem");

    /* Initialize with the disconnected graph, all valid, with space for all edges: */
    G->fst[0] = 0;
    for(int64_t ix = 0; ix < NV; ix++) 
      { G->fst[ix+1] = G->fst[ix] + ND;
        G->vdg[ix] = 0; /* For now. */
      }
    assert(G->fst[NV] == NE);

    /* Add the edges: */
    boag_graph_initialize_edges(G);
    
  }

void boag_graph_free(boag_graph_t *G)
  { free(G->nbr);
    free(G->fst);
    free(G);
  }
  
void boag_graph_initialize_edges(boag_graph_t *G)
  {
    int64_t NV = G->NV;
    int64_t ND = G->ND;
    int64_t NE = G->NE;
    /* Paranoia: */
    assert(NE == NV*ND);
    assert((NV >= 0) && (ND >= 0) && (NE >= 0));
    assert(G->fst[0] == 0);

    auto void add_edge(int64_t ixb);
      /* Visiting procedure for enumeration, that adds a directed edge 
        from vertex {ix} to vertex {ixb}. */

    for (int64_t ix = 0; ix < NV; ix++)
      { /* Paranoia: */
        assert(G->fst[ix+1] - G->fst[ix] == ND);
        assert(G->val[ix]);
        assert(G->vdg[ix] == 0);
        /* Find booklets that are incompatible with {ix}: */
        boag_graph_enum_incompat_booklets(NT, NB, K, ix, add_edge);
      }
      
    /* Paranoia: */
    for (int64_t ix = 0; ix < NV; ix++) { assert(G->vdg[ix] == ND); }
        
    return;
    
    /* INTERNAL IMPLEMENTATIONS: */
        
    void add_edge(int64_t ixb)
      { assert(G->vdg[ix] < ND);
        assert((ixb >= 0) && (ixb < NV));
        int64_t ie = g->fst[ix] + G->vdg[ix];
        G->nbr[ie] = ixb;
        G->vdg[ix]++;
      }
  }

/* ---------------------------------------------------------------------- */
/* {booklets_ag} */

void boag_invalidate_incompat_booklets
  ( int32_t NT, 
    int32_t NB, 
    int64_t NV, 
    int32_t qv[], 
    int64_t ix, 
    int32_t K, 
    bool_t val[], 
    int64_t deg[], 
    int64_t *nvalP
  );
  /* Removes from the valid set {val[0..NV-1]} the booklet {ix} (which must be in the valid set) and every booklet {ixc} 
    that has more than {K} question blocks in common with {ix}.  Updates {deg[0..NV-1]} and {*nvalP}.  Assumes that 
    {qv[0..NT-1]} is the vector of the booklet {ix}. */

void boag_invalidate_incompat_booklets
  ( int32_t NT, 
    int32_t NB, 
    int64_t NV, 
    int32_t qv[], 
    int64_t ix, 
    int32_t K, 
    bool_t val[], 
    int64_t deg[], 
    int64_t *nvalP
  )
  {
    demand((ix >= 0) && (ix < NV), "invalid booklet index");
    demand(((*nvalP) >= 0) && ((*nvalP) <= NV), "invalid valid booklet count");
    /* Eliminate the booklet {ix}, if valid: */
    if (val[ix]) 
      { val[ix] = FALSE; 
        deg[ix] = 0;
        boag_decrement_degrees_of_neighbors(NT, NB, NV, qv, ix, K, val, deg);
        (*nvalP)--;
      }
    /* Enumerate all booklets and exclude those with excessive intersection with {ix}: */
    int32_t qvc[NT]; /* Booklet vector. */
    for (int64_t ixc = 0; ixc < NV; ixc++)
      { if (val[ixc])
          { /* See whether it is compatible with {ix}: */
            boag_booklet_index_to_vector(NT, NB, NV, ixc, qvc);
            int32_t nshare = 0;
            for (int32_t it = 0; (it < NT) && (nshare <= K); it++)
              { if (qvc[it] == qv[it]) { nshare++; } }
            if (nshare > K)
              { /* Booklet {ixc} is incompatible with {ix}: */
                val[ixc] = FALSE;
                boag_decrement_degrees_of_neighbors(NT, NB, NV, qvc, ixc, K, val, deg);
                (*nvalP)--;
              }
           }
      }
  }