Debian Codegraph @

Source/Reasoner/Preprocess/CCoreOntologyCyclesExtractorPreProcess.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #include "CCoreOntologyCyclesExtractorPreProcess.h"
22
23
24 namespace Konclude {
25
26 namespace Reasoner {
27
28 namespace Preprocess {
29
30
31 CCoreOntologyCyclesExtractorPreProcess::CCoreOntologyCyclesExtractorPreProcess() {
32 }
33
34
35 CCoreOntologyCyclesExtractorPreProcess::~CCoreOntologyCyclesExtractorPreProcess() {
36 }
37
38
39 bool CCoreOntologyCyclesExtractorPreProcess::addConceptsToList(CSortedNegLinker<CConcept*>* opLinker, bool negated, QList<TConceptNegPair>& nextTestingConceptList) {
40 for (CSortedNegLinker<CConcept*>* opLinkerIt = opLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
41 CConcept* opConcept = opLinkerIt->getData();
42 bool opConNeg = opLinkerIt->isNegated()^negated;
43 nextTestingConceptList.append(TConceptNegPair(opConcept,opConNeg));
44 }
45 return true;
46 }
47
48
49
50
51 bool CCoreOntologyCyclesExtractorPreProcess::getConceptCycle(QSet<TConceptNegPair>* visitedConceptSet, QSet<TConceptNegPair>* cylceConceptSet, bool* cycleNominalConnection) {
52
53 bool cycleClosed = false;
54 bool nominalConn = false;
55 QHash<TConceptNegPair,CTestingItem*> testedConceptHash;
56
57 QList<CTestingItem*> itemContainer;
58 QList<CTestingItem*> testingConceptList;
59 QList<TConceptNegPair> nextTestingConceptList;
60
61 for (QSet<TConceptNegPair>::const_iterator it = cylceConceptSet->constBegin(), itEnd = cylceConceptSet->constEnd(); it != itEnd; ++it) {
62 TConceptNegPair testConNegPair(*it);
63 CConcept* testingConcept = testConNegPair.first;
64 bool testConNegation = testConNegPair.second;
65
66 CSortedNegLinker<CConcept*>* opConLinker = testingConcept->getOperandList();
67
68 cint64 testOpCode = testingConcept->getOperatorCode();
69 if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
70 || testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
71
72 addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
73
74 CRole* role = testingConcept->getRole();
75 if (role) {
76 addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
77 addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
78 }
79
80 } else if (testOpCode == CCAQCHOOCE) {
81 for (CSortedNegLinker<CConcept*>* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
82 CConcept* opConcept = opLinkerIt->getData();
83 bool opConNeg = opLinkerIt->isNegated();
84 if (opConNeg == testConNegation) {
85 nextTestingConceptList.append(TConceptNegPair(opConcept,false));
86 }
87 }
88 }
89
90 while (!nextTestingConceptList.isEmpty()) {
91 TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
92 if (!cylceConceptSet->contains(nextConNegPair)) {
93 CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair);
94 itemContainer.append(nextTestingItem);
95 // depth first search
96 testingConceptList.prepend(nextTestingItem);
97 }
98 }
99 }
100
101
102 while (!testingConceptList.isEmpty()) {
103 CTestingItem* testingItem = testingConceptList.takeFirst();
104 TConceptNegPair testConNegPair(testingItem->mConNegPair);
105 CConcept* testingConcept = testConNegPair.first;
106 bool testConNegation = testConNegPair.second;
107
108 if (cylceConceptSet->contains(testConNegPair)) {
109
110 QList<CTestingItem*> backtrackingItemList;
111 backtrackingItemList.append(testingItem->mPrevItem);
112
113 while (!backtrackingItemList.isEmpty()) {
114 CTestingItem* testedItem = backtrackingItemList.takeFirst();
115
116 if (testedItem && !cylceConceptSet->contains(testedItem->mConNegPair)) {
117 cylceConceptSet->insert(testedItem->mConNegPair);
118 QList<CTestingItem*> depList(testedConceptHash.values(testedItem->mConNegPair));
119 foreach (CTestingItem* depTestedItem, depList) {
120 if (depTestedItem) {
121 backtrackingItemList.append(depTestedItem);
122 }
123 }
124 }
125 }
126
127
128
129
130 }
131
132 if (!testedConceptHash.contains(testConNegPair)) {
133
134
135 CSortedNegLinker<CConcept*>* opConLinker = testingConcept->getOperandList();
136
137 cint64 testOpCode = testingConcept->getOperatorCode();
138 if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
139 || testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
140
141 addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
142
143 CRole* role = testingConcept->getRole();
144 if (role) {
145 addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
146 addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
147 }
148
149 } else if (testOpCode == CCAQCHOOCE) {
150 for (CSortedNegLinker<CConcept*>* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
151 CConcept* opConcept = opLinkerIt->getData();
152 bool opConNeg = opLinkerIt->isNegated();
153 if (opConNeg == testConNegation) {
154 nextTestingConceptList.append(TConceptNegPair(opConcept,false));
155 }
156 }
157 } else if (testOpCode == CCNOMINAL || testOpCode == CCVALUE) {
158 nominalConn = true;
159 }
160
161 while (!nextTestingConceptList.isEmpty()) {
162 TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
163 CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair,testingItem->mSearchingDepth+1,testingItem);
164 itemContainer.append(nextTestingItem);
165 // depth first search
166 testingConceptList.prepend(nextTestingItem);
167 }
168
169 }
170 testedConceptHash.insertMulti(testConNegPair,testingItem->mPrevItem);
171 }
172
173 cDeleteAll(itemContainer);
174
175
176 for (QSet<TConceptNegPair>::const_iterator it = cylceConceptSet->constBegin(), itEnd = cylceConceptSet->constEnd(); it != itEnd; ++it) {
177 TConceptNegPair testConNegPair(*it);
178 visitedConceptSet->insert(testConNegPair);
179 }
180
181 if (cycleNominalConnection) {
182 *cycleNominalConnection = nominalConn;
183 }
184
185 return true;
186 }
187
188
189
190 bool CCoreOntologyCyclesExtractorPreProcess::hasConceptCycle(CConcept* concept, bool negated, QSet<TConceptNegPair>* visitedConceptSet, QSet<TConceptNegPair>* cylceConceptSet) {
191
192 TConceptNegPair conNegPair(concept,negated);
193
194 if (!visitedConceptSet->contains(conNegPair)) {
195
196 bool cycleClosed = false;
197 QHash<TConceptNegPair,CTestingItem*> testedConceptDepHash;
198
199 QList<CTestingItem*> itemContainer;
200 QList<CTestingItem*> testingConceptList;
201 CTestingItem* firstTestingItem = new CTestingItem(conNegPair);
202 itemContainer.append(firstTestingItem);
203 testingConceptList.append(firstTestingItem);
204
205 QList<TConceptNegPair> nextTestingConceptList;
206
207 while (!testingConceptList.isEmpty() && !cycleClosed) {
208 CTestingItem* testingItem = testingConceptList.takeFirst();
209 TConceptNegPair testConNegPair(testingItem->mConNegPair);
210 CConcept* testingConcept = testConNegPair.first;
211 bool testConNegation = testConNegPair.second;
212
213 CTestingItem* alreadyTestedItem = testedConceptDepHash.value(testConNegPair,nullptr);
214 if (alreadyTestedItem) {
215
216
217 if (alreadyTestedItem->mSearchingDepth < testingItem->mSearchingDepth) {
218 // test for real cycle
219 bool foundCycle = false;
220 CTestingItem* prevTestedItemIt = testingItem->mPrevItem;
221 while (prevTestedItemIt && !foundCycle) {
222 if (testConNegPair == prevTestedItemIt->mConNegPair) {
223 foundCycle = true;
224 }
225 prevTestedItemIt = prevTestedItemIt->mPrevItem;
226 }
227 if (foundCycle) {
228 CTestingItem* prevTestedItemIt = testingItem->mPrevItem;
229 while (prevTestedItemIt && !cycleClosed) {
230 cylceConceptSet->insert(prevTestedItemIt->mConNegPair);
231
232 if (testConNegPair == prevTestedItemIt->mConNegPair) {
233 cycleClosed = true;
234 }
235 prevTestedItemIt = prevTestedItemIt->mPrevItem;
236 }
237 }
238 }
239 // concept is already examined, no cycle for this concept
240
241
242 } else {
243 if (!visitedConceptSet->contains(testConNegPair)) {
244 visitedConceptSet->insert(testConNegPair);
245 // examine concept and sub concepts
246 testedConceptDepHash.insert(testConNegPair,testingItem);
247
248 CSortedNegLinker<CConcept*>* opConLinker = testingConcept->getOperandList();
249
250 cint64 testOpCode = testingConcept->getOperatorCode();
251 if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
252 || testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
253
254 addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
255
256 CRole* role = testingConcept->getRole();
257 if (role) {
258 addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
259 addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
260 }
261
262 } else if (testOpCode == CCAQCHOOCE) {
263 for (CSortedNegLinker<CConcept*>* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
264 CConcept* opConcept = opLinkerIt->getData();
265 bool opConNeg = opLinkerIt->isNegated();
266 if (opConNeg == testConNegation) {
267 nextTestingConceptList.append(TConceptNegPair(opConcept,false));
268 }
269 }
270 }
271
272 while (!nextTestingConceptList.isEmpty()) {
273 TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
274 CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair,testingItem->mSearchingDepth+1,testingItem);
275 itemContainer.append(nextTestingItem);
276 // depth first search
277 testingConceptList.prepend(nextTestingItem);
278 }
279 }
280
281 }
282
283 }
284
285 cDeleteAll(itemContainer);
286 return cycleClosed;
287
288 }
289 return false;
290 }
291
292
293
294 CConcreteOntology* CCoreOntologyCyclesExtractorPreProcess::preprocess(CConcreteOntology* ontology, CPreProcessContext* context) {
295
296 bool skipForELOntologies = CConfigDataReader::readConfigBoolean(context->getConfiguration(),"Konclude.Calculation.Preprocessing.CoreConceptCyclesExtraction.SkipForELFragment",true);
297 bool nonELConstructsUsed = ontology->getDataBoxes()->getExpressionDataBoxMapping()->getBuildConstructFlags()->isNonELConstructUsed();
298
299 bool nominalsUsed = ontology->getStructureSummary()->hasNominalOccurrence();
300
301 if (nominalsUsed && (nonELConstructsUsed || !skipForELOntologies)) {
302
303 CTBox* tbox = ontology->getDataBoxes()->getTBox();
304 CABox* abox = ontology->getDataBoxes()->getABox();
305 CRBox* rbox = ontology->getDataBoxes()->getRBox();
306
307 CConceptVector* conVec = tbox->getConceptVector();
308 qint64 itemConCounts = conVec->getItemCount();
309
310 QSet<TConceptNegPair> visitedConceptSet;
311 COntologyContext* ontoContext = ontology->getOntologyContext();
312 CMemoryAllocationManager* mMemMan = ontoContext->getMemoryAllocationManager();
313 COntologyCoreConceptCyclesData* coreConCyclesData = ontology->getCoreConceptCyclesData();
314
315 mStatExtractedCyclesCount = 0;
316 mStatCyclicConceptsCount = 0;
317
318 cint64 nextCycleID = 0;
319
320 for (qint64 i = 0; i < itemConCounts; ++i) {
321 CConcept* concept = conVec->getData(i);
322 if (concept) {
323 cint64 opCode = concept->getOperatorCode();
324 if (opCode == CCSOME || opCode == CCALL || opCode == CCATLEAST || opCode == CCAQSOME || opCode == CCSOME || opCode == CCSUB || opCode == CCEQ) {
325 bool negated = opCode == CCALL || opCode == CCATMOST;
326 bool opNegated = opCode == CCALL;
327
328 CSortedNegLinker<CConcept*>* opLinkerIt = concept->getOperandList();
329 while (opLinkerIt) {
330
331 CConcept* opConcept = concept;
332 bool opNegate = opNegated^opLinkerIt->isNegated();
333
334 QSet<TConceptNegPair> cylceConceptSet;
335
336 if (hasConceptCycle(opConcept,opNegate,&visitedConceptSet,&cylceConceptSet)) {
337 bool cycleNominalConnection = false;
338 if (getConceptCycle(&visitedConceptSet,&cylceConceptSet,&cycleNominalConnection)) {
339
340 ++mStatExtractedCyclesCount;
341 cint64 cycleConceptCount = cylceConceptSet.count();
342 mStatCyclicConceptsCount += cycleConceptCount;
343
344 CConceptCycleData* conCycleData = CObjectParameterizingAllocator< CConceptCycleData,CContext* >::allocateAndConstructAndParameterize(mMemMan,ontoContext);
345 conCycleData->initConceptCycleData();
346 conCycleData->addCycleConcepts(cylceConceptSet);
347 conCycleData->setNominalConnection(cycleNominalConnection);
348 conCycleData->setCycleID(nextCycleID++);
349
350 coreConCyclesData->installCycle(conCycleData);
351
352 }
353 }
354
355 opLinkerIt = opLinkerIt->getNext();
356 }
357 }
358 }
359 }
360
361 LOG(INFO,"::Konclude::Reasoner::Preprocess::CoreConceptCycleExtractor",logTr("Found %1 concept cycles with %2 cyclic concepts.").arg(mStatExtractedCyclesCount).arg(mStatCyclicConceptsCount),this);
362 }
363
364 return ontology;
365 }
366
367
368 }; // end namespace Preprocess
369
370 }; // end namespace Reasoner
371
372 }; // end namespace Konclude