This repository mirrors software page from Professor Vibhav Gogate at UT Dallas.
- Vibhav Gogate and Rina Dechter, “A complete Anytime Algorithm for Treewidth,” In 20th Conference on Uncertainty in Artificial Intelligence (UAI), 2004.
$ quickbb [option1] [option2] –cnffile CNFFILE
A description of the (input) CNF format is given here. Any graph can be written in this format. For example, a chain 1-2-3 can be specified as:
p cnf 3 2
1 2 0
2 3 0
The first line says that we are specifying the graph using 3 variables and 2 cliques (each edge is a clique. Trivially, you can specify a graph using its edges) The second line describes the first clique between vertex 1 and 2. “0” is the delimiter which specifies end of line. The third line describes the second clique between vertex 2 and vertex 3.
Options: [option1] should be one of the following:
- --random-ordering: Branching performed in quickbb using random ordering
- --min-fill-ordering: Branching performed in quickbb using min-fill ordering
[option2] can be any of the following or combination thereof:
- --time [int]: Integer time-bound.
- --lb: Computes lb of the graph,
- --outfile [filename]: Store the output like treewidth, lb and the current best perfect elimination order (peo).
- --statfile [filename]: Program statistics. The statfile has the following format:
- row1:#vertices,
- row2: #edges
- row3: lb if --lb is used else 0,
- row4: an upper bound on the treewidth
- row5: Time elapsed,
- row6:Nodes Visited,
- row7:Nodes Pruned
- row8:1 if the treewidth given in row3 is exact and 0 if it is not.
$ /quickbb_64 –min-fill-ordering –lb –outfile myout –statfile mystat –cnffile ls8_normalized.cnf
This will run quickbb on the ls8_normalized.cnf instance. The ordering heuristic used is min-fill. The output will be stored in myout and the statistics will be stored in mystat