Packages

class GraphqlOpt extends AnyRef

The 'GraphqlOpt' class provides an implementation for Subgraph Isomorphism of GraphQL's Algorithm.

See also

http://cs.ucsb.edu/~dbl/papers/he_sigmod_2008.pdf (GraphQL paper)

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. GraphqlOpt
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new GraphqlOpt(g: Graph, q: Graph)

    g

    the data graph G(V, E, l)

    q

    the query graph Q(U, D, k)

Value Members

  1. def bijections(): Unit

    Apply the 'GraphQL' Subgraph Isomorphism algorithm to find subgraphs of data graph 'g' that isomorphically match query graph 'q'.

    Apply the 'GraphQL' Subgraph Isomorphism algorithm to find subgraphs of data graph 'g' that isomorphically match query graph 'q'. This method represents the Algorithm 1: Graph Pattern Matching of the 'GraphQL' paper.

  2. def check(u: Int, v: Int): Boolean

    Examines, if 'u' can be mapped to 'v', by considering their edges.

    Examines, if 'u' can be mapped to 'v', by considering their edges. This method is the part of Algorithm 1, line 19 to 26, of the 'GraphQL' paper.

    u

    vertex u can be mapped to v

    v

    vertex v can be mapped to u

  3. def contains(matVert: Array[Int], v: Int): Boolean

    Determine whether vertex 'v' is contained in any matched vertex.

    Determine whether vertex 'v' is contained in any matched vertex.

    matVert

    array of matched vertex from a query vertex u to graph vertex v

    v

    the vertex v to check

  4. def feasibleMates(): Array[Set[Int]]

    Create an initial array of feasible mappings 'phi' from each query vertex 'u' to the corresponding set of data graph vertices '{v}' whose label matches 'u's.

  5. def getMatches(): Set[Array[Int]]

    Returns all subgraph isomorphic matches.

  6. def getNeighborProfile(graph: Graph, u: Int): MutableList[TLabel]

    Find neighborhood profile of vertex 'u' in a graph.

    Find neighborhood profile of vertex 'u' in a graph. The profile is constructed in lexicographical order, refer figure 13 of the 'GraphQL' paper for example.

    graph

    For which graph, we are finding neighbor profile of u

    u

    Vertex u, for which neighborhood profile is created

  7. def getNeighbors(graph: Graph, u: Int): Set[Int]

    Finds all the neighbors of vertex 'u' in a graph.

    Finds all the neighbors of vertex 'u' in a graph.

    graph

    For which graph, we are finding neighbors of u

    u

    Vertex u, for which all neighbors are found

  8. def getSearchOrder(): Unit

    Sorts according to the feasible matches size in ascending order.

    Sorts according to the feasible matches size in ascending order. This method represents the Section 4.4.2 : Optimization of search order based on greedy approach of the 'GraphQL' paper. i.e., at join 'i', choose a leaf node that minimizes the estimated cost of the join.

  9. def neighborProfilePruning(): Unit

    Examines neighborhood profile(sorted neighborhood labels) of query vertex 'u' with feasible vertex 'v' profile of 'v' must contain profile of 'u'.

    Examines neighborhood profile(sorted neighborhood labels) of query vertex 'u' with feasible vertex 'v' profile of 'v' must contain profile of 'u'. This method is the part of Algorithm 1: line 3 and the section 4.2 of the 'GraphQL' paper.

  10. def search(depth: Int): Unit

    Iterates on the 'u'th Node to find feasible mapping for that node.

    Iterates on the 'u'th Node to find feasible mapping for that node. This is the part of Algorithm 1, Line 8 to 18, of the 'GraphQL' paper

    depth

    the depth of recursion