Given a hypergraph H=(V,E), the program htcbdd computes the transversal hypergraph of H by generating all minimal hitting sets for E.

A hypergraph is a pair H=(V,E) of a set V and a family E of subsets of V, where the sets in E are called hyperedges. A hitting set or transversal for E is a subset T of V such that T meets every hyperedge in E. A hitting set is minimal if no proper subsets are hitting sets. The transversal hypergraph of H is a hypergraph whose ground set is V and whose hyperedges are the minimal hitting sets for E.

Binary decision diagrams (BDDs) and zero-suppressed BDDs (ZDDs) are compressed data structures for Boolean functions and set families, respectively. CU Decision Diagram Package Release 2.5.0 is used in htcbdd to manipulate BDDs and ZDDs. For detailed information, see README in the directory cudd-2.5.0 and also on-line document.

The requirements for an input file format are:

For example: The following data corresponds to the hypergraph H = {{2,4,7}, {7,8}, {9}, {9,10}} on the vertex set {1,...,10}.

2 4 7 
7 8 
9 
9 10 

      

Given this data, htcbdd outputs the following hypergraph:

7 9 
4 8 9 
2 8 9 

      

There are sample datasets in the directory data. Many datasets can be found in Hypergraph Dualization Repository.

Compile BDD/ZDD library (i.e. CUDD) first and then compile our code in the top directory.

$ tar zxvf htcbdd-1.2.0.tar.gz
$ cd htcbdd-1.2.0/cudd-2.5.0
$ make
$ cd ..
$ make

      

The above method is basically sufficient in Linux. For MacOSX and cygwin on Windows, the compilation of CUDD may fail. In this case, it may be good to modify Makefile in cudd-2.5.0 so that for MacOSX, all lines concerning XCFLAGS are commented out, and for cygwin on Windows, the line of XCFLAG in the "Windows 95/98/NT/XP/Vista/7 with Cygwin" section is only uncommented (and other lines are commented). If compilation fails in spite of Linux, select approapriate XCFLAG according to your environment such as architechture and gcc version.

$ htcbdd [option] input-filename [output-filename]
-t   :Toda method (default)
-k   :Knuth method

If output-filename is not given, then HTC-BDD does not decompress an output ZDD and does not produce any datafile.

htcbdd does not maintain reference counts of BDD and ZDD nodes! Hence, an error will occur if either the number of nodes exceeds the limit size or the memory space available in a computer is exhausted.

htcbdd accesses BDD/ZDD library through bdd_interface.h, in which all functions for BDD/ZDD manipulation are defined. Perhaps, you can easily change to other BDD/ZDD libraries, if you like, by modifying bdd_interface.h and Makefile in the top directory.

If the macros MISC_LOG, TIME_LOG, SIZE_LOG are defined in Makefile, the following information will be outputed to stdout. The meaning of each line is described as a comment following //.

$ ./htcbdd data/TH-3-30.dat 
date  Thu May 14 13:25:30 2015
program HTCBDD-1.2.2
package CU Decision Diagram Package Release 2.5.0
input data/TH-3-30.dat
method  Toda

generator_type  default         // selected random number generator
first_value 1627153179          // the first generated random number
max_value 2147483647            // the maximum value of random numbers
seed  1431577530

maxval  30                      // the maximum value of items in input
#row  435                       // the number of rows in input
#entry  12180                   // the number of entries in input with repetition

GC  disabled                    // garbage collection was disabled
time(INPUT) 0.00  sec           // time for compression phase
|zdd| 86                        // the number of nodes in a ZDD
#sets 435                       // the number of sets represented in a ZDD

time(HIT) 0.03  sec             // time for hitting set generation phase
|bdd| 85                        // the number of nodes in an intermediate BDD

time(MIN) 0.05  sec             // time for restricting into minimal sets
|zdd| 86                        // the number of nodes in an output ZDD
#sets 4060                      // the number of sets in output