1 /* This file is part of Conauto. 2 3 Conauto is free software: you can redistribute it and/or modify 4 it under the terms of the GNU General Public License as published by 5 the Free Software Foundation, either version 3 of the License, or 6 (at your option) any later version. 7 8 Conauto is distributed in the hope that it will be useful, 9 but WITHOUT ANY WARRANTY; without even the implied warranty of 10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 GNU General Public License for more details. 12 13 You should have received a copy of the GNU General Public License 14 along with Conauto. If not, see <http://www.gnu.org/licenses/>. 15 */ 16 17 /* data structures and function to generate sequences of partitions */ 18 19 #ifndef _SEQPART_H_ 20 #define _SEQPART_H_ 21 22 #include <stdint.h> 23 24 #include "graph.h" 25 #include "groups.h" 26 #include "mismatches.h" 27 28 #define SET 0 29 #define VERTEX 1 30 #define BACKTR 2 31 #define UNKNOWN 3 32 #define LAST 4 33 34 #define TRUE 1 35 #define FALSE 0 36 37 #define EXCHANGE( a, b, type ) { type aux; aux=a; a=b; b=aux; } 38 39 typedef struct{ 40 uint16_t* vertices; 41 uint16_t* belongs; 42 uint16_t* start; 43 uint64_t* attrib; 44 uint64_t* adeg; 45 MismatchCollection* mm_collection; 46 uint8_t* affected; 47 uint16_t* discarded_cells; 48 Graph_Orbits *go; 49 int backtrack_level; 50 int auto_search_limit; 51 uint16_t pivot; 52 uint16_t noc; /* number of cells in this partition */ 53 uint16_t nodc; /* number of discarded cells */ 54 uint16_t nopdv; /* number of previously discarded vertices */ 55 uint16_t no; /* number of orbits */ 56 uint8_t tor; /* type of refinement applied */ 57 } Partition; 58 59 typedef struct { 60 Partition* partition; 61 int lp; /* last partition in the sequence */ 62 uint16_t nodv; /* number of discarded vertices */ 63 uint16_t* discarded_vert; /* vertices that have been discarded */ 64 uint8_t* valid_new; 65 uint8_t* valid_old; 66 uint64_t *num_adj; 67 uint32_t nodes; 68 uint32_t nodes_limit; 69 uint32_t dcs_nodes; 70 uint32_t bad_nodes; 71 } SeqPart; 72 73 void free_partitions ( SeqPart *sp, int level ); 74 75 void allocate_partition ( SeqPart *sp, int level, uint16_t noc, uint16_t num_vert ); 76 77 uint16_t best_pivot ( const struct graph *g, SeqPart *sp, int level, uint8_t choose_not_valid ); 78 79 int is_subpartition ( SeqPart *sp, int level, int bl ); 80 81 void free_seqpart ( SeqPart *sp ); 82 83 void allocate_seqpart ( SeqPart *sp, uint32_t size ); 84 85 void generate_degree_partition ( SeqPart *sp, const struct graph *g ); 86 87 void exchange_partitions ( Partition *p1, Partition *p2 ); 88 89 void generate_seqpart ( SeqPart *sp, const struct graph *g, int level ); 90 91 int degree_partitions_are_compatible ( Partition *p1, Partition *p2 ); 92 93 void compute_auto_search_limits ( SeqPart *sp ); 94 95 void compute_backtrack_levels ( SeqPart *sp ); 96 97 uint16_t num_backtrack_levels ( SeqPart *sp ); 98 99 void find_automorphisms ( const struct graph *g, SeqPart *sp, Perm_Group *pg ); 100 101 int match ( int level, uint16_t *old_vertices, const struct graph *h, Perm_Group *pg, const struct graph *g, SeqPart *sp, Graph_Orbits *go, uint16_t *iso, uint16_t *perm_sets, uint16_t *leaders ); 102 103 #endif 104 105