3 % Adding a variable
for the current path
.
4 extractDiagnoses
(HSTree
,Diagnoses
):-
5 extractDiagnoses2
(HSTree
, Diagnoses
, []).
7 % Set path
in set
and end recursion
when leaf had been reached
8 extractDiagnoses2
(leaf
, [PathEnd
], PathEnd
).
9 % Finished clearing empty node
10 extractDiagnoses2
(node
([], []), [], _
).
11 extractDiagnoses2
(node
([CsHead
|CsTail
], [CsHeadBranch
|CsTailBranches
]),
12 DiagnosesSet
, CurrentPath
) :-
13 % Add new visited conflict item to the visited path
14 append
(CurrentPath
, [CsHead
], NewPath
),
15 % Recursively collects all paths from the recursive calls into the depth
16 % and the width
and puts them into the DiagnosesSet
17 append
(DepthPaths
, WidthPaths
, DiagnosesSet
),
18 % Continues into the depth of the branch
19 extractDiagnoses2
(CsHeadBranch
,DepthPaths
,NewPath
),
20 % Calls on all conflict items
in the width of the branch
21 extractDiagnoses2
(node
(CsTail
, CsTailBranches
), WidthPaths
, CurrentPath
).
23 % Computes
length of smallest diagnosis
24 getLengthSmallestSet
([Diagnosis
], DiagnosisLength
):-
25 % Calls
length single diagnosis
26 length(Diagnosis
,DiagnosisLength
).
27 getLengthSmallestSet
([HeadDiagnosis
|RestOfDiagnoses
], Minimal
):-
28 % Recursively gets the
length of tail
.
29 getLengthSmallestSet
(RestOfDiagnoses
, RestLength
),
30 % Initialises
length of the head diagnosis
.
31 length(HeadDiagnosis
,HeadLength
),
32 % Gets minimal
length of diagnoses
.
33 Minimal is min
(HeadLength
, RestLength
).
37 %Checks if the set isn
't bigger than the smallest set.
41 getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets):-
42 %Gets the length of the smallest set to prune the diagnoses.
43 %Break so that there will be no backtracking if something goes wrong.
44 getLengthSmallestSet(DiagnosesSets,Length),!,
45 % Excludes sets that are bigger than the smallest set
46 exclude(filterLength(Length), DiagnosesSets, MinimalDiagnosesSets).
48 % Function that returns minimal hitting sets from a problem.
49 subsetMinimalDiagnoses(SD, COMP, OBS, HsTree, DiagnosesSets, MinimalDiagnosesSets) :-
50 % Generate hitting tree.
51 generateHittingSetTree(SD, COMP, OBS, [], HsTree),
53 % Get diagnoses out of the hitting tree.
54 extractDiagnoses(HsTree, DiagnosesSets),
56 % Determine smallest diagnoses.
57 getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets).