CNF_IO
Read or Write a CNF File

CNF_IO is a FORTRAN77 library which can read or write a file, in the DIMACS CNF format, containing information about a boolean formula written in conjunctive normal form.

Boolean expressions, written in conjunctive normal form, may be used as test cases for the satisfiability problem. That problem seeks to determine all possible combinations of variable values that result in the formula being evaluated as TRUE.

The routines in CNF_IO are intended to make it possible to transfer information between a CNF file and a computer program.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

CNF_IO is available in a C++ version and a FORTRAN77 version and a FORTRAN90 version.

Related Data and Programs:

CNF, a data directory which describes the DIMACS CNF file format for specifying instances of the satisfiability problem for boolean formulas in conjunctive normal form.

SATISFY, a FORTRAN77 program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem.

Reference:

1. Rina Dechter,
   Enhancement Schemes for constraint processing: Backjumping, learning, and cutset decomposition,
   Artificial Intelligence,
   Volume 41, Number 3, January 1990, pages 273-312.
2. dimacs_cnf.pdf, a writeup of the DIMACS CNF file format.

Source Code:

• cnf_io.f, the source code.
• cnf_io.sh, commands to compile the source code.

Examples and Tests:

• cnf_io_prb.f, a sample calling program.
• cnf_io_prb.sh, commands to compile and run the sample program.
• cnf_io_prb_output.txt, the output file.
• test01_v3_c2.cnf, a CNF file, for 3 variables and 2 clauses, written by the sample program.
• test02_v16_c18.cnf, a CNF file, for 16 variables and 18 clauses, written by the sample program.

List of Routines:

• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_IS_SPACE is TRUE if a character is a whitespace character.
• CNF_EVALUATE evaluates a formula in CNF form.
• CNF_DATA_READ reads the data of a CNF file.
• CNF_DATA_WRITE writes data to a CNF file.
• CNF_HEADER_READ reads the header of a CNF file.
• CNF_HEADER_WRITE writes the header for a CNF file.
• CNF_PRINT prints CNF information.
• CNF_WRITE writes the header and data of a CNF file.
• GET_UNIT returns a free FORTRAN unit number.
• Purpose:
• S_ADJUSTL flushes a string left.
• S_BLANKS_DELETE replaces consecutive blanks by one blank.
• S_EQI is a case insensitive comparison of two strings for equality.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• S_TO_I4 reads an I4 from a string.
• S_WORD_EXTRACT_FIRST extracts the first word from a string.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.

You can go up one level to the FORTRAN77 source codes.