net.xqhs.graphs.matchingPlatform
Class GraphMatcherPersistent

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

public class GraphMatcherPersistent
extends GraphMatcherQuick

The class extends GraphMatcherQuick (and therefore implements GraphMatchingProcess) to handle persistent matching -- matching in which the graph changes slightly from time to time. With each change, only affected matches should be removed or created.

The pattern is not allowed to change.

Author:
Andrei Olaru

Nested Class Summary
 
Nested classes/interfaces inherited from class net.xqhs.graphs.matcher.GraphMatcherQuick
GraphMatcherQuick.EdgeComparator, GraphMatcherQuick.MatchSingleComparator
 
Field Summary
protected  java.util.Map<Edge,java.util.Set<Match>> eMatchIndex
          An index containing the matches that contain each graph edge.
protected  java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex
          An index containing the matches that contain each pattern edge.
protected  java.util.SortedSet<Match> sortedMatches
          THe set of all matches, sorted by k (lowest k first).
 
Fields inherited from class net.xqhs.graphs.matcher.GraphMatcherQuick
allMatches, graph, initialState, kThreshold, matchIterator, matchQueue, monitor, pattern
 
Constructor Summary
protected GraphMatcherPersistent(Graph graph, GraphPattern pattern)
          Creates a new matcher for the specified graph and pattern.
 
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)
 GraphMatcherPersistent addMatches(Edge e)
          The method should be called for each new edge added to the graph.
protected  Match addMergeMatch(Match m1, Match m2)
          Merges two matches into one.
 GraphMatcherPersistent clearData()
          Clears the match queue and the list of all matches.
 GraphMatcherPersistent completeMatches()
          Completes the matching process, growing all matches to their maximum coverage.
static GraphMatcherPersistent getMatcher(Graph graph, GraphPattern pattern, MonitorPack monitoring)
          Returns a newly created GraphMatcherQuick instance for the specified graph and pattern.
protected  int getMemory()
           
 GraphMatcherPersistent initializeMatching()
          Initializes the matching progress, by creating the match comparator and adding the initial matches to the match queue.
 GraphMatcherPersistent removeMatches(Edge edge)
          The method should be called for each edge removed from the graph.
 
Methods inherited from class net.xqhs.graphs.matcher.GraphMatcherQuick
addInitialMatches, computeVertexDistances, getAllCompleteMatches, getAllMatches, getBestMatches, getNextMatch, growMatches, initializeMatchQueue, invalidateMatch, isMatch, resetIterator, resetIterator, setMonitor, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

sortedMatches

protected java.util.SortedSet<Match> sortedMatches
THe set of all matches, sorted by k (lowest k first).


eMatchIndex

protected java.util.Map<Edge,java.util.Set<Match>> eMatchIndex
An index containing the matches that contain each graph edge. The index contains only the edges that are contained in any matches.


ePMatchIndex

protected java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex
An index containing the matches that contain each pattern edge. The index contains only the edges that are contained in any matches.

Constructor Detail

GraphMatcherPersistent

protected GraphMatcherPersistent(Graph graph,
                                 GraphPattern pattern)
Creates a new matcher for the specified graph and pattern. Any further changes to the graph will be signaled by calling addMatches(Edge) and removeMatches(Edge).

Parameters:
graph - - the graph.
pattern - - the pattern.
Method Detail

initializeMatching

public GraphMatcherPersistent initializeMatching()
Description copied from class: GraphMatcherQuick
Initializes the matching progress, by creating the match comparator and adding the initial matches to the match queue.

Overrides:
initializeMatching in class GraphMatcherQuick
Returns:
the instance itself.

clearData

public GraphMatcherPersistent clearData()
Description copied from class: GraphMatcherQuick
Clears the match queue and the list of all matches.

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

completeMatches

public GraphMatcherPersistent completeMatches()
Completes the matching process, growing all matches to their maximum coverage.

Returns:
the instance itself.

addMatches

public GraphMatcherPersistent addMatches(Edge e)
The method should be called for each new edge added to the graph. It is assumed that the graph contains the new edge when the method is called.

The method creates the initial matches containing the new edge, adds their merge candidates, but does not grow any matches. This can be requested through any of the match retrieval methods or by calling completeMatches().

Parameters:
e - - the new edge added to the graph.
Returns:
the instance itself.

removeMatches

public GraphMatcherPersistent removeMatches(Edge edge)
The method should be called for each edge removed from the graph. It is assumed that the graph doesn't contain the edge anymore at the time the method is called.

The method only removes the edge from the edge → matches index, and marks the matches containing the edge as invalid. Whenever an iteration finds the invalidated match, it will be removed from the containing collection. This saves a large number of operations that would have been required by looping through the various lists and indexes.

Parameters:
edge - - the edge removed from the graph.
Returns:
the instance itself.

addInitialMatch

protected Match addInitialMatch(Edge e,
                                Edge eP,
                                java.lang.String matchID)
Description copied from class: GraphMatcherQuick
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)

Overrides:
addInitialMatch in class GraphMatcherQuick
Parameters:
e - - the edge in the graph.
eP - - the edge in the pattern.
matchID - - the id for the new match.
Returns:
the newly created and configured match.

addMergeMatch

protected Match addMergeMatch(Match m1,
                              Match m2)
Description copied from class: GraphMatcherQuick
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.

Overrides:
addMergeMatch in class GraphMatcherQuick
Parameters:
m1 - - the first match.
m2 - - the second match.
Returns:
the merged match.

getMatcher

public static GraphMatcherPersistent 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.

getMemory

protected int getMemory()
Returns:
an indication of the used memory (sizes of indexes).