ptolemy.actor.gt
Class GraphMatcher

java.lang.Object
  ptolemy.actor.gt.GraphAnalyzer
      ptolemy.actor.gt.GraphMatcher

public class GraphMatcher
extends GraphAnalyzer

Implementation of a recursive algorithm to match a pattern to any subgraph of a a graph. The pattern is specified as the pattern part of a graph transformation rule. The graph to be matched to, called host graph, is an arbitrary Ptolemy II model, whose top level is an instance of CompositeEntity.

Since:

Ptolemy II 7.1

Version:

$Id: GraphMatcher.java 57046 2010-01-27 23:35:53Z cxh $

Author:

Thomas Huining Feng

Accepted Rating:

Red (tfeng)

Proposed Rating:

Yellow (tfeng)

Nested Class Summary

private static class	GraphMatcher.LookbackEntry An entry for a lookback item.
private static class	GraphMatcher.LookbackList A list of lookback entries.
private static class	GraphMatcher.NameComparator A comparator to sort objects in a container by their types and names.
private static class	GraphMatcher.ObjectList A list of Java objects.
private class	GraphMatcher.ParameterIterator A class of objects used to iterate over all possible values of the value iterators (object in class ValueIterator) in a given composite entity.

Nested classes/interfaces inherited from class ptolemy.actor.gt.GraphAnalyzer

GraphAnalyzer.IndexedList, GraphAnalyzer.IndexedLists, GraphAnalyzer.Path

Field Summary

private java.util.Map<java.lang.Object,java.lang.Boolean>	_cachedCreatedObjects A map from objects to Booleans value that identify whether they are tagged to be created.
private java.util.Map<java.lang.Object,java.lang.Boolean>	_cachedIgnoredObjects A map from objects to Boolean values that identify whether they are tagged to be ignored.
private java.util.Map<java.lang.Object,java.lang.Boolean>	_cachedNegatedObjects A map from objects to Boolean values that identify whether they are tagged to be negated.
private java.util.Map<NamedObj,java.lang.Object>	_cachedOptionalContainers A map from objects to their optional containers.
private MatchCallback	_callback The callback to invoke in pattern matching.
private java.util.List<MatchCallback>	_callbacksInPattern The objects in the pattern that implement the MatchCallback interface, which are to be invoked when a match is found.
private static GraphMatcher.NameComparator	_comparator A comparator to sort objects in a container by their types and names.
private java.util.Map<java.lang.Object,java.lang.Boolean>	_ignoredOptionalObjects A map from objects to Boolean values that identify whether those objects have been ignored in the pattern matching.
private GraphMatcher.LookbackList	_lookbackList A list of lookback entries.
private MatchResult	_matchResult The map that matches objects in the pattern to the objects in the host.
private boolean	_negation Whether the pattern matching has processed to the negation phase, where all negated objects are to be matched but if any of them is found, the match is in fact unsuccessful.
private SequentialTwoWayHashMap<ValueIterator,Token>	_parameterValues A map from parameters that are ValueIterators to their original values (which are changed by in pattern matching to different values).
private boolean	_success The variable that indicates whether the last match operation is successful.
private MatchResult	_temporaryMatch The part of match result that is temporary.
static MatchCallback	DEFAULT_CALLBACK The default callback that always returns true.

Constructor Summary

GraphMatcher()

Method Summary

private boolean	_checkBackward() Check the items in the lookback list for more matching requirements.
private boolean	_checkConstraint(Pattern pattern, Constraint constraint) Check whether the constraint is satisfied by the matching.
private boolean	_checkConstraints() Check all the constraints are satisfied.
private static boolean	_checkCriteria(NamedObj patternObject, NamedObj hostObject) Check all the criteria are satisfied by matching the pattern object to the host object.
private void	_clearCaches() Clear all the cached objects.
private void	_findAllMatchCallbacksInPattern(NamedObj container) Find all instances of NamedObj that implement the MatchCallback interface, and record them in the _callbacksInPattern list to be invoked when a match is found.
private Token	_getAttribute(NamedObj container, java.lang.Class<? extends Parameter> attributeClass, boolean searchContainer, boolean patternOnly, boolean hostOnly) Search for the value of an attribute in the pattern hierarchy or the host model hierarchy.
private static java.lang.String	_getNameString(java.lang.Object object) Get a string that represents the object.
private NamedObj	_getOptionalContainer(NamedObj object) Get the container of the object that is tagged to be optional.
private boolean	_isCreated(java.lang.Object object) Return whether the object in the pattern is tagged to be created.
protected boolean	_isIgnored(java.lang.Object object) Return whether the object in the pattern should be ignored in the pattern matching.
private boolean	_isNegated(java.lang.Object object) Return whether the object in the pattern is tagged to be negated.
protected boolean	_isOpaque(CompositeEntity entity) Test whether the composite entity is opaque or not.
private boolean	_matchAtomicEntity(ComponentEntity patternEntity, ComponentEntity hostEntity) Match an atomic entity in the pattern to an atomic entity in the host model.
private boolean	_matchAttribute(AttributeMatcher patternAttribute, Attribute hostAttribute) Match an attribute in the pattern to an attribute in the host model.
private boolean	_matchCompositeEntity(CompositeEntity patternEntity, CompositeEntity hostEntity) Match a composite entity in the pattern to a composite entity in the host model.
private boolean	_matchCompositeEntityAtAllLevels(CompositeEntity patternEntity, CompositeEntity hostEntity) Try to match a composite entity in the pattern to any composite entity in the host model.
private boolean	_matchList(GraphMatcher.LookbackEntry matchedObjectLists) Match the list of pattern objects in the lookback entry to the list of host objects in it.
private boolean	_matchObject(java.lang.Object patternObject, java.lang.Object hostObject) Match an object of any kind in the pattern to an object in the host model.
private boolean	_matchPath(GraphAnalyzer.Path patternPath, GraphAnalyzer.Path hostPath) Match a connection path (multiple links between a pair of ports with one or more relations in between) in the pattern to a connection path in the host model.
private boolean	_matchPort(Port patternPort, Port hostPort) Match a port in the pattern to a port in the host model.
private boolean	_matchRelation(Relation patternRelation, Relation hostRelation) Match a relation in the pattern to a relation in the host model.
private static void	_printMatch(MatchResult match) Print the match result in a readable format to standard output.
protected boolean	_relationCollapsing(NamedObj container) Return whether the interconnected relations should be collapsed into one in pattern matching.
private boolean	_shallowMatchDirector(Director patternDirector, Director hostDirector) Shallow-match a director in the pattern to a director in the host model but not anything that the director depends on.
private static boolean	_shallowMatchPath(GraphAnalyzer.Path patternPath, GraphAnalyzer.Path hostPath) Shallow-match a path in the pattern to a path in the host model but not anything that the path depends on.
private static boolean	_shallowMatchPort(Port patternPort, Port hostPort) Shallow-match a port in the pattern to a port in the host model but not anything that the port depends on.
private boolean	_shallowMatchRelation(Relation patternRelation, Relation hostRelation) Shallow-match a relation in the pattern to a relation in the host model but not anything that the relation depends on.
MatchResult	getMatchResult() Return the most recent match result, which the user should not modify.
boolean	isSuccessful() Return whether the last matching was successful.
static void	main(java.lang.String[] args) Match a rule file to a model file.
boolean	match(Pattern pattern, CompositeEntity hostGraph) Match a pattern specified in the patternGraph to a model in hostGraph.
static GraphMatcher	match(java.lang.String ruleXMLFile, java.lang.String hostXMLFile) Match the rule stored in the file with name ruleXMLFile to the model stored in the file with name hostXMLFile, whose top-level should be an instance of CompositeEntity.
static GraphMatcher	match(java.lang.String ruleXMLFile, java.lang.String hostXMLFile, MatchCallback callback) Match the rule stored in the file with name ruleXMLFile to the model stored in the file with name hostXMLFile, whose top-level should be an instance of CompositeEntity, and invoke callback's MatchCallback.foundMatch(GraphMatcher) method whenever a match is found.
void	setMatchCallback(MatchCallback callback) Set the callback to be invoked by future calls to match(Pattern, CompositeEntity).

Methods inherited from class ptolemy.actor.gt.GraphAnalyzer

findFirstChild, findFirstPath, findNextChild, findNextPath

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEFAULT_CALLBACK

public static final MatchCallback DEFAULT_CALLBACK

The default callback that always returns true. A callback is invoked whenever a match is found. Because this callback always returns true, it terminates the matching process after the first match is found, and the match result can be obtained later using getMatchResult().

_cachedCreatedObjects

private java.util.Map<java.lang.Object,java.lang.Boolean> _cachedCreatedObjects

A map from objects to Booleans value that identify whether they are tagged to be created.

_cachedIgnoredObjects

private java.util.Map<java.lang.Object,java.lang.Boolean> _cachedIgnoredObjects

A map from objects to Boolean values that identify whether they are tagged to be ignored.

_cachedNegatedObjects

private java.util.Map<java.lang.Object,java.lang.Boolean> _cachedNegatedObjects

A map from objects to Boolean values that identify whether they are tagged to be negated.

_cachedOptionalContainers

private java.util.Map<NamedObj,java.lang.Object> _cachedOptionalContainers

A map from objects to their optional containers. If it has been determined that they have no optional container, then the value would be Boolean.FALSE rather than a NamedObj.

_callback

private MatchCallback _callback

The callback to invoke in pattern matching.

_callbacksInPattern

private java.util.List<MatchCallback> _callbacksInPattern

The objects in the pattern that implement the MatchCallback interface, which are to be invoked when a match is found. All these objects are invoked when a match is found, and if they all return true, the callback set by the user (using setMatchCallback(MatchCallback)) is invoked. If not all of them return true, a false is returned by the matcher without invoking the callback set by the user.

_comparator

private static final GraphMatcher.NameComparator _comparator

A comparator to sort objects in a container by their types and names.

_ignoredOptionalObjects

private java.util.Map<java.lang.Object,java.lang.Boolean> _ignoredOptionalObjects

A map from objects to Boolean values that identify whether those objects have been ignored in the pattern matching.

_lookbackList

private GraphMatcher.LookbackList _lookbackList

A list of lookback entries.

_matchResult

private MatchResult _matchResult

The map that matches objects in the pattern to the objects in the host. These objects include actors, ports, relations, etc.

_negation

private boolean _negation

Whether the pattern matching has processed to the negation phase, where all negated objects are to be matched but if any of them is found, the match is in fact unsuccessful.

_parameterValues

private SequentialTwoWayHashMap<ValueIterator,Token> _parameterValues

A map from parameters that are ValueIterators to their original values (which are changed by in pattern matching to different values).

_success

private boolean _success

The variable that indicates whether the last match operation is successful.

_temporaryMatch

private MatchResult _temporaryMatch

The part of match result that is temporary. I.e., the matches included here are not final.

Constructor Detail

GraphMatcher

public GraphMatcher()

Method Detail

getMatchResult

public MatchResult getMatchResult()

Return the most recent match result, which the user should not modify. During the matching process, when a callback routine (an instance implementing MatchCallback) is invoked (see setMatchCallback(MatchCallback)), that callback routine can call this method to retrieve the match result that has just been found.

Note that the returned match result object may be changed by future matching. To maintain a copy, MatchResult.clone() may be called that returns a clone of it.

Returns:

The most recent match result.

isSuccessful

public boolean isSuccessful()

Return whether the last matching was successful.

Returns:

Whether the last matching was successful.

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception

Match a rule file to a model file. This main method takes a parameter array of length 2 or 3. If the array's length is 2, the first string is the rule file name, and the second is the model file name. In this case, an arbitrary match (the first one found) is printed to the console. If the array has 3 elements, the first string should be "-A" (meaning "all matches"), the second string is the rule file name, and the third is the model file name. In that case, all the matches are printed to to console one by one.

Parameters:

args - The parameter array.

Throws:

java.lang.Exception - If the rule file or the model file cannot be read.

match

public boolean match(Pattern pattern,
                     CompositeEntity hostGraph)

Match a pattern specified in the patternGraph to a model in hostGraph. If the match is successful, true is returned, and the match result is stored internally, which can be retrieved with getMatchResult(). A matching was successful if at least one match result was found, and the callback (an instance implementing MatchCallback) returned true when it was invoked.

Parameters:

pattern - The pattern.

hostGraph - The host graph.

Returns:

true if the match is successful; false otherwise.

match

public static GraphMatcher match(java.lang.String ruleXMLFile,
                                 java.lang.String hostXMLFile)
                          throws java.lang.Exception

Match the rule stored in the file with name ruleXMLFile to the model stored in the file with name hostXMLFile, whose top-level should be an instance of CompositeEntity. The first match result (which is arbitrarily decided by the recursive algorithm) is recorded in the returned matcher object. This result can be obtained with getMatchResult(). If the match is unsuccessful, the match result is empty, and isSuccessful() of the returned matcher object returns false.

Parameters:

ruleXMLFile - The name of the file in which the rule is stored.

hostXMLFile - The name of the file in which the model to be matched is stored.

Returns:

A matcher object with the first match result stored in it. If no match is found, isSuccessful() of the matcher object returns false, and getMatchResult() returns an empty match.

Throws:

java.lang.Exception - If the rule file or the model file cannot be read.

See Also:

match(String, String, MatchCallback)

match

public static GraphMatcher match(java.lang.String ruleXMLFile,
                                 java.lang.String hostXMLFile,
                                 MatchCallback callback)
                          throws java.lang.Exception

Match the rule stored in the file with name ruleXMLFile to the model stored in the file with name hostXMLFile, whose top-level should be an instance of CompositeEntity, and invoke callback's MatchCallback.foundMatch(GraphMatcher) method whenever a match is found. If the callback returns true, the match will terminate and no more matches will be reported; otherwise, the match process continues, and the callback may be invoked again. If callback is null, the behavior is the same as match(String, String).

Parameters:

ruleXMLFile - The name of the file in which the rule is stored.

hostXMLFile - The name of the file in which the model to be matched is stored.

callback - The callback to be invoked when matches are found.

Returns:

A matcher object with the last match result stored in it. If no match is found, or though matches are found, the callback returns false for all the matches, then isSuccessful() of the matcher object returns false, and getMatchResult() returns an empty match.

Throws:

java.lang.Exception - If the rule file or the model file cannot be read.

See Also:

match(String, String)

setMatchCallback

public void setMatchCallback(MatchCallback callback)

Set the callback to be invoked by future calls to match(Pattern, CompositeEntity).

Parameters:

callback - The callback. If it is null, the callback is set to DEFAULT_CALLBACK.

See Also:

match(Pattern, CompositeEntity)

_isIgnored

protected boolean _isIgnored(java.lang.Object object)

Return whether the object in the pattern should be ignored in the pattern matching. An object is ignored if it is tagged to be ignored, or it is tagged to be optional but a match including that object has failed.

Overrides:

_isIgnored in class GraphAnalyzer

Parameters:

object - The object to be tested.

Returns:

true if the object is ignored.

_isOpaque

protected boolean _isOpaque(CompositeEntity entity)

Test whether the composite entity is opaque or not. Return true if the composite entity is an instance of CompositeActor and it is opaque. A composite actor is opaque if it has a director inside, which means the new level of hierarchy that it creates cannot be flattened, or it has a HierarchyFlatteningAttribute attribute inside with value true.

Specified by:

_isOpaque in class GraphAnalyzer

Parameters:

entity - The composite entity to be tested.

Returns:

true if the composite entity is an instance of CompositeActor and it is opaque.

_relationCollapsing

protected boolean _relationCollapsing(NamedObj container)

Return whether the interconnected relations should be collapsed into one in pattern matching.

Specified by:

_relationCollapsing in class GraphAnalyzer

Parameters:

container - The container of the relations.

Returns:

true if the relation should be collapsed.

_checkBackward

private boolean _checkBackward()

Check the items in the lookback list for more matching requirements. If no more requirements are found (i.e., all the lists in the lookback list have been fully explored), then a match is found, and the callback's MatchCallback.foundMatch(GraphMatcher) is invoked. If that method returns true, the matching process terminates; otherwise, the matching proceeds by backtracking.

Returns:

Whether the match is successful.

_checkConstraint

private boolean _checkConstraint(Pattern pattern,
                                 Constraint constraint)

Check whether the constraint is satisfied by the matching.

Parameters:

pattern - The object in the pattern that has been matched with the matched result stored in the _matchResult field.

constraint - The constraint to be checked.

Returns:

true if the constraint is satisfied.

_checkConstraints

private boolean _checkConstraints()

Check all the constraints are satisfied.

Returns:

true if all the constraints are satisfied.

_checkCriteria

private static boolean _checkCriteria(NamedObj patternObject,
                                      NamedObj hostObject)

Check all the criteria are satisfied by matching the pattern object to the host object.

Parameters:

patternObject - The object in the pattern to which criteria are associated.

hostObject - The object in the host model to be tested.

Returns:

true if all criteria, if any, are satisfied.

_clearCaches

private void _clearCaches()

Clear all the cached objects.

_findAllMatchCallbacksInPattern

private void _findAllMatchCallbacksInPattern(NamedObj container)

Find all instances of NamedObj that implement the MatchCallback interface, and record them in the _callbacksInPattern list to be invoked when a match is found.

Parameters:

container - The container of the NamedObjs to be found.

_getAttribute

private Token _getAttribute(NamedObj container,
                            java.lang.Class<? extends Parameter> attributeClass,
                            boolean searchContainer,
                            boolean patternOnly,
                            boolean hostOnly)

Search for the value of an attribute in the pattern hierarchy or the host model hierarchy.

Parameters:

container - The contained in the host model or the pattern.

attributeClass - The class of the attribute to be searched for.

searchContainer - Whether containers of the contain need to be searched.

patternOnly - Whether the attribute should only be in the pattern.

hostOnly - Whether the attribute should only be in the host model.

Returns:

The value of the attribute, if found, or null otherwise.

_getNameString

private static java.lang.String _getNameString(java.lang.Object object)

Get a string that represents the object. If the object is an instance of NamedObj, the returned string is its name retrieved by NamedObj.getFullName(); otherwise, the toString() method of the object is called to get the string.

Parameters:

object - The object.

Returns:

The string that represents the object.

_getOptionalContainer

private NamedObj _getOptionalContainer(NamedObj object)

Get the container of the object that is tagged to be optional. If none, return null.

Parameters:

object - The object whose optional container is to be found.

Returns:

The optional container, or null.

_isCreated

private boolean _isCreated(java.lang.Object object)

Return whether the object in the pattern is tagged to be created.

Parameters:

object - The object in the pattern.

Returns:

true if the object is to be created (so it is not actually part of the pattern but the replacement).

_isNegated

private boolean _isNegated(java.lang.Object object)

Return whether the object in the pattern is tagged to be negated. Negated objects should not appear in the subgraph for the match to be successful.

Parameters:

object - The object in the pattern.

Returns:

true if the object is to be negated.

_matchAtomicEntity

private boolean _matchAtomicEntity(ComponentEntity patternEntity,
                                   ComponentEntity hostEntity)

Match an atomic entity in the pattern to an atomic entity in the host model.

Parameters:

patternEntity - The atomic entity in the pattern.

hostEntity - The atomic entity in the host model.

Returns:

true if the match is successful by matching the pattern entity to the host entity. If false, no match can be found if the given pattern entity is matched to the host entity.

_matchAttribute

private boolean _matchAttribute(AttributeMatcher patternAttribute,
                                Attribute hostAttribute)

Match an attribute in the pattern to an attribute in the host model.

Parameters:

patternAttribute - The attribute in the pattern.

hostAttribute - The attribute in the host model.

Returns:

true if the match is successful by matching the pattern attribute to the host attribute. If false, no match can be found if the given pattern attribute is matched to the host attribute.

_matchCompositeEntity

private boolean _matchCompositeEntity(CompositeEntity patternEntity,
                                      CompositeEntity hostEntity)

Match a composite entity in the pattern to a composite entity in the host model.

Parameters:

patternEntity - The composite entity in the pattern.

hostEntity - The composite entity in the host model.

Returns:

true if the match is successful by matching the pattern entity to the host entity. If false, no match can be found if the given pattern entity is matched to the host entity.

_matchCompositeEntityAtAllLevels

private boolean _matchCompositeEntityAtAllLevels(CompositeEntity patternEntity,
                                                 CompositeEntity hostEntity)

Try to match a composite entity in the pattern to any composite entity in the host model. This method should only be used at the beginning of pattern matching, where the whole pattern should be matched to any composite entity in the host model.

Parameters:

patternEntity - The composite entity in the pattern.

hostEntity - The composite entity in the host model.

Returns:

true if the match is successful by matching the pattern attribute to the host attribute. If false, no match can be found if the given pattern attribute is matched to the host attribute.

See Also:

_matchCompositeEntity(CompositeEntity, CompositeEntity)

_matchList

private boolean _matchList(GraphMatcher.LookbackEntry matchedObjectLists)

Match the list of pattern objects in the lookback entry to the list of host objects in it.

Parameters:

matchedObjectLists - The lookback entry containing a list of pattern objects and a list of host objects.

Returns:

true if the match is successful.

_matchObject

private boolean _matchObject(java.lang.Object patternObject,
                             java.lang.Object hostObject)

Match an object of any kind in the pattern to an object in the host model.

Parameters:

patternObject - The object in the pattern.

hostObject - The object in the host model.

Returns:

true if the match is successful by matching the pattern object to the host object. If false, no match can be found if the given pattern object is matched to the host object.

_matchPath

private boolean _matchPath(GraphAnalyzer.Path patternPath,
                           GraphAnalyzer.Path hostPath)

Match a connection path (multiple links between a pair of ports with one or more relations in between) in the pattern to a connection path in the host model.

Parameters:

patternPath - The path in the pattern.

hostPath - The path in the host model.

Returns:

true if the match is successful by matching the pattern path to the host path. If false, no match can be found if the given pattern path is matched to the host path.

_matchPort

private boolean _matchPort(Port patternPort,
                           Port hostPort)

Match a port in the pattern to a port in the host model.

Parameters:

patternPort - The port in the pattern.

hostPort - The port in the host model.

Returns:

true if the match is successful by matching the pattern port to the host port. If false, no match can be found if the given pattern port is matched to the host port.

_matchRelation

private boolean _matchRelation(Relation patternRelation,
                               Relation hostRelation)

Match a relation in the pattern to a relation in the host model.

Parameters:

patternRelation - The relation in the pattern.

hostRelation - The relation in the host model.

Returns:

true if the match is successful by matching the pattern relation to the host relation. If false, no match can be found if the given pattern relation is matched to the host relation.

_printMatch

private static void _printMatch(MatchResult match)

Print the match result in a readable format to standard output.

Parameters:

match - The match result to be printed.

_shallowMatchDirector

private boolean _shallowMatchDirector(Director patternDirector,
                                      Director hostDirector)

Shallow-match a director in the pattern to a director in the host model but not anything that the director depends on. Return true if the director itself matches, and false otherwise.

Parameters:

patternDirector - The director in the pattern.

hostDirector - The director in the host model.

Returns:

true if the director matches, and false otherwise.

_shallowMatchPath

private static boolean _shallowMatchPath(GraphAnalyzer.Path patternPath,
                                         GraphAnalyzer.Path hostPath)

Shallow-match a path in the pattern to a path in the host model but not anything that the path depends on. Return true if the path itself matches, and false otherwise.

Parameters:

patternPath - The path in the pattern.

hostPath - The path in the host model.

Returns:

true if the path matches, and false otherwise.

_shallowMatchPort

private static boolean _shallowMatchPort(Port patternPort,
                                         Port hostPort)

Shallow-match a port in the pattern to a port in the host model but not anything that the port depends on. Return true if the port itself matches, and false otherwise.

Parameters:

patternPort - The port in the pattern.

hostPort - The port in the host model.

Returns:

true if the port matches, and false otherwise.

_shallowMatchRelation

private boolean _shallowMatchRelation(Relation patternRelation,
                                      Relation hostRelation)

Shallow-match a relation in the pattern to a relation in the host model but not anything that the relation depends on. Return true if the relation itself matches, and false otherwise.

Parameters:

patternRelation - The relation in the pattern.

hostRelation - The relation in the host model.

Returns:

true if the relation matches, and false otherwise.