dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
coloring.h
Go to the documentation of this file.
1// Copyright 2024 Markus Anders
2// This file is part of dejavu 2.0.
3// See LICENSE for extended copyright information.
4
5#ifndef DEJAVU_COLORING_H
6#define DEJAVU_COLORING_H
7
8#include <vector>
9#include <cassert>
10#include <cstring>
11#include "utility.h"
12
13namespace dejavu { namespace ds {
14 // (need to nest namespaces due to C++ 14)
15
23 class coloring {
24 public:
25 int *lab = nullptr;
26 int *ptn = nullptr;
27 int *vertex_to_col = nullptr;
28 int *vertex_to_lab = nullptr;
31 int cells = 1;
32 int domain_size = 0;
34 private:
35 int *alloc_pt = nullptr;
36
42 void alloc(int sz) {
43 dej_assert(sz >= 0);
44
45 if (alloc_pt) dealloc();
46 alloc_pt = (int *) malloc(sz * 4 * sizeof(int));
47 dej_assert(alloc_pt != nullptr);
48
49 lab = alloc_pt;
50 ptn = lab + sz;
51 vertex_to_col = lab + sz * 2;
52 vertex_to_lab = lab + sz * 3;
53
54 domain_size = sz;
55 }
56
60 void dealloc() {
61 if (alloc_pt) free(alloc_pt);
62 lab = nullptr;
63 ptn = nullptr;
64 vertex_to_col = nullptr;
65 vertex_to_lab = nullptr;
66
67 domain_size = 0;
68 };
69
70 public:
72 if (alloc_pt) {
73 dealloc();
74 }
75 }
76
83 void copy_ptn(coloring *c) const {
84 dej_assert(alloc_pt);
85 dej_assert(c->alloc_pt);
87 memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
88 }
89
99 if (alloc_pt) {
100 if (domain_size != c->domain_size) {
101 dealloc();
102 } else {
103 cells = c->cells;
104 memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
105 return;
106 }
107 }
108
109 if (!alloc_pt) alloc(c->domain_size);
110
111 memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
112 memcpy(lab, c->lab, c->domain_size * sizeof(int));
113 memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
114 memcpy(vertex_to_lab, c->vertex_to_lab, c->domain_size * sizeof(int));
115
117 cells = c->cells;
118 }
119
126 if (alloc_pt) {
127 if (domain_size != c->domain_size) dealloc();
128 }
129
130 if (!alloc_pt) {
131 alloc(c->domain_size);
132 }
133
134 memcpy(ptn, c->ptn, c->domain_size * sizeof(int));
135 memcpy(lab, c->lab, c->domain_size * sizeof(int));
136 memcpy(vertex_to_col, c->vertex_to_col, c->domain_size * sizeof(int));
137 memcpy(vertex_to_lab, c->vertex_to_lab, c->domain_size * sizeof(int));
138
140 cells = c->cells;
141 }
142
149 void initialize(int new_domain_size) {
150 alloc(new_domain_size);
151 }
152
153 void check() const {
154 bool comp = true;
155
156 for (int i = 0; i < domain_size; ++i) {
157 comp = comp && (lab[i] >= 0 && lab[i] < domain_size);
158 comp = comp && (lab[vertex_to_lab[i]] == i);
159 }
160
161 int counter = 1;
162 for (int i = 0; i < domain_size; ++i) {
163 --counter;
164 if (counter == 0) {
165 counter = ptn[i] + 1;
166 dej_assert(ptn[i] >= 0 && ptn[i] < domain_size);
167 }
168 }
169
170 for (int i = 0; i < domain_size;) {
171 dej_assert(vertex_to_col[lab[i]] == i);
172 i += ptn[i] + 1;
173 }
174 dej_assert(comp);
175 }
176 };
177}}
178
179#endif //DEJAVU_COLORING_H
Vertex coloring for a graph.
Definition: coloring.h:23
void initialize(int new_domain_size)
Definition: coloring.h:149
void copy_any(coloring *c)
Definition: coloring.h:125
void check() const
Definition: coloring.h:153
void copy_from_ir_ancestor(coloring *c)
Definition: coloring.h:98
void copy_ptn(coloring *c) const
Definition: coloring.h:83
Definition: bfs.h:10
#define dej_assert(expr)
Definition: utility.h:40