1 /*
2 Copyright (C) 2016 Arb authors
3
4 This file is part of Arb.
5
6 Arb is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #ifndef BOOL_MAT_H
13 #define BOOL_MAT_H
14
15 #ifdef BOOL_MAT_INLINES_C
16 #define BOOL_MAT_INLINE
17 #else
18 #define BOOL_MAT_INLINE static __inline__
19 #endif
20
21 #include <stdio.h>
22 #include "flint/flint.h"
23 #include "flint/fmpz_mat.h"
24
25 #ifndef flint_abort
26 #if __FLINT_RELEASE <= 20502
27 #define flint_abort abort
28 #endif
29 #endif
30
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34
35 /* currently defined in the arb module, but global to the library */
36 double arb_test_multiplier(void);
37
38 typedef struct
39 {
40 int *entries;
41 slong r;
42 slong c;
43 int **rows;
44 }
45 bool_mat_struct;
46
47 typedef bool_mat_struct bool_mat_t[1];
48
49 #define bool_mat_nrows(mat) ((mat)->r)
50 #define bool_mat_ncols(mat) ((mat)->c)
51
52 BOOL_MAT_INLINE int
bool_mat_get_entry(const bool_mat_t mat,slong i,slong j)53 bool_mat_get_entry(const bool_mat_t mat, slong i, slong j)
54 {
55 return mat->rows[i][j];
56 }
57
58 BOOL_MAT_INLINE void
bool_mat_set_entry(bool_mat_t mat,slong i,slong j,int value)59 bool_mat_set_entry(bool_mat_t mat, slong i, slong j, int value)
60 {
61 mat->rows[i][j] = value;
62 }
63
64 /* Memory management */
65
66 void bool_mat_init(bool_mat_t mat, slong r, slong c);
67
68 void bool_mat_clear(bool_mat_t mat);
69
70 BOOL_MAT_INLINE void
bool_mat_swap(bool_mat_t mat1,bool_mat_t mat2)71 bool_mat_swap(bool_mat_t mat1, bool_mat_t mat2)
72 {
73 bool_mat_struct t = *mat1;
74 *mat1 = *mat2;
75 *mat2 = t;
76 }
77
78 /* Conversions */
79
80 void bool_mat_set(bool_mat_t dest, const bool_mat_t src);
81
82 /* Random generation */
83
84 void bool_mat_randtest(bool_mat_t mat, flint_rand_t state);
85
86 void bool_mat_randtest_diagonal(bool_mat_t mat, flint_rand_t state);
87
88 void bool_mat_randtest_nilpotent(bool_mat_t mat, flint_rand_t state);
89
90 /* I/O */
91
92 void bool_mat_fprint(FILE * file, const bool_mat_t mat);
93
94 BOOL_MAT_INLINE void
bool_mat_print(const bool_mat_t mat)95 bool_mat_print(const bool_mat_t mat)
96 {
97 bool_mat_fprint(stdout, mat);
98 }
99
100 /* Comparisons */
101
102 int bool_mat_equal(const bool_mat_t mat1, const bool_mat_t mat2);
103
104 int bool_mat_any(const bool_mat_t mat);
105
106 int bool_mat_all(const bool_mat_t mat);
107
108 int bool_mat_is_diagonal(const bool_mat_t mat);
109
110 int bool_mat_is_lower_triangular(const bool_mat_t mat);
111
112 int bool_mat_is_transitive(const bool_mat_t mat);
113
114 int bool_mat_is_nilpotent(const bool_mat_t mat);
115
116 BOOL_MAT_INLINE int
bool_mat_is_empty(const bool_mat_t mat)117 bool_mat_is_empty(const bool_mat_t mat)
118 {
119 return (mat->r == 0) || (mat->c == 0);
120 }
121
122 BOOL_MAT_INLINE int
bool_mat_is_square(const bool_mat_t mat)123 bool_mat_is_square(const bool_mat_t mat)
124 {
125 return (mat->r == mat->c);
126 }
127
128 /* Special matrices */
129
130 void bool_mat_zero(bool_mat_t mat);
131
132 void bool_mat_one(bool_mat_t mat);
133
134 void bool_mat_directed_path(bool_mat_t mat);
135
136 void bool_mat_directed_cycle(bool_mat_t mat);
137
138 /* Transpose */
139
140 void bool_mat_transpose(bool_mat_t mat1, const bool_mat_t mat2);
141
142 /* Arithmetic */
143
144 void bool_mat_complement(bool_mat_t mat1, const bool_mat_t mat2);
145
146 void bool_mat_add(bool_mat_t res, const bool_mat_t mat1, const bool_mat_t mat2);
147
148 void bool_mat_mul(bool_mat_t res, const bool_mat_t mat1, const bool_mat_t mat2);
149
150 void bool_mat_mul_entrywise(bool_mat_t res, const bool_mat_t mat1, const bool_mat_t mat2);
151
152 void bool_mat_pow_ui(bool_mat_t B, const bool_mat_t A, ulong exp);
153
154 BOOL_MAT_INLINE void
bool_mat_sqr(bool_mat_t B,const bool_mat_t A)155 bool_mat_sqr(bool_mat_t B, const bool_mat_t A)
156 {
157 bool_mat_mul(B, A, A);
158 }
159
160 /* Special functions */
161
162 int bool_mat_trace(const bool_mat_t mat);
163
164 slong bool_mat_nilpotency_degree(const bool_mat_t mat);
165
166 void bool_mat_transitive_closure(bool_mat_t dest, const bool_mat_t src);
167
168 slong bool_mat_get_strongly_connected_components(slong *partition, const bool_mat_t A);
169
170 slong bool_mat_all_pairs_longest_walk(fmpz_mat_t B, const bool_mat_t A);
171
172 #ifdef __cplusplus
173 }
174 #endif
175
176 #endif
177