1
2 #include "graph/digraph.h"
3 #include "graph/digraph-paths.h"
4 // demo-include "graph/search-digraph.cc"
5 #include "graph/mk-special-digraphs.h"
6 // demo-include "graph/mk-debruijn-digraph.cc"
7
8
9 #include "bits/print-bin.h"
10 #include "bits/parity.h"
11 #include "bits/graycode.h"
12
13 #include "nextarg.h"
14
15 #include "fxttypes.h"
16 #include "fxtio.h"
17 #include "jjassert.h"
18
19
20 //% Complement-shift sequence via paths in a directed graph.
21
22 ulong pq; // whether and what to print with each path
23 ulong
pfunc(const digraph_paths & dp)24 pfunc(const digraph_paths &dp)
25 // Function to be called with each path.
26 {
27 switch ( pq )
28 {
29 case 0: break; // just count
30 case 1: // print lowest bits
31 {
32 ulong *rv = dp.rv_, ng = dp.ng_;
33 for (ulong k=0; k<ng; ++k) cout << (rv[k]&1UL ? '1' : '.');
34 cout << endl;
35 break;
36 }
37 case 2: dp.print_bin_path();
38 break;
39 case 3: dp.print_bin_path();
40 break;
41 case 4: dp.print_bin_horiz_path();
42 break;
43 case 5: // print lowest bits
44 {
45 ulong *rv = dp.rv_, ng = dp.ng_;
46 for (ulong k=0; k<ng; ++k) cout << (rv[k]&1UL ? '1' : '.');
47 cout << endl;
48 break;
49 }
50 default:
51 {
52 ulong *rv = dp.rv_;
53 ulong b = dp.ngbits_;
54 for (ulong k=0; k<dp.ng_; ++k)
55 {
56 ulong t = rv[k];
57 print_bin(" ", t, b);
58 print_bin(" ", gray_code(t), b);
59 // print_bin(" ", inverse_gray_code(t), b);
60 cout << endl;
61 }
62
63 // dp.print_bin_path();
64 // ulong *rv = dp.rv_;
65 // for (ulong k=0; k<dp.ng_; ++k) cout << rv[k] << " ";
66 // cout << endl;
67 //// for (ulong k=0,t=~0UL; k<dp.ng_; ++k)
68 //// { t^=rv[k]; print_bin(" ",t, dp.ngbits_); cout << endl; }
69 // jjassert( dp.path_is_cycle() );
70 // break;
71 }
72 }
73
74 return 1;
75 }
76 // -------------------------
77
78
79 void
db_manip(digraph & dg,ulong mq)80 db_manip(digraph &dg, ulong mq)
81 {
82 ulong n = dg.ng_/2;
83
84 if ( mq >= 100 )
85 {
86 dg.reverse_edge_order(); // reverse ordering
87 mq -= 100;
88 }
89
90 switch ( mq )
91 {
92 case 1:
93 // different ordering: more changes in first half
94 for (ulong k=0; k<2*n; k+=2) dg.reverse_edge_order(k);
95 break;
96 case 2:
97 dg.reverse_edge_order(0, n-1);
98 break;
99 case 3:
100 dg.reverse_edge_order(n, 2*n-1);
101 break;
102 case 4:
103 // different ordering:
104 for (ulong k=0; k<n; ++k) if ( parity(k) ) dg.reverse_edge_order(k);
105 break;
106 }
107 }
108 // -------------------------
109
110
111 int
main(int argc,char ** argv)112 main(int argc, char **argv)
113 {
114 ulong n = 32;
115 NXARG(n, "size of graph == 2*n");
116 pq = 2;
117 NXARG(pq, "whether and what to print with each path");
118 ulong maxnp = 1;
119 NXARG(maxnp, "stop after maxnp paths (0: never stop)");
120 ulong mq = 0;
121 NXARG(mq, "special: manipulate graph");
122
123 digraph * dgp = make_complement_shift_digraph(n);
124 digraph &dg = *dgp;
125 digraph_paths dp(dg);
126
127 if ( mq ) db_manip(dg, mq);
128
129 // dg.print_horiz("Graph =");
130
131 // call pfunc() with each path:
132 dp.all_paths(pfunc, 0, 0, maxnp);
133
134 cout << "n = " << n;
135 cout << " (ng=" << dg.ng_ << ")";
136 cout << " #cycles = " << dp.cct_;
137 cout << endl;
138
139 delete dgp;
140
141 return 0;
142 }
143 // -------------------------
144
145 /// Emacs:
146 /// Local Variables:
147 /// MyRelDir: "demo/graph"
148 /// makefile-dir: "../../"
149 /// make-target: "1demo DSRC=demo/graph/graph-complementshift-demo.cc"
150 /// make-target2: "1demo DSRC=demo/graph/graph-complementshift-demo.cc DEMOFLAGS=-DTIMING"
151 /// End:
152
153