/*
* Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
*
* This file is part of the reasoning system Konclude.
* For details and support, see .
*
* Konclude is free software: you can redistribute it and/or modify
* it under the terms of version 3 of the GNU Lesser General Public
* License (LGPLv3) as published by the Free Software Foundation.
*
* Konclude is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU (Lesser) General Public License for more details.
*
* You should have received a copy of the GNU (Lesser) General Public
* License along with Konclude. If not, see .
*
*/
#include "CCoreOntologyCyclesExtractorPreProcess.h"
namespace Konclude {
namespace Reasoner {
namespace Preprocess {
CCoreOntologyCyclesExtractorPreProcess::CCoreOntologyCyclesExtractorPreProcess() {
}
CCoreOntologyCyclesExtractorPreProcess::~CCoreOntologyCyclesExtractorPreProcess() {
}
bool CCoreOntologyCyclesExtractorPreProcess::addConceptsToList(CSortedNegLinker* opLinker, bool negated, QList& nextTestingConceptList) {
for (CSortedNegLinker* opLinkerIt = opLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
CConcept* opConcept = opLinkerIt->getData();
bool opConNeg = opLinkerIt->isNegated()^negated;
nextTestingConceptList.append(TConceptNegPair(opConcept,opConNeg));
}
return true;
}
bool CCoreOntologyCyclesExtractorPreProcess::getConceptCycle(QSet* visitedConceptSet, QSet* cylceConceptSet, bool* cycleNominalConnection) {
bool cycleClosed = false;
bool nominalConn = false;
QHash testedConceptHash;
QList itemContainer;
QList testingConceptList;
QList nextTestingConceptList;
for (QSet::const_iterator it = cylceConceptSet->constBegin(), itEnd = cylceConceptSet->constEnd(); it != itEnd; ++it) {
TConceptNegPair testConNegPair(*it);
CConcept* testingConcept = testConNegPair.first;
bool testConNegation = testConNegPair.second;
CSortedNegLinker* opConLinker = testingConcept->getOperandList();
cint64 testOpCode = testingConcept->getOperatorCode();
if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
|| testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
CRole* role = testingConcept->getRole();
if (role) {
addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
}
} else if (testOpCode == CCAQCHOOCE) {
for (CSortedNegLinker* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
CConcept* opConcept = opLinkerIt->getData();
bool opConNeg = opLinkerIt->isNegated();
if (opConNeg == testConNegation) {
nextTestingConceptList.append(TConceptNegPair(opConcept,false));
}
}
}
while (!nextTestingConceptList.isEmpty()) {
TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
if (!cylceConceptSet->contains(nextConNegPair)) {
CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair);
itemContainer.append(nextTestingItem);
// depth first search
testingConceptList.prepend(nextTestingItem);
}
}
}
while (!testingConceptList.isEmpty()) {
CTestingItem* testingItem = testingConceptList.takeFirst();
TConceptNegPair testConNegPair(testingItem->mConNegPair);
CConcept* testingConcept = testConNegPair.first;
bool testConNegation = testConNegPair.second;
if (cylceConceptSet->contains(testConNegPair)) {
QList backtrackingItemList;
backtrackingItemList.append(testingItem->mPrevItem);
while (!backtrackingItemList.isEmpty()) {
CTestingItem* testedItem = backtrackingItemList.takeFirst();
if (testedItem && !cylceConceptSet->contains(testedItem->mConNegPair)) {
cylceConceptSet->insert(testedItem->mConNegPair);
QList depList(testedConceptHash.values(testedItem->mConNegPair));
foreach (CTestingItem* depTestedItem, depList) {
if (depTestedItem) {
backtrackingItemList.append(depTestedItem);
}
}
}
}
}
if (!testedConceptHash.contains(testConNegPair)) {
CSortedNegLinker* opConLinker = testingConcept->getOperandList();
cint64 testOpCode = testingConcept->getOperatorCode();
if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
|| testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
CRole* role = testingConcept->getRole();
if (role) {
addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
}
} else if (testOpCode == CCAQCHOOCE) {
for (CSortedNegLinker* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
CConcept* opConcept = opLinkerIt->getData();
bool opConNeg = opLinkerIt->isNegated();
if (opConNeg == testConNegation) {
nextTestingConceptList.append(TConceptNegPair(opConcept,false));
}
}
} else if (testOpCode == CCNOMINAL || testOpCode == CCVALUE) {
nominalConn = true;
}
while (!nextTestingConceptList.isEmpty()) {
TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair,testingItem->mSearchingDepth+1,testingItem);
itemContainer.append(nextTestingItem);
// depth first search
testingConceptList.prepend(nextTestingItem);
}
}
testedConceptHash.insertMulti(testConNegPair,testingItem->mPrevItem);
}
cDeleteAll(itemContainer);
for (QSet::const_iterator it = cylceConceptSet->constBegin(), itEnd = cylceConceptSet->constEnd(); it != itEnd; ++it) {
TConceptNegPair testConNegPair(*it);
visitedConceptSet->insert(testConNegPair);
}
if (cycleNominalConnection) {
*cycleNominalConnection = nominalConn;
}
return true;
}
bool CCoreOntologyCyclesExtractorPreProcess::hasConceptCycle(CConcept* concept, bool negated, QSet* visitedConceptSet, QSet* cylceConceptSet) {
TConceptNegPair conNegPair(concept,negated);
if (!visitedConceptSet->contains(conNegPair)) {
bool cycleClosed = false;
QHash testedConceptDepHash;
QList itemContainer;
QList testingConceptList;
CTestingItem* firstTestingItem = new CTestingItem(conNegPair);
itemContainer.append(firstTestingItem);
testingConceptList.append(firstTestingItem);
QList nextTestingConceptList;
while (!testingConceptList.isEmpty() && !cycleClosed) {
CTestingItem* testingItem = testingConceptList.takeFirst();
TConceptNegPair testConNegPair(testingItem->mConNegPair);
CConcept* testingConcept = testConNegPair.first;
bool testConNegation = testConNegPair.second;
CTestingItem* alreadyTestedItem = testedConceptDepHash.value(testConNegPair,nullptr);
if (alreadyTestedItem) {
if (alreadyTestedItem->mSearchingDepth < testingItem->mSearchingDepth) {
// test for real cycle
bool foundCycle = false;
CTestingItem* prevTestedItemIt = testingItem->mPrevItem;
while (prevTestedItemIt && !foundCycle) {
if (testConNegPair == prevTestedItemIt->mConNegPair) {
foundCycle = true;
}
prevTestedItemIt = prevTestedItemIt->mPrevItem;
}
if (foundCycle) {
CTestingItem* prevTestedItemIt = testingItem->mPrevItem;
while (prevTestedItemIt && !cycleClosed) {
cylceConceptSet->insert(prevTestedItemIt->mConNegPair);
if (testConNegPair == prevTestedItemIt->mConNegPair) {
cycleClosed = true;
}
prevTestedItemIt = prevTestedItemIt->mPrevItem;
}
}
}
// concept is already examined, no cycle for this concept
} else {
if (!visitedConceptSet->contains(testConNegPair)) {
visitedConceptSet->insert(testConNegPair);
// examine concept and sub concepts
testedConceptDepHash.insert(testConNegPair,testingItem);
CSortedNegLinker* opConLinker = testingConcept->getOperandList();
cint64 testOpCode = testingConcept->getOperatorCode();
if (!testConNegation && (testOpCode == CCEQ || testOpCode == CCSUB || testOpCode == CCAND || testOpCode == CCSOME || testOpCode == CCATLEAST || testOpCode == CCAQSOME)
|| testConNegation && (testOpCode == CCOR || testOpCode == CCALL)) {
addConceptsToList(opConLinker,testConNegation,nextTestingConceptList);
CRole* role = testingConcept->getRole();
if (role) {
addConceptsToList(role->getDomainConceptList(),false,nextTestingConceptList);
addConceptsToList(role->getRangeConceptList(),false,nextTestingConceptList);
}
} else if (testOpCode == CCAQCHOOCE) {
for (CSortedNegLinker* opLinkerIt = opConLinker; opLinkerIt; opLinkerIt = opLinkerIt->getNext()) {
CConcept* opConcept = opLinkerIt->getData();
bool opConNeg = opLinkerIt->isNegated();
if (opConNeg == testConNegation) {
nextTestingConceptList.append(TConceptNegPair(opConcept,false));
}
}
}
while (!nextTestingConceptList.isEmpty()) {
TConceptNegPair nextConNegPair(nextTestingConceptList.takeFirst());
CTestingItem* nextTestingItem = new CTestingItem(nextConNegPair,testingItem->mSearchingDepth+1,testingItem);
itemContainer.append(nextTestingItem);
// depth first search
testingConceptList.prepend(nextTestingItem);
}
}
}
}
cDeleteAll(itemContainer);
return cycleClosed;
}
return false;
}
CConcreteOntology* CCoreOntologyCyclesExtractorPreProcess::preprocess(CConcreteOntology* ontology, CPreProcessContext* context) {
bool skipForELOntologies = CConfigDataReader::readConfigBoolean(context->getConfiguration(),"Konclude.Calculation.Preprocessing.CoreConceptCyclesExtraction.SkipForELFragment",true);
bool nonELConstructsUsed = ontology->getDataBoxes()->getExpressionDataBoxMapping()->getBuildConstructFlags()->isNonELConstructUsed();
bool nominalsUsed = ontology->getStructureSummary()->hasNominalOccurrence();
if (nominalsUsed && (nonELConstructsUsed || !skipForELOntologies)) {
CTBox* tbox = ontology->getDataBoxes()->getTBox();
CABox* abox = ontology->getDataBoxes()->getABox();
CRBox* rbox = ontology->getDataBoxes()->getRBox();
CConceptVector* conVec = tbox->getConceptVector();
qint64 itemConCounts = conVec->getItemCount();
QSet visitedConceptSet;
COntologyContext* ontoContext = ontology->getOntologyContext();
CMemoryAllocationManager* mMemMan = ontoContext->getMemoryAllocationManager();
COntologyCoreConceptCyclesData* coreConCyclesData = ontology->getCoreConceptCyclesData();
mStatExtractedCyclesCount = 0;
mStatCyclicConceptsCount = 0;
cint64 nextCycleID = 0;
for (qint64 i = 0; i < itemConCounts; ++i) {
CConcept* concept = conVec->getData(i);
if (concept) {
cint64 opCode = concept->getOperatorCode();
if (opCode == CCSOME || opCode == CCALL || opCode == CCATLEAST || opCode == CCAQSOME || opCode == CCSOME || opCode == CCSUB || opCode == CCEQ) {
bool negated = opCode == CCALL || opCode == CCATMOST;
bool opNegated = opCode == CCALL;
CSortedNegLinker* opLinkerIt = concept->getOperandList();
while (opLinkerIt) {
CConcept* opConcept = concept;
bool opNegate = opNegated^opLinkerIt->isNegated();
QSet cylceConceptSet;
if (hasConceptCycle(opConcept,opNegate,&visitedConceptSet,&cylceConceptSet)) {
bool cycleNominalConnection = false;
if (getConceptCycle(&visitedConceptSet,&cylceConceptSet,&cycleNominalConnection)) {
++mStatExtractedCyclesCount;
cint64 cycleConceptCount = cylceConceptSet.count();
mStatCyclicConceptsCount += cycleConceptCount;
CConceptCycleData* conCycleData = CObjectParameterizingAllocator< CConceptCycleData,CContext* >::allocateAndConstructAndParameterize(mMemMan,ontoContext);
conCycleData->initConceptCycleData();
conCycleData->addCycleConcepts(cylceConceptSet);
conCycleData->setNominalConnection(cycleNominalConnection);
conCycleData->setCycleID(nextCycleID++);
coreConCyclesData->installCycle(conCycleData);
}
}
opLinkerIt = opLinkerIt->getNext();
}
}
}
}
LOG(INFO,"::Konclude::Reasoner::Preprocess::CoreConceptCycleExtractor",logTr("Found %1 concept cycles with %2 cyclic concepts.").arg(mStatExtractedCyclesCount).arg(mStatCyclicConceptsCount),this);
}
return ontology;
}
}; // end namespace Preprocess
}; // end namespace Reasoner
}; // end namespace Konclude