$Id: README 2814 2001-11-10 20:39:47Z bremner $

This is release 0.2 of "mpc", which stands for "matroid polytope completion",
This release includes "oms", a simple backtracking algorithm, and
"hls", the Hyperline searcher.  "hls" should generate the same output
as "oms", unless the input file does not specify a sign for basis 1,
in which case hls assumes 1 and oms tries both signs.

Option parsing has changed.

BUILDING:
 	Configuration is now taken care of in the parent directory.

	So just	type make.


RUNNING:
	oms < datafile
where date file is a "state" description, described below.

OPTIONS:

Options can be found by running ./oms -h or ./hls -h


Run-length encoding:

chirotope TAB boundary

where each of chirotope, boundary is a string of the form

((NUMBER)?[+-z])*

where e.g. 23+6z-

means 23 +'s, followed by 6 zeros, followed by 1 minus.


CAVEATS:
	1) The code depends on the compiler to inline functions quite 
	aggressively. There may be a substantial performance loss 
	if this expectation is not met.
	
	2) Currently, the only tested checkpointing method uses
	the LSF system.

INPUT/OUTPUT FILES:

	The input and output of oms and hls are (partial) chiropes, and 
	(partial) boundary descriptions. There are several example files
	in directory ../bench.  There is a script im2state.pl in
	../filters that	converts incidence matrices (*.im) into state files

	 The context free grammer is 
	as follows:
	
 
state_file: parameter_list  section_list
parameter_list: /* empty */
	| parameter_list parameter_pair
opt_eq: /* empty */ | '='
opt_comma: | ','
parameter_pair: rank_pair | elements_pair  
rank_pair: RANK opt_eq INT  
elements_pair: ELEMENTS opt_eq INT 
section_list: | section_list section 
section: distance| boundary | chirotope
distance: DISTANCE ('  basis_list ')' opt_eq INT
chirotope: CHIROTOPE opt_eq '{' basis_list '}' 
boundary: BOUNDARY opt_eq '{' basis_list '}'  
basis_list: | basis_list opt_comma basis ;
basis:  bindex		
basis: '-' bindex	
bindex: INT
bindex: '['  index_list ']'
index_list:  | index_list INT 

