Introduction

CG, Concept, and Relation

Concept Matching

Relation Matching

CG Matching-Based Operations

Introduction

This document is concerned by implementation details on CG, Concept, and Relation structures, as well as details on CG, Concept, and Relation matching-based operations. Recall that matching-based operations are defined also on Amine structures, see Amine Structures Matching for further details.

CG, Concept, and Relation

This section presents structural details on CG, Concept, and Relation.

A Conceptual Graph (CG)

A CG is implemented as an object composed of an ArrayList of Concept(s). Relations are not specified explicitly in CG, they are accessed from concepts. The reason is that CG matching-based operations and the most relevant operations on CGs (in Amine) are concept-centered.

 public class CG implements AmineConstants, Serializable,
                                                Matching, AmineObject {

    private ArrayList concepts;
    private static boolean functionalCG = true;
    private static boolean headedCG = false;

    private static boolean canonicity = true;

    ...

 }

A concept

A concept is implemented as an object composed of a type, a designator with an optional coreferent, a descriptor, a state (used in the context of Synergy Language) and a point (used in the case of graphic display of the concept). A Concept can be related to other concepts by income and/or outcome relations. Only concept type is mandatory, the other components of a concept are optional.

concept type is either a variable or a reference to a Type CS contained in the current ontology. It is important to note that the concept type is not a string or an identifier, but a reference to a Type CS that is contained in the current ontology.

concept designator is either: a) a variable (with, by default, an existential quantifier), b) a reference to an Individual CS contained in the current ontology, c) a set of Individual(s), or d) a pseudo-designator. Again, it is important to note that an individual is not a string or an identifier, but a reference to an Individual CS that is contained in the current ontology.

Concept coreferent, if specified, is represented by a variable shared by concepts that belong to different contexts. For instance, the two concepts [Human: khalid *x]  and [Man ?x] can be two concepts in coreference, with x the variable that specifies this coreference. If coreference is specified, it is grouped with designator in an (internal) class DesignatorCoreferent which is considered as a (composed) designator.

Concept descriptor is either: a) a variable, b) a reference to a CS, c) any Amine Object (including CG), or d) even any Java Object.

Concept state represents the current state of the concept according to its concept lifecycle. This attribute is relevant only in the context of Synergy where active CGs (and concepts) are treated.

Concept point represents the top-left point of the rectangle that will enclose the concept (if it is drawn).

If a concept is used to compose Conceptual Graph (CG) structure, the concept can be related to other concepts by income and/or outcome relations. incomeRelations and outcomeRelations are ArrayList of object(s) Relation. Of course, these ArrayList(s) do not contain relations themselves but references to object(s) Relation. By specifying both income and outcome relations of a concept, we allow a redundancy in the representation. Below, we discuss the reason and the advantage of this redundancy. Note also that a concept can be used "alone", like any other Amine structure. In this case incomeRelations and outcomeRelations will be null.

 public class Concept implements AmineConstants, java.io.Serializable,
                                                AmineObject, Matching {

    private Object type = null;
    private Object designator = null;
    private Object descriptor = null;
    private byte state = STEADY;
    private Point leftTopPoint = null;
    private ArrayList incomeRelations = null;
    private ArrayList outcomeRelations = null;

    ...

 }

Discussion

Why relations are associated to concepts, and not directly to CG ? Why a relation is specified both as an outcome relation for its source concept and as an income relation for its target concept (why not specify only outcome relations for each concept, income relations can be determined by treatment: the relation that is an outcome for its source concept is also an income relation for its target concept) ? It is well known that a data structure (like graph) can be implemented in many ways, which implementation to select depends on the classical trade-off and compromise space/time. Another important parameter is the operations that will manipulate the structure. For instance, CG matching-based operations and other important operations in Amine (like activation/interpretation of active CGs in the context of Synergy) are "concept-centered and relation/propagation-centered" operations. They need a direct and rapid access to income relations and outcome relations of a concept. To allow such a direct and rapid access, we decided to formulate relations at the level of concepts, instead of CG, and to specify both income and outcome relations of each concept (instead of specifying only outcome relations). These decisions reflect our preference for efficient operations (optimization of time) rather than economy of storage.

Conceptual relation

A conceptual relation relates a concept to another concept. It is composed of a type, a source (concept), a target (concept), a collection of points and the position of its type identifier (if graphic display is considered). Relation type, source and target concepts are mandatory.

The type of a relation is a RelationType CS contained in the current ontology. Like concept type and individual designator, it is important to note that the relation type is not a string or an identifier, but a reference to a RelationType CS that is contained in the current ontology.

Like concept, conceptual relation is used, in general, to compose CG but it can be used "alone" as an Amine Object, like any other Amine structure.

  public class Relation implements java.io.Serializable,
                                AmineObject, Matching, AmineConstants {

    private RelationType type = null;
    private Concept sourceConcept = null;
    private Concept targetConcept = null;
    private ArrayList segmentPoints = null;
    private Point posRelNameOnSegments = null;

    ...
  }

As discussed in ontology, "internal" CG description is "free language" and strongly connected to an ontology: concept types, relation types, and individuals are not identifiers but references to CSs that correspond to nodes in the ontology. Each CS is connected to other CSs that represent the direct context for the CS.

CG Matching (recall)

We reproduce here our introduction on match() operation specified in Structures Matching, since it concerns also Concept, Relation and CG. match() operation is the most relevant operation in Amine algebraic level. Matching-based operations (equal(), generalize(), maximalJoin(), subsume(), unify()) are defined in term of match() operation which is a generic operation. match() attempts to compare two structures. The nature of the comparison depends on the nature of the match: equality matching, generalization matching, subsumption matching, or unification matching. Let us recall some points about match() operation that concern all Amine structures (including Concept, Relation, and CG):

1. some matching operations like generalize(), maximalJoin(), and subsumeWithResult() construct a new structure as a result of a successful matching. Other matching operations like equal() and subsume() does not construct a new structure, they check only if the match is true or not. Unification matching doesn't construct a new structure but it has a side effect on variable binding.

2. match() attempts to compare the current object with the specified object obj. Other parameters of match() include bindingContext and binding information which are necessary to interpret variables that can occur in the two structures to match.

3. The specification of match() is the same for all Amine structures:

/**
* Match the current object with the specified object obj, according to the value of
* the parameter matchOperation. Match considers the binding context and the binding
* information for the two objects.
* @param matchOperation A byte value that specifies which kind of matching to apply.
* Atually, these values are defined in AmineConstants interface and are: EQUAL,
* UNIFY, SUBSUME, SUBSUME_WITH_RSLT, MAXIMAL_JOIN, and GENERALIZE.
* @param bindContext The binding context
* @param bindInf The binding information for the current object
* @param obj The object to match with the current object
* @param bindInfObj The binding information for the parameter obj
* @return an object which is the result of the match operation
*/

public Object match(byte matchOperation, BindingContext bindContext,

                    Object bindInf, Object obj, Object bindInfObj);

The first part of match() operation is the same for all Amine structures: since obj can be a variable and since match() considers the case of variable binding and resolution, the first step is to consider this case (variable binding and resolution). Let us assume, for next sections, that valObj refers to obj if obj is not a variable or if binding should not be considered. Otherwise, valObj refers to the value of obj. Two special cases are considered in the first part of the match operation: the case where the current object and valObj refeer to the same object, and the case where valObj is either null or it is a variable but binding context and resolution is not considered or it is a free variable (and binding is considered):

If the current object and valObj refeer to the same object; equality of reference, then the two objects match and a copy of the object is returned (if the match should return a value).

ElseIf valObj is null or it is a variable, then the matching depends on the nature of the match:

if matchOperation is maximalJoin then return a copy of the current object. Recall that maximalJoin seeks specificity, that is why it returns a copy of the current object.

elseIf matchOperation is equal or subsume then return failure. Since the current object is not null, neither a variable, then it is not equal to valObj. Also, subsume checks that current object is more general than valObj, but this is not the case here.

elseIf matchOperation is unify and valObj is a Variable then unify valObj with the current object (associate the current object to valObj in the current binding context).

elseIf matchOperation is generalize then return a variable. Recall that generalize seeks the minimal generalization and since, in this case, the current object is specific and valObj is a variable (or is null), then generalization matching returns a variable.

Let us consider now the matching of Concept, then Relation, and last CG.

Concept Matching

The complete code is in : aminePlatform.util.cg.Concept

Match a concept c1 with a concept c2 consists in a match of their types, designators, coreferents, and descriptors. The following Java statement illustrates this definition:

boolean areMatched =
  matchTypeDesignator(matchOperation, bindContext, bindInf,         

                        conc2, bindInfValObj, (Concept) conc3) &&
  matchCoref(matchOperation, conc2, (Concept) conc3, cgOperations) &&
  matchDescriptor(matchOperation, bindContext, bindInf,
                    conc2.getDescriptor(), bindInfValObj,

                    (Concept) conc3, cgOperations);

Method matchTypeDesignator() calls match() operation on concept's types and concept's designators, and takes into account the case of coercion of individuals and the case of type relaxation (see CGOperations for detail). Method matchCoref() records the match of two coreferences (two variables). Such a record can be used later as a potential source for entry concepts for nested CGs (see CGOperations for detail). Method matchDescriptor() calls match() operation on concept's descriptors.

Relation Matching

The complete code is in : aminePlatform.util.cg.Relation

Match a relation r1 with a relation r2 consists in checking that their types are equals, and that their source and target concepts match respectively. The following Java code illustrates this definition ("this" corresponds to r1 and rel2 to r2):

if (this.getType() == rel2.getType()) {
  Concept srceRel3 = (Concept)
    this.getSourceConcept().match(matchOperation, bindContext,

                                  bindInf, rel2.getSourceConcept(),

                                  bindInfValObj);
  Concept trgtRel3 = null;
  if (srceRel3 != null)
    areMatched = false;
  else trgtRel3 = (Concept)
    this.getTargetConcept().match(matchOperation, bindContext, bindInf,
                                  rel2.getTargetConcept(), bindInfValObj);

  areMatched = areMatched && (trgtRel3 == null);
}
else areMatched = false;

CG Matching-Based Operations

The complete code is in : aminePlatform.util.cg.CGOperations

As explained in CGOperations, Amine adopts concept-centered CG matching scheme with an emphasis on fixing the appropriate context for the match. Bootstrap steps and functional CGs determine the appropriate context for a deterministic matching. We urge reader to consider CGOperations first. Code below is a reformulation (in Java and with the required detail) of the discussion and the specification formulated in CGOperations. We provide a detailed description of CG matching (with fragments from the source code) to give the reader a precise view on the implementation of this important operation.

Note first that match() and CG matching-based operations (like maximalJoin(), generalize(), etc.) are provided in two variants: as methods of CG (see CG API) and as static methods of CGOperations class. The match() and the other CG operations provided by CG API are defined in term of match() of CGOperations. The following code, extracted from the definition of match() in CG API, illustrates this point (in the code below, "this" represents the first CG and the two "null" parameters concern entry concepts that are not considered in this case):

...

CGOperations cgOper = new CGOperations(bindContext);
ResMatchCG resMatchCG = cgOper.match(matchOperation, this, null,
                                     bindInf, cg2, null, bindInfValObj);

...

Hence, our discussion here concerns match() of CGOperations API.

match():

public ResMatchCG match(byte matchOperation,
                        CG G1, Concept E1, Object bindInf1,
                        CG G2, Concept E2, Object bindInf2)

CGOperations API contains several variants of the method match(). The current one sets the appropriate context and then calls another variant of match() which performs the matching. Let us consider first the parameters: matchOperation specifies the type of the match, G1 represents the first CG, E1 is the entry concept for G1 (E1 is a concept from G1 and the parameter can be null if entry concepts are not considered), bindInf1 is the binding information concerning G1, G2 is the second CG, E2 is the entry concept for G2, and bindInf2 is the binding information concerning G2. match() returns ResMatchCG: a couple composed of a CG (the result of the match if this later has to construct a result, like maximalJoin and generalize) and a concept (the result of the match of the two entry concepts if they are not null). The BindingContext is specified as a parameter for the constructor of CGOperations. Of course, G1 and G2 can be simple CGs or compound CGs with coreferences.

Match() uses four structures to record relevant information:

1. conceptsMatched which is a HashMap of Key:ConcFromG1 and Value:ConcCouple =<ConcFromG2, ConcFromG3>. This structure records result of concepts matching,

2. relationsMatched which is a HashMap of Key:RelationG1 and Value:RelationG2. This structure records result of relations matching,

3. toLocalMatchs which is an ArrayList of ConcCouple : <ConcFromG1, ConcFromG2>. This structure records collection of couples of concepts (from G1 and G2 respectively) for whom local matching should be performed. Once the local match for a couple is performed, this later is removed from toLocalMatchs,

4. corefMatchL which is ArrayList of triplet: <CorefFromG1, CorefFromG2, CorefFromG3>. This structure records result of coreferences matching.

The three first structures (conceptsMatched, relationsMatched, and toLocalMatchs) are "local" structures; each (recursive) call to match() has its proper conceptsMatched, relationsMatched, and toLocalMatchs structures. Used when the match concerns compound CGs with coreferences, corefMatchL is a "global" structure: it is used by nested calls to match().

Set the context for the match, by the initialization of the involved structures (conceptsMatched, relationsMatched, and toLocalMatchs), then calls the variant match() to perform the match. Clear after that the structure corefMatchL and return the result of the match.
public ResMatchCG match(byte matchOperation, CG G1, Concept E1, Object bindInf1,
                                             CG G2, Concept E2, Object bindInf2) {
  this.conceptsMatched.clear();
  this.relationsMatched.clear();
  this.toLocalMatchs.clear();
  ResMatchCG resMatchCG = new ResMatchCG();
  corefMatchL = new ArrayList(5);
  boolean succeeded = match(matchOperation, G1, E1, bindInf1, G2, E2, bindInf2, resMatchCG);
  clearCorefMatchL();
  corefMatchL = null;
  if (!succeeded) {
    //resMatchCG.finalize();
    resMatchCG = null;
  }
  return resMatchCG;
}

match():

boolean match(byte matchOperation1,
              CG G1, Concept E1, Object bindInf1,
              CG G2, Concept E2, Object bindInf2,
              ResMatchCG resMatchCG)

This variant of match(), called from the first variant of match() specified previously, starts the matching of the two CGs by initiating the bootstrap step to determine (at least) two concepts (from G1 and G2) to match. In fact, once the two concepts <C1, C2> are determined, match() will initiate the first local matching on <C1, C2>. This local matching will trigger other local matchings and so on, until all possible local matchings are performed. Then, depending on the nature of the matching (like maximalJoin, generalize, and subsumeWithResult), the result (a CG) will be constructed and returned. Of course, some special cases and specific details are considered by the match operation. Among them, we note the following:

1. if the match operation is a projection-based operation (like equal, subsume and unify), then a first condition that can be checked immediatly is that all relation types used in the first CG (with the number of their occurrences) should be used also in the second CG. This condition is performed by the method bagInclusion() called by the code below. If the match operation is equal(), then another condition is that the two CGs should have the same number and types of relations (according to their occurrences). Of course, this condition is necessary but not suffisant to decide if the first CG can be projected on (or equal to) the second CG.

2. The match() considers first the case where one of the two CGs in input is composed of only one concept C. match() searchs in this case a concept in the other CG that can match with C.

Commented code of match() follows (especially for reader interested by details and by the Java implementation of the operation):
boolean match(byte matchOperation1,
              CG G1, Concept E1, Object bindInf1,
              CG G2, Concept E2, Object bindInf2,
              ResMatchCG resMatchCG) {
  boolean succeeded = false;
    // For the matching part, if matchOperation is SPECIALIZE or GENERALISE, consider the first as MAXIMAL_JOIN
   // and the second as GENERALIZE, the difference will concern only the construction of the result
  byte matchOperation = 0;
  if (matchOperation1 == SPECIALIZE)
    matchOperation = MAXIMAL_JOIN;
  else if (matchOperation1 == GENERALISE)
    matchOperation = GENERALIZE;
  else matchOperation = matchOperation1;

  HashMap allRelsG1 = null;
  HashMap allRelsG2 = null;
  AmineInteger nbrRelsG1 = null;
  AmineInteger nbrRelsG2 = null;
  int nbreRelsG1 = 0;
  int nbreRelsG2 = 0;

   // If the match operation is a projection-based operation, then check that relation types

   // (with their occurrences) that are used in G1 are also used in G2. Consider also the

   // case of equality matching.
if (AmineObjects.in(matchOperation, PRJCT_OPERS)) {
    nbrRelsG1 = new AmineInteger(0);
    nbrRelsG2 = new AmineInteger(0);
    allRelsG1 = G1.getRelationsInHmp(nbrRelsG1);
    allRelsG2 = G2.getRelationsInHmp(nbrRelsG2);
    nbreRelsG1 = nbrRelsG1.getInt();
    nbreRelsG2 = nbrRelsG2.getInt();
    nbrRelsG1 = null;
    nbrRelsG2 = null;

    if (!bagInclusion(nbreRelsG1, nbreRelsG2, allRelsG1, allRelsG2) ||
        (matchOperation == EQUAL && (nbreRelsG1 != nbreRelsG2 ||
        G1.getNbrConcepts() != G2.getNbrConcepts()))) {
      AmineObjects.clearHmpOfArrayList(allRelsG1);
      allRelsG1 = null;
      AmineObjects.clearHmpOfArrayList(allRelsG2);
      allRelsG2 = null;
      return false;
    }
}

 // BootStrap and start matching, first case : headed CGs or entry concepts are given
if (CG.isHeadedCG()) { // The case of HeadedCGs
  headedCG = true;
  succeeded = matchConcept(matchOperation, G1.getHead(), bindInf1, G2.getHead(), bindInf2);
}

if(E1 != null && E2 != null) { // Two entry points have been provided, matching them
  if(!G1.isConceptInCG(E1) || !G2.isConceptInCG(E2))
    succeeded = false;
  else {
    entryPoints = true;
    if (headedCG) // the two matching sources should be satisfied
      succeeded = succeeded &&
                  matchConcept(matchOperation, E1, bindInf1, E2, bindInf2);
    else succeeded = matchConcept(matchOperation, E1, bindInf1, E2, bindInf2);
  }
}

if (headedCG || entryPoints) { // initiate a deterministic matching
  succeeded = succeeded &&
              matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
  if (succeeded && AmineObjects.in(matchOperation, OPERS_WITH_RSLT)) {
    // The result of the match of the two entries E1 and E2 should be returned
    ConcCouple csCple = (ConcCouple) conceptsMatched.get(E1);
    resMatchCG.setConcept(csCple.conc2);
  }
}
else if(G1.isAConcept()) { // Special case: G1 contains one concept C1 without relation
    Concept C1 = G1.getConcept(0);
    Concept C2;

     // Search a concept C2 in G2 that could match C1
    for(Enumeration e = G2.getConcepts(); e.hasMoreElements() && !succeeded;) {
      C2 = (Concept) e.nextElement();
      succeeded = matchConc(matchOperation, C1, bindInf1, C2, bindInf2);
    }
}
else if (G2.isAConcept()) { // Special case: G2 contains one concept C2 without relation
    Concept C1;
    Concept C2 = G2.getConcept(0);

      // Search a concept C1 in G1 that could match C2
    for(Enumeration e = G1.getConcepts(); e.hasMoreElements() && !succeeded;) {
      C1 = (Concept) e.nextElement();
      succeeded = matchConc(matchOperation, C1, bindInf1, C2, bindInf2);
    }
}
else { // Consider other cases of bootstrap
    ConcCouple concCple = new ConcCouple();
    RelationType relG1 = null;
    Relation rel1 = null;
    Relation rel2 = null;
    ArrayList rels1 = null;
    ArrayList rels2 = null;

     // BootStrap and start matching, second case : identical designators (which concern   

     specific individual or a set of individuals) or partially matched coreferences. This

     bootstrap does not apply on generalization matching
    if(matchOperation != GENERALIZE &&
         (individualDesignator(G1, bindInf1, G2, bindInf2, concCple) ||
          matchedCoref(G1, bindInf1, G2, bindInf2, concCple) )) {

        // concCouple will contain conc1, a concept in G1, and conc2, a concept in G2, so that conc1 and conc2

         have the same individual(s) designator or the same (already) matched coreferences
      succeeded = // match conc1 and conc2 and start deterministic matching
          matchConcept(matchOperation, concCple.conc1, bindInf1, concCple.conc2, bindInf2) &&
          matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
      concCple = null;
    }

         // BootStrap and start matching for projection-based operation
    else if (AmineObjects.in(matchOperation, PRJCT_OPERS)) {
      concCple = null;

        // BootStrap and start matching, the third case: a relation with one occurrence in

          both G1 and G2. The matching will be deterministic.
      boolean found = false;
      for(Iterator e = allRelsG1.keySet().iterator(); e.hasNext() && !found;) {
        // look for a relation with one occurrence in G1 and in G2
        relG1 = (RelationType) e.next();
        rels1 = (ArrayList) allRelsG1.get(relG1);
        rels2 = (ArrayList) allRelsG2.get(relG1);
        if (rels1.size() == 1 && rels2.size() == 1) {
          found = true;
          rel1 = (Relation) rels1.get(0);
          rel2 = (Relation) rels2.get(0);
          succeeded = // match source and target concepts of the two relations and start a deterministic

                                       matching

                matchConcept(matchOperation, rel1.getSourceConcept(), bindInf1,
                                             rel2.getSourceConcept(), bindInf2) &&
                matchConcept(matchOperation, rel1.getTargetConcept(), bindInf1,
                                             rel2.getTargetConcept(), bindInf2) &&
                matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
        }
      } // end for
 

         // If the case above does not occur, then consider the general case for projection-

         based operation with non deterministic bootstrap : take one relation r1 from G1

         (the first in occurrence) and attempt to match it with a relation r2 of G2. G2 can   

         contain several relations with the same type as the one of r1. So there is a loop that

         searchs the relation from G2 with the same type as the type of r1 and will lead to a

         successful projection. The match in this case is not deterministic; several results

         are possible but the current match() will consider only the first successful result.
      if (!found) {
        relG1 = (RelationType) allRelsG1.keySet().iterator().next();
        rel1 = (Relation) ((ArrayList) allRelsG1.get(relG1)).get(0);

        rels2 = (ArrayList) allRelsG2.get(relG1);
        for (Iterator i = rels2.iterator(); i.hasNext() && !succeeded;) {
          rel2 = (Relation) i.next();
          succeeded =

                matchConcept(matchOperation, rel1.getSourceConcept(), bindInf1,
                                             rel2.getSourceConcept(), bindInf2) &&
                matchConcept(matchOperation, rel1.getTargetConcept(), bindInf1,
                                             rel2.getTargetConcept(), bindInf2) &&
                matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
        }
      }
    }

    else {
          // The matching operation is not a projection-based matching and no deterministic

            bootstrap is available: search two relations from G1 and G2 with the same relation

            type and so that their source and target concepts can match. The match in this

            case is not deterministic; several results are possible but the current match() will

            consider only the first successful result.
      concCple = null;
      allRelsG1 = G1.getRelationsInHmp();
      allRelsG2 = G2.getRelationsInHmp();
      for(Iterator e = allRelsG1.keySet().iterator(); e.hasNext() && !succeeded;) {
        // look for a relation from the first CG G1 ..
        relG1 = (RelationType) e.next();
        // .. so that a relation with the same name exists also in the second CG G2
        rels2 = (ArrayList) allRelsG2.get(relG1); // all relations in G2 that have the same 

                                                  // type as the selected relation from G1
        if (rels2 != null) {
          rels1 = (ArrayList) allRelsG1.get(relG1);
          for (Iterator i = rels1.iterator(); i.hasNext() && !succeeded;) {
            rel1 = (Relation) i.next();
            for (Iterator j = rels2.iterator(); j.hasNext() && !succeeded;) {
              rel2 = (Relation) j.next();
              succeeded =
                    matchConcept(matchOperation, rel1.getSourceConcept(), bindInf1,

                                                 rel2.getSourceConcept(), bindInf2) &&
                    matchConcept(matchOperation, rel1.getTargetConcept(), bindInf1,

                                                 rel2.getTargetConcept(), bindInf2) &&
                    matchCG(matchOperation, G1, bindInf1, G2, bindInf2, nbreRelsG1);
            } // end for
          } // end for
        } // end if
      } // end for
 

      if (!succeeded) {
             // If the above matching fail ; no relation in G1 can match with a relation from
                G2, then search two concepts concG1 and concG2 from the two CG so that

                concG1 match concG2 and join the two CG (a special join in fact). This is of

                course the "minimal" match that can be done! Note that the match is not

                deterministic; several results are possible (one concept of G1 can match with

                several concepts in G2) but the current match() will consider only the first

                successful result
        Concept concG1;
        Concept concG2;
        for(Enumeration e = G1.getConcepts(); e.hasMoreElements() && !succeeded;) {
          concG1 = (Concept) e.nextElement();
          for(Enumeration i = G2.getConcepts(); i.hasMoreElements() && !succeeded;) {
            concG2 = (Concept) i.nextElement();
            succeeded =

                matchConc(matchOperation, concG1, bindInf1, concG2, bindInf2) &&
                isPossibleToJoin(matchOperation, concG1, bindInf1, concG2, bindInf2);

                 // isPossibleToJoin() checks that the CG that will result from the join is

                    a functional CG
            if (!succeeded)
                clearAuxStrs();

          } // end for
        } // end for
      } // end if
    } // end else
} // end of matching as such
 

   // Step 3 : Construct the result G3 (if the operation requires such a result),
   // or change G1 if matchOperation1 is SPECIALIZE or GENERALISE
if (succeeded && AmineObjects.in(matchOperation1, OPERS_WITH_RSLT)) {
    CG cg3 = null;
    if (matchOperation1 != SPECIALIZE && matchOperation1 != GENERALISE)
      cg3 = new CG(10);

    succeeded = constructG3(matchOperation1, G1, bindInf1, G2, bindInf2, cg3);
    if (succeeded && cg3 != null) {
      cg3.trimToSize();
      resMatchCG.setCG(cg3);
    }
    else cg3 = null;
}

AmineObjects.clearHmpOfArrayList(allRelsG1);
allRelsG1 = null;
AmineObjects.clearHmpOfArrayList(allRelsG2);
allRelsG2 = null;
return succeeded;

}

matchCG():

boolean matchCG(byte matchOperation,

                CG G1, Object bindInf1,
                CG G2, Object bindInf2, int nbreRelsG1)

This method is called by the match() specified above. matchCG() is concerned by the propagation of local matching that was initiated by the bootstrap step in the method match(). Recall that local matching of a concept C1 (from G1) with a concept C2 (from G2) consists in a match of the two concepts, followed by matching their income relations, and then by matching their outcome relations. When the current local matching determines that a new local matching should be performed around two concepts C1a and C2a (from G1 and G2 respectively), then a new couple <C1a, C2a> is added to the ArrayList toLocalMatchs, which records the "to do local match(s)". matchCG() iterates on toLocalMatchs and once the local match of the current couple is done, this later is removed from toLocalMatchs.

Recall that match() and matchCG() do not construct immediately the result (a CG), but determine first the matching (the overlay) of the two CGs, according to the nature of the matching (provided by the parameter matchOperation). The construction is done after the match. Also and as explained in CGOperations, matchCG() performs a breadth-first matching; it considers the matching of nested CGs only after the matching of the current CG.

boolean matchCG(byte matchOperation,

                CG G1, Object bindInf1,
                CG G2, Object bindInf2, int nbreRelsG1) {
  // memorize the current size of corefMatchL in order to restore this state if the match fail
  int oldLastElemIdx = corefMatchL.size() - 1;
  boolean succeeded = true;
  ConcCouple csCple;

  // Iterate on toLocalMatchs to propagate local matching
  while (!toLocalMatchs.isEmpty() && succeeded) {
    csCple = (ConcCouple) toLocalMatchs.remove(toLocalMatchs.size() - 1);
    // Do local match : match income relations and outcome relations of the two current

    concepts. Note that the two concepts are already matched.
    succeeded =
        matchRelations(matchOperation, csCple.conc1.getIncomeRelations(), bindInf1,
                       csCple.conc2.getArrayIncomeRelations(), bindInf2) &&
        matchRelations(matchOperation, csCple.conc1.getOutcomeRelations(), bindInf1,
                       csCple.conc2.getArrayOutcomeRelations(), bindInf2) ;
    csCple = null;
  };

  // if match is a projection matching, then check that all relations of G1 have been

      matched
  if (succeeded && AmineObjects.in(matchOperation, PRJCT_OPERS))
    succeeded = (nbreRelsG1 == relationsMatched.size());
 

  // Now we consider contexts matching
  succeeded = succeeded && matchContexts(matchOperation, G1, bindInf1, G2, bindInf2);
 

   // if the match does not succeed, clear the content of the structures to prepare for a new

      match
  if (!succeeded)
    clearMatchCGStrs(oldLastElemIdx);

  return succeeded;
}
 

matchRelations(): match income/outcome relations relations1 of a concept c1 (from G1) with income/outcome relations relations2 of a concept c1 (from G1): for any relation r1 in relations1 that is not already matched, search in relations2 a relation r2 with the same relation type. If such a relation is found, match the two relations (match their sources and targets concepts respectively). Note that since we consider only functional CG we assume that if two relations have the same relation type, then they should match, except for generalization matching.

boolean matchRelations(byte matchOperation, Enumeration relations1, Object bindInf1,
                        Object[] relations2, Object bindInf2) {
  boolean succeeded = true;
  Relation rel1;
  Relation rel2;
  ConcCouple csCple;
  if (relations1 == null || relations2 == null)
    return true;

  int relations2Size = relations2.length;
  RelationCouple relCple = null;
  boolean rel2Found = false;
  while (relations1.hasMoreElements() && succeeded) {
    rel1 = (Relation) relations1.nextElement();
    // check that rel1 has not been matched
    rel2 = (Relation) relationsMatched.get(rel1);
    if (rel2 == null) {
      rel2Found = false;
      // search for a relation in rel2 of G2 that could match with rel1
      for (int i = 0; i < relations2Size && !rel2Found && succeeded; i++) {
        rel2 = (Relation) relations2[i];
        // The two relations should have the same relation type
        if (rel1.getType() == rel2.getType()) {
          rel2Found = true; // we adopt functional interpretation
          succeeded =
                matchConcept(matchOperation, rel1.getSourceConcept(), bindInf1,
                             rel2.getSourceConcept(), bindInf2) &&
                matchConcept(matchOperation, rel1.getTargetConcept(), bindInf1,
                             rel2.getTargetConcept(), bindInf2);
          if (succeeded)
            relationsMatched.put(rel1, rel2);
          else if (matchOperation == GENERALIZE)
            succeeded = true;
        } // end if
      } // end for
    } // end if
  }

  return succeeded;
}

matchContexts(): search all nested CGs in the two CGs (G1 and G2) and match them.

boolean matchContexts(byte matchOperation, CG G1, Object bindInf1, CG G2, Object bindInf2) {
  boolean succeeded = true;
  ConcCouple ccCple;
  Concept cc1;
  for (Iterator i = conceptsMatched.keySet().iterator(); i.hasNext() && succeeded; ) {
    cc1 = (Concept) i.next();
    ccCple = (ConcCouple) conceptsMatched.get(cc1);
    CG cg1 = cc1.isContext(this.bindContext, bindInf1);
    CG cg2 = ccCple.conc1.isContext(this.bindContext, bindInf2);
    if (cg1 != null && cg2 != null) {
      CGOperations cgOperCtxt = new CGOperations(this.bindContext);
      cgOperCtxt.corefMatchL = this.corefMatchL; // share the list of coreferences matching
      ResMatchCG resMatchCG = new ResMatchCG();
      succeeded =
          cgOperCtxt.match(matchOperation, cg1, null, bindInf1,
                                           cg2, null, bindInf2, resMatchCG);

      if (succeeded && AmineObjects.in(matchOperation, OPERS_WITH_RSLT))
        ccCple.conc2.setDescriptor(resMatchCG.getCG());

      cgOperCtxt = null; // for gc
      resMatchCG = null;
    }
  }

  return succeeded;
}
 

matchConcept(): If the two concepts to match (conc1 and conc2) have been already matched, then nothing is done, else match the two concepts, add the result to conceptsMatched, and add a new entry to toLocalMatchs in order to perform a local matching around the two concepts. The matching of two concepts is a method of Concept (it corresponds to the matching of their types, designators, coreferences, and descriptors).

boolean matchConcept(byte matchOperation, Concept conc1, Object bindInf1,
                     Concept conc2, Object bindInf2) {
  boolean succeeded = true;
  if (conceptsMatched.get(conc1) == null) {
    succeeded =
        matchConc(matchOperation, conc1, bindInf1, conc2, bindInf2) &&
        toLocalMatchs.add(new ConcCouple(conc1, conc2));
  }
  return succeeded;
}

boolean matchConc(byte matchOperation, Concept conc1, Object bindInf1,
                  Concept conc2, Object bindInf2) {
  Concept conc3 = (Concept) conc1.match(matchOperation, this.bindContext, bindInf1,
                                        conc2, bindInf2, this);
  boolean areMatched = true;
  if (AmineObjects.in(matchOperation, OPERS_WITH_RSLT)) {
    if (conc3 != null)
      conceptsMatched.put(conc1, new ConcCouple(conc2, conc3));
    else areMatched = false;
  }
  else if (conc3 != null)
    areMatched = false;
  // else areMatched = true; by default

  return areMatched;
}
 

ConstructG3(): The construction of the result (for maximalJoin, generalize, subsumeWithResult, specialize, and generalise) is explained in the source code. We describe here the main treatment:

boolean constructG3(byte matchOperation,

                    CG G1, Object bindInf1,
                    CG G2, Object bindInf2,

                    CG G3) {
  if (matchOperation == MAXIMAL_JOIN)
    return maxJoinRslt(G1, bindInf1, G2, bindInf2, G3);
  else if (matchOperation == SPECIALIZE)
    return specialize(G1, bindInf1, G2, bindInf2);
  else if (matchOperation == SUBSUME_WITH_RSLT || matchOperation == GENERALIZE)
    return commonRslt(G1, bindInf1, G3);
  else if (matchOperation == GENERALISE)
    return generalise(G1, bindInf1, G2, bindInf2);
  else return false;
}

1. Construct the result of maximalJoin: the construction is done in two steps : a) create G3 as a copy of G1 but replace each concept of G1 by the result of concept matching or by a copy of the concept (if the concept has not been matched), b) scan G2 for relations that are specific to G2, add them to G3 with replacing each concept by the result of concept matching or by a copy of the concept (if the concept has not been matched).

2. Construct the result of generalize and subsumeWithResult: the resulted CG G3 is the common graph of the two input CGs, 'modulo' the result of the match operation (generalize or subsumeWithResult). The construction is done in two steps: a) put in G3 all concepts that resulted from the match, b) scan G1 to create a copy of each relation matched, but replace each concept in the relation with the concept that resulted from concept matching.

3. Construct the result of specialize: the result of specialize is not a new CG but the modification of G1 (the first CG) itself. This specialization is done in two steps : a) change in G1 the matched concepts by the result of the match, b) Add to G1 what is specific to G2 (relations that are in G2 but not in G1).

4. Construct the result of generalise: the result of generalise is not a new CG but the modification of G1 (the first CG) itself. This generalization is done in two steps: a) change in G1 the matched concepts by the result of the match and remove concepts that are specific to G1, b) remove specific relations from G1 (remove from G1 relations that were not matched).