3 generateHittingSetTree
(SD
, COMP
, OBS
, HS
, HSTREE
) :- %test with problem1
(SD
,COMP
,OBS
), generateHittingSetTree
(SD
,COMP
,OBS
,[],T
). This needs to report node
([a1
], [node
([a2
], [leaf
])]).
4 tp
(SD
, COMP
, OBS
, HS
, CS
) -> generateParts
(SD
, COMP
, OBS
, HS
, CS
, HSTREE
) ; generateParts
(_
, _
, _
, _
, [], HSTREE
). %second part of the OR is needed to translate an empty conflict set into a leaf
.
6 generateParts
(_
,_
,_
,_
, [],leaf
).%generates leaf
if at the end of all possible conflict sets
in a branch
7 generateParts
(SD
, COMP
, OBS
, HS
, CS
, node
(CS
, RESTOFTREE
)) :- %generates node
if the conflict set isn
't empty and goes on.
8 repairBranch(SD, COMP, OBS, HS, CS, RESTOFTREE). %repairs the branch by branching out for each item in the conflict set and generating new conflict sets for the next node
11 repairBranch(SD, COMP, OBS, HS, [CS], [X]) :- %single item left in conflict set
12 append(HS, [CS], HSNEW), %add the used conflict set item for this branch to the new hitting set
13 generateHittingSetTree(SD, COMP, OBS, HSNEW, X). %find the next new conflict set with the new hitted item
14 repairBranch(SD, COMP, OBS, HS, [CSHEAD|CSTAIL], [X|Xs]) :- %multiple items left in conflict set
15 append(HS, [CSHEAD], HSNEW), %add the used conflict set item for this branch to the new hitting set
16 generateHittingSetTree(SD, COMP, OBS, HSNEW, X), %find the next new conflict set with the new hitted item
17 repairBranch(SD, COMP, OBS, HS, CSTAIL, Xs). %goes on in recursion for each item in the conflict set of the current node