ArtSponsor is given below (it is stored in the ontology as a definition of type ArtSponsor):
New CG Operations:
Specification, Examples and
Implementation Details
by
Adil KABBAJ
Recall. Apart from operations specified in AmineObject and Matching interfaces and implemented by CG class (and CG Operations), CG has a large set of specific operations: getters and finders to get and find concepts and/or relations, checkers to check various constraints, adders and removers to add/remove concepts and/or relations, setters to set values for specific parameters, file operations (Load/Save) to load/save a CG from/in a file, I/O operations to read/write a CG according to the different CG notations, etc. There is also a set of operations (methods) that implement the canonical formation rules: restrictType(), restrictDesignator(), restrictDescriptor(), generalizeType(), generalizeDesignator(), generalizeDescriptor(), analogizeType() and join(). Also, in addition to the operations specified in Matching interface and implemented by CG class (match(), equal(), unify(), subsume(), maximalJoin(), and generalize()), there is a set of specific CG operations that are either variants or derived from the Matching operations (specialize(), generalise(), isCanonic(), expand()).
New CG operations include contract (with different variants), coveredBy, analogy and compare:
- contract(): contract a CG from another CG taking into account the connectivity and the information specificity of the two graphs. Different versions are provided for the contraction operation.
- analogy(): this analogy operation has some similarity with the analogy engine developed by Falkenhainer, Forbus and Gentner [1, 2]. The operation analogy(sourceCG, targetCG) determines the “best” structural matching of the two CGs and then transfers to the targetCG all the elements that are specific to the source CG and that respect the canonicity of the targetCG (of course, the transfer is based on the result of the matching).
- compare(): compare two CGs and return the detail of the comparison: a) is the first CG equal, more general, more specific, have common information, or have nothing in common with the second CG, b) the common CG (if the two CGs have common information), c) the matched part of the first CG, d) the matched part of the second CG, e) the specific parts of the first CG, and d) the specific parts of the second CG.
- coveredBy(): coveredBy(G1, G2) determines which part (a subgraph S1) of G1 covers a part (a subgraph S2) of G2, i.e. S1 covers S2 if S1 is equal or more specific than S2 (i.e. an isomorphic matching between S1 and S2 modulo equal_or_moreSpecific operation on concepts). coveredBy can be complete if all G1 covers a subgraph from G2 (i.e. if G1 is equal or more specific than a subgraph of G2) or it can be partial if only a subgraph of G1 covers a subgraph of G2. Note that the result, if not null, is a new CG G that is a "view" of G2: concepts and relations of G are (exactly) concepts and relations of G2; they are not copies of these concepts/relations.
The next section provides more detail on these operations: for each operation we specify variant specifications, then some examples and then some implementation details. See CG's API documentation and CGOperations API documentation for more detail on these (and other) new methods.
This section introduces four new CG operations (i.e. methods of CG class): contract (contract type definition and other variants of contraction), analogy, compare and coveredBy. Note that all these operations are implemented as methods of CG class.
contract(): contract a CG from another CG taking into account the connectivity and the information specificity of the two graphs. Different versions are provided for the contraction operation:
Contract the definition of the specified type from the current CG, using the specified concept as the entry point. After, the contraction, the type of the specified concept will be replaced by the specified type. contractTypeDefinition is the inverse of the specializeByExpansion operation. Note that the contraction concerns the CG itself. To proceed otherwise, you can give a copy of the CG to the present method.
boolean contractTypeDefinition(BindingContext bindContext, Object bindInf, Concept concept, Type type);
This is a variant of the previous definition: instead of a Concept as third parameter and Type as forth parameter, this variant accepts two objects with the specification of their binding information. This variant is usefull in a programming context (with a variable that could have a concept or a type as value).
boolean contractTypeDefinition(BindingContext bindContext, Object bindInf,
Object objConcept, Object bindInfObj1,
Object objType, Object bindInfObj2);
Contract the definition of the type of the specified concept from the current CG, using the specified concept as the entry point.
boolean contractTypeDefinition(BindingContext bindContext, Object bindInf, Concept concept);
This is a variant of the previous definition: instead of a Concept as third parameter, this variant allows an object with the specification of its binding information. This variant is usefull in a programming context (with a variable that could have a concept as value).
boolean contractTypeDefinition(BindingContext bindContext, Object bindInf, Object objConcept, Object bindInfObj);
Contract the definition of the specified Type from the current CG.
boolean contractTypeDefinition(Concept concept, Type type);
Contract the definition of the type of the specified concept from the current CG, using the specified concept as the entry point.
boolean contractTypeDefinition(Concept concept);
Contract the definition of the specified Type from the current CG.
boolean contractTypeDefinition(Type type);
Examples
To run the following examples, load first the Ontology "samples/ontology/ManOntology2.xml".
Let us consider the classical
example provided by J. Sowa in his first book: contraction of the definition of
the type ArtSponsor from a current CG. Definition of
ArtSponsor is given below (it is stored in the ontology as a definition of type ArtSponsor):
[Give
#0] -
-obj->[Money],
-rcpt->[Artist],
-agnt->[Man :super]
We illustrate the following example with CGOperations GUI. In the left-top panel we provide a CG, then we specify the concept [Man: Karim] as the entry point and we initiate the contract operation (button Contract). An input dialog appears asking the user the identifier of the type to contract its definition. We give ArtSponsor. The result of the contraction is returned in the bottom panel.
Partial contraction is done to preserve initial information. For instance, contraction of ArtSponsor definition from the following CG:
[Give]
-
-obj->[Money],
-rcpt->[Artist]-attr->[Rich],
-agnt->[Man :Karim]-attr->[Rich]
produces the following result:
[Give #0] -
-rcpt->[Artist]-attr->[Rich],
-agnt->[ArtSponsor :karim]-attr->[Rich]
Note that the contraction will fail if the definition is not more general than the current CG. This is the case for the following CG:
[Give] -
-obj->[Money],
-rcpt->[Human:Mary],
-agnt->[Man :Karim]
Implementation Details
We consider here the typical case of contraction: contract, from a CG G the definition D of a type T. The operation searches first the definition of T, then it checks that D subsumes G (the definition is more general than G). Next, it searches the genus from D and searches, from G the concept C that matched with the genus. The type of C is replaced by T (to initiate the contraction) and then the contact operation is called.
public boolean contractTypeDefinition(CG cg, Type type) {
CG definition = (CG) type.getDefinition();
// Get the definition of the concept type and
check that it is not null
if (definition == null)
return false;
ResMatchCG resMatchCG = this.match(SUBSUME, definition, null, cg, null);
if (resMatchCG == null)
return false;
// We assume here that the
definition contains only one genus.
// Change the type of the concept in cg that matched the genus by
the specified type.
Concept genus = definition.getConceptWithDesignator(Variable.SUPER);
ConcCouple csCple = (ConcCouple) this.conceptsMatched.get(genus);
Concept concInCGMatchedToGenus = csCple.conc1;
concInCGMatchedToGenus.setType(type);
contract(cg, null); // contract
the definition from the specified
cg
return true;
}
Let us consider now the
implementation of contract operation in more detail:
contract attempts to remove all information (branches) that can be removed
without loose of information. This is the role of the first while. Inside,
there is another iteration (the second while) that attempts to remove all
dangling relations. Note that the remove of a dangling relation can render
another relation dangling. So we iterate on the matchedRelations until no
dangling relation remain (this is the role of the embedded loops while--for).
Then, we consider the case of a relation to remove that is not a connecting
relation (removing it will not produce a disconnected graph). If such a relation
exists, it is removed and then we start again the search for dangling relations
(a relation is dangling if either its source or target concept has no other
relation and the "isolated" concept is not specific to cg; it can be recovered
by definition expansion).
void contract(Object bindInf1, CG cg2, Object bindInf2) {
Relation relation;
ArrayList matchedRelations = new ArrayList(this.relationsMatched.values());
boolean removedRelation = true;
while (removedRelation) {
while (removedRelation) {
removedRelation = false;
for (Iterator i = matchedRelations.iterator();
i.hasNext();) {
relation = (Relation) i.next();
if (removeDanglingRelation(bindInf1,
cg2, relation, bindInf2)) {
i.remove();
removedRelation = true;
}
}
} // second while (removedRelation)
for (Iterator i = matchedRelations.iterator(); i.hasNext();)
{
relation = (Relation) i.next();
if (!isConnectingRelation(cg2, relation)) {
cg2.removeRelation(relation);
i.remove();
removedRelation = true;
break;
}
}
} // first while (removedRelation)
matchedRelations.clear();
matchedRelations = null;
}
A relation is dangling if either its source or target concept has no other
relation and the "isolated" concept is not specific to cg; it can be recovered
by definition expansion, i.e. locate the concept in the current CG that matched
the specified concept in cg2 and check if the two concepts are equal (in
content) to be sure that no information will be lost if the concept concInCG2 is
removed (contracted) from cg2.
boolean removeDanglingRelation(Object bindInf1, CG cg2, Relation relation,
Object bindInf2) {
boolean dangling = true;
Concept source = relation.getSourceConcept();
Concept target = relation.getTargetConcept();
if (source.getNbrRelations() == 1 && isConcEQMatched(bindInf1, source,
bindInf2)) {
cg2.removeConcept(source);
// will remove the concept and the relation from
the CG
source = null;
}
else if (target.getNbrRelations() == 1 && isConcEQMatched(bindInf1,
target, bindInf2)) {
cg2.removeConcept(target);
target = null;
}
else
dangling = false;
return dangling;
}
A
relation is a connecting relation if its elimination would make the CG
disconnected.
boolean isConnectingRelation(CG cg, Relation relation) {
Concept source = relation.getSourceConcept();
Concept target = relation.getTargetConcept();
cg.removeRelation(relation);
boolean isThereAPath = isThereAPath(source, target);
// Check if there is a path that link source
to target
cg.addRelation(relation);
return !isThereAPath;
}
Analogy is a CG matching based operation; it determines the "best" structural matching of the two CGs (the source and the target CGs) and then transfer to the target CG all the elements that are specific to the source CG and that respect the canonicity of the targetCG (of course, the transfer is based on the result of the matching).
This variant considers the binding context and the binding information for the two objects as well as the specification of entry points.
boolean analogy(BindingContext bindContext, Object bindInf, Object
entryConcept1, Object bindInfEntry1,
Object obj, Object bindInfObj, Object entryConcept2, Object bindInfEntry2);
Similar to the above definition, except that entry points are not specified.
boolean analogy(BindingContext bindContext, Object bindInf, Object obj, Object bindInfObj);
Similar to the above definition, except that this variant doesn't considers the binding context and the binding information for the two objects.
boolean analogy(Object obj);
Examples
CG operations can be called from CG Operations GUI, from a Java code using CG and CGOperations APIs, and from Amine programming languages (Prolog+CG, Synergy). This example of analogy is provided using Prolog+CG (file: "samples/prologPlusCG/CGOperations/analogyExples.pcg").
To run these examples, load first the Ontology "samples/ontology/ManOntology2.xml".
analogy(_source, _targetBefore, _targetAfter) :-
cg(_source, _targetBefore), //
get the source CG and the target CG
_targetAfter is _targetBefore:copy(),
// copy the target CG in _targetAfter
_targetAfter:analogy(_source).
// call analogy method to apply an analogical transfer from source to target
First Example: An Example of an analogy between two CGs.
The cg fact records source and target CGs (before the analogy).
cg([Man:karim]<-agnt-[Cut]-
-obj->[Apple]-
-colorOf->[Color: yellow],
-attr->[Good];
-instr->[Knife],
-manr->[Strong],
[Woman]<-agnt-[Cut]-obj->[Orange]-colorOf->[Color: red]).
Application of the analogy operation:
?-
analogy(_source, _targetBefore, _targetAfter).
{_source = [Cut #0] -
-obj->[Apple #1] -
-colorOf->[Color :yellow],
-attr->[Good];
-instr->[Knife],
-manr->[Strong],
-agnt->[Man :karim],
_targetBefore = [Cut #0] -
-obj->[Orange]-colorOf->[Color :red],
-agnt->[Woman],
_targetAfter = [Cut #0] -
-obj->[Orange #1] -
-colorOf->[Color :red],
-attr->[Good]; //
parts added by analogical transfer
-agnt->[Woman],
-instr->[Knife], //
parts added by analogical transfer
-manr->[Strong] }
Second example: this example illustrates
the case where some parts of the source CG cannot be transfered because their
transfer will violate the canonicity of the CG.
cg([Man:karim]<-agnt-[Cut]-
-obj->[Apple]-
-colorOf->[Color: yellow],
-attr->[Good];
-instr->[Knife],
-manr->[Strong],
[Monkey]<-agnt-[Drink]-obj->[Milk]).
Application of the analogy operation:
?-
analogy(_source, _targetBefore, _targetAfter).
{_source = [Cut #0] -
-obj->[Apple #1] -
-colorOf->[Color :yellow],
-attr->[Good];
-instr->[Knife], // it is
not transfered since it violates target CG canonicity
-manr->[Strong],
-agnt->[Man :karim],
_targetBefore = [Drink #0] -
-obj->[Milk],
-agnt->[Monkey],
_targetAfter = [Drink #0] -
-obj->[Milk #1] -
-colorOf->[Color :yellow],
-attr->[Good];
-agnt->[Monkey],
-manr->[Strong]}
Third example: An Example of an analogy
between two CGs that illustrates the possibility of several overlap (matching);
at least : three possible matching: a matching with 1 relation (attr) matched, a
matching with 2 relations (colorOf and sizeOf) and a matching with 3 relations (agnt,
obj, colorOf). analogy will select the third matching because it has the maximal
overlap.
cg([Man:karim]-
-colorOf->[Color:white],
-sizeOf->[Size:
big],
<-agnt-[Cut]-
-obj->[Apple]-
-colorOf->[Color: yellow],
-attr->[Good];
-instr->[Knife],
-manr->[Strong],
[Nice]<-attr-[Woman]<-agnt-[Cut]-obj->[Orange]-
-sizeOf->[Size: small],
-colorOf->[Color: red]).
Application of the analogy operation:
?- analogy(_source, _targetBefore, _targetAfter).
{_source = [Cut #0] -
-obj->[Apple #1] -
-colorOf->[Color :yellow],
-attr->[Good];
-instr->[Knife],
-manr->[Strong],
-agnt->[Man :karim] -
-colorOf->[Color :white],
-sizeOf->[Size :big],
_targetBefore = [Orange #1] -
-sizeOf->[Size :small],
-colorOf->[Color :red],
<-obj-[Cut #0]-agnt->[Woman]-attr->[Nice],
_targetAfter = [Woman #0] -
-attr->[Nice],
-colorOf->[Color :white],
-sizeOf->[Size :big],
<-agnt-[Cut #1] -
-obj->[Orange #2] -
-sizeOf->[Size :small],
-colorOf->[Color :red],
-attr->[Good];
-instr->[Knife],
-manr->[Strong]}
Forth Example: an example of an analogy between two compound CGs (CGs with contexts). Note that the analogy of embedded contexts is sensitive to analogy of antecedent contexts.
We illustrate the following example with CGOperations GUI (for the execution of this example with Prolog+CG, see the file "analogyExples" presented above). targetCG before the analogy is specified in the left-top panel. In the right-top panel, the sourceCG is provided. The bottom panel shows the result of the analogy operation: the new description of the targetCG (after the analogy). source CG and target CG are stored in "samples/cg/Analogy/AtomicSystem.lnf" and "samples/cg/Analogy/AtomicSystem.lnf" respectively. So you can load them in the left-top panel and the right-top panel to run this example (after loading the ontology "samples/ontology/ManOntology2.xml").
Figure 1: Example of Analogy Operation
Implementation Details
Analogy is a CG matching based operation. match operation has been updated to take into account this new kind of matching. We describe in some detail the analogy operation, then we provide Java code for some parts of the operation.
If the two CGs contain two matched coreferents, then consider their corresponding concepts as entry points, else we have to find the best structural matching of the two CG: search the match that produces the maximal number of relation matching. Since analogy is not a projection-based operation, we should consider the general case and look for two relations (tuples) from the two CG that could match, i.e. search a relation from the first CG so that a relation with the same name exists in the second CG. Then the matching of the two CG is initiated. If the current matching is better than the best matching (before the current match), then set it as the best match and store its result (concepts matching and relations matching). Then consider other matching. Once the best matching is determined, its result (concepts and relations matching) will be considered for the next steps in the analogy process.
The next step is to update the target CG by an analogical transfer, from the source CG to the target CG, based on the result of the (best) matching and any transfer should respect the canonicity of the target CG: transfer to target CG any relation that is specific to source CG and that satisfy its canonicity in the new context (the target CG). Note that canons of copied concepts, from source to target CGs, are also checked.
If the concept to transfer is a context, the copy of the context should be sensitive to the analogy between concepts of the antecedent contexts. Thus, if a concept conc in the context is in coreference with a concept (or conc has the same individual as a concept) that was matched already with a concept c, then make a copy of c, not of conc. Also, if the canon of the copied relation is not satisfied in the new context (newCG) then remove the relation from this context.
Java code for the matching part of the analogy operation:
If the two CGs contain two matched coreferents, then consider their
corresponding concepts as entry points:
if (matchedCoref(matchOperation, G1, bindInf1,
G2, bindInf2, concCple))) {
succeeded = matchConcept(matchOperation, concCple.conc1, bindInf1,
concCple.conc2, bindInf2) &&
matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
concCple = null;
}
If no matched coreferents exist then we have to find the best structural matching of the two CG: search the match that produces the maximal number of relation matching. Since analogy is not a projection-based operation, we should consider the general case and look for two relations (tuples) from the two CG that could match, i.e. search a relation from the first CG so that a relation with the same name exists in the second CG. Then the matching of the two CG is initiated. If the current matching is better than the best matching (before the current match), then set it as the best match and store its result (concept matching and relation matching). Then consider other matching. Once the best matching is determined, its result (concepts and relations matching) will be considered for the next steps in the analogy process.
if (matchOperation == ANALOGY) {
concCple = null;
allRelsG1 = G1.getRelationsInHmp();
allRelsG2 = G2.getRelationsInHmp();
HashMap bestConceptsMatched = new HashMap();
HashMap bestRelationsMatched = new HashMap();
ArrayList bestCorefMatchL = new ArrayList();
ArrayList corefMatchL_Before = new ArrayList(corefMatchL);
for(Iterator e = allRelsG1.keySet().iterator(); e.hasNext();) {//
look for a relation from the first CG ..
relG1 = (Type) e.next();
// .. so that a relation with the same name
exists also in the second CG
rels2 = (ArrayList) allRelsG2.get(relG1);
if (rels2 != null) {
rels1 = (ArrayList) allRelsG1.get(relG1);
for (Iterator i = rels1.iterator(); i.hasNext();)
{
rel1 = (Relation) i.next();
for (Iterator j = rels2.iterator();
j.hasNext();) {
rel2 = (Relation) j.next();
// The matching will lead
to a solution
matchConcept(matchOperation,
rel1.getSourceConcept(), bindInf1, rel2.getSourceConcept(), bindInf2);
matchConcept(matchOperation,
rel1.getTargetConcept(), bindInf1, rel2.getTargetConcept(), bindInf2);
matchCG(matchOperation,
G1, bindInf1, G2, bindInf2, nbreRelsG1);
// update Best Match
if (relationsMatched.size()
> bestRelationsMatched.size()) {
bestConceptsMatched.clear();
bestConceptsMatched.putAll(conceptsMatched);
bestRelationsMatched.clear();
bestRelationsMatched.putAll(relationsMatched);
bestCorefMatchL.clear();
bestCorefMatchL.addAll(corefMatchL);
}
// Initialize the book-keeping structures used
for the matching
conceptsMatched.clear();
relationsMatched.clear();
toLocalMatchs.clear();
corefMatchL.clear();
corefMatchL.addAll(corefMatchL_Before);
}
// end for
} // end
for
} // end if
}// end for
Once the best matching is determined,
its result (concepts and relations matching) will be considered for the next
steps in the analogy process
conceptsMatched.putAll(bestConceptsMatched);
bestConceptsMatched.clear();
bestConceptsMatched = null;
relationsMatched.putAll(bestRelationsMatched);
bestRelationsMatched.clear();
bestRelationsMatched = null;
corefMatchL.addAll(bestCorefMatchL);
bestCorefMatchL.clear();
bestCorefMatchL = null;
corefMatchL_Before.clear();
corefMatchL_Before = null;
succeeded = !conceptsMatched.isEmpty();
}
Methods for the analogical transfer can be consulted from source code (in the class aminePlatform.util.cg.CGOperations).
Compare two CGs cg1 and cg2 : The
operation starts by computing the generalization between the two CG cg1 and cg2.
Then, the operation proceeds to determine the type of the relation between the
two CGs :
1- the two CG are equal if: the matched concepts are equal, the same number of
concepts and the same number of relations (and all the relations have been
matched).
2- else, newCG is more general than G2 if: the number of concepts of newCG is
equal to the number of matched concepts, and the number of relations of newCG is
equal to the number of matched relations, and the matched concepts are equals to
the corresponding concepts in newCG.
3- else, newCG is more specific than G2 if: the number of concepts of currentCG
is equal to the number of matched concepts, and the number of relations of
currentCG is equal to the number of matched relations, and the matched concepts
are equals to the corresponding concepts in currentCG.
4- else, newCG and currentCG have common information if the result of the
generalization is not null and it doesn't correspond to the specified
fatherOntNode or to its description.
5- else, newCG and currentCG are incomparable.
CompareCGResults compare(Concept entryPoint1, CG cg2, Concept entryPoint2);
Example
To run this example, load first the Ontology "samples/ontology/VehicleOntology.xml"). The CG in the left-top panel can be loaded from the file "samples/cg/OntologyProcesses/ElabByDefEx1.lnf".
(a) the two CG to compare: the operation returns the type of the comparison ..
(b) and the common CG in the bottom panel ..
(c) and matched parts of CG g1 and g2 and parts that are specific to g1 and to g2
Figure 2: Comparison operation
Implementation Details
The implementation of compare operation follows strictly its description (provided above):
public CompareCGResults compare(CG cg1, Concept entryPoint1, CG cg2, Concept
entryPoint2) throws Exception {
CompareCGResults compareCGResults = new CompareCGResults();
if (cg1 == null || cg2 == null || !cg1.isConceptInCG(entryPoint1) ||
!cg2.isConceptInCG(entryPoint2)) {
compareCGResults.setCompareResult(UNCOMPARABLE);
return compareCGResults;
}
ResMatchCG resMatchCG = this.generalize(cg1, entryPoint1, cg2,
entryPoint2); // generalization step
if (resMatchCG == null) {
compareCGResults.setCompareResult(UNCOMPARABLE);
return compareCGResults;
}
CG commonCG = resMatchCG.getCG();
// get common CG
compareCGResults.setCommonCG(commonCG);
if (this.relationsMatched == null || this.relationsMatched.isEmpty()) {
Concept conc1 = (Concept) this.conceptsMatched.keySet().iterator().next();
Concept conc2 = ((ConcCouple) this.conceptsMatched.get(conc1)).conc1;
compareCGResults.setMatchedPartOfG1(conc1.toCG());
compareCGResults.setMatchedPartOfG2(conc2.toCG());
compareCGResults.setSpecificPartOfG1(cg1);
compareCGResults.setSpecificPartOfG2(cg2);
}
else {
compareCGResults.setMatchedPartOfG1(CG.constructCG(this.relationsMatched.keySet().iterator()));
compareCGResults.setMatchedPartOfG2(CG.constructCG(this.relationsMatched.values().iterator()));
ArrayList list1 = specificPart(cg1,
this.relationsMatched.keySet());
ArrayList list2 = specificPart(cg2,
this.relationsMatched.values());
if (list1 != null) {
compareCGResults.setSpecificPartOfG1(CG.constructCG(list1.iterator()));
list1.clear();
}
if (list2 != null) {
compareCGResults.setSpecificPartOfG2(CG.constructCG(list2.iterator()));
list2.clear();
}
}
// Testing the different
cases to set the byte-result
if ( (cg1.getNbrConcepts()== cg2.getNbrConcepts()) && (eqMatchConc(1,2,conceptsMatched))
&&
(cg1.getNbrRelations() ==
commonCG.getNbrRelations()) && (cg1.getNbrRelations() == cg2.getNbrRelations()))
compareCGResults.setCompareResult(EQUAL);
// same number of concepts (and they are equal)
and the same number of
relations (and all have been matched).
else if ( (cg1.getNbrConcepts() == commonCG.getNbrConcepts()) &&
(cg1.getNbrRelations() == commonCG.getNbrRelations()) && (eqMatchConc(1,3,conceptsMatched)))
compareCGResults.setCompareResult(MORE_GENERAL);
// the number of concepts of cg1 is equal to
the number of matched
concepts, the number of relations of cg1 is equal to the number of matched relations, and the matched concepts
are equals to the corresponding concepts in cg1
else if ( (cg2.getNbrConcepts() == commonCG.getNbrConcepts()) &&
(cg2.getNbrRelations() == commonCG.getNbrRelations()) && (eqMatchConc(2,3,conceptsMatched)))
compareCGResults.setCompareResult(MORE_SPECIFIC);
// the number of concepts of cg2 is
equal to the number of matched
concepts, the number of relations of cg2 is equal to the number of matched relations, and the matched concepts
are equals to the corresponding concepts in cg2
else
compareCGResults.setCompareResult(HAVE_AN_INTERSECTION);
return compareCGResults;
}
coveredBy is a CG matching operation that determines which part of the current CG G1 (a subgraph S1) covers a part of obj G2 (a subgraph S2), i.e. S1 covers S2 if S1 match S2 and each relation in S1 match one relation in S2 and each concept in S1 is either equal or more specific than its corresponding concept in S2. coveredBy can be complete if all G1 covers a subgraph from G2: if G1 is equal or more specific than a subgraph of G2. coveredBy is partial if only a subgraph of G1 covers a subgraph of G2. Note that the result, if not null, is a new CG G that is a "view" of G2: concepts and relations of G are (exactly) concepts and relations of G2; they are NOT copies of these concepts/relations. This operation is used by the Ontology Information Retrieval Process.
Enumeration coveredBy(BindingContext bindContext, Object bindInf, Object
entryConcept1, Object bindInfEntry1,
Object obj, Object bindInfObj, Object entryConcept2, Object bindInfEntry2);
Similar to the above specification except that entry points are not specified.
Enumeration coveredBy(BindingContext bindContext, Object bindInf, Object obj, Object bindInfObj);
Example
To run the following examples, load first the Ontology "samples/ontology/VehicleOntology.xml".
We illustrate the following example with CGOperations GUI. Given two CGs G1 (provided in left-top panel) and G2 (provided in right-top panel), CoveredBy returns the result in the bottom panel.
Figure 3: CoveredBy operation
Implementation Details
coveredBy is a CG matching operation that determines which part of the current CG G1 (a subgraph S1) covers a part of obj G2 (a subgraph S2), i.e. S1 covers S2 if S1 is equal or more specific than S2 (i.e. an isomorphic matching between S1 and S2 modulo equal_or_moreSpecific operation on concepts). The result, if not null, is a new CG G that is a "view" of G2: concepts and relations of G are (exactly) concepts and relations of G2; they are NOT copies of these concepts/relations. Here is the corresponding Java code:
public Enumeration coveredBy(CG G1, Concept E1, CG G2, Concept E2) {
ResMatchCG resMatchCG = match(EQ_OR_MORE_SPCFQ, G1, E1, null, G2, E2,
null);
if (resMatchCG == null)
return null;
else {
CG cg3 = resMatchCG.getCG();
Enumeration rslt = cg3.getConcept(0).getOutcomeRelations();
cg3 = null;
return rslt;
}
}
References
[1] Falkenhainer B., K. D. Forbus and D. Gentner, The Structure-Mapping Engine: Algorithm and Examples, Artificial Intelligence 41, 1-63, 1989/90.
[2] Forbus K. D., D. Gentner and K. Law, MAC/FAC: A Model of Similarity-Based Retrieval, Cognitive Science 19, 141-205, 1994.