frontier_basic_tdzdd

An example implementation of the frontier-based search using TdZdd (https://github.com/kunisura/TdZdd ).

This program constructs a ZDD representing all the single cycles and a ZDD representing all the s-t paths on a given graph.

Usage

make
./program --cycle --show grid3x3.txt

You will get the following:

Reading "grid3x3.txt" ... done in 0.00s elapsed, 0.00s user, 4MB.
# of vertices = 9
# of edges = 12
FrontierExampleSpec .......... <53> in 0.00s elapsed, 0.00s user, 4MB.
# of ZDD nodes = 53
# of solutions = 13

This constructs a ZDD representing all the single cycles. If we specify an argument without '--', it is interpreted as the input graph filename, which is in an edge list format. The first edge (the first line in the file) corresponds to the variable (label) of the root of the constructed ZDD. See the document in English or Japanese for detail.

If you run

./program --path --show grid3x3.txt

You will get a ZDD representing all the s-t paths.

The frontier-based search for single cycles is implemented in the FrontierSingleCycleSpec class (as a "spec" of TdZdd), and that for s-t paths is implemeneted in the FrontierSTPathSpec class.

If you run the program without arguments like

./program

it runs for n x n grid for n = 2,...,10, and you will get the following:

n = 2, # of solutions = 1
n = 3, # of solutions = 13
n = 4, # of solutions = 213
n = 5, # of solutions = 9349
n = 6, # of solutions = 1222363
n = 7, # of solutions = 487150371
n = 8, # of solutions = 603841648931
n = 9, # of solutions = 2318527339461265
n = 10, # of solutions = 27359264067916806101

This implementation uses the Graph class in the TdZdd library. See the document in English or Japanese.

Options

General options

Option	Effect
--show	Show information and error messages.
--dot	Output the constructed ZDD in the graphviz dot format.
--show-fs	Show the frontiers of the input graph.
--enum	Enumerate all the subgraphs.

Graph types

Option	Graph
--path	s-t paths
--hampath	Hamiltonian s-t paths
--cycle	Cycles
--letter_O	O-shaped graphs (equivalent to cycles)
--hamcycle	Hamiltonian cycles
--path_m	s-t Paths (using mate)
--hampath_m	s-t Hamiltonian paths (using mate)
--cycle_m	Cycles (using mate)
--hamcycle_m	Hamiltonian paths (using mate)
--forest	Forests
--tree	Trees
--stree	Spanning trees
--matching	Machings
--cmatching	Complete matchings
--letter_I	I-shaped graphs (equivalent to paths)
--letter_L	L-shaped graphs (equivalent to paths)
--letter_P	P-shaped graphs

Vertices s and t of (Hamiltonian) paths are fixed to be 1 and n (the number of vertices), respectively.

License

MIT License