This directory contains all files necessary to make performanceexperiments on solving RCC8 CSPs as described in J. Renz, B. Nebel, "Efficient methods for Qualitative Spatial Reasoning", JAIR 15, 2001. After unpacking the tar archive you may want to edit the Makefile in orderto set the right compilation flags. Afterwards call 'make', which generates all the programs. They should compile and execute on all UNIX and Linux machines.CONTENTS========1) Text files	README 		- this file2) Data files (ASCII)	baserels	- the 8 base relations of RCC8	closebaserels	- all relations contained in the closure of the 			  set of base relations	hornrels	- all relations of the maximal tractable set H^8        c8rels	        - all relations of the maximal tractable set C_8        q8rels	        - all relations of the maximal tractable set Q_8        interrels       - intersection of H^8, C_8, and Q_8        nprels          - all relations not contained in one of the three                           maximal tractable subsets 	basesplit	- gives for each possible relation in RCC8 it's 			  (non-disjoint) union of base relations. This file			  can be generated by the 'cover' program	closebasesplit	- same for the relations of closebaserels	hornsplit	- same for the relations of hornrels	c8split	        - same for the relations of c8rels	q8split	        - same for the relations of q8rels        intersplit      - same for the relations of interrels3) Configuration files	Makefile	- check CFLAGS and CC. Used for generating all programs4) Program modules	rcc8.h		- defines representation of RCC8 relations	rcc8io.h	rcc8io.c	- I/O 	rcc8op.h	rcc8op.c	- basic operations in RCC8	pc1.c	        - basic path-consistency algorithm	pcvb.c		- van Beek's path-consistency algorithm	pcwq.c		- weighted queue path-consistency algorithm	backtrack.c	- backtrack algorithm for checking consistency	5) Programs	cover.c		- compute cover sets. To compute hornsplit, e.g.,			  call: cover < hornrels > hornsplit	genall.c	- prints all 256 RCC8 relations to stdout	gencsp.c	- generates RCC8 CSPs of a specified form			  (a detailed description is given below)	solve.c		- CSP-solver (a detailed description is given below)Generating CSPs===============The program 'gencsp' generates a specified number of RCC8 CSPs onstandard output. The properties of the CSPs can be controlled by severalflags:    gencsp [-ue] [-is number] [-cdlnCDLN min [max step]]  [-rx file] [-o name]    Generates RCC8 CSPs.     options are:       -u   uniform distribution of labels (50% probability for each label,             overwrites -l)       -e   all possible relations are equally distributed (owerwrites -u             and -l)       -i <number>  specifies number of instances to be generated (default 1)       -s <number>  specifies the seed for the random function      The following options expect either one value (particular value) or       three values (minimum value, maximum value and the stepwidth) which       specifies the range of the generated instances.      Numbers in brackets specify the range of accepted values.       -c   specifies the constraint density (default 0.0) [0.01 - 1.0]       -d   specifies the average degree of a node (default 0) [0 - MAXCSP]       -l   specifies the average labelsize (default 4.0) [1.0 - 8.0]        -n   specifies the number of nodes (default 3) [3 - MAXCSP]      The following options restrict the output of the generated instances       to those within the given range; again either one value or three values       are expected. These options are by default unset. Do not set C without       setting c, D without d, L without l, and N without n.        -C   restricts the output constraint density [0.01 - 1.0]       -D   restricts the output average degree of a node [0 - MAXCSP]       -L   restricts the output labelsize [1.0 - 8.0]       -N   restricts the output number of nodes [3 - MAXCSP]       -r <file>  restricts all relations to be the ones mentioned in the file       -x <file>  specifies the relations to be excluded       -o <name>  specifies the prefix of the outputfile                   (default is none)       The -c and -d options override each other.For example, the following program-call generates 100 CSP instanceswith 50 nodes, such that the average degree of the constraint graph is9.5 and the labels are chosen from the set 'hornrels':	gencsp -i 100 -n 50 -d 9.5 -r hornrels The following program-call generates 5 CSP instances for each even node size from n=10 to n=20 nodes and for each average constraint density from c=0.2 to c=0.6 with a step of 0.1 which contains only relations of the set 'nprels' such that each relation of 'nprels' is chosen with the same probability. Only those CSPs whose size is n=20 are written to stdout.        gencsp -i 5 -n 10 20 2 -c 0.2 0.6 0.1 -e -N 20 -r nprelsSolving CSPs============The program 'solve' reads the file supplied as the argument (or if noargument is given, it reads from standard input) and solves the CSPinstances in the file. There are a number of switches that control how and what CSPs are solved and what is given as output:   solve [-bdefnpqrsv] [-w[v]] [-z[p]] [-m[f] number] [-g number] [-ctx file] [-o file [number]] [-h[a|A file] order] [-li <file>] [-le <file>] [file1 file2 ...]      solves RCC8 CSPs.  solve [-bdefnpqrsvwz] [-m number] [-ctx file] [-o file [number]] [-h[a|A file] order] [file1 file2 ...]         solves RCC8 CSPs.    options are:    -b    return brief summary info on stdout (even if -q)    -c <file> use the coverage info in file to split relations    -d    give debugging info on stderr    -e    use environment constrainedness to select next node (van Beek)    -f    fixed ordering of variables     -g <number>  solve only instances larger than <number>     -h[a|A <file>]  <order>  use the orthogonal combination of the different                     heuristic methods. (a = always run all methods, the maximal                    number of visited nodes of following methods is restricted                    by the number required by the previously best method;                     A = run all methods and write output in <file>)                     <order> specifies the order of the methods.                     1=H^/dyn/loc, 2=H^/dyn/glo/, 3=H^/sta/loc, 4=H^/sta/glo,                     A=B^/dyn/loc, B=B^/dyn/glo/, C=B^/sta/loc, D=B^/sta/glo,                    a=B/dyn/loc, b=B/dyn/glo/, c=B/sta/loc, d=B/sta/glo,                    s=C/dyn/loc, t=C/dyn/glo/, u=C/sta/loc, v=C/sta/glo, 		    S=Q/dyn/loc, T=Q/dyn/glo/, U=Q/sta/loc, V=Q/sta/glo,                    i=I/dyn/loc, j=I/dyn/glo/, k=I/sta/loc, l=I/sta/glo,                    <order>=2B4a means that the order is 2,B,4 and finally a.                    NOTE: It is assumed that the files hornsplit,        	            closebasesplit, c8split, q8split and intersplit exist.                     This option overrides the options -c <file>, -f, and -e.      -li <file>   Include all headers of the logfile <file>    -le <file>   Exclude all headers of the logfile <file>                 NOTE: `-li <file>' must be given before `-le <file>'.     -m[f] <number> maximal number of nodes to visit (default NV_UPPER_LIMIT)                   if -mf is set (f=factor), then the maximal number of nodes                    to visit is the instance size multiplicated by <number>     -n    restrict summary to negative (inconsistent) cases    -o <file> <number> solve only those CSP that are tagged with [-1,0,1]                        (default -1) (should be a log-file)    -p    restrict summary to positive (consistent) cases    -q    return 0 if (last) CSP was consistent (suppresses -v)     -r    use random variable ordering     -s    return summary info on stdout (even if -q)    -t <file> print return summary to file after typeid changes    -v    give verbose output on stderr after solving a CSP    -w[v] use weighted queue scheme for computing path-consistency           (v = van Beek)    -x <file> print CSPs that could not been solved to file    -z[p] compute path-consistency only (p=print path-consistent CSP to stdout)    file[i] are CSP-input files. If none specified, solve uses stdin.     More than one CSP can be specified in each file (each must be     terminated by a point '.').    Format of the CSP should be <node1> <node2> '(' <relations> ')'.    First line of CSP should contain maximum node id and typeid (string).For example, the following program-call solves the CSP-file "hardproblem" by using the weighted queue scheme and splits the relations as given in the'hornsplit' file. The Output is a summary restricted to those cases which turnout to be non-consistent:	solve -s -n -w -c hornsplit hardproblemThe experiments in the paper were done using the following program calls: Figure 4, path-consistency --------------------------generating instances: gencsp -i 10 -n 50 1000 50 -d 8.0 11.0 0.5 -l 4.0 enforcing path-consistency: solve -z     -t pcnw  (no weights)solve -z -wv -t pcaw  (approx. weights)solve -z -w  -t pcew  (exact weights)The average CPU times can be extracted and combined from the files pcnw, pcaw, and pcew (first value in line "CPU time").Figures 5, 6, and 7, probability of satisfiability --------------------------------------------------generating instances: A: gencsp -i 500 -n 10 100 2 -d 2.0 18.0 0.5 -l 4.0H: gencsp -i 500 -n 10  80 2 -d 4.0 20.0 0.5 -l 4.0 -r nprelssolving instances: solve -w -c hornsplit -f -e -t probsatThe probability of satisfiability (second value in line "Consistent"), the median CPU time (second value in line "CPU times"), and the percentage points of incorrect path-consistency answers (second value (global) minus first value (path) in line "Consistent") can be extracted from the file "probsat". Table 1, Figure 9 and 10, evaluation of heuristics--------------------------------------------------generating instances: A: gencsp -i 500 -n 10 100 2 -d 2.0 18.0 0.5 -l 4.0H: gencsp -i 500 -n 10  80 2 -d 4.0 20.0 0.5 -l 4.0 -r nprelssolving instances: solve -w -c <splitfile> <heuristic> -m 10000 -t heuristic<h> -x hardinst<h>where <splitfile> is either hornsplit, q8split, c8split, closebasesplit, or basesplit. <heuristic> is either -f -e, -f, -e, or empty, and <h> is either _fe, _f, _e, or empty, respectively. The hard instances for the different heuristics are written in the file "hardinst<h>" where their number can be counted. The total number is the number of instances which occur in all 20 files. The CPU times of figures 9 and 10 can be extracted and combined from the files heuristic<h> (median: second value in line "CPU time", 99%-percentile: fifth value in line "CPU times")Table 2 and 3, Figure 11, orthogonal combination of heuristics--------------------------------------------------------generate instances:see above, hard instances are stored in the files hardinst<h>. compute percentage of solved instances: easily calculated from Table 1.compute first response: we recommend to generate a file which contains the headers of all hard instances: grep # hardinst* -h | sort -u > hardheaders This avoids that instances which occur in multiple files are solved more than once.solve -w -ha 1234stuvSTUVABCDabcd -li hardheaders -m 10000 -x hardestinst   hardinst*  > firstresponseThe first value of each line in firstresponse gives the consistency, (0 for inconsistent, 1 for consistent, -1 for unsolved)the third value gives the method which solves the instance with the least number of visited nodes. this number is given as the second value. If instead of -ha we use -hA fullresponse, then the number of visited nodes of each heuristic is written in fullresponse. These values can be used to compute Table 3. Figure 12, solving the hardest of the H instances-------------------------------------------------generating instances:The hardest instances are those which are stored in hardestinst as computed above.  computing first response using at most 100,000 visited nodes: solve -w -ha 1234stuvSTUVABCDabcd -m 100000 hardestinst > firstresponse_hThe values of firstresponse_h are the same as described above for firstresponse. Figure 13 and 14, solving large instances with the best heuristics------------------------------------------------------------------generating instances: gencsp -i 100 -n 110 500 10 -d 2 18 0.5 -l 4.0solving instances: solve -w -h 41sC -mf 2 -x largeunsolved -t largesummaryThe instances which cannot be solved by any of the four heuristics 4,1,s, and C with at most 2n visited nodes are stored in largeunsolved. The probability of satisfiability (second value in line "Consistent"), the averag number of visited nodes (first value in line "Nodes v."), and the 70% and 99% percentile (third and fifth value in line "CPU time") is given in largesummary. All Programs are written by	Ronny Fehling, Bernhard Nebel, Jochen Renz	fehling,nebel,renz@informatik.uni-freiburg.de	http://www.informatik.uni-freiburg.de/~sppraum 			  Institut fuer Informatik                                     	         Albert-Ludwigs-Universitaet                                                   Am Flughafen 17                                                      79110 Freiburg,Germany