:- use_module(library(lists)). :- use_module(library(apply_macros)). % call hypothesisSelection(startNode,FinalHypothesis) % output is a candidate hypothesis which include the current node. This hypothesis is accompanied by its properties: DL-EITIs-H. H = sets of ClaID with their coverage. % why EITIs, rather than EIs -- that will make the scoring even easier? -- But when you calculate the intersection with current node, EITI will make it easy. -- that is why EIs is not included, because it will be changed after computing the intersection. hypothesisSelection(CurrentNode,BestCandidate):- expandNode(CurrentNode,ChildNodes), extractEndNode(ChildNodes,EndNodeEITIs0,NonEndChildNodes),sort(EndNodeEITIs0,EndNodeEITIs), maplist(hypothesisSelection,NonEndChildNodes,ReturnedCandidates), % if NonEndChildNodes=[], then--??? (EndNodeEITIs0==[]-> candidateSelection(ReturnedCandidates,CurrentNode,BestCandidate); candidateSelection([0-EndNodeEITIs-[]|ReturnedCandidates],CurrentNode,BestCandidate)). expandNode(CurrentNode,ChildNodes):- findall(Child,connect(CurrentNode,Child),ChildNodes). extractEndNode([],[],[]). extractEndNode([ChildNode|ChildNodes],EndNodeCoverge,NonEndNode):- extractEndNode(ChildNodes,PreEndNodeCoverge,PreNonEndNode), (ChildNode=endNode-EI-TI -> EndNodeCoverge=[EI-TI|PreEndNodeCoverge], NonEndNode=PreNonEndNode; EndNodeCoverge=PreEndNodeCoverge, NonEndNode=[ChildNode|PreNonEndNode] ). % The returned candidate include the current node, while the scoring doesn't: when combining, don't want to include the current node repeatedly. % score, then sort, then combine -- start from the highest score % group is done before scoring? there is scoring and sorting within each group % then another scoring and sorting for those chosen from the group. candidateSelection(ReturnedCandidates,CurrentNode,DescriptionLength-EITIs-[CurrentNode-EITIs|NewCandidate]):- maplist(scoreCandidateBranches(CurrentNode),ReturnedCandidates,ScoredCandidates0), selectlist(nonNegativeScoreBranch,ScoredCandidates0,ScoredCandidates), % filter out those nonZero branches first before combining sort(ScoredCandidates,SortedScoredCandidates), combine_and_competing(SortedScoredCandidates,DescriptionLength0-EICoverage-EITIs-NewCandidate), claLength(CurrentNode,CurrentNodeDescriptionLength), DescriptionLength is DescriptionLength0+CurrentNodeDescriptionLength. nonNegativeScoreBranch(Score-DL-EIs-EITIs-CandidateBranch):- Score>=0. % coverage and description length (the currentNode is only used for obtaining the intersection of coverage) scoreCandidateBranches(CurrentNode,CandidateDescriptionLength-EITIs-Candidate,Score-CandidateDescriptionLength-NewEIs-NewEITIs-Candidate):- claNode(CurrentNode,CurrendNodeEITIs), ord_intersection(EITIs,CurrendNodeEITIs,NewEITIs), exExtraction(NewEITIs,NewEIs), length(NewEIs,NewEINum), Score is 3*NewEINum-CandidateDescriptionLength. % Input is [1-1,1-2,2-1,2-2,2-3], then the output is [1,2] exExtraction([],[]). exExtraction([EI-TI|Record],EIs):- exExtraction(Record,PreEIs), (PreEIs=[EI|Rest] -> EIs=PreEIs; EIs=[EI|PreEIs] ). identifyComputingPart(EITIs,PreEITIs,CompetingEIs):- exExtraction(EITIs,EIs), exExtraction(PreEITIs,PreEIs), ord_intersection(EIs,PreEIs,CompetingEIs). % combining from the highest score. -- for the last one, which has highest score, just % competing with each other for the same example. % Combined Candidate is DescriptionLength-EICoverage-EITIs-NewCandidate combine_and_competing([Score-DescriptionLength-EICoverage-CandidateEITIs-Candidate],DescriptionLength-EICoverage-CandidateEITIs-Candidate). combine_and_competing([Score-DL-EIs-EITIs-Candidate|SortedScoredCandidates],NewDL-NewEIs-NewEITIs-NewCandidate):- combine_and_competing(SortedScoredCandidates,PreDL-PreEIs-PreEITIs-PreCandidate), % now is the computing between Pre and the newly adding candidate %identifyComputingPart(EITIs,PreEITIs,CompetingEIs),% ord_intersection(EIs,PreEIs,CompetingEIs), (CompetingEIs=[] -> combineTwoRecordedCandidate(EITIs-Candidate,PreEITIs-PreCandidate,NewDL-NewEIs-NewEITIs-NewCandidate); powersets(ComputingEIs,Possibles), maplist(getCompensatedPair(ComputingEIs),Possibles,CompensatedPairs), maplist(combine_and_score,CompensatedPairs,ScoredPossibleCombinations), sort(ScoredPossibleCombinations,SortedScoredPossibleCombinations), % choose the head -- the one with lowest DL. -- that is the NewCandidate getCompensatedPair(TotalSet,Set,{Set,CompensatedSet}):- ord_subtract(TotalSet,Set,CompensatedSet). % another function that take in such a pair -- produce a candidate -- re-score(remove-duplicate(be careful -- they may just have different EI_Coverage)->description length -- their EI coverage remains the same -- all is comparisons about description length ) combineTwoCompetingCandidates({EIs1,EIs2},Candidate1,Candidate2,NewDL-CombinedEIs-CombinedEITIs-CombinedCandidate):- isolation(Candidate1,EIs1,RemainEITIs1-RemainCandidate1), %OverlapEITIs-CandidateOverlapPart), isolation(Candidate2,EIs2,RemainEITIs2-RemainCandidate2), combineTwoRecordedCandidate(RemainEITIs1-RemainCandidate1,RemainEITIs2-RemainCandidate2,NewDL-CombinedEIs-CombinedEITIs-CombinedCandidate) new isolation -- take care update the EITI for the removed ones score -- simply description length. % update about EITIs -- you don't need % update about EIs % update about DL. isolation(Candidate,CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart), descriptionLength(CandidateOverlapPart,OverlapDescriptionLength), isolation(PreCandidate,CompetingEIs,PreRemainEITIs-PreRemainCandidate,PreOverlapEITIs-PreCandidateOverlapPart), descriptionLength(PreCandidateOverlapPart,PreOverlapDescriptionLength), (OverlapDescriptionLength>=PreOverlapDescriptionLength-> write({OverlapDescriptionLength,PreOverlapDescriptionLength}),write('the new one is more expensive, so keep the previous one'), DL is PreDL+DescriptionLength-OverlapDescriptionLength, % then you should keep the one in PreOverlap exExtraction(RemainEITIs,RemainEIs), ord_union(RemainEIs,PreEICoverage,NewEICoverage), ord_union(RemainEITIs,PreEITIs,NewEITIs), maplist(removeAlones(OverlapEITIs),RemainCandidate,RemainCandidate_noRedundant), append(RemainCandidate_noRedundant,PreCandidate,NewCandidate); write({OverlapDescriptionLength,PreOverlapDescriptionLength}),write('not more expensive, so use the old one'), DL is PreDL+DescriptionLength-PreOverlapDescriptionLength, ord_union(EICoverage,PreRemainEITIs,NewEICoverage), ord_union(CandidateEITIs,PreRemainEITIs,NewEITIs), maplist(removeAlones(PreOverlapEITIs),PreRemainCandidate,PreRemainCandidate_noRedundant), append(Candidate,PreRemainCandidate_noRedundant,NewCandidate) ) ). %). % *** when you remove certain bits, the EITI coverage is changed! -- the EITI is not simply the isolation you have now -- you can remove the DL and PreDL -- that two info is not used % suppose there is redundancy (DAG) combineTwoRecordedCandidate(EITIs-Candidate,PreEITIs-PreCandidate,NewDL-NewEIs-NewEITIs-NewCandidate):- ord_union(EITIs,PreEITIs,NewEITIs), exExtraction(NewEITIs,NewEIs), combineTwoCandidate(Candidate,PreCandidate,NewCandidate), descriptionLength(NewCandidate,NewDL). combineTwoCandidate([],PreCandidate,PreCandidate). combineTwoCandidate([ClaID-ClaEITIs|Candidate],PreCandidate,NewCandidateUpdated):- combineTwoCandidate(Candidate,PreCandidate,NewCandidate), (append(PreClas,[ClaID-ClaPreEITIs|AfterClas],NewCandidate) -> append(ClaEITIs,ClaPreEITIs,ClaNewEITIs), append(PreClas,[ClaID-ClaNewEITIs|AfterClas],NewCandidateUpdated); NewCandidateUpdated=[ClaID-ClaEITIs|NewCandidate] ). removeAlones(AloneEITIs,ClaID-EITIs,ClaID-EITIsNoAlone):- %nl,write({EITIs,AloneEITIs}), write('check whether they are in order'),nl, ord_subtract(EITIs,AloneEITIs,EITIsNoAlone). isolation([],CompetingEIs,[]-[],[]-[]). isolation([ClaID-ClaEITIs|Candidate],CompetingEIs,RemainEITIs-RemainCandidate,OverlapEITIs-CandidateOverlapPart):- isolation(Candidate,CompetingEIs,PreRemainEITIs-PreRemainCandidate,PreOverlapEITIs-PreCandidateOverlapPart), exExtraction(ClaEITIs,ClaEIs), (ord_subset(ClaEIs,CompetingEIs)-> % Here maybe a problem, what if it just contains part of the computing EI? RemainEITIs-RemainCandidate=PreRemainEITIs-PreRemainCandidate, ord_union(ClaEITIs,PreOverlapEITIs,OverlapEITIs), CandidateOverlapPart=[ClaID-ClaEITIs|PreCandidateOverlapPart]; OverlapEITIs-CandidateOverlapPart=PreOverlapEITIs-PreCandidateOverlapPart, ord_union(ClaEITIs,PreRemainEITIs,RemainEITIs), RemainCandidate=[ClaID-ClaEITIs|PreRemainCandidate] ). % if a subset, then remove that clause -- update the EITI in the rest of the clauses. % what if the remaining become uncompressed because -- no worry, it will be removed when new branch come. -- simply check whether the remaining still has coverage -- remove the one with single coverage -- long description: e.g. two computing components -- you can't simply remove that branch, maybe the rest still worth for that -- you are allowing the flexibility to decompose the module. % no worry, you can make the selection at this step more complicated later. % selectlist(extractCompetingCla(CompetingEIs),) % no, it is better to isolate % for each claID, removing those belongs -- for the competing part, it doesn't necessarily always one branch, maybe a combination. descriptionLength([],0). descriptionLength([ClaID-ClaEICoverage|Candidate],DescriptionLength):- descriptionLength(Candidate,PreDescriptionLength), %claInterprete(ClaID,Cla),length(Cla,ClaDescriptionLength), -- don't worry about translate them more than once, since there is no redundant node -- probably there is (due to the DAG) claLength(ClaID,ClaDescriptionLength), DescriptionLength is PreDescriptionLength+ClaDescriptionLength.