Quelle homos-graphs.c Sprache: C

/********************************************************************************
**
**  homos-graphs.h  (Di)graphs for the homomorphism finder J. D. Mitchell
**
**  Copyright (C) 2019 - J. D. Mitchell
**
**  This file is free software, see the digraphs/LICENSE.
**
********************************************************************************/

#include "homos-graphs.h"

// C headers
#include <stdlib.h>  // for free, malloc, NULL

// GAP headers
#include "gap-includes.h"  // for Obj, Int

// Digraphs headers
#include "digraphs-config.h"  // for DIGRAPHS_WITH_INCLUDED_BLISS
#include "digraphs-debug.h"   // for DIGRAPHS_ASSERT
#include "safemalloc.h"       // for safe_malloc
#include "schreier-sims.h"    // for PERM_DEGREE

extern Obj GeneratorsOfGroup;

Digraph* new_digraph(uint16_t const nr_verts) {
  DIGRAPHS_ASSERT(nr_verts <= MAXVERTS);
  Digraph* digraph        = safe_malloc(sizeof(Digraph));
  digraph->in_neighbours  = safe_malloc(nr_verts * sizeof(BitArray));
  digraph->out_neighbours = safe_malloc(nr_verts * sizeof(BitArray));

  for (uint16_t i = 0; i < nr_verts; i++) {
    digraph->in_neighbours[i]  = new_bit_array(nr_verts);
    digraph->out_neighbours[i] = new_bit_array(nr_verts);
  }
  digraph->nr_vertices = nr_verts;
  digraph->capacity    = nr_verts;
  return digraph;
}

Graph* new_graph(uint16_t const nr_verts) {
  DIGRAPHS_ASSERT(nr_verts <= MAXVERTS);
  Graph* graph      = safe_malloc(sizeof(Graph));
  graph->neighbours = safe_malloc(nr_verts * sizeof(BitArray));

  for (uint16_t i = 0; i < nr_verts; i++) {
    graph->neighbours[i] = new_bit_array(nr_verts);
  }
  graph->nr_vertices = nr_verts;
  graph->capacity    = nr_verts;

  return graph;
}

// free_digraph is not currently used, but kept in case it is required in
// the future. JDM 2019

void free_digraph(Digraph* const digraph) {
  DIGRAPHS_ASSERT(digraph != NULL);

  uint16_t const nr = digraph->capacity;

  for (uint16_t i = 0; i < nr; i++) {
    free_bit_array(digraph->in_neighbours[i]);
    free_bit_array(digraph->out_neighbours[i]);
  }
  free(digraph->in_neighbours);
  free(digraph->out_neighbours);
  free(digraph);
}

// free_graph is not currently used, but kept in case it is required in
// the future. JDM 2019

void free_graph(Graph* const graph) {
  DIGRAPHS_ASSERT(graph != NULL);
  uint16_t const nr = graph->capacity;
  for (uint16_t i = 0; i < nr; i++) {
    free_bit_array(graph->neighbours[i]);
  }
  free(graph->neighbours);
  free(graph);
}

void clear_digraph(Digraph* const digraph, uint16_t const nr_verts) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(nr_verts <= MAXVERTS);
  DIGRAPHS_ASSERT(nr_verts <= digraph->capacity);
  for (uint16_t i = 0; i < nr_verts; i++) {
    init_bit_array(digraph->in_neighbours[i], false, nr_verts);
    init_bit_array(digraph->out_neighbours[i], false, nr_verts);
  }
  digraph->nr_vertices = nr_verts;
}

void clear_graph(Graph* const graph, uint16_t const nr_verts) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(nr_verts <= MAXVERTS);
  DIGRAPHS_ASSERT(nr_verts <= graph->capacity);

  for (uint16_t i = 0; i < nr_verts; i++) {
    init_bit_array(graph->neighbours[i], false, nr_verts);
  }
  graph->nr_vertices = nr_verts;
}

void add_edge_digraph(Digraph* const digraph,
                      uint16_t const i,
                      uint16_t const j) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(i < digraph->nr_vertices);
  DIGRAPHS_ASSERT(j < digraph->nr_vertices);
  set_bit_array(digraph->out_neighbours[i], j, true);
  set_bit_array(digraph->in_neighbours[j], i, true);
}

void add_edge_graph(Graph* const graph, uint16_t const i, uint16_t const j) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(i < graph->nr_vertices);
  DIGRAPHS_ASSERT(j < graph->nr_vertices);
  set_bit_array(graph->neighbours[i], j, true);
  set_bit_array(graph->neighbours[j], i, true);
}

#ifdef DIGRAPHS_WITH_INCLUDED_BLISS
static void init_bliss_graph_from_digraph(Digraph const* const  digraph,
                                          uint16_t const* const colors,
                                          BlissGraph*           bg) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(colors != NULL);

  bliss_digraphs_clear(bg);
  uint16_t       out_color = 0;
  uint16_t const n         = digraph->nr_vertices;
  for (uint16_t i = 0; i < n; i++) {
    out_color = (colors[i] >= out_color ? colors[i] + 1 : out_color);
    bliss_digraphs_change_color(bg, i, colors[i]);
  }
  uint16_t const in_color = out_color + 1;
  for (uint16_t i = 0; i < n; i++) {
    bliss_digraphs_change_color(bg, i + n, out_color);
    bliss_digraphs_change_color(bg, i + 2 * n, in_color);
    bliss_digraphs_add_edge(bg, i, i + n);
    bliss_digraphs_add_edge(bg, i + 2 * n, i);
  }
  for (uint16_t i = 0; i < n; i++) {
    for (uint16_t j = 0; j < n; j++) {
      if (is_adjacent_digraph(digraph, i, j)) {
        bliss_digraphs_add_edge(bg, i + n, j + 2 * n);
      }
    }
  }
}
#else
static BlissGraph* new_bliss_graph_from_digraph(Digraph const* const  digraph,
                                                uint16_t const* const colors) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(colors != NULL);
  BlissGraph*    bg;
  uint16_t       out_color = 0;
  uint16_t const n         = digraph->nr_vertices;
  bg                       = bliss_digraphs_new(0);
  for (uint16_t i = 0; i < n; i++) {
    out_color = (colors[i] >= out_color ? colors[i] + 1 : out_color);
    bliss_digraphs_add_vertex(bg, colors[i]);
  }
  uint16_t const in_color = out_color + 1;
  for (uint16_t i = n; i < 2 * n; i++) {
    bliss_digraphs_add_vertex(bg, out_color);
  }
  for (uint16_t i = 0; i < n; i++) {
    bliss_digraphs_add_vertex(bg, in_color);
    bliss_digraphs_add_edge(bg, i, i + n);
    bliss_digraphs_add_edge(bg, i + 2 * n, i);
  }
  for (uint16_t i = 0; i < n; i++) {
    for (uint16_t j = 0; j < n; j++) {
      if (is_adjacent_digraph(digraph, i, j)) {
        bliss_digraphs_add_edge(bg, i + n, j + 2 * n);
      }
    }
  }
  return bg;
}
#endif

#ifdef DIGRAPHS_WITH_INCLUDED_BLISS
static void init_bliss_graph_from_graph(Graph const* const    graph,
                                        uint16_t const* const colors,
                                        BlissGraph*           bg) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(colors != NULL);
  bliss_digraphs_clear(bg);
  uint16_t const n = graph->nr_vertices;
  for (uint16_t i = 0; i < n; i++) {
    bliss_digraphs_change_color(bg, i, colors[i]);
  }
  for (uint16_t i = 0; i < n; i++) {
    for (uint16_t j = 0; j < n; j++) {
      if (is_adjacent_graph(graph, i, j)) {
        bliss_digraphs_add_edge(bg, i, j);
      }
    }
  }
}
#else
static BlissGraph* new_bliss_graph_from_graph(Graph const* const    graph,
                                              uint16_t const* const colors) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(colors != NULL);
  BlissGraph*    bg;
  uint16_t const n = graph->nr_vertices;
  bg               = bliss_digraphs_new(0);
  for (uint16_t i = 0; i < n; i++) {
    bliss_digraphs_add_vertex(bg, colors[i]);
  }
  for (uint16_t i = 0; i < n; i++) {
    for (uint16_t j = 0; j < n; j++) {
      if (is_adjacent_graph(graph, i, j)) {
        bliss_digraphs_add_edge(bg, i, j);
      }
    }
  }
  return bg;
}
#endif

static void bliss_hook(void*               user_param_arg,  // perm_coll!
                       unsigned int        N,
                       const unsigned int* aut) {
  Perm               p   = new_perm(PERM_DEGREE);
  unsigned int const min = (N < PERM_DEGREE ? N : PERM_DEGREE);
  for (uint16_t i = 0; i < min; i++) {
    DIGRAPHS_ASSERT(aut[i] < min);
    p[i] = aut[i];
  }
  for (uint16_t i = min; i < PERM_DEGREE; i++) {
    p[i] = i;
  }
  add_perm_coll((PermColl*) user_param_arg, p);
  free(p);
}

#ifdef DIGRAPHS_WITH_INCLUDED_BLISS
void automorphisms_digraph(Digraph const* const  digraph,
                           uint16_t const* const colors,
                           PermColl*             out,
                           BlissGraph*           bg) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(out != NULL);
  DIGRAPHS_ASSERT(bg != NULL);
  clear_perm_coll(out);
  out->degree = PERM_DEGREE;
  init_bliss_graph_from_digraph(digraph, colors, bg);
  bliss_digraphs_find_automorphisms(bg, bliss_hook, out, 0);
}
#else
void automorphisms_digraph(Digraph const* const  digraph,
                           uint16_t const* const colors,
                           PermColl*             out) {
  DIGRAPHS_ASSERT(digraph != NULL);
  DIGRAPHS_ASSERT(out != NULL);
  clear_perm_coll(out);
  out->degree    = PERM_DEGREE;
  BlissGraph* bg = new_bliss_graph_from_digraph(digraph, colors);
  bliss_digraphs_find_automorphisms(bg, bliss_hook, out, 0);
  bliss_digraphs_release(bg);
}
#endif

#ifdef DIGRAPHS_WITH_INCLUDED_BLISS
void automorphisms_graph(Graph const* const    graph,
                         uint16_t const* const colors,
                         PermColl*             out,
                         BlissGraph*           bg) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(out != NULL);
  DIGRAPHS_ASSERT(bg != NULL);
  clear_perm_coll(out);
  out->degree = PERM_DEGREE;
  init_bliss_graph_from_graph(graph, colors, bg);
  bliss_digraphs_find_automorphisms(bg, bliss_hook, out, 0);
}
#else
void automorphisms_graph(Graph const* const    graph,
                         uint16_t const* const colors,
                         PermColl*             out) {
  DIGRAPHS_ASSERT(graph != NULL);
  DIGRAPHS_ASSERT(out != NULL);
  clear_perm_coll(out);
  out->degree    = PERM_DEGREE;
  BlissGraph* bg = new_bliss_graph_from_graph(graph, colors);
  bliss_digraphs_find_automorphisms(bg, bliss_hook, out, 0);
  bliss_digraphs_release(bg);
}
#endif

quality89%

¤ Dauer der Verarbeitung: 0.12 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.