Quelle conditions.h Sprache: C

/********************************************************************************
**
**  conditions.h  Data structure for homomorphisms search     J. D. Mitchell
**
**  Copyright (C) 2019 - J. D. Mitchell
**
**  This file is free software, see the digraphs/LICENSE.
**
********************************************************************************/

#ifndef DIGRAPHS_SRC_CONDITIONS_H_
#define DIGRAPHS_SRC_CONDITIONS_H_

// C headers
#include <stdbool.h>  // for false, true
#include <stdint.h>   // for uint16_t, uint64_t
#include <string.h>   // for NULL, memcpy, size_t

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

// Digraphs headers
#include "bitarray.h"        // for BitArray, intersect_bit_arrays, size_b...
#include "digraphs-debug.h"  // for DIGRAPHS_ASSERT

// This file contains a data structure for keeping track of what possible
// values a uint16_t can be mapped to by a partially defined homomorphism, given
// the existing values of the homomorphism.
//
// If <nr1> is the number of vertices in the source di/graph and <nr2> is the
// number of vertices in the range di/graph, then a Conditions object looks
// like:
//
//  ^
//  |
//  |
//
//  n                +------------+
//  r                | BitArray*  |
//  1                | length nr2 |
//                   +------------+                    +------------+
//  r                | BitArray*  |                    | BitArray*  |
//  o                | length nr2 |                    | length nr2 |
//  w                +------------+------------+       +------------+
//  s                | BitArray*  | BitArray*  |       | BitArray*  |
//                   | length nr2 | length nr2 |       | length nr2 |
//  |   +------------+------------+------------+ - -  -+------------+
//  |   | BitArray*  | BitArray*  | BitArray*  |       | BitArray*  |
//  |   | length nr2 | length nr2 | length nr2 |       | length nr2 |
//  v   +------------+------------+------------+ - -  -+------------+
//
//      <----------------------- nr1 columns ----------------------->
//
//  The BitArray pointed to in row <i+1> and column <j> row is the intersection
//  of the BitArray pointed to in row <i> and column <j> with some other
//  BitArray (the things adjacent to some uint16_t in di/graph2).
//

struct conditions_struct {
  BitArray** bit_array;  // nr1 * nr1 array of bit arrays of length nr2
  uint16_t*  changed;
  uint16_t*  height;
  uint16_t*  sizes;
  uint16_t   nr1;
  uint16_t   nr2;
  uint64_t   size;
};

typedef struct conditions_struct Conditions;

//! Returns a pointer to a Conditions with one complete row where every bit is
//! set to true.
Conditions* new_conditions(uint16_t const nr1, uint16_t const nr2);

//! Clears all the information in the Conditions object, and puts it back into
//! the state it was when it was initially created. The second and third
//! arguments indicate how much of the Conditions object is to be cleared. I.e.
//! if we want to use the Conditions object in a homomorphism search for graphs
//! with 5 and 19 vertices, then we clear the Conditions object with 2nd and
//! 3rd parameters 5, and 19.
static inline void clear_conditions(Conditions* const conditions,
                                    uint16_t const    nr1,
                                    uint16_t const    nr2) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(nr1 != 0);
  DIGRAPHS_ASSERT(nr2 != 0);

  for (uint64_t i = 0; i < nr1 * nr1; i++) {
    init_bit_array(conditions->bit_array[i], false, nr2);
  }

  for (uint64_t i = 0; i < nr1; i++) {
    init_bit_array(conditions->bit_array[i], true, nr2);
    conditions->changed[i + 1]         = i;
    conditions->changed[(nr1 + 1) * i] = 0;
    conditions->height[i]              = 1;
  }
  conditions->changed[0] = nr1;
  conditions->nr1        = nr1;
  conditions->nr2        = nr2;
}

//! Free an entire Conditions object pointed to by
void free_conditions(Conditions* const conditions);

//! Returns the top most BitArray* in column \p i.
static inline BitArray* get_conditions(Conditions const* const conditions,
                                       uint16_t const          i) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(i < conditions->nr1);
  return conditions
      ->bit_array[conditions->nr1 * (conditions->height[i] - 1) + i];
}

//! Store the size of the BitArray pointed to at the top of column \p i.
static inline void store_size_conditions(Conditions* const conditions,
                                         uint16_t const    i) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(i < conditions->nr1);
  uint16_t const nr1 = conditions->nr1;
  conditions->sizes[nr1 * (conditions->height[i] - 1) + i] =
      size_bit_array(get_conditions(conditions, i), conditions->nr2);
}

//! Copy the top of the <i>th column of the <conditions> and intersect it with
//! <bit_array> and then push this onto the top of the <i>th column.
static ALWAYS_INLINE void push_conditions(Conditions* const     conditions,
                                          uint16_t const        depth,
                                          uint16_t const        i,
                                          BitArray const* const bit_array) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(i < conditions->nr1);
  DIGRAPHS_ASSERT(depth < conditions->nr1);

  uint16_t const nr1 = conditions->nr1;

  memcpy((void*) conditions->bit_array[nr1 * conditions->height[i] + i]->blocks,
         (void*) conditions->bit_array[nr1 * (conditions->height[i] - 1) + i]
             ->blocks,
         (size_t) conditions->bit_array[0]->nr_blocks * sizeof(Block));

  conditions->changed[(nr1 + 1) * depth]++;
  conditions
      ->changed[(nr1 + 1) * depth + conditions->changed[(nr1 + 1) * depth]] = i;

  conditions->height[i]++;

  if (bit_array != NULL) {
    intersect_bit_arrays(
        get_conditions(conditions, i), bit_array, conditions->nr2);
  }
}

//! Pop the tops off all of the columns which were pushed on at depth \p depth.
static inline void pop_conditions(Conditions* const conditions,
                                  uint16_t const    depth) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(depth < conditions->nr1);

  uint16_t const nr1 = conditions->nr1;

  for (uint16_t i = 1; i < conditions->changed[(nr1 + 1) * depth] + 1; i++) {
    conditions->height[conditions->changed[(nr1 + 1) * depth + i]]--;
  }
  conditions->changed[(nr1 + 1) * depth] = 0;
}

//! Return the size of the BitArray pointed to by the top of the \p i-th
//! column.
static inline uint16_t size_conditions(Conditions const* const conditions,
                                       uint16_t const          i) {
  DIGRAPHS_ASSERT(conditions != NULL);
  DIGRAPHS_ASSERT(i < conditions->nr1);
  return conditions->sizes[conditions->nr1 * (conditions->height[i] - 1) + i];
}

#endif  // DIGRAPHS_SRC_CONDITIONS_H_

quality89%

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