1 /********************************************************************************
2 **
3 ** conditions.h Data structure for homomorphisms search J. D. Mitchell
4 **
5 ** Copyright (C) 2019 - J. D. Mitchell
6 **
7 ** This file is free software, see the digraphs/LICENSE.
8 **
9 ********************************************************************************/
10
11 #ifndef DIGRAPHS_SRC_CONDITIONS_H_
12 #define DIGRAPHS_SRC_CONDITIONS_H_
13
14 // C headers
15 #include <stdbool.h> // for false, true
16 #include <stdint.h> // for uint16_t, uint64_t
17 #include <string.h> // for NULL, memcpy, size_t
18
19 // GAP headers
20 #include "src/system.h" // for ALWAYS_INLINE
21
22 // Digraphs headers
23 #include "bitarray.h" // for BitArray, intersect_bit_arrays, size_b...
24 #include "digraphs-debug.h" // for DIGRAPHS_ASSERT
25
26 // This file contains a data structure for keeping track of what possible
27 // values a uint16_t can be mapped to by a partially defined homomorphism, given
28 // the existing values of the homomorphism.
29 //
30 // If <nr1> is the number of vertices in the source di/graph and <nr2> is the
31 // number of vertices in the range di/graph, then a Conditions object looks
32 // like:
33 //
34 // ^
35 // |
36 // |
37 //
38 // n +------------+
39 // r | BitArray* |
40 // 1 | length nr2 |
41 // +------------+ +------------+
42 // r | BitArray* | | BitArray* |
43 // o | length nr2 | | length nr2 |
44 // w +------------+------------+ +------------+
45 // s | BitArray* | BitArray* | | BitArray* |
46 // | length nr2 | length nr2 | | length nr2 |
47 // | +------------+------------+------------+ - - -+------------+
48 // | | BitArray* | BitArray* | BitArray* | | BitArray* |
49 // | | length nr2 | length nr2 | length nr2 | | length nr2 |
50 // v +------------+------------+------------+ - - -+------------+
51 //
52 // <----------------------- nr1 columns ----------------------->
53 //
54 // The BitArray pointed to in row <i+1> and column <j> row is the intersection
55 // of the BitArray pointed to in row <i> and column <j> with some other
56 // BitArray (the things adjacent to some uint16_t in di/graph2).
57 //
58
59 struct conditions_struct {
60 BitArray** bit_array; // nr1 * nr1 array of bit arrays of length nr2
61 uint16_t* changed;
62 uint16_t* height;
63 uint16_t* sizes;
64 uint16_t nr1;
65 uint16_t nr2;
66 };
67
68 typedef struct conditions_struct Conditions;
69
70 //! Returns a pointer to a Conditions with one complete row where every bit is
71 //! set to true.
72 Conditions* new_conditions(uint16_t const nr1, uint16_t const nr2);
73
74 //! Clears all the information in the Conditions object, and puts it back into
75 //! the state it was when it was initially created. The second and third
76 //! arguments indicate how much of the Conditions object is to be cleared. I.e.
77 //! if we want to use the Conditions object in a homomorphism search for graphs
78 //! with 5 and 19 vertices, then we clear the Conditions object with 2nd and
79 //! 3rd parameters 5, and 19.
clear_conditions(Conditions * const conditions,uint16_t const nr1,uint16_t const nr2)80 static inline void clear_conditions(Conditions* const conditions,
81 uint16_t const nr1,
82 uint16_t const nr2) {
83 DIGRAPHS_ASSERT(conditions != NULL);
84 DIGRAPHS_ASSERT(nr1 != 0);
85 DIGRAPHS_ASSERT(nr2 != 0);
86
87 for (uint64_t i = 0; i < nr1 * nr1; i++) {
88 init_bit_array(conditions->bit_array[i], false, nr2);
89 }
90
91 for (uint64_t i = 0; i < nr1; i++) {
92 init_bit_array(conditions->bit_array[i], true, nr2);
93 conditions->changed[i + 1] = i;
94 conditions->changed[(nr1 + 1) * i] = 0;
95 conditions->height[i] = 1;
96 }
97 conditions->changed[0] = nr1;
98 conditions->nr1 = nr1;
99 conditions->nr2 = nr2;
100 }
101
102 //! Free an entire Conditions object pointed to by
103 void free_conditions(Conditions* const conditions);
104
105 //! Returns the top most BitArray* in column \p i.
get_conditions(Conditions const * const conditions,uint16_t const i)106 static inline BitArray* get_conditions(Conditions const* const conditions,
107 uint16_t const i) {
108 DIGRAPHS_ASSERT(conditions != NULL);
109 DIGRAPHS_ASSERT(i < conditions->nr1);
110 return conditions
111 ->bit_array[conditions->nr1 * (conditions->height[i] - 1) + i];
112 }
113
114 //! Store the size of the BitArray pointed to at the top of column \p i.
store_size_conditions(Conditions * const conditions,uint16_t const i)115 static inline void store_size_conditions(Conditions* const conditions,
116 uint16_t const i) {
117 DIGRAPHS_ASSERT(conditions != NULL);
118 DIGRAPHS_ASSERT(i < conditions->nr1);
119 uint16_t const nr1 = conditions->nr1;
120 conditions->sizes[nr1 * (conditions->height[i] - 1) + i] =
121 size_bit_array(get_conditions(conditions, i), conditions->nr2);
122 }
123
124 //! Copy the top of the <i>th column of the <conditions> and intersect it with
125 //! <bit_array> and then push this onto the top of the <i>th column.
push_conditions(Conditions * const conditions,uint16_t const depth,uint16_t const i,BitArray const * const bit_array)126 static ALWAYS_INLINE void push_conditions(Conditions* const conditions,
127 uint16_t const depth,
128 uint16_t const i,
129 BitArray const* const bit_array) {
130 DIGRAPHS_ASSERT(conditions != NULL);
131 DIGRAPHS_ASSERT(i < conditions->nr1);
132 DIGRAPHS_ASSERT(depth < conditions->nr1);
133
134 uint16_t const nr1 = conditions->nr1;
135
136 memcpy((void*) conditions->bit_array[nr1 * conditions->height[i] + i]->blocks,
137 (void*) conditions->bit_array[nr1 * (conditions->height[i] - 1) + i]
138 ->blocks,
139 (size_t) conditions->bit_array[0]->nr_blocks * sizeof(Block));
140
141 conditions->changed[(nr1 + 1) * depth]++;
142 conditions
143 ->changed[(nr1 + 1) * depth + conditions->changed[(nr1 + 1) * depth]] = i;
144
145 conditions->height[i]++;
146
147 if (bit_array != NULL) {
148 intersect_bit_arrays(
149 get_conditions(conditions, i), bit_array, conditions->nr2);
150 }
151 }
152
153 //! Pop the tops off all of the columns which were pushed on at depth \p depth.
pop_conditions(Conditions * const conditions,uint16_t const depth)154 static inline void pop_conditions(Conditions* const conditions,
155 uint16_t const depth) {
156 DIGRAPHS_ASSERT(conditions != NULL);
157 DIGRAPHS_ASSERT(depth < conditions->nr1);
158
159 uint16_t const nr1 = conditions->nr1;
160
161 for (uint16_t i = 1; i < conditions->changed[(nr1 + 1) * depth] + 1; i++) {
162 conditions->height[conditions->changed[(nr1 + 1) * depth + i]]--;
163 }
164 conditions->changed[(nr1 + 1) * depth] = 0;
165 }
166
167 //! Return the size of the BitArray pointed to by the top of the \p i-th
168 //! column.
size_conditions(Conditions const * const conditions,uint16_t const i)169 static inline uint16_t size_conditions(Conditions const* const conditions,
170 uint16_t const i) {
171 DIGRAPHS_ASSERT(conditions != NULL);
172 DIGRAPHS_ASSERT(i < conditions->nr1);
173 return conditions->sizes[conditions->nr1 * (conditions->height[i] - 1) + i];
174 }
175
176 #endif // DIGRAPHS_SRC_CONDITIONS_H_
177