#ifndef boag_graph_H
#define boag_graph_H

/* Representation and manipulation of the booklet incompatibilty graph. */
/* Last edited on 2018-02-13 01:00:20 by stolfilocal */

#define _GNU_SOURCE
#include <stdint.h>

#include <bool.h>

#include <boag_booklet_index.h>

typedef struct boag_graph_t 
  { /* Parameters of the problem: */
    int32_t NT;     /* Number of topics. */
    int32_t NB;     /* Number of question blocks per topic. */
    int32_t K;      /* Max number of shared blocks allowed. */
    /* The complete incompatibility graph: */
    int64_t NV;     /* Number of vertices (booklets), that is, {NB^NT}. */
    int64_t ND;     /* Degree of each vertex. */
    /* Parameters of the valid subgraph: */
    int64_t NH;     /* Number of valid vertices. */
    bool_t *val;    /* Validity of each vertex (true if valid). */
    int64_t *vdg;   /* Number of valid neighbors of each valid vertex. */
  } boag_graph_t;
  /* Describes the incompatibilty graph {G} for booklets with parameters
    {NT,NB,K}, and the subgraph of it determined by the vertices that are
    still valid candidate booklets (compatible with all booklets already
    selected).
    
    The complete graph has {NV = NB^NT} vertices and {NE=NV*ND} edges,
    where {ND} is the number of booklets that share {K} or more question
    blocks with a given booklet. The vertices have indices {0..NV-1}
    that correspond to the choice of question blocks per topic,
    according to {boag_index_from_vector}.
    
    There is an edge betwen two vertices {ixa,ixb}
    if the corresponding booklets have more than {K} blocks in common.
    The edges are not stored explicitly, but can be enumerated 
    with {boag_graph_enum_incompat_booklets}.
    
    The valid subgraph {H} is the subgraph induceed by the vertices {ix}
    such that {val[ix]} is true.  The number of such vertices is {NH},
    The degree of each valid vertex {ix} in {H} is {vdg[ix]}; this number
    is {-1} if {ix} is not valid.  The neighbors of {ix} in {H} are the first 
    {vdg[ix]} neighbors of {ix} in {G}; namely, {nbr[fst[ix]+j]} for {j}
    in {0..vdg[ix]-1}. */

int64_t boag_graph_num_vertices(int32_t NT, int32_t NB);
  /* Returns the number {NV} of vertices in the complete incompatibility
    graph, that is, the number of possible booklets, compatibe or not.
    The result is {NB^NT}, but the procedure will bomb out if the number
    is excessive. */
  
boag_graph_t *boag_graph_new(int32_t NT, int32_t NV, int32_t K);
  /* Creates the incompatibility graph {G} for the given problem parameters.
    Initially all vertices are valid, that is, {H=G}. */
  
void boag_graph_free(boag_graph_t *G);
  /* Deallocates all storage used by {G}, including the head record {*G}. */
  
typedef void boag_graph_neighbor_proc_t(int64_t ixb);
  /* Type of a procedure that can be passed to
    {boag_graph_enum_incompat_booklets} to process each neighbor {ixb}
    of a given vertex {ixa} (that is, each booklet that is distinct from
    {ixa} but incompatible with it. */

void boag_graph_enum_incompat_booklets(boag_graph_t *G, int64_t ix, boag_graph_neighbor_proc_t *proc);
  /* Enumerates all vertices of {G} which are distinct from vertex {ix}
    but incompatible with it. Namely, the booklets that have between
    {G.K+1} and {G.NT-1} question blocks in common with booklet {ix}.
    For every such vertex {ixb}, calls {proc(ixb)}. */

void boag_graph_invalidate_vertex(boag_graph_t *G, int64_t ix);
  /* Invalidates the vertex {ix} (which must be valid), and decreases
    the {H}-degree of every booklet that is still valid but is
    incompatible with {ix}.*/    
 
#endif