|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.xqhs.graphs.matcher.GraphMatcherQuick
public class GraphMatcherQuick
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.
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 |
---|
protected Graph graph
protected GraphPattern pattern
protected MonitorPack monitor
MonitorPack
instance to use for performance information and visualization.
protected java.util.PriorityQueue<Match> matchQueue
PriorityQueue
of matches that still have merge candidates. It is kept until a clearData()
is
issued.
protected java.util.List<Match> allMatches
clearData()
is issued.
protected java.util.Iterator<Match> matchIterator
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.
protected boolean initialState
true
if the iterator has just been reset. Becomes false
with the first call to
getNextMatch()
.
protected int kThreshold
getNextMatch()
have a k lower than or equal
to this threshold.
Constructor Detail |
---|
protected GraphMatcherQuick(Graph graph, GraphPattern pattern)
graph
- : the graph (G).pattern
- : the pattern (GP).Method Detail |
---|
public GraphMatcherQuick setMonitor(MonitorPack monitoring)
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.
monitoring
- - the MonitorPack
to use.
public GraphMatcherQuick initializeMatching()
public GraphMatcherQuick resetIterator()
GraphMatchingProcess
GraphMatchingProcess.getNextMatch()
will return the first match conforming to the
current k threshold.
resetIterator
in interface GraphMatchingProcess
public GraphMatcherQuick resetIterator(int k)
GraphMatchingProcess
GraphMatchingProcess.resetIterator()
) and specifies a new k threshold.
resetIterator
in interface GraphMatchingProcess
k
- - the new threshold.
public GraphMatcherQuick clearData()
clearData
in interface GraphMatchingProcess
public Match getNextMatch()
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.
getNextMatch
in interface GraphMatchingProcess
GraphMatchingProcess.resetIterator()
.public java.util.List<Match> getAllMatches(int k)
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.
getAllMatches
in interface GraphMatchingProcess
k
- - the threshold.
List
of matches complying with the threshold.public java.util.List<Match> getAllCompleteMatches()
GraphMatchingProcess
Performance of a call will be influenced by existing matching information.
getAllCompleteMatches
in interface GraphMatchingProcess
List
of complete matches of the pattern in the graph.public java.util.List<Match> getBestMatches()
GraphMatchingProcess
getBestMatches
in interface GraphMatchingProcess
List
with the matches of lowest k.protected java.util.PriorityQueue<Match> initializeMatchQueue()
PriorityQueue
with the appropriate comparator.protected java.util.Map<Node,java.lang.Integer> computeVertexDistances()
Then, computes the distances of each vertex in the pattern from the start vertex.
protected void addInitialMatches()
protected Match addInitialMatch(Edge e, Edge eP, java.lang.String matchID)
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.
protected boolean isMatch(Edge eP, Edge e)
eP
- - the edge in the pattern (eP in EP).e
- - the edge in the graph (eP in E).
true
if the edges match.protected java.util.List<Match> growMatches(int threshold, boolean stopAtFirstMatch)
stopAtFirstMatch
is true
, the process is interrupted when the first
satisfactory match is created, and the match is returned.
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.
stopAtFirstMatch
is true
, the returned
list will have at most one element.protected Match addMergeMatch(Match m1, Match m2)
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.
m1
- - the first match.m2
- - the second match.
protected void invalidateMatch(Match m)
m
- - the match to invalidate.public java.lang.String toString()
toString
in class java.lang.Object
public static GraphMatcherQuick getMatcher(Graph graph, GraphPattern pattern, MonitorPack monitoring)
GraphMatcherQuick
instance for the specified graph and pattern.
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.
GraphMatcherQuick
instance.
java.lang.IllegalArgumentException
- if the monitoring
argument is null
.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |