dejavu
Fast probabilistic symmetry detection.
Loading...
Searching...
No Matches
dejavu.cpp
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#include <iostream>
6#include <thread>
7#include "dejavu.h"
8#include <chrono>
9#include <string>
10
11typedef std::chrono::high_resolution_clock Clock;
12
15
16void empty_hook(int, const int*, int, const int *) {}
17
18int commandline_mode(int argc, char **argv) {
19 std::string filename;
20 bool entered_file = false;
21 bool permute_graph = false;
22 bool permute_graph_have_seed = false;
23 int permute_graph_given_seed = 0;
24 bool print = true;
25
26 bool true_random = false;
27 bool true_random_seed = false;
28
29 int error_bound = 10;
30
31 bool write_grp_sz = false;
32 bool write_benchmark_lines = false;
33 bool write_auto_stdout = false;
34 bool write_auto_file = false;
35 std::string write_auto_file_name;
36
37 for (int i = 1; i < argc; ++i) {
38 std::string arg = std::string(argv[i]);
39 std::transform(arg.begin(), arg.end(), arg.begin(), ::toupper);
40 std::replace(arg.begin(), arg.end(), '-', '_');
41
42 if (arg == "__HELP" || arg == "_H") {
43 std::cout << "Usage: dejavu [file] [options]" << std::endl;
44 std::cout << "Computes the automorphism group of undirected graph described in FILE." << std::endl;
45 std::cout << "FILE is expected to be in DIMACS format." << std::endl;
46 std::cout << "Options:" << std::endl;
47 std::cout << " " << std::left << std::setw(20) <<
48 "--err [n]" << std::setw(16) <<
49 "Sets the error to be bounded by 1/2^N, assuming uniform random numbers" << std::endl;
50 std::cout << " " << std::left << std::setw(20) <<
51 "--silent" << std::setw(16) <<
52 "Does not print progress of the solver" << std::endl;
53 std::cout << " " << std::left << std::setw(20) <<
54 "--gens" << std::setw(16) <<
55 "Prints found generators line-by-line to console" << std::endl;
56 std::cout << " " << std::left << std::setw(20) <<
57 "--gens-file [f]" << std::setw(16) <<
58 "Writes found generators line-by-line to file F" << std::endl;
59 std::cout << " " << std::left << std::setw(20) <<
60 "--grp-sz" << std::setw(16) <<
61 "Prints group size to console (even if --silent)" << std::endl;
62 std::cout << " " << std::left << std::setw(20) <<
63 "--pseudo-random" << std::setw(16) <<
64 "Uses pseudo random numbers (default)" << std::endl;
65 std::cout << " " << std::left << std::setw(20) <<
66 "--true-random" << std::setw(16) <<
67 "Uses random device of OS" << std::endl;
68 std::cout << " " << std::left << std::setw(20) <<
69 "--true-random-seed" << std::setw(16) <<
70 "Seeds pseudo random with random device of OS" << std::endl;
71 std::cout << " " << std::left << std::setw(20) <<
72 "--permute" << std::setw(16) <<
73 "Randomly permutes the given graph" << std::endl;
74 std::cout << " " << std::left << std::setw(20) <<
75 "--permute-seed [n]" << std::setw(16) <<
76 "Seed for the previous option with N" << std::endl;
77 return 0;
78 } else if (arg == "__VERSION" || arg == "_V") {
79 std::cout << DEJAVU_VERSION_MAJOR << "." << DEJAVU_VERSION_MINOR <<
80 (DEJAVU_VERSION_IS_PREVIEW?"preview":"") << std::endl;
81 return 0;
82 } else if (arg == "__FILE") {
83 if (i + 1 < argc) {
84 i++;
85 filename = argv[i];
86 entered_file = true;
87 } else {
88 std::cerr << "--file option requires one argument." << std::endl;
89 return 1;
90 }
91 } else if (arg == "__ERR") {
92 if (i + 1 < argc) {
93 i++;
94 error_bound = atoi(argv[i]);
95 } else {
96 std::cerr << "--err option requires one argument." << std::endl;
97 return 1;
98 }
99 } else if (arg == "__GRP_SZ") {
100 write_grp_sz = true;
101 } else if (arg == "__BENCHMARK_LINES") {
102 write_benchmark_lines = true;
103 } else if (arg == "__GENS") {
104 write_auto_stdout = true;
105 } else if (arg == "__GENS_FILE") {
106 if (i + 1 < argc) {
107 i++;
108 write_auto_file = true;
109 write_auto_file_name = argv[i];
110 } else {
111 std::cerr << "--write-gens-file option requires one argument." << std::endl;
112 return 1;
113 }
114 } else if (arg == "__TRUE_RANDOM") {
115 if(true_random_seed) {
116 std::cerr << "--true-random and --true-random-seed can not be activated at the same time:" <<
117 "--true-random-seed seeds a pseudo random number generator with a random number" << std::endl;
118 return 1;
119 }
120 true_random = true;
121 } else if (arg == "__PSEUDO_RANDOM") {
122 true_random = false;
123 } else if (arg == "__TRUE_RANDOM_SEED") {
124 if(true_random) {
125 std::cerr << "--true-random and --true-random-seed can not be activated at the same time:" <<
126 "--true-random-seed seeds a pseudo random number generator with a random number" << std::endl;
127 return 1;
128 }
129 true_random_seed = true;
130 } else if (arg == "__PERMUTE") {
131 permute_graph = true;
132 } else if (arg == "__PERMUTE_SEED") {
133 if (i + 1 < argc) {
134 i++;
135 permute_graph_have_seed = true;
136 permute_graph_given_seed = atoi(argv[i]);
137 } else {
138 std::cerr << "--permute_seed option requires one argument." << std::endl;
139 return 1;
140 }
141 } else if (arg == "__SILENT") {
142 print = false;
143 } else if (argv[i][0] != '-') {
144 if(!entered_file) {
145 filename = argv[i];
146 entered_file = true;
147 } else {
148 std::cerr << "Extraneous file '" << argv[i] << "'. Only 1 file required." << std::endl;
149 return 1;
150 }
151 } else {
152 std::cerr << "Invalid commandline option '" << argv[i] << "'." << std::endl;
153 return 1;
154 }
155 }
156
157 if (!entered_file) {
158 std::cerr << "no file was specified, usage: dejavu [file] [options], use --help for options" << std::endl;
159 return 1;
160 }
161
162 if(!file_exists(filename)) {
163 std::cerr << "File '" << filename << "' does not exist." << std::endl;
164 return 1;
165 }
166
167 if(print) std::cout << "dejavu version=" << DEJAVU_VERSION_MAJOR << "." << DEJAVU_VERSION_MINOR <<
168 (DEJAVU_VERSION_IS_PREVIEW?"preview":"") << std::endl;
169 if(print) std::cout << "------------------------------------------------------------------" << std::endl;
170
172 if(print) std::cout << "parsing '" << filename << "'" << std::endl;
173 int* colmap = nullptr;
174
175 int permute_seed = 0;
176 if(permute_graph) {
177 permute_seed = permute_graph_given_seed;
178 if(!permute_graph_have_seed) {
179 std::random_device r;
180 permute_seed = static_cast<int>(r());
181 }
182 if(print) std::cout << (true_random?"true_random=true, ":"") << (true_random_seed?"true_random_seed=true":"");
183 if(print) std::cout << "permutation_seed=" << permute_seed << ", ";
184 }
185 parse_dimacs(filename, &g, &colmap, !print, permute_seed);
186 if(print) std::cout << ", n=" << g.v_size << ", " << "m=" << g.e_size/2 << std::endl << std::endl;
187
188 // manage hooks
189 auto empty_hook_func = dejavu_hook(empty_hook);
191 std::ofstream output_file;
192 dejavu::hooks::ostream_hook file_hook(output_file);
193 dejavu::hooks::ostream_hook cout_hook(std::cout);
194 dejavu_hook* hook;
195
196 // write automorphism to file or cout
197 if(write_auto_stdout) hooks.add_hook(cout_hook.get_hook());
198 if(write_auto_file) {
199 output_file.open(write_auto_file_name);
200 hooks.add_hook(file_hook.get_hook());
201 }
202
203 // debug hook
204#ifndef NDEBUG
205#ifdef DEJDEBUG
206 auto test_hook_func = dejavu_hook(dejavu::test_hook);
208 hooks.add_hook(&test_hook_func);
209#endif
210#endif
211
212 // use multi-hook or empty hook
213 if(hooks.size() == 0) hook = &empty_hook_func; // using empty_hook_func for fair benchmarks, 'nullptr' is faster
214 else hook = hooks.get_hook();
215
216 // no coloring given? let's insert the trivial coloring
217 if (colmap == nullptr) colmap = (int *) calloc(g.v_size, sizeof(int));
218
219 // now run the solver with the given options...
220 Clock::time_point timer = Clock::now();
221
223 d.set_error_bound(error_bound);
224 d.set_print(print);
225 if (true_random_seed) d.randomize_seed();
226 d.set_true_random(true_random);
227 d.automorphisms(&g, colmap, hook);
228
229 long dejavu_solve_time = (std::chrono::duration_cast<std::chrono::nanoseconds>(Clock::now() - timer).count());
231
232 if (print) std::cout << "------------------------------------------------------------------" << std::endl;
233 if (print || write_benchmark_lines)
234 std::cout << std::setprecision(4) << "symmetries=" << grp_sz
235 << ", deterministic=" << (d.get_deterministic_termination() ? "true" : "false")
236 << ", error=1/2^" << d.get_error_bound() << "," << std::endl;
237
238 if(print || write_benchmark_lines) std::cout << "solve_time=" <<
239 static_cast<double>(dejavu_solve_time) / 1000000.0 << "ms" << std::endl;
240 if(!print && write_grp_sz) std::cout << grp_sz << std::endl;
241
242 free(colmap);
243 return 0;
244}
245
246int main(int argc, char *argv[]) {
247 return commandline_mode(argc, argv);
248}
Stores big numbers.
Definition: utility.h:138
Calls several other hooks.
Definition: dejavu.h:55
void add_hook(dejavu_hook *hook)
Definition: dejavu.h:65
dej_nodiscard size_t size() const
Definition: dejavu.h:73
dejavu_hook * get_hook() override
Definition: dejavu.h:77
Writes to an ostream.
Definition: dejavu.h:96
dejavu_hook * get_hook() override
Definition: dejavu.h:124
Color refinement and related algorithms.
Definition: refinement.h:143
Internal graph data structure.
Definition: graph.h:19
void copy_graph(sgraph *g)
Definition: graph.h:243
int e_size
Definition: graph.h:49
int v_size
Definition: graph.h:48
The dejavu solver.
Definition: dejavu.h:257
dej_nodiscard big_number get_automorphism_group_size() const
Definition: dejavu.h:389
dej_nodiscard bool get_deterministic_termination() const
Definition: dejavu.h:397
int get_error_bound() const
Definition: dejavu.h:298
void set_true_random(bool use_true_random=true)
Definition: dejavu.h:308
void set_print(bool print=true)
Definition: dejavu.h:381
void automorphisms(static_graph *g, dejavu_hook *hook=nullptr)
Definition: dejavu.h:410
void randomize_seed()
Definition: dejavu.h:371
void set_error_bound(int error_bound=10)
Definition: dejavu.h:288
int main(int argc, char *argv[])
Definition: dejavu.cpp:246
std::chrono::high_resolution_clock Clock
Definition: dejavu.cpp:11
dejavu::ir::refinement test_r
Definition: dejavu.cpp:13
dejavu::sgraph dej_test_graph
Definition: dejavu.cpp:14
int commandline_mode(int argc, char **argv)
Definition: dejavu.cpp:18
void empty_hook(int, const int *, int, const int *)
Definition: dejavu.cpp:16
#define DEJAVU_VERSION_MAJOR
Definition: dejavu.h:8
#define DEJAVU_VERSION_IS_PREVIEW
Definition: dejavu.h:10
#define DEJAVU_VERSION_MINOR
Definition: dejavu.h:9
std::function< void(int, const int *, int, const int *)> dejavu_hook
Definition: utility.h:95