1 #define YAPB_NO_GAP
2
3 #include "simple_graph.h"
4
5 #include <iostream>
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <chrono>
9 #include "library/stats.hpp"
10 #include "search/search_options.hpp"
11
outputGraph(const ParsedGraph & g,SearchOptions so,GraphConfig gc,GraphDirected directed,bool stats)12 void outputGraph(const ParsedGraph& g, SearchOptions so, GraphConfig gc,
13 GraphDirected directed, bool stats)
14 {
15 auto sols = SolveGraph(g, so, gc, directed);
16
17 std::cout << "[";
18 for(auto const& sol : sols)
19 {
20 std::cout << sol.cycle() << ",\n";
21 }
22 std::cout << "()]\n";
23 if(stats)
24 {
25 std::cout << "Generators: " << sols.size() << "\n";
26 }
27 }
28
print_usage_instructions()29 void print_usage_instructions()
30 {
31 std::cout <<
32 " A simple graph symmetry detector\n"
33 " Usage:\n"
34 " ./symmetry_detect [--stats] [--directed] [--order [random|scf|ordered]]\n"
35 " [--find [generators|all]]\n"
36 " --saucy|--dimacs|--json <filename>\n"
37 " --stats : Print extra stats\n"
38 " --directed : Graph is directed (ignored with --json)\n"
39 " --order : The order in which search should be performed:\n"
40 " random : Choose search order randomly\n"
41 " scf : Choose smallest cell to branch on\n"
42 " directed: Choose cell which is most connected in the graph(defaut)\n"
43 " ordered : Choose cells in order of input\n"
44 " --find : Which set of permutations should be produced:\n"
45 " generators : Generators of the symmetry group (default)\n"
46 " all : All members of the symmetry group (can be VERY large)\n"
47 " --saucy : Accept graph in saucy format\n"
48 " --dimacs : Accept graph in dimacs format\n"
49 " --json : Accept an AST in json format (see in-depth docs)\n"
50 " <filename> : Filename of graph\n"
51 " --startpathlength <num> : Length of paths to consider at root node (default 1)"
52 " --normalpathlength <num> : Length of paths to consider at all other nodes (default 1)";
53 }
54
55
main(int argc,char ** argv)56 int main(int argc, char **argv)
57 {
58 std::chrono::high_resolution_clock::time_point startTime;
59 std::chrono::high_resolution_clock::time_point endTime;
60 startTime = std::chrono::high_resolution_clock::now();
61 char* filename = 0;
62 GraphDirected directed = GraphDirected_no;
63 bool stats = false;
64 SearchOptions so;
65 so.heuristic = Heuristic::adviseHeuristic();
66 // formats: 1 - DIMACS, 2 - saucy
67 int format = 1;
68 GraphConfig gc;
69 for(int i = 1; i < argc; ++i)
70 {
71 if(argv[i] == std::string("--directed"))
72 directed = GraphDirected_yes;
73 else if(argv[i] == std::string("--stats"))
74 stats = true;
75 else if(argv[i] == std::string("--dimacs"))
76 format = 1;
77 else if(argv[i] == std::string("--saucy"))
78 format = 2;
79 else if(argv[i] == std::string("--json"))
80 {
81 format = 3;
82 directed = GraphDirected_yes;
83 }
84 else if(argv[i] == std::string("--order"))
85 {
86 i++;
87 if(argv[i] == std::string("random"))
88 {
89 so.heuristic = Heuristic::randomHeuristic();
90 }
91 else if(argv[i] == std::string("scf"))
92 {
93 so.heuristic = Heuristic::scfHeuristic();
94 }
95 else if(argv[i] == std::string("ordered"))
96 {
97 so.heuristic = Heuristic::orderHeuristic();
98 }
99 else if(argv[i] == std::string("directed"))
100 {
101 so.heuristic = Heuristic::adviseHeuristic();
102 }
103 else
104 {
105 std::cerr << "Do not understand order '" << argv[i] << "'\n";
106 exit(1);
107 }
108 }
109 else if(argv[i] == std::string("--find"))
110 {
111 i++;
112 if(argv[i] == std::string("generators"))
113 so.only_find_generators = true;
114 else if(argv[i] == std::string("all"))
115 so.only_find_generators = false;
116 else
117 {
118 std::cerr << "Do not understand --find argument '" << argv[i] << "'\n";
119 exit(1);
120 }
121 }
122 else if(argv[i] == std::string("--startpathlength"))
123 {
124 i++;
125 gc.start_path_length = atoi(argv[i]);
126 if(gc.start_path_length <= 0) {
127 std::cerr << "Invalid startpathlength\n";
128 exit(1);
129 }
130 }
131 else if(argv[i] == std::string("--normalpathlength"))
132 {
133 i++;
134 gc.normal_path_length = atoi(argv[i]);
135 if(gc.normal_path_length <= 0) {
136 std::cerr << "Invalid normalpathlength\n";
137 exit(1);
138 }
139 }
140 else if(argv[i] == std::string("-h") || argv[i] == std::string("-help") || argv[i] == std::string("--help"))
141 {
142 print_usage_instructions();
143 exit(0);
144 }
145 else
146 {
147 if(filename == 0)
148 filename = argv[i];
149 else
150 {
151 std::cerr << "Only one filename allowed\n";
152 exit(1);
153 }
154 }
155 }
156
157 if(filename == 0)
158 {
159 std::cerr << "Error: No filename" << std::endl;
160 print_usage_instructions();
161 exit(1);
162 }
163 if(format == 3)
164 {
165 solveJsonGraph(filename, so, gc);
166 }
167 else
168 {
169 FILE* fp = fopen(filename, "r");
170
171 if(!fp)
172 {
173 std::cerr << "Could not open file '" << filename << "'\n";
174 perror("Error: ");
175 }
176
177 ParsedGraph g;
178 switch(format)
179 {
180 case 1: g = read_dimacs_graph(fp); break;
181 case 2: g = read_saucy_graph(fp); break;
182 default: abort();
183
184 }
185
186 g.clean();
187
188 outputGraph(g, so, gc, directed, stats);
189 }
190
191 if(stats) {
192 endTime = std::chrono::high_resolution_clock::now();
193 int64_t timeTaken =
194 std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count();
195 timeTaken /= 1000;
196 std::cout << "time taken (ms): " << timeTaken << std::endl;
197 std::cout << "Nodes: " << Stats::container().node_count << "\n"
198 << "Bad leaves: " << Stats::container().bad_leaves << "\n"
199 << "Bad internal: "
200 << Stats::container(). bad_internal_nodes << "\n";
201 for(auto p : Stats::container().getConstraintCalls())
202 {
203 std::cout << p.first << ": " << p.second << "\n";
204 }
205 }
206 return 0;
207 }
208