1
2 #include "graph/digraph.h"
3 #include "graph/digraph-paths.h"
4 #include "graph/mk-special-digraphs.h"
5 // demo-include "graph/search-digraph.cc"
6 // demo-include "graph/mk-gray-digraph.cc"
7
8 //#include "comb/gray.h"
9
10 #include "comb/comb-print.h"
11
12 #include "graph/print-path.h"
13 #include "bits/bitcount.h"
14 #include "bits/graycode.h"
15 #include "bits/bitlex.h"
16 #include "bits/bittransforms.h"
17
18 #include "nextarg.h"
19 #include "fxttypes.h" // ulong
20
21 #include "fxtio.h"
22
23
24 //% Paths through a directed graph: Gray paths.
25
26
27 ulong
pfunc_gray(const digraph_paths & dp)28 pfunc_gray(const digraph_paths &dp)
29 // Function to be called with each path.
30 {
31 const ulong *rv = dp.rv_;
32 ulong ng = dp.ng_;
33
34 // ----- conditions:
35 // if ( ! dp.cq_ ) return 0; // only cycles
36 // if ( dp.cq_ ) return 0; // no cycles (monotonic are never cycles)
37
38 // if ( ! is_canonical_gray(rv, ng) ) return 0;
39 // if ( ! is_complementary_gray(rv, ng) ) return 0;
40
41 // ----- actions:
42
43 cout << dp.pfct_ << ":" << endl;
44 print_gray(rv, ng);
45 // print_gray_delta(rv, ng);
46 // cout << endl;
47
48 int shortq = 1;
49 dp.print_turns( shortq );
50 cout << endl;
51
52
53 // static ulong ct = 0; ++ct;
54 // if ( 0==(ct&1023) ) { cout << "\r" << ct; cout.flush(); }
55
56 return 1;
57 }
58 // -------------------------
59
60
cmp_lex(const ulong & a,const ulong & b)61 int cmp_lex(const ulong &a, const ulong &b)
62 {
63 if ( a==b ) return 0;
64 #define CODE(x) lexrev2negidx(x)
65 ulong ca = CODE(a), cb = CODE(b);
66 #undef CODE
67 return (ca<cb ? +1 : -1);
68 }
69 // -------------------------
70
71
cmp_blue(const ulong & a,const ulong & b)72 int cmp_blue(const ulong &a, const ulong &b)
73 {
74 if ( a==b ) return 0;
75 #define CODE(x) blue_code(x)
76 ulong ca = CODE(a), cb = CODE(b);
77 #undef CODE
78 return (ca>cb ? +1 : -1);
79 }
80 // -------------------------
81
82 int
main(int argc,char ** argv)83 main(int argc, char **argv)
84 {
85 ulong n = 6;
86 NXARG(n, "word size in bits, n>=2");
87 if ( n<2 ) n = 2;
88
89 ulong rq = 0;
90 // NXARG(rq, "force path to start as 0 1 3");
91
92 ulong maxnp = 1;
93 NXARG(maxnp, "stop after maxnp paths (0: never stop)");
94
95 ulong sortq = 1;
96 NXARG(sortq, "whether to do edge-sorting 0:no, 1:lex 2:blue, >2:randomize");
97
98 ulong erevq = 0;
99 NXARG(erevq, "whether to reverse edge-order");
100
101 digraph * dgp = make_gray_digraph(n, rq);
102 digraph &dg = *dgp;
103
104 if ( 1==sortq ) dg.sort_edges(cmp_lex);
105 if ( 2==sortq ) dg.sort_edges(cmp_blue);
106 srand( (uint)sortq );
107 if ( 3<=sortq ) dg.randomize_edge_order();
108
109 if ( erevq ) dg.reverse_edge_order();
110
111 // dg.print("Graph =");
112
113
114 digraph_paths dp(dg);
115
116 // All the work is done here:
117 // (pfunc_gray() is called with each path)
118 dp.all_paths(pfunc_gray, 0, 0, maxnp);
119
120 cout << "n = " << n;
121 cout << " #pfct = " << dp.pfct_;
122 cout << endl;
123 cout << " #paths = " << dp.pct_;
124 cout << " #cycles = " << dp.cct_;
125 cout << endl;
126
127 delete dgp;
128
129 return 0;
130 }
131 // -------------------------
132
133 // n=4:
134 // #paths = 5712 #cycles = 2688
135 // canonical: 238
136 // canonical cycles: 112
137 // canonical complementary: 92
138
139 // complementary cycles for n = 4:
140 //
141 //n = 4 #pfct = 4
142 // #paths = 5712 #cycles = 2688
143 //
144 // 0: .... 0 0
145 // 1: ...1 1 1 0 ...1
146 // 2: ..11 2 3 1 ..1.
147 // 3: ..1. 1 2 0 ...1
148 // 4: .11. 2 6 2 .1..
149 // 5: .1.. 1 4 1 ..1.
150 // 6: .1.1 2 5 0 ...1
151 // 7: .111 3 7 1 ..1.
152 // 8: 1111 4 15 3 1...
153 // 9: 111. 3 14 0 ...1
154 // 10: 11.. 2 12 1 ..1.
155 // 11: 11.1 3 13 0 ...1
156 // 12: 1..1 2 9 2 .1..
157 // 13: 1.11 3 11 1 ..1.
158 // 14: 1.1. 2 10 0 ...1
159 // 15: 1... 1 8 1 ..1.
160 //
161 // 0: .... 0 0
162 // 1: ...1 1 1 0 ...1
163 // 2: ..11 2 3 1 ..1.
164 // 3: .111 3 7 2 .1..
165 // 4: .11. 2 6 0 ...1
166 // 5: .1.. 1 4 1 ..1.
167 // 6: .1.1 2 5 0 ...1
168 // 7: 11.1 3 13 3 1...
169 // 8: 1111 4 15 1 ..1.
170 // 9: 111. 3 14 0 ...1
171 // 10: 11.. 2 12 1 ..1.
172 // 11: 1... 1 8 2 .1..
173 // 12: 1..1 2 9 0 ...1
174 // 13: 1.11 3 11 1 ..1.
175 // 14: 1.1. 2 10 0 ...1
176 // 15: ..1. 1 2 3 1...
177 //
178 // 0: .... 0 0
179 // 1: ...1 1 1 0 ...1
180 // 2: ..11 2 3 1 ..1.
181 // 3: .111 3 7 2 .1..
182 // 4: .11. 2 6 0 ...1
183 // 5: ..1. 1 2 2 .1..
184 // 6: 1.1. 2 10 3 1...
185 // 7: 1.11 3 11 0 ...1
186 // 8: 1111 4 15 2 .1..
187 // 9: 111. 3 14 0 ...1
188 // 10: 11.. 2 12 1 ..1.
189 // 11: 1... 1 8 2 .1..
190 // 12: 1..1 2 9 0 ...1
191 // 13: 11.1 3 13 2 .1..
192 // 14: .1.1 2 5 3 1...
193 // 15: .1.. 1 4 0 ...1
194 //
195 // 0: .... 0 0
196 // 1: ...1 1 1 0 ...1
197 // 2: ..11 2 3 1 ..1.
198 // 3: .111 3 7 2 .1..
199 // 4: .1.1 2 5 1 ..1.
200 // 5: 11.1 3 13 3 1...
201 // 6: 1..1 2 9 2 .1..
202 // 7: 1.11 3 11 1 ..1.
203 // 8: 1111 4 15 2 .1..
204 // 9: 111. 3 14 0 ...1
205 // 10: 11.. 2 12 1 ..1.
206 // 11: 1... 1 8 2 .1..
207 // 12: 1.1. 2 10 1 ..1.
208 // 13: ..1. 1 2 3 1...
209 // 14: .11. 2 6 2 .1..
210 // 15: .1.. 1 4 1 ..1.
211 //
212
213 // monotonic:
214 // 0: .... 0 0
215 // 1: ...1 1 1 0 ...1
216 // 2: ..11 2 3 1 ..1.
217 // 3: ..1. 1 2 0 ...1
218 // 4: .11. 2 6 2 .1..
219 // 5: .1.. 1 4 1 ..1.
220 // 6: 11.. 2 12 3 1...
221 // 7: 1... 1 8 2 .1..
222 // 8: 1.1. 2 10 1 ..1.
223 // 9: 1.11 3 11 0 ...1
224 // 10: 1..1 2 9 1 ..1.
225 // 11: 11.1 3 13 2 .1..
226 // 12: .1.1 2 5 3 1...
227 // 13: .111 3 7 1 ..1.
228 // 14: 1111 4 15 3 1...
229 // 15: 111. 3 14 0 ...1
230
231 /// Emacs:
232 /// Local Variables:
233 /// MyRelDir: "demo/graph"
234 /// makefile-dir: "../../"
235 /// make-target: "1demo DSRC=demo/graph/graph-gray-demo.cc"
236 /// make-target2: "1demo DSRC=demo/graph/graph-gray-demo.cc DEMOFLAGS=-DTIMING"
237 /// End:
238
239