net.xqhs.graphs.matcher
Class Match

java.lang.Object
  extended by net.xqhs.graphs.matcher.Match

public class Match
extends java.lang.Object

Class describing a [partial] match of GP in G. In time, matches go from a 1-edge match to a maximal match.

Main components:

Version 1.5 brings integration of some of the processes related to matching into the implementation of Match, such as checking merge candidates, merging, etc.

Author:
Andrei Olaru

Nested Class Summary
static class Match.Candidacy
          Possible values for the situations in which two matches can be with regard to merging.
static class Match.MatchComparator
          Match comparator.
 
Field Summary
(package private)  java.util.Map<Edge,java.util.List<Edge>> edgeFunction
          The correspondence (edge) function EmP -> E'
(package private)  java.util.Map<Node,java.util.concurrent.atomic.AtomicInteger> frontier
          The nodes on the frontier of GmP - nodes that have adjacent edges in ExP.
(package private)  java.lang.String id
          The name of the edge.
(package private)  int k
          k, the number of edges in GxP
(package private)  Graph matchedGraph
          G', the subgraph of G that has been matched.
(package private)  java.util.Set<Match> mergeCandidates
          MC, matches that could possibly be merged with this one (i.e.
(package private)  java.util.Set<Match> mergeOuterCandidates
          MO, matches that could potentially merge with this one, but not immediately (they are not adjacent).
(package private)  java.util.Map<Node,Node> nodeFunction
          The correspondence (node) function VmP -> V'
(package private)  GraphPattern patternLink
          Reference to the pattern GP
(package private)  GraphPattern solvedPart
          GmP, the part of GP that has been matched.
(package private)  Graph targetGraphLink
          Reference to the graph G.
(package private)  GraphPattern unsolvedPart
          GxP, the part of GP that has not been matched.
(package private)  boolean valid
          States that the match is still valid.
 
Constructor Summary
Match(Graph g, GraphPattern p)
          Create a new empty match; some parts may be uninitialized / undefined (like frontier, or matchCandidates)
Match(Graph g, GraphPattern p, Edge e, Edge eP, java.lang.String id)
          Create a match, using an initial matching edge.
 
Method Summary
 Match.Candidacy considerCandidate(Match mc, java.util.Map<Edge,java.util.Set<Match>> eMatchIndex, java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex, MonitorPack monitor)
          The method checks if the given match is a merge candidate for this match, and if it is, the matches are added to the merge candidate lists of each other.
 Match.Candidacy getCandidacy(Match mc, java.util.Map<Edge,java.util.Set<Match>> eMatchIndex, java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex, MonitorPack monitor)
          The method checks whether another match can be considered as a candidate for merger with this match, and, if yes, what kind (see Match.Candidacy).
protected  Match.Candidacy getCandidacyInternal(Match mc, MonitorPack monitor)
          Internal method that tests candidacy status based solely on internal properties of the matches.
 Graph getGraph()
           
 int getK()
          Gets the k of the match -- the number of edges from the pattern that don't have a match in the matched subgraph.
 Graph getMatchedGraph()
           
 java.util.List<Edge> getMatchedGraphEdges(Edge patternEdge)
          Retrieves the edges in the matched subgraph that correspond to the specified edge from the solved part.
 Node getMatchedGraphNode(Node patternNode)
          Retrieves the node in the matched subgraph that corresponds to the specified node from the solved part.
 GraphPattern getPattern()
           
 int getSize()
           
 GraphPattern getSolvedPart()
           
 GraphPattern getUnsolvedPart()
           
protected  void invalidate()
          Invalidates the match.
 boolean isValid()
          Checks if the match is valid.
 Match merge(Match m1, java.util.Map<Edge,java.util.Set<Match>> eMatchIndex, java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex, MonitorPack monitor)
          Merges two matches into a new one and returns the result.
 java.lang.String toString()
           
static java.lang.String toStringDemo()
          Shows a legend of the toString output.
 java.lang.String toStringExtended()
          Provides a complete one-line representation of the match.
 java.lang.String toStringLong()
          Provides an extensive string representation of the match, spanning multiple rows.
 GraphRepresentation toVisual(net.xqhs.graphical.GCanvas canvas, java.awt.Point topleft, java.awt.Point bottomright)
          Creates a graphical representation of the match and displays it using the specified GCanvas.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

targetGraphLink

Graph targetGraphLink
Reference to the graph G.


patternLink

GraphPattern patternLink
Reference to the pattern GP


matchedGraph

Graph matchedGraph
G', the subgraph of G that has been matched. It is connected and it is a proper graph.


solvedPart

GraphPattern solvedPart
GmP, the part of GP that has been matched. It is connected and it is a proper graph.


unsolvedPart

GraphPattern unsolvedPart
GxP, the part of GP that has not been matched. It may contain edges without the adjacent nodes.


k

int k
k, the number of edges in GxP


nodeFunction

java.util.Map<Node,Node> nodeFunction
The correspondence (node) function VmP -> V'


edgeFunction

java.util.Map<Edge,java.util.List<Edge>> edgeFunction
The correspondence (edge) function EmP -> E'


frontier

java.util.Map<Node,java.util.concurrent.atomic.AtomicInteger> frontier
The nodes on the frontier of GmP - nodes that have adjacent edges in ExP. Nodes are a subset of VmP.

For each node the number of remaining edges in ExP that are adjacent to it is given.


mergeCandidates

java.util.Set<Match> mergeCandidates
MC, matches that could possibly be merged with this one (i.e. not intersecting and sharing at least one common vertex (with a common correspondent in the graph).


mergeOuterCandidates

java.util.Set<Match> mergeOuterCandidates
MO, matches that could potentially merge with this one, but not immediately (they are not adjacent).


id

java.lang.String id
The name of the edge.

Initially (for single-edge matches) the id is the id of the pattern edge, dash, a counter for matches based on that edge.


valid

boolean valid
States that the match is still valid. In persistent matching, a match may become invalid but not yet removed from various structures.

Since:
1.5
Constructor Detail

Match

public Match(Graph g,
             GraphPattern p)
Create a new empty match; some parts may be uninitialized / undefined (like frontier, or matchCandidates)

This constructor is meant just to construct matches that will later be completely initialized as a result of merging two existing matches.

Parameters:
g - : the graph
p - : the pattern

Match

public Match(Graph g,
             GraphPattern p,
             Edge e,
             Edge eP,
             java.lang.String id)
Create a match, using an initial matching edge.

Parameters:
g - : the graph
p - : the pattern
e - : the matching edge in the graph
eP - : the matching edge in the pattern
id - : the matching graph edge's id
Method Detail

invalidate

protected void invalidate()
Invalidates the match. The method can be used classes extending GraphMatcherQuick by calling GraphMatcherQuick.invalidateMatch(Match). This way matches cannot be invalidated by other classes.

Since:
1.5

isValid

public boolean isValid()
Checks if the match is valid. Invalid matches are on the way to be removed from various structures.

Returns:
true if the match is still valid.
Since:
1.5

getK

public int getK()
Gets the k of the match -- the number of edges from the pattern that don't have a match in the matched subgraph. Best k is 0, worst k (single-edge match) is number of edges in the pattern minus 1.

Returns:
the k of the match.

getSize

public int getSize()
Returns:
the number of edges in the matched part (solved part) of the pattern.

getGraph

public Graph getGraph()
Returns:
the Graph against which is the match.

getPattern

public GraphPattern getPattern()
Returns:
the GraphPattern of which is the match.

getSolvedPart

public GraphPattern getSolvedPart()
Returns:
the "solved part" of the pattern.

getUnsolvedPart

public GraphPattern getUnsolvedPart()
Returns:
the "unsolved part" of the pattern. WARNING the returned graph may contain edges that have adjacent nodes outside of the graph.

getMatchedGraph

public Graph getMatchedGraph()
Returns:
the subgraph matched by the "solved part" of the pattern.

getMatchedGraphNode

public Node getMatchedGraphNode(Node patternNode)
Retrieves the node in the matched subgraph that corresponds to the specified node from the solved part.

Parameters:
patternNode - - the node in the solved part of the pattern.
Returns:
the corresponding node in the matched subgraph.
Throws:
java.lang.IllegalArgumentException - if the node is not found in the solved part of the pattern.
java.lang.IllegalStateException - if the node is not found in the node function map.

getMatchedGraphEdges

public java.util.List<Edge> getMatchedGraphEdges(Edge patternEdge)
Retrieves the edges in the matched subgraph that correspond to the specified edge from the solved part. If the pattern edge is not labeled with a regular expression, the returned list will contain only one edge.

Parameters:
patternEdge - - the edge in the solved part of the pattern.
Returns:
the corresponding sequence of edges in the matched subgraph.
Throws:
java.lang.IllegalArgumentException - if the edge is not found in the solved part of the pattern.
java.lang.IllegalStateException - if the edge is not found in the edge function map.

getCandidacy

public Match.Candidacy getCandidacy(Match mc,
                                    java.util.Map<Edge,java.util.Set<Match>> eMatchIndex,
                                    java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex,
                                    MonitorPack monitor)
The method checks whether another match can be considered as a candidate for merger with this match, and, if yes, what kind (see Match.Candidacy).

This version of the method relies on edge-to-containing-match and pattern-edge-to-containing-match indexes to locate potential intersection in the matches.

Parameters:
mc - - the other match.
eMatchIndex - - the index of graph edge → matches that contain that edge.
ePMatchIndex - - the index of graph pattern edge → matches that contain that edge.
monitor - - the MonitorPack to use for performance measures.
Returns:
the appropriate Match.Candidacy value for this match and the match in the argument.
Throws:
java.lang.IllegalArgumentException - if any of the arguments is null.

getCandidacyInternal

protected Match.Candidacy getCandidacyInternal(Match mc,
                                               MonitorPack monitor)
Internal method that tests candidacy status based solely on internal properties of the matches.

More precisely, it checks that nodes on the frontiers of moth matches have the same correspondent nodes in the graph. It also checks if there is any intersection between the two frontiers, deciding between Match.Candidacy.OUTER (no intersection) and Match.Candidacy.IMMEDIATE.

Parameters:
mc - - the other match.
monitor - - the MonitorPack to use for performance measures.
Returns:
the appropriate Match.Candidacy value for this match and the match in the argument.

considerCandidate

public Match.Candidacy considerCandidate(Match mc,
                                         java.util.Map<Edge,java.util.Set<Match>> eMatchIndex,
                                         java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex,
                                         MonitorPack monitor)
The method checks if the given match is a merge candidate for this match, and if it is, the matches are added to the merge candidate lists of each other. This call modifies the matches (their candidate lists) in case candidacy is not Match.Candidacy.NONE.

Parameters:
mc - - the other match.
eMatchIndex - - the index of graph edge → matches that contain that edge.
ePMatchIndex - - the index of graph pattern edge → matches that contain that edge.
monitor - - the MonitorPack to use for performance measures.
Returns:
the appropriate Match.Candidacy value for this match and the match in the argument.
Throws:
java.lang.IllegalArgumentException - if any of the arguments is null or if the other match is not between the same graph and pattern.

merge

public Match merge(Match m1,
                   java.util.Map<Edge,java.util.Set<Match>> eMatchIndex,
                   java.util.Map<Edge,java.util.Set<Match>> ePMatchIndex,
                   MonitorPack monitor)
Merges two matches into a new one and returns the result.

Matches are expected to be correct merge candidates, that is disjoint (in terms of edges), both as GmP (matched part of pattern) and as G' (matched subgraph); also, all common nodes in GmP must correspond to the same nodes in G' (this check should be done initially in getCandidacy(Match, Map, Map, MonitorPack).

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

If the passed indexes are not null, the match is added to the indexes.

Parameters:
m1 - - the other match.
eMatchIndex - - the index of graph edge → matches that contain that edge. If not null, it is used for indexing the new match.
ePMatchIndex - - the index of graph pattern edge → matches that contain that edge. If not null, it is used for indexing the new match.
monitor - - the MonitorPack to use for performance measures.
Returns:
the merged match.

toStringDemo

public static java.lang.String toStringDemo()
Shows a legend of the toString output.

Returns:
the output.

toString

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

toStringExtended

public java.lang.String toStringExtended()
Provides a complete one-line representation of the match. Not to be confused with toStringLong().

Returns:
the string representation.

toStringLong

public java.lang.String toStringLong()
Provides an extensive string representation of the match, spanning multiple rows.

Returns:
the string representation

toVisual

public GraphRepresentation toVisual(net.xqhs.graphical.GCanvas canvas,
                                    java.awt.Point topleft,
                                    java.awt.Point bottomright)
Creates a graphical representation of the match and displays it using the specified GCanvas.

Parameters:
canvas - - the canvas to use for the representation.
topleft - - the top left point for the representation, on the canvas.
bottomright - - the bottom right point for the representation, on the canvas.
Returns:
- the created representation.