net.xqhs.graphs.matcher
Class GraphMatcherQuick

java.lang.Object
  extended by net.xqhs.graphs.matcher.GraphMatcherQuick
All Implemented Interfaces:
GraphMatchingProcess
Direct Known Subclasses:
GraphMatcherPersistent

public class GraphMatcherQuick
extends java.lang.Object
implements GraphMatchingProcess

An algorithm that finds partial matches between a graph pattern GP (or G^P) and a graph (G).

In order to evaluate the performance and to visualize the process, a MonitorPack instance is used throughout the code.

All matches generated in the matching process are retained throughout the life of the instance. They can be cleared with a call to clearData(). If a call to clearData() is not issued, queries for matches that have already been found in the past will complete quickly, as it will only take a pass through the list of generated matches. However, memory will remain occupied until clearData() is issued (or the instance is garbage-collected).

The algorithm has been published in: Andrei Olaru, Context Matching for Ambient Intelligence Applications, Proceedings of SYNASC 2013, 15th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, September 23-26, 2013 Timisoara, Romania, IEEE CPS, 2013.

Author:
Andrei Olaru

Nested Class Summary
static class GraphMatcherQuick.EdgeComparator
          Graph/pattern edge comparator based on label and then hash code.
protected static class GraphMatcherQuick.MatchSingleComparator
          Match comparator with additional features for single-edge matches.
 
Field Summary
protected  java.util.List<Match> allMatches
          A list of all generated matches.
protected  Graph graph
          The graph to match the pattern to (G).
protected  boolean initialState
          Is true if the iterator has just been reset.
protected  int kThreshold
          The current k threshold.
protected  java.util.Iterator<Match> matchIterator
          An Iterator over allMatches that keeps is used to remember the already-returned matches.
protected  java.util.PriorityQueue<Match> matchQueue
          The PriorityQueue of matches that still have merge candidates.
protected  MonitorPack monitor
          The MonitorPack instance to use for performance information and visualization.
protected  GraphPattern pattern
          The pattern to match to the graph (GP).
 
Constructor Summary
protected GraphMatcherQuick(Graph graph, GraphPattern pattern)
          Initializes a matcher.
 
Method Summary
protected  Match addInitialMatch(Edge e, Edge eP, java.lang.String matchID)
          Create a single-edge match and add it to the matching queue; also add matches from the queue to its merge candidate list (as well as adding the match to other matches' merge candidates)
protected  void addInitialMatches()
          Add initial (i.e.
protected  Match addMergeMatch(Match m1, Match m2)
          Merges two matches into one.
 GraphMatcherQuick clearData()
          Clears the match queue and the list of all matches.
protected  java.util.Map<Node,java.lang.Integer> computeVertexDistances()
          Decides which is the "start vertex" in the pattern (maximum value of in-degree minus out-degree).
 java.util.List<Match> getAllCompleteMatches()
          The method returns all complete matches.
 java.util.List<Match> getAllMatches(int k)
          As with getNextMatch(), satisfactory matches are searched in the list of existing matches.
 java.util.List<Match> getBestMatches()
          The method creates all matches and returns the set of matches with the best (lowest) k.
static GraphMatcherQuick getMatcher(Graph graph, GraphPattern pattern, MonitorPack monitoring)
          Returns a newly created GraphMatcherQuick instance for the specified graph and pattern.
 Match getNextMatch()
          Searches for the next match with a k lower than or equal to the current threshold.
protected  java.util.List<Match> growMatches(int threshold, boolean stopAtFirstMatch)
          Grows incrementally the list of matches, by merging existing matches from the match queue with their merge candidates.
 GraphMatcherQuick initializeMatching()
          Initializes the matching progress, by creating the match comparator and adding the initial matches to the match queue.
protected  java.util.PriorityQueue<Match> initializeMatchQueue()
          The method initializes the match queue by creating an appropriate comparator (based on distances of edges to a start vertex).
protected  void invalidateMatch(Match m)
          Relay for the invalidation of a match, since matches should only be invalidated by classes extending this class.
protected  boolean isMatch(Edge eP, Edge e)
          Test the match between two edges: matching from and to nodes, matching label.
 GraphMatcherQuick resetIterator()
          Resets the iterator.
 GraphMatcherQuick resetIterator(int k)
          Resets the iterator (see GraphMatchingProcess.resetIterator()) and specifies a new k threshold.
 GraphMatcherQuick setMonitor(MonitorPack monitoring)
          Calling this method with a different MonitorPack instance than previously set does not result in keeping any information from one monitor to the other, and aggregation of indicators and output will have to be done manually.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

graph

protected Graph graph
The graph to match the pattern to (G).


pattern

protected GraphPattern pattern
The pattern to match to the graph (GP).


monitor

protected MonitorPack monitor
The MonitorPack instance to use for performance information and visualization.


matchQueue

protected java.util.PriorityQueue<Match> matchQueue
The PriorityQueue of matches that still have merge candidates. It is kept until a clearData() is issued.


allMatches

protected java.util.List<Match> allMatches
A list of all generated matches. It is kept until a clearData() is issued.


matchIterator

protected java.util.Iterator<Match> matchIterator
An Iterator over allMatches that keeps is used to remember the already-returned matches. It is reset with resetIterator() or when the list of matches has been completely iterated over and no satisfactory match has been found.


initialState

protected boolean initialState
Is true if the iterator has just been reset. Becomes false with the first call to getNextMatch().


kThreshold

protected int kThreshold
The current k threshold. Matches returned by getNextMatch() have a k lower than or equal to this threshold.

Constructor Detail

GraphMatcherQuick

protected GraphMatcherQuick(Graph graph,
                            GraphPattern pattern)
Initializes a matcher. Does not do any matching.

Parameters:
graph - : the graph (G).
pattern - : the pattern (GP).
Method Detail

setMonitor

public GraphMatcherQuick setMonitor(MonitorPack monitoring)
Calling this method with a different MonitorPack instance than previously set does not result in keeping any information from one monitor to the other, and aggregation of indicators and output will have to be done manually.

Parameters:
monitoring - - the MonitorPack to use.
Returns:
the matcher itself.

initializeMatching

public GraphMatcherQuick initializeMatching()
Initializes the matching progress, by creating the match comparator and adding the initial matches to the match queue.

Returns:
the instance itself.

resetIterator

public GraphMatcherQuick resetIterator()
Description copied from interface: GraphMatchingProcess
Resets the iterator. The next call to GraphMatchingProcess.getNextMatch() will return the first match conforming to the current k threshold.

Specified by:
resetIterator in interface GraphMatchingProcess
Returns:
the instance itself.

resetIterator

public GraphMatcherQuick resetIterator(int k)
Description copied from interface: GraphMatchingProcess
Resets the iterator (see GraphMatchingProcess.resetIterator()) and specifies a new k threshold.

Specified by:
resetIterator in interface GraphMatchingProcess
Parameters:
k - - the new threshold.
Returns:
the instance itself.

clearData

public GraphMatcherQuick clearData()
Clears the match queue and the list of all matches.

Specified by:
clearData in interface GraphMatchingProcess
Returns:
the instance itself.

getNextMatch

public Match getNextMatch()
Searches for the next match with a k lower than or equal to the current threshold. The match returned is the first match that was not previously returned after the last call to resetIterator().

It the matching process has not been already initialized, first all initial matches will be created.

If a satisfactory match has already been generated (and no call to clearData() has been issued in the mean time), that match will be found in the list of existing matches and returned.

Otherwise, the matching process will continue (potentially based on existing information from previous calls) until a satisfactory match will be found or the matching process completes.

In the latter case, null is returned.

Specified by:
getNextMatch in interface GraphMatchingProcess
Returns:
the first match that was not previously returned after the last call to GraphMatchingProcess.resetIterator().

getAllMatches

public java.util.List<Match> getAllMatches(int k)
As with getNextMatch(), satisfactory matches are searched in the list of existing matches. Next, the matching process is completed and any newly found matches are added to the result.

Specified by:
getAllMatches in interface GraphMatchingProcess
Parameters:
k - - the threshold.
Returns:
a List of matches complying with the threshold.

getAllCompleteMatches

public java.util.List<Match> getAllCompleteMatches()
Description copied from interface: GraphMatchingProcess
The method returns all complete matches.

Performance of a call will be influenced by existing matching information.

Specified by:
getAllCompleteMatches in interface GraphMatchingProcess
Returns:
a List of complete matches of the pattern in the graph.

getBestMatches

public java.util.List<Match> getBestMatches()
Description copied from interface: GraphMatchingProcess
The method creates all matches and returns the set of matches with the best (lowest) k. If any complete matches exist, the returned list will contain all complete matches.

Specified by:
getBestMatches in interface GraphMatchingProcess
Returns:
a List with the matches of lowest k.

initializeMatchQueue

protected java.util.PriorityQueue<Match> initializeMatchQueue()
The method initializes the match queue by creating an appropriate comparator (based on distances of edges to a start vertex).

Returns:
an empty PriorityQueue with the appropriate comparator.

computeVertexDistances

protected java.util.Map<Node,java.lang.Integer> computeVertexDistances()
Decides which is the "start vertex" in the pattern (maximum value of in-degree minus out-degree).

Then, computes the distances of each vertex in the pattern from the start vertex.

Returns:
the distance map.

addInitialMatches

protected void addInitialMatches()
Add initial (i.e. all single-edge) matches to the match queue.


addInitialMatch

protected Match addInitialMatch(Edge e,
                                Edge eP,
                                java.lang.String matchID)
Create a single-edge match and add it to the matching queue; also add matches from the queue to its merge candidate list (as well as adding the match to other matches' merge candidates)

Parameters:
g - - the graph.
p - - the pattern.
e - - the edge in the graph.
eP - - the edge in the pattern.
matchID - - the id for the new match.
m - - the match to add to the queue.
queue - - the match queue.
monitor - - the monitoring instance.
Returns:
the newly created and configured match.

isMatch

protected boolean isMatch(Edge eP,
                          Edge e)
Test the match between two edges: matching from and to nodes, matching label.

Parameters:
eP - - the edge in the pattern (eP in EP).
e - - the edge in the graph (eP in E).
Returns:
true if the edges match.

growMatches

protected java.util.List<Match> growMatches(int threshold,
                                            boolean stopAtFirstMatch)
Grows incrementally the list of matches, by merging existing matches from the match queue with their merge candidates. In case stopAtFirstMatch is true, the process is interrupted when the first satisfactory match is created, and the match is returned.

Parameters:
threshold - - the threshold for matches: satisfactory matches have a k lower than or equal to this number.
stopAtFirstMatch - - if true, the method returns after the first satisfactory match is found.
Returns:
the list of satisfactory matches. If stopAtFirstMatch is true, the returned list will have at most one element.

addMergeMatch

protected Match addMergeMatch(Match m1,
                              Match m2)
Merges two matches into one.

Matches are expected to be disjoint, both as GmP and as G' (in terms of edges); also, all common nodes in GmP must correspond to the same nodes in G' (this check should be done in addMatcheToQueue.

Attention: matches are expected to be merge-able without checks.

Parameters:
m1 - - the first match.
m2 - - the second match.
Returns:
the merged match.

invalidateMatch

protected void invalidateMatch(Match m)
Relay for the invalidation of a match, since matches should only be invalidated by classes extending this class.

Parameters:
m - - the match to invalidate.
Since:
1.5

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object

getMatcher

public static GraphMatcherQuick getMatcher(Graph graph,
                                           GraphPattern pattern,
                                           MonitorPack monitoring)
Returns a newly created GraphMatcherQuick instance for the specified graph and pattern.

Parameters:
graph - - the graph.
pattern - - the pattern.
monitoring - - the monitoring instance. It must not be null but it can be a newly created instance with no configuration.
Returns:
the GraphMatcherQuick instance.
Throws:
java.lang.IllegalArgumentException - if the monitoring argument is null.