The fxt demos: graph search

Directory graph: Searching directed graphs, mostly to find combinatorial objects.
Find a list of all files in this directory here. An index of all topics is here

You may want to look at the outputs first.

graph-acgray-out.txt is the output of graph-acgray-demo.cc.
Paths through a directed graph: adjacent changes (AC) Gray paths.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph-cond.cc (fxt/src/graph/search-digraph-cond.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-gray-digraph.cc (fxt/src/graph/mk-gray-digraph.cc)

graph-complementshift-out.txt is the output of graph-complementshift-demo.cc.
Complement-shift sequence via paths in a directed graph.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-debruijn-digraph.cc (fxt/src/graph/mk-debruijn-digraph.cc)

graph-debruijn-out.txt is the output of graph-debruijn-demo.cc.
Find all paths through the binary De Bruijn graph.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-debruijn-digraph.cc (fxt/src/graph/mk-debruijn-digraph.cc)

graph-debruijn-m-out.txt is the output of graph-debruijn-m-demo.cc.
Find all paths through the m-ary De Bruijn graph.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-debruijn-digraph.cc (fxt/src/graph/mk-debruijn-digraph.cc)

graph-fibrepgray-out.txt is the output of graph-fibrepgray-demo.cc.
Gray codes through Fibonacci representations.
The demo uses the functions from fibrep.h (fxt/src/bits/fibrep.h) fibonacci.h (fxt/src/aux0/fibonacci.h) digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph-cond.cc (fxt/src/graph/search-digraph-cond.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-fibrep-gray-digraph.cc (fxt/src/graph/mk-fibrep-gray-digraph.cc)

graph-gray-out.txt is the output of graph-gray-demo.cc.
Paths through a directed graph: Gray paths.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-gray-digraph.cc (fxt/src/graph/mk-gray-digraph.cc)

graph-lyndon-gray-out.txt is the output of graph-lyndon-gray-demo.cc.
Paths through a directed graph: Gray paths through Lyndon words.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) search-digraph-cond.cc (fxt/src/graph/search-digraph-cond.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-lyndon-gray-digraph.cc (fxt/src/graph/mk-lyndon-gray-digraph.cc) lyndon-cmp.cc (fxt/src/graph/lyndon-cmp.cc)

graph-macgray-out.txt is the output of graph-macgray-demo.cc.
Paths through a directed graph: modular adjacent changes (MAC) Gray paths.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph-cond.cc (fxt/src/graph/search-digraph-cond.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-gray-digraph.cc (fxt/src/graph/mk-gray-digraph.cc)

graph-monotonicgray-out.txt is the output of graph-monotonicgray-demo.cc.
Paths through a directed graph: all canonical monotonic Gray paths starting with zero.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-gray-digraph.cc (fxt/src/graph/mk-gray-digraph.cc) search-digraph.cc (fxt/src/graph/search-digraph.cc) search-digraph-cond.cc (fxt/src/graph/search-digraph-cond.cc)

graph-mtl-out.txt is the output of graph-mtl-demo.cc.
Cycles through a directed graph: middle two levels.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc)

graph-parengray-out.txt is the output of graph-parengray-demo.cc.
Gray codes through valid parentheses strings
The demo uses the functions from parenwords.h (fxt/src/bits/parenwords.h) digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-paren-gray-digraph.cc (fxt/src/graph/mk-paren-gray-digraph.cc)

graph-perm-out.txt is the output of graph-perm-demo.cc.
Paths through the complete graph: Permutations.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-complete-digraph.cc (fxt/src/graph/mk-complete-digraph.cc)

graph-perm-doubly-adjacent-gray-out.txt is the output of graph-perm-doubly-adjacent-gray-demo.cc.
Gray codes through permutations with only adjacent interchanges and successive transpositions overlapping (doubly-adjacent Gray codes).
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-perm-gray-digraph.cc (fxt/src/graph/mk-perm-gray-digraph.cc)

graph-perm-pref-rev-out.txt is the output of graph-perm-pref-rev-demo.cc.
Permutations by prefix reversals.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-perm-pref-rev-digraph.cc (fxt/src/graph/mk-perm-pref-rev-digraph.cc)

graph-perm-pref-rot-out.txt is the output of graph-perm-pref-rot-demo.cc.
Permutations by prefix rotations.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-perm-pref-rot-digraph.cc (fxt/src/graph/mk-perm-pref-rot-digraph.cc)

graph-perm-star-transpositions-out.txt is the output of graph-perm-star-transpositions-demo.cc.
Gray codes through permutations with star transpositions.
The demo uses the functions from digraph.h (fxt/src/graph/digraph.h) digraph-paths.h (fxt/src/graph/digraph-paths.h) search-digraph.cc (fxt/src/graph/search-digraph.cc) mk-special-digraphs.h (fxt/src/graph/mk-special-digraphs.h) mk-perm-gray-digraph.cc (fxt/src/graph/mk-perm-gray-digraph.cc)

lyndon-gray-out.txt is the output of lyndon-gray-demo.cc.
Gray cycle through n-bit Lyndon words. Must have n odd, and n < BITS_PER_LONG. By default print (length-7710, base-36) delta sequence for n=17.
The demo uses the functions from lyndon-gray.h (fxt/src/graph/lyndon-gray.h) crc64.h (fxt/src/bits/crc64.h)

sta-graph-acgray-out.txt is the output of sta-graph-acgray-demo.cc.
Paths through a directed graph: adjacent changes (AC) Gray paths. Streamlined standalone routine (for backtracking).

sta-graph-macgray-out.txt is the output of sta-graph-macgray-demo.cc.
Paths through a directed graph: modular adjacent changes (MAC) Gray paths. Streamlined standalone routine for backtracking.