Quelle cliques.c Sprache: C

////////////////////////////////////////////////////////////////////////////////
//
// cliques.c               cliques                           Julius Jonusas
//
// Copyright (C) 2020 - Julius Jonusas
//
// This file is free software, see the digraphs/LICENSE.

#include "cliques.h"

// C headers
#include <stdbool.h>  // for true, false, bool
#include <stdint.h>   // for uint16_t, uint64_t

// GAP headers
#include "gap-includes.h"

// Digraphs package headers
#include "bitarray.h"        // for BitArray
#include "conditions.h"      // for Conditions
#include "digraphs-debug.h"  // for DIGRAPHS_ASSERT
#include "homos-graphs.h"    // for Digraph, Graph, . . .
#include "perms.h"           // for UNDEFINED, PermColl, Perm
#include "safemalloc.h"

////////////////////////////////////////////////////////////////////////////////
// Macros
////////////////////////////////////////////////////////////////////////////////

#define MIN(a, b) (a < b ? a : b)
#define EXIT 0

////////////////////////////////////////////////////////////////////////////////
// Forward declarations
////////////////////////////////////////////////////////////////////////////////

// Defined in digraphs.h
Int DigraphNrVertices(Obj);
Obj FuncOutNeighbours(Obj, Obj);
Obj FuncADJACENCY_MATRIX(Obj, Obj);

// GAP level things, imported in digraphs.c
extern Obj IsDigraph;
extern Obj Infinity;
extern Obj IsSymmetricDigraph;
extern Obj GeneratorsOfGroup;
extern Obj AutomorphismGroup;
extern Obj IsPermGroup;
extern Obj IsDigraphAutomorphism;
extern Obj LargestMovedPointPerms;
extern Obj SmallestMovedPointPerm;
extern Obj IsClique;
extern Obj IsTrivial;
extern Obj Orbit;
extern Obj Stabilizer;
extern Obj IsSubset;
extern Obj OnTuples;
extern Obj Group;
extern Obj ClosureGroup;

////////////////////////////////////////////////////////////////////////////////
// CliquesData
////////////////////////////////////////////////////////////////////////////////

struct cliques_data {
  void* user_param;    // A USER_PARAM for the hook
  Obj   gap_func;      // Variable to hold a GAP level hook function
  UInt (*hook)(void*,  // HOOK function applied to every homo found
               const BitArray*,
               const uint16_t,
               Obj);

  Graph*    graph;  // Graphs to hold incoming GAP symmetric digraphs
  BitArray* clique;

  Conditions* ban;
  Conditions* to_try;

  Conditions* try_;

  BitArray* temp_bitarray;
  Obj       orbit;
  size_t    capacity;
};

typedef struct cliques_data CliquesData;

static void free_cliques_data(CliquesData* data) {
  DIGRAPHS_ASSERT(data != NULL);
  if (data->capacity > 0) {
    free_graph(data->graph);
    free_bit_array(data->clique);
    free_conditions(data->try_);
    free_conditions(data->ban);
    free_conditions(data->to_try);
    free_bit_array(data->temp_bitarray);
    data->capacity = 0;
  }
}

static void init_cliques_data(CliquesData* data, size_t capacity) {
  DIGRAPHS_ASSERT(capacity > 0);
  DIGRAPHS_ASSERT(data != NULL);

  free_cliques_data(data);
  data->capacity = capacity;
  data->graph    = new_graph(capacity);

  // Currently Conditions are a nr1 x nr1 array of BitArrays, so both
  // values have to be set to MAXVERTS
  data->clique = new_bit_array(capacity);
  data->try_   = new_conditions(capacity, capacity);
  data->ban    = new_conditions(capacity, capacity);
  data->to_try = new_conditions(capacity, capacity);

  data->orbit         = Fail;
  data->temp_bitarray = new_bit_array(capacity);
}

static CliquesData* global_cliques_data(void) {
  static CliquesData data;
  static bool        first_call = true;
  if (first_call) {
    data.capacity = 0;
    first_call    = false;
  }
  return &data;
}

Obj FuncDIGRAPHS_FREE_CLIQUES_DATA(Obj self) {
  free_cliques_data(global_cliques_data());
  return 0L;
}

////////////////////////////////////////////////////////////////////////////////
// Hook functions
////////////////////////////////////////////////////////////////////////////////

static UInt clique_hook_collect(void*           user_param,
                                const BitArray* clique,
                                const uint16_t  nr,
                                Obj             gap_func) {
  UInt i;
  Obj  c;

  c = NEW_PLIST(T_PLIST, nr);
  for (i = 1; i <= nr; ++i) {
    if (get_bit_array(clique, i - 1)) {
      PushPlist(c, INTOBJ_INT(i));
    }
  }

  ASS_LIST(user_param, LEN_LIST(user_param) + 1, c);
  return 1;
}

static UInt
clique_hook_gap_list(void* user_param, Obj clique_list, Obj gap_func) {
  Obj n = CALL_2ARGS(gap_func, user_param, clique_list);
  if (!IS_INTOBJ(n)) {
    ErrorQuit("the 2nd argument must be a function which returns "
              "an integer,",
              0L,
              0L);
  }
  return INT_INTOBJ(n);
}

static UInt clique_hook_gap(void*           user_param,
                            const BitArray* clique,
                            const uint16_t  nr,
                            Obj             gap_func) {
  UInt i;
  Obj  c;

  c = NEW_PLIST(T_PLIST, nr);
  for (i = 1; i <= nr; ++i) {
    if (get_bit_array(clique, i - 1)) {
      PushPlist(c, INTOBJ_INT(i));
    }
  }
  return clique_hook_gap_list(user_param, c, gap_func);
}

////////////////////////////////////////////////////////////////////////////////
// Static helper functions
////////////////////////////////////////////////////////////////////////////////

// Update a BitArray to only include one vertex per orbit with respect to
// the group <group>
static void get_orbit_reps_bitarray(BitArray*    bit_array,
                                    Obj const    group,
                                    CliquesData* data) {
  if (group == Fail) {
    return;
  }

  uint16_t nr = data->graph->nr_vertices;
  for (uint16_t v = 0; v < nr; ++v) {
    if (get_bit_array(bit_array, v)) {
      // Find the orbit of pt and remove all other points of the orbit from
      // <bit_array>

      data->orbit = CALL_2ARGS(Orbit, group, INTOBJ_INT(v + 1));
      DIGRAPHS_ASSERT(IS_LIST(data->orbit));

      for (Int i = 1; i <= LEN_LIST(data->orbit); ++i) {
        set_bit_array(
            bit_array, INT_INTOBJ(ELM_LIST(data->orbit, i)) - 1, false);
      }
      set_bit_array(bit_array, v, true);
    }
  }
}

// Initialise the graph from GAP digraph and discard non-symmetric edges and
// loops
static void init_graph_from_digraph_obj(Graph* const graph, Obj digraph_obj) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(CALL_1ARGS(IsDigraph, digraph_obj) == True);
  Int const nr      = DigraphNrVertices(digraph_obj);
  Obj       adj_mat = FuncADJACENCY_MATRIX(0L, digraph_obj);
  DIGRAPHS_ASSERT(nr < MAXVERTS);
  DIGRAPHS_ASSERT(IS_PLIST(adj_mat));
  DIGRAPHS_ASSERT(IS_PLIST(FuncOutNeighbours(0L, digraph_obj)));
  clear_graph(graph, nr);

  // Only include symmetric edges
  for (Int i = 1; i < nr; ++i) {
    Obj row = ELM_PLIST(adj_mat, i);
    DIGRAPHS_ASSERT(IS_LIST(row));
    Obj zero_obj = INTOBJ_INT(0);
    for (Int j = i + 1; j <= nr; ++j) {
      if (ELM_PLIST(row, j) != zero_obj
          && ELM_PLIST(ELM_PLIST(adj_mat, j), i) != zero_obj) {
        add_edge_graph(graph, i - 1, j - 1);
        add_edge_graph(graph, j - 1, i - 1);
      }
    }
  }
}

// Initialise the global variables
static bool init_data_from_args(Obj          digraph_obj,
                                Obj          hook_obj,
                                Obj          user_param_obj,
                                Obj          include_obj,
                                Obj          exclude_obj,
                                Obj          max_obj,
                                Obj*         group,
                                CliquesData* data) {
  if (data->capacity == 0
      || (size_t) DigraphNrVertices(digraph_obj) + 1 > data->capacity) {
    init_cliques_data(data, DigraphNrVertices(digraph_obj) + 1);
  }

  uint16_t nr = DigraphNrVertices(digraph_obj);
  init_graph_from_digraph_obj(data->graph, digraph_obj);

  clear_conditions(data->try_, nr + 1, nr);
  clear_conditions(data->ban, nr + 1, nr);
  clear_conditions(data->to_try, nr + 1, nr);
  init_bit_array(data->ban->bit_array[0], false, nr);

  init_bit_array(data->clique, false, nr);
  // Update CLIQUE and try_ using include_obj
  if (include_obj != Fail) {
    set_bit_array_from_gap_list(data->clique, include_obj);
    complement_bit_arrays(get_conditions(data->try_, 0), data->clique, nr);
    for (uint16_t i = 1; i <= LEN_LIST(include_obj); ++i) {
      intersect_bit_arrays(
          get_conditions(data->try_, 0),
          data->graph->neighbours[INT_INTOBJ(ELM_LIST(include_obj, i)) - 1],
          nr);
    }
  }
  // Update try_ using exclude_obj
  if (exclude_obj != Fail) {
    set_bit_array_from_gap_list(data->temp_bitarray, exclude_obj);
    complement_bit_arrays(
        get_conditions(data->try_, 0), data->temp_bitarray, nr);
  }

  // Get the isolated vertices of the graph
  // temp_bitarray now represents isolated vertices
  init_bit_array(data->temp_bitarray, false, nr);
  Int first_isolated = -1;
  for (uint16_t i = 0; i < nr; ++i) {
    if (size_bit_array(data->graph->neighbours[i], nr) == 0) {
      if (first_isolated == -1
          && get_bit_array(get_conditions(data->try_, 0), i)) {
        first_isolated = i;
      }
      set_bit_array(data->temp_bitarray, i, true);
    }
  }
  // Update try_ using isolated, only one isolated vertex is used
  if (first_isolated != -1) {
    complement_bit_arrays(
        get_conditions(data->try_, 0), data->temp_bitarray, nr);
    set_bit_array(get_conditions(data->try_, 0), first_isolated, true);
  }

  // Discard the generators of aut_grp_obj which act on the isolated vertices
  if (size_bit_array(data->temp_bitarray, nr) > 0) {
    Obj new_group = Fail;
    Obj gens      = CALL_1ARGS(GeneratorsOfGroup, *group);
    DIGRAPHS_ASSERT(IS_LIST(gens));
    for (Int i = 1; i <= LEN_LIST(gens); ++i) {
      Obj s = CALL_1ARGS(SmallestMovedPointPerm, ELM_LIST(gens, i));
      if (s != Infinity
          && !get_bit_array(data->temp_bitarray, INT_INTOBJ(s) - 1)) {
        if (new_group == Fail) {
          new_group = CALL_1ARGS(Group, ELM_LIST(gens, i));
        } else {
          new_group = CALL_2ARGS(ClosureGroup, new_group, ELM_LIST(gens, i));
        }
      }
    }
    *group = new_group;
  }

  if (hook_obj != Fail) {
    data->gap_func = hook_obj;
    data->hook     = clique_hook_gap;
  } else {
    data->gap_func = Fail;
    data->hook     = clique_hook_collect;
  }
  data->user_param = user_param_obj;

  return true;
}

////////////////////////////////////////////////////////////////////////////////
// Main functions
////////////////////////////////////////////////////////////////////////////////

static int BronKerbosch(uint16_t     depth,
                        uint16_t     rep_depth,
                        uint64_t     limit,
                        uint64_t*    nr_found,
                        bool         max,
                        uint16_t     size,
                        Obj          group,
                        CliquesData* data) {
  uint16_t  nr   = data->graph->nr_vertices;
  BitArray* try_ = get_conditions(data->try_, 0);
  BitArray* ban  = get_conditions(data->ban, 0);

  if (depth > 0 && !max && (size == 0 || size == depth)) {
    // We are not looking for maximal cliques
    *nr_found += data->hook(data->user_param, data->clique, nr, data->gap_func);
    if (*nr_found >= limit) {
      return EXIT;
    }
  } else if (size_bit_array(try_, nr) == 0 && size_bit_array(ban, nr) == 0
             && (size == 0 || size == depth)) {
    // <CLIQUE> is a maximal clique
    *nr_found += data->hook(data->user_param, data->clique, nr, data->gap_func);
    if (*nr_found >= limit) {
      return EXIT;
    }
  }

  BitArray* to_try = get_conditions(data->to_try, 0);
  if (max) {
    // Choose a pivot with as many neighbours in <try_> as possible
    uint16_t pivot          = 0;
    int16_t  max_neighbours = -1;

    for (uint16_t i = 0; i < nr; ++i) {
      if (get_bit_array(try_, i) || get_bit_array(ban, i)) {
        copy_bit_array(data->temp_bitarray, try_, nr);
        intersect_bit_arrays(
            data->temp_bitarray, data->graph->neighbours[i], nr);
        uint16_t num_neighbours = size_bit_array(data->temp_bitarray, nr);
        if (num_neighbours > max_neighbours) {
          pivot          = i;
          max_neighbours = num_neighbours;
        }
      }
    }

    // try_ adding vertices from <try_> minus neighbours of <pivot>
    init_bit_array(to_try, true, nr);
    complement_bit_arrays(to_try, data->graph->neighbours[pivot], nr);
    intersect_bit_arrays(to_try, try_, nr);
  } else {
    // If we are not looking for maximal cliques, a pivot cannot be used
    copy_bit_array(to_try, try_, nr);
  }
  // Update the height of the condition data->to_try, since we didn't use
  // push_condition
  data->to_try->height[0]++;

  // Get orbit representatives of <to_try>
  get_orbit_reps_bitarray(to_try, group, data);

  for (uint16_t v = 0; v < nr; ++v) {
    if (get_bit_array(to_try, v)) {
      set_bit_array(data->clique, v, true);

      push_conditions(data->try_, depth + 1, 0, data->graph->neighbours[v]);
      push_conditions(data->ban, depth + 1, 0, data->graph->neighbours[v]);

      // recurse
      if (group == Fail) {
        if (EXIT
            == BronKerbosch(depth + 1,
                            rep_depth,
                            limit,
                            nr_found,
                            max,
                            size,
                            group,
                            data)) {
          return EXIT;
        }
      } else {
        Obj stabiliser = CALL_2ARGS(Stabilizer, group, INTOBJ_INT(v + 1));
        if (CALL_1ARGS(IsTrivial, stabiliser) == True) {
          stabiliser = Fail;
        }
        if (EXIT
            == BronKerbosch(depth + 1,
                            rep_depth + 1,
                            limit,
                            nr_found,
                            max,
                            size,
                            stabiliser,
                            data)) {
          return EXIT;
        }
      }

      pop_conditions(data->try_, depth + 1);
      pop_conditions(data->ban, depth + 1);
      data->to_try->height[0]--;
      set_bit_array(data->clique, v, false);

      if (group == Fail) {
        set_bit_array(get_conditions(data->try_, 0), v, false);
        set_bit_array(get_conditions(data->ban, 0), v, true);
      } else {
        data->orbit = CALL_2ARGS(Orbit, group, INTOBJ_INT(v + 1));
        set_bit_array_from_gap_list(data->temp_bitarray, data->orbit);
        complement_bit_arrays(
            get_conditions(data->try_, 0), data->temp_bitarray, nr);
        union_bit_arrays(get_conditions(data->ban, 0), data->temp_bitarray, nr);
      }
    }
  }
  return EXIT + 1;
}

// FuncDigraphsCliquesFinder is the main function to use the C implementation
// of Bron-Kerbosch algorithm
//
// The arguments are as follows:
//
// 1. digraphs_obj    the digraph to search for cliques in
// 2. hook_obj        a function to apply to every clique found, or Fail if no
//                    such function is needed
// 3. user_param_obj  GAP variable that can be used in the hook_obj, must be a
//                    plist if hook_obj is Fail
// 4. limit_obj       the maximum number of cliques to find
// 5. include_obj     a list of vertices of digraph_obj to required to be
// present in
//                    every clique found. The list needs to be invariant under
//                    aut_grp_obj or the full automorphism group if aut_grp_obj
//                    is Fail
// 6. exclude_obj     a list of vertices of digraph_obj which cannot be present
//                    in any of the cliques found. The list needs to be
//                    invariant under aut_grp_obj or the full automorphism
//                    group if aut_grp_obj is Fail
// 7. max_obj         True if only maximal cliques need to be found and False
//                    otherwise
// 8. size_obj        an integer specifying the size of cliques to be found
// 9. aut_grp_obj     an optional argument that can specify the automorphisms
//                    of the graph that will be used in the recursive search.
//                    If not given, the full automorphism group will be used.
//
// Remarks:
// 1. The function returns orbit representatives of cliques rather than all of
// the
//    cliques themselves.
// 2. Only one isolated vertex will be returned even if aut_grp_obj does not
//    act transitevely on all isolated vertices.

Obj FuncDigraphsCliquesFinder(Obj self, Obj args) {
  if (LEN_PLIST(args) != 8 && LEN_PLIST(args) != 9) {
    ErrorQuit("there must be 8 or 9 arguments, found %d,", LEN_PLIST(args), 0L);
  }
  Obj digraph_obj    = ELM_PLIST(args, 1);
  Obj hook_obj       = ELM_PLIST(args, 2);
  Obj user_param_obj = ELM_PLIST(args, 3);
  Obj limit_obj      = ELM_PLIST(args, 4);
  Obj include_obj    = ELM_PLIST(args, 5);
  Obj exclude_obj    = ELM_PLIST(args, 6);
  Obj max_obj        = ELM_PLIST(args, 7);
  Obj size_obj       = ELM_PLIST(args, 8);
  Obj aut_grp_obj    = Fail;

  if (LEN_PLIST(args) == 9) {
    aut_grp_obj = ELM_PLIST(args, 9);
  }

  // Validate the arguments
  if (CALL_1ARGS(IsDigraph, digraph_obj) != True) {
    ErrorQuit("the 1st argument must be a digraph, not %s,",
              (Int) TNAM_OBJ(digraph_obj),
              0L);
  } else if (DigraphNrVertices(digraph_obj) > MAXVERTS) {
    ErrorQuit("the 1st argument must have at most %d vertices, "
              "found %d,",
              MAXVERTS,
              DigraphNrVertices(digraph_obj));
  }
  if (hook_obj == Fail) {
    if (!IS_LIST(user_param_obj) || !IS_MUTABLE_OBJ(user_param_obj)) {
      ErrorQuit("the 2nd argument is fail and so the 3th argument must "
                "be a mutable list, not %s,",
                (Int) TNAM_OBJ(user_param_obj),
                0L);
    }
  } else if (!IS_FUNC(hook_obj) || NARG_FUNC(hook_obj) != 2) {
    ErrorQuit(
        "the 2nd argument must be a function with 2 arguments,", 0L, 0L);
  }
  if (!IS_INTOBJ(limit_obj) && limit_obj != Infinity) {
    ErrorQuit("the 4th argument must be an integer "
              "or infinity, not %s,",
              (Int) TNAM_OBJ(limit_obj),
              0L);
  } else if (IS_INTOBJ(limit_obj) && INT_INTOBJ(limit_obj) <= 0) {
    ErrorQuit("the 4th argument must be a positive integer, "
              "not %d,",
              INT_INTOBJ(limit_obj),
              0L);
  }
  if (!IS_LIST(include_obj) && include_obj != Fail) {
    ErrorQuit("the 5th argument must be a list or fail, not %s,",
              (Int) TNAM_OBJ(include_obj),
              0L);
  } else if (IS_LIST(include_obj)) {
    for (Int i = 1; i <= LEN_LIST(include_obj); ++i) {
      if (!ISB_LIST(include_obj, i)) {
        ErrorQuit("the 5th argument must be a dense list,", 0L, 0L);
      } else if (!IS_POS_INTOBJ(ELM_LIST(include_obj, i))) {
        ErrorQuit("the 5th argument must only contain positive "
                  "small integers, but found %s in position %d,",
                  (Int) TNAM_OBJ(ELM_LIST(include_obj, i)),
                  i);
      } else if (INT_INTOBJ(ELM_LIST(include_obj, i))
                 > DigraphNrVertices(digraph_obj)) {
        ErrorQuit("in the 5th argument position %d is out of range, "
                  "must be in the range [1, %d],",
                  i,
                  DigraphNrVertices(digraph_obj));
      } else if (INT_INTOBJ(POS_LIST(
                     include_obj, ELM_LIST(include_obj, i), INTOBJ_INT(0)))
                 < i) {
        ErrorQuit(
            "in the 5th argument position %d is a duplicate,", i, 0L);
      }
    }
  }
  if (!IS_LIST(exclude_obj) && exclude_obj != Fail) {
    ErrorQuit("the 6th argument must be a list or fail, not %s,",
              (Int) TNAM_OBJ(exclude_obj),
              0L);
  } else if (IS_LIST(exclude_obj)) {
    for (Int i = 1; i <= LEN_LIST(exclude_obj); ++i) {
      if (!ISB_LIST(exclude_obj, i)) {
        ErrorQuit("the 6th argument must be a dense list,", 0L, 0L);
      } else if (!IS_POS_INTOBJ(ELM_LIST(exclude_obj, i))) {
        ErrorQuit("the 6th argument must only contain positive "
                  "small integers, but found %s in position %d,",
                  (Int) TNAM_OBJ(ELM_LIST(exclude_obj, i)),
                  i);
      } else if (INT_INTOBJ(ELM_LIST(exclude_obj, i))
                 > DigraphNrVertices(digraph_obj)) {
        ErrorQuit("in the 6th argument position %d is out of range, "
                  "must be in the range [1, %d],",
                  i,
                  DigraphNrVertices(digraph_obj));
      } else if (INT_INTOBJ(POS_LIST(
                     exclude_obj, ELM_LIST(exclude_obj, i), INTOBJ_INT(0)))
                 < i) {
        ErrorQuit(
            "in the 6th argument position %d is a duplicate,", i, 0L);
      }
    }
  }
  if (max_obj != True && max_obj != False) {
    ErrorQuit("the 7th argument must true or false, not %s,",
              (Int) TNAM_OBJ(max_obj),
              0L);
  }
  if (!IS_POS_INTOBJ(size_obj) && size_obj != Fail) {
    ErrorQuit("the 8th argument must be a positive small integer "
              "or fail, not %s,",
              (Int) TNAM_OBJ(size_obj),
              0L);
  }

  if (aut_grp_obj != Fail) {
    if (CALL_1ARGS(IsPermGroup, aut_grp_obj) != True) {
      ErrorQuit("the 9th argument must be a permutation group "
                "or fail, not %s,",
                (Int) TNAM_OBJ(aut_grp_obj),
                0L);
    }
    Obj gens = CALL_1ARGS(GeneratorsOfGroup, aut_grp_obj);
    Int lmp  = INT_INTOBJ(CALL_1ARGS(LargestMovedPointPerms, gens));
    if (lmp > 0 && LEN_LIST(gens) >= lmp) {
      ErrorQuit("expected at most %d generators in the 9th argument "
                "but got %d,",
                lmp - 1,
                LEN_LIST(gens));
    }
    for (Int i = 1; i <= LEN_LIST(gens); ++i) {
      if (CALL_2ARGS(IsDigraphAutomorphism, digraph_obj, ELM_LIST(gens, i))
          != True) {
        ErrorQuit("expected group of automorphisms, but found a "
                  "non-automorphism in position %d of the group generators,",
                  i,
                  0L);
      }
    }
  } else {
    aut_grp_obj = CALL_1ARGS(AutomorphismGroup, digraph_obj);
  }

  // Check that include_obj and exclude_obj are invariant under aut_grp_obj
  Obj gens = CALL_1ARGS(GeneratorsOfGroup, aut_grp_obj);
  DIGRAPHS_ASSERT(IS_LIST(gens));
  DIGRAPHS_ASSERT(LEN_LIST(gens) > 0);
  for (Int i = 1; i <= LEN_LIST(gens); ++i) {
    if (include_obj != Fail
        && CALL_2ARGS(IsSubset,
                      include_obj,
                      CALL_2ARGS(OnTuples, include_obj, ELM_LIST(gens, i)))
               != True) {
      ErrorQuit("the 5th argument must be invariant under , "
                "or the full automorphism if is not given,",
                0L,
                0L);
    }
    if (exclude_obj != Fail
        && CALL_2ARGS(IsSubset,
                      exclude_obj,
                      CALL_2ARGS(OnTuples, exclude_obj, ELM_LIST(gens, i)))
               != True) {
      ErrorQuit("the 6th argument must be invariant under , "
                "or the full automorphism if is not given,",
                0L,
                0L);
    }
  }

  uint16_t size         = (size_obj == Fail ? 0 : INT_INTOBJ(size_obj));
  uint16_t include_size = (include_obj == Fail ? 0 : LEN_LIST(include_obj));
  uint16_t exclude_size = (exclude_obj == Fail ? 0 : LEN_LIST(exclude_obj));
  uint16_t nr           = DigraphNrVertices(digraph_obj);

  // Check the trivial cases:
  // The digraph has 0 vertices
  if (nr == 0) {
    Obj c = NEW_PLIST(T_PLIST, 0);
    if (hook_obj != Fail) {
      clique_hook_gap_list(user_param_obj, c, hook_obj);
    } else {
      ASS_LIST(user_param_obj, LEN_LIST(user_param_obj) + 1, c);
    }
    return user_param_obj;
  }
  // The desired clique is too small
  if (size != 0 && include_size > size) {
    return user_param_obj;
  }
  // The desired clique is too big
  if (size != 0 && size > nr - exclude_size) {
    return user_param_obj;
  }
  // Check if include and exclude have empty intersection
  if (include_size != 0 && exclude_size != 0) {
    bool* lookup =
        safe_calloc(DigraphNrVertices(digraph_obj) + 1, sizeof(bool));
    for (UInt i = 1; i <= include_size; ++i) {
      lookup[INT_INTOBJ(ELM_LIST(include_obj, i)) - 1] = true;
    }
    for (UInt i = 1; i <= exclude_size; ++i) {
      if (lookup[INT_INTOBJ(ELM_LIST(exclude_obj, i)) - 1]) {
        free(lookup);
        return user_param_obj;
      }
    }
    free(lookup);
  }
  // Check if the set we are trying to extend is a clique
  if (include_obj != Fail
      && CALL_2ARGS(IsClique, digraph_obj, include_obj) == False) {
    return user_param_obj;
  }
  uint64_t nr_found = 0;
  uint64_t limit =
      (limit_obj == Infinity ? SMALLINTLIMIT : INT_INTOBJ(limit_obj));
  bool max = (max_obj == True ? true : false);

  CliquesData* data = global_cliques_data();

  // Initialise all the variable which will be used to carry out the recursion
  if (!init_data_from_args(digraph_obj,
                           hook_obj,
                           user_param_obj,
                           include_obj,
                           exclude_obj,
                           max_obj,
                           &aut_grp_obj,
                           data)) {
    return user_param_obj;
  }
  // The clique we are trying to extend is already big enough
  if (size != 0 && include_size == size) {
    data->hook(data->user_param, data->clique, nr, data->gap_func);
    return user_param_obj;
  }

  // go!
  BronKerbosch(0,
               0,
               limit,
               &nr_found,
               max,
               (size == 0 ? size : size - include_size),
               aut_grp_obj,
               data);

  return user_param_obj;
}

quality95%

¤ Dauer der Verarbeitung: 0.20 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.