

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object edu.ucdenver.ccp.esm.ESM
public class ESM
The Exact Subgraph Matching (ESM) algorithm Java implementation for subgraph isomorphism problems
The subgraph isomorphism problem is NPhard. We designed a simple exact subgraph matching (ESM) algorithm for dependency graphs using a backtracking approach. This algorithm is designed to process dependency graphs (directed graphs, direction from governor token to dependent token) from dependency parsers for biological relation and event extraction. It has been demonstrated to be very efficient in these biological information extraction applications.
The total worstcase algorithm complexity is O(n^2 * k^n) where n is the number of vertices and k is the vertex degree (number of adjacent edges). The bestcase algorithm complexity is O(n^3 * k^2).
For more details about our ESM algorithm, the analysis on time complexity, and the different applications of the algorithm, see the section "Related Publications" in the README file for the complete list of our ESMrelated publications.
This ESM implementation also provides a function to determine the graph isomorphism between two graphs.
Constructor Summary  

ESM(edu.uci.ics.jung.graph.DirectedGraph<Vertex,Edge> subgraph,
edu.uci.ics.jung.graph.DirectedGraph<Vertex,Edge> graph)
Constructor to initialize the subgraph and graph and specify the start node of the subgraph and the set of start nodes of the graph 
Method Summary  

List<Map<Vertex,Vertex>> 
getSubgraphMatchingMatches()
Retrieve specific matchings between the subgraph and the graph matching result is store in a map. 
boolean 
isGraphIsomorphism()
Provide an additional function to determine if two graphs are isomorphic to each other based on the fact that if two graphs are subgraph isomorphic to each other, then they are isomorphic to each other 
boolean 
isSubgraphIsomorphism()
Check if the input subgraph is subsumed by the input graph 
void 
setGraphStartNodes(List<Vertex> vertices)
The default setting for choosing the set of start nodes for the graph is use all nodes in the graph as start nodes. 
void 
setSubgraphStartNode(Vertex vertex)
Instead of the default random start node, users can specify the start node for the subgraph 
Methods inherited from class java.lang.Object 

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

public ESM(edu.uci.ics.jung.graph.DirectedGraph<Vertex,Edge> subgraph, edu.uci.ics.jung.graph.DirectedGraph<Vertex,Edge> graph)
subgraph
 : subgraph (supposed to be smaller)graph
 : graph (supposed to be bigger)Method Detail 

public void setSubgraphStartNode(Vertex vertex)
vertex
 : userspecified start nodepublic void setGraphStartNodes(List<Vertex> vertices)
vertices
 : userspecified set of start nodespublic List<Map<Vertex,Vertex>> getSubgraphMatchingMatches()
public boolean isSubgraphIsomorphism()
public boolean isGraphIsomorphism()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 