edu.ucdenver.ccp.esm
Class ESM

java.lang.Object
  edu.ucdenver.ccp.esm.ESM

public class ESM
extends Object

The Exact Subgraph Matching (ESM) algorithm Java implementation for subgraph isomorphism problems

The subgraph isomorphism problem is NP-hard. 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 worst-case 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 best-case 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 ESM-related publications.

This ESM implementation also provides a function to determine the graph isomorphism between two graphs.

Author:

Implemented by Haibin Liu and Tested by Philippe Thomas

ESM

public 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

Parameters:

subgraph - : subgraph (supposed to be smaller)

graph - : graph (supposed to be bigger)

setSubgraphStartNode

public void setSubgraphStartNode(Vertex vertex)

Instead of the default random start node, users can specify the start node for the subgraph

Parameters:

vertex - : user-specified start node

setGraphStartNodes

public 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. However, users can set the set of start nodes for the graph to specify which specific set of nodes they want to use to compare with the subgraph start node. This will narrow down the search by avoiding to match the subgraph start node with every graph node. Consequently, more efficient.

Parameters:

vertices - : user-specified set of start nodes

getSubgraphMatchingMatches

public List<Map<Vertex,Vertex>> getSubgraphMatchingMatches()

Retrieve specific matchings between the subgraph and the graph matching result is store in a map. the key is the node in the subgraph and the value is the injective matching node in the graph Since a subgraph can match different places of a graph, we record all the matchings by putting each matching into a List

Returns:

a list of matchings between two graphs

isSubgraphIsomorphism

public boolean isSubgraphIsomorphism()

Check if the input subgraph is subsumed by the input graph

Returns:

true or false

isGraphIsomorphism

public 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

Returns:

true or false