1
2 #include "graph/digraph.h"
3 #include "graph/digraph-paths.h"
4 // demo-include "graph/search-digraph.cc"
5 // demo-include "graph/search-digraph-cond.cc"
6 #include "graph/mk-special-digraphs.h"
7 // demo-include "graph/mk-lyndon-gray-digraph.cc"
8 // demo-include "graph/lyndon-cmp.cc"
9
10 // for the comparison function my_lyndon_cmp():
11 #include "bits/bitcount.h"
12 #include "bits/graycode.h"
13 #include "bits/bitlex.h"
14 #include "bits/revbin.h"
15 #include "bits/bitlow.h"
16 #include "bits/bithigh.h"
17 #include "bits/bitsequency.h"
18 #include "bits/bittransforms.h"
19
20 #include "bits/bit2pow.h"
21
22
23 #include "nextarg.h"
24
25 #include "fxttypes.h"
26 #include "fxtio.h"
27 #include "jjassert.h"
28
29
30 //% Paths through a directed graph: Gray paths through Lyndon words.
31
32
33 lyngray_dat *ldat;
34
35 void
print(const digraph_paths & dp)36 print(const digraph_paths &dp)
37 {
38 const ulong *rv = dp.rv_;
39 ulong ng = dp.ng_;
40
41 lyndon_gray_rot_delta(rv, ng, ldat);
42
43 cout << setw(4) << dp.pfct_ << ": ";
44
45 // // print delta sequence:
46 // const char dd[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ@";
47 // // enough w/base: "_23456789.123456789.123456789.123456789";
48 // cout << endl;
49 // for (ulong k=0; k<ng; ++k)
50 // {
51 // cout << dd[(ulong)(ldat->dd[k])];
52 // if ( 0==((k+1)%100) ) cout << endl;
53 // }
54
55 cout << endl;
56
57 // detailed print:
58 print_lyndon_gray_path(dp, ldat);
59
60 int shortq = 1;
61 dp.print_turns( shortq );
62 cout << endl;
63 }
64 // -------------------------
65
66
67 ulong
pfunc_lyndon_gray(const digraph_paths & dp)68 pfunc_lyndon_gray(const digraph_paths &dp)
69 // Function to be called with each path.
70 {
71 // return 0; // just count
72
73 // if ( dp.cq_ ) return 0; // select NON-cycles e.g. for monotonic paths
74
75 print(dp);
76
77 return 1;
78 }
79 // -------------------------
80
81 ulong
pfunc_lyndon_gray_cyc(const digraph_paths & dp)82 pfunc_lyndon_gray_cyc(const digraph_paths &dp)
83 // Function to be called with each path.
84 {
85 // return 0; // just count
86
87 if ( ! dp.cq_ ) return 0; // select cycles
88
89 print(dp);
90
91 return 1;
92 }
93 // -------------------------
94
95
96
cfunc_rot0(digraph_paths & dp,ulong ns)97 bool cfunc_rot0(digraph_paths &dp, ulong ns)
98 {
99 // if ( 1>=ns ) return true;
100 ulong p = dp.rv_[ns], p1 = dp.rv_[ns-1];
101 ulong *vn = dp.g_.vn_;
102 p = vn[p]; p1 = vn[p1];
103 if ( one_bit_q( p ^ p1 ) ) return true;
104 return false;
105 }
106 // -------------------------
107
cfunc_monotonic(digraph_paths & dp,ulong ns)108 bool cfunc_monotonic(digraph_paths &dp, ulong ns)
109 {
110 if ( 1>=ns ) return true;
111 ulong p = dp.rv_[ns], p2 = dp.rv_[ns-2];
112 ulong *vn = dp.g_.vn_;
113 p = vn[p]; p2 = vn[p2];
114 if ( bit_count(p) >= bit_count(p2) ) return true;
115 return false;
116 }
117 // -------------------------
118
cfunc_both(digraph_paths & dp,ulong ns)119 bool cfunc_both(digraph_paths &dp, ulong ns)
120 {
121 return ( cfunc_rot0(dp, ns) && cfunc_monotonic(dp, ns) );
122 }
123 // -------------------------
124
my_lyndon_cmp(const ulong & a,const ulong & b)125 static int my_lyndon_cmp(const ulong &a, const ulong &b)
126 // Playground.
127 // Works as given for n<=13
128 {
129 // return 0; // do not sort
130 if ( a==b ) return 0;
131
132 int bc = bit_count_cmp(a, b);
133 if ( bc ) return -bc;
134
135 //#define CODE(x) (x)
136 //#define CODE(x) inverse_gray_code(x)
137 //#define CODE(x) blue_code(x)
138 #define CODE(x) bit_sequency(x)
139 ulong ta = CODE(a), tb = CODE(b);
140 if ( ta==tb ) return 0;
141 // return ( ta<tb ? +1 : -1);
142 return ( ta>tb ? +1 : -1);
143 #undef CODE
144 }
145 // -------------------------
146
mon_cmp(const ulong & a,const ulong & b)147 static int mon_cmp(const ulong &a, const ulong &b)
148 {
149 int bc = bit_count_cmp(a, b);
150 if ( bc ) return bc;
151 return ( a<b ? +1 : -1 );
152 }
153 // -------------------------
154
155
156 typedef int (*CF)(const ulong &, const ulong &);
157 CF cf[] = {
158 lyndon_cmp0, // [0]
159 lyndon_cmp1, // [1]
160 lyndon_cmp2, // [2]
161 lyndon_cmp3, // [3]
162 lyndon_cmp4, // [4]
163 lyndon_cmp5, // [5]
164 lyndon_cmp6, // [6]
165 lyndon_cmp7, // [7]
166
167 mon_cmp, // [8]
168 my_lyndon_cmp, // [9]
169 nullptr // [10]==end
170 };
171 // -------------------------
172
173 // ==================================
174 // These values for cn quickly lead to Gray codes
175 // for size-p Lyndon words:
176 // cn: p =
177 // 0: 3 5 7 11 13
178 // 1: 3 5 7 11 17 19
179 // 2: 3 5 7 11 13 17
180 // 3: 3 5 7 11 13 17 19 23
181 // 4: 3 5 7 11 13
182 // 5: 3 5 7 11 13 19 23
183 // 6: 3 5 7 11 13 17 19
184 // 7: 3 5 7 11 13 17 19 23 (29 31)
185 // ==================================
186
187
188 int
main(int argc,char ** argv)189 main(int argc, char **argv)
190 {
191 ulong n = 7;
192 NXARG(n, "a prime <=23");
193 if ( n<3 ) n = 3;
194
195 ulong maxnp = 1;
196 NXARG(maxnp, "stop after maxnp paths (0: never stop)");
197
198
199 ulong cn = 0;
200 NXARG(cn, "choose comparison function for sorting edges");
201 ulong mcn = 0; while ( cf[mcn+1] ) ++mcn;
202 ulong erevq = 0;
203 NXARG(erevq, "whether to reverse edge-order");
204
205 ulong condn = 0;
206 NXARG(condn, "choose condition: 0==>cycles, 1==>rot0, 2==>monotonic, 3==>1&2, 4==>nil");
207
208 ulong rot0q = condn & 1;
209 digraph * dgp = make_lyndon_gray_digraph(n, ldat, rot0q);
210 digraph &dg = *dgp;
211
212 if ( cn<=mcn )
213 {
214 cout << "Using comparison function #" << cn << endl;
215 dg.sort_edges(cf[cn]);
216 jjassert( dg.is_edge_sorted(cf[cn]) );
217 }
218
219 if ( erevq ) dg.reverse_edge_order();
220 // dg.print("Graph ="); return 0;
221
222 // cout << "Graph (binary values) =" << endl;
223 // print_lyndon_gray_digraph(dg, ldat);
224 cout << " #nodes=" << dg.num_nodes();
225 cout << " #edges=" << dg.num_edges();
226 cout << endl;
227
228 digraph_paths dp(dg);
229
230 // All the work is done here:
231 // (pfunc_lyndon_gray() is called with each path)
232 switch ( condn )
233 {
234 case 0: dp.all_paths(pfunc_lyndon_gray_cyc, 0, 0, maxnp); break;
235 case 1: dp.all_paths(pfunc_lyndon_gray, 0, 0, maxnp); break;
236 case 2: dp.all_cond_paths(pfunc_lyndon_gray, cfunc_monotonic, 0, 0, maxnp); break;
237 // monotonic rot0 only for 3 and 5:
238 case 3: dp.all_cond_paths(pfunc_lyndon_gray, cfunc_monotonic, 0, 0, maxnp); break;
239
240 default: dp.all_paths(pfunc_lyndon_gray, 0, 0, maxnp); break;
241 }
242
243 cout << "n = " << n;
244 cout << " #pfct = " << dp.pfct_;
245 cout << endl;
246 cout << " #paths = " << dp.pct_;
247 cout << " #cycles = " << dp.cct_;
248 cout << endl;
249
250 delete ldat;
251 delete dgp;
252
253 return 0;
254 }
255 // -------------------------
256
257
258 // n: pathes cycles zero-rot-seq lowest-one-seq monotonic
259 // tot. / cycles tot. / cycles
260 // 3: 1 1 1 / 1 1 / 1 0
261 // 5: 8 4 3 / 2 5 / 3 4
262 // 7: 1022148 294144 395 / 112 108901 / 26256 3180
263
264
265 // ./bin 13 1 8 1
266 // ./bin 9 1 7
267 // ./bin 25 1 7 # takes a moment
268 // ./bin 6 999999 7 0 2
269
270 /// Emacs:
271 /// Local Variables:
272 /// MyRelDir: "demo/graph"
273 /// makefile-dir: "../../"
274 /// make-target: "1demo DSRC=demo/graph/graph-lyndon-gray-demo.cc"
275 /// make-target2: "1demo DSRC=demo/graph/graph-lyndon-gray-demo.cc DEMOFLAGS=-DTIMING"
276 /// End:
277
278