scalation
API
Generated with
scalation/scalation/scalation.database/scalation.database.graph_pm/GraphSim

GraphSim

scalation.database.graph_pm.GraphSim
class GraphSim(g: Graph, q: Graph) extends GraphMatcher

The GraphSim class provides an implementation for Simple Graph Simulation. For each vertex in a query graph q, it returns all matching vertices in the data graph g with the same vertex label and matching children.

Value parameters

g

the data graph G(V, E, l)

q

the query graph Q(U, D, k)

Attributes

See also
Graph
Supertypes
trait GraphMatcher
class Object
trait Matchable
class Any

Members list

Value members

Concrete methods

def prune(φ: Array[Set[Int]]): Array[Set[Int]]

Given the mappings φ produced by the feasibleMates method, eliminate mappings u -> v when v's children fail to match u's. This version checks edge labels.

Given the mappings φ produced by the feasibleMates method, eliminate mappings u -> v when v's children fail to match u's. This version checks edge labels.

Value parameters

φ

array of mappings from a query vertex u to { graph vertices v }

Attributes

def prune0(φ: Array[Set[Int]]): Array[Set[Int]]

Given the mappings φ produced by the feasibleMates method, eliminate mappings u -> v when v's children fail to match u's. This version ignores edge labels.

Given the mappings φ produced by the feasibleMates method, eliminate mappings u -> v when v's children fail to match u's. This version ignores edge labels.

Value parameters

φ

array of mappings from a query vertex u to { graph vertices v }

Attributes

See also
def remove(φ: Array[Set[Int]], u: Int, rem: Set[Int]): Boolean

Remove the vertices found by a pruninng step and signal early termination when φ(u) become empty by returning true.

Remove the vertices found by a pruninng step and signal early termination when φ(u) become empty by returning true.

Value parameters

rem

the vertices to be pruned from mapping of u

u

the query graph vertices whose mapping is being pruned

φ

array of mappings from a query vertex u to { graph vertices v }

Attributes

Inherited methods

def bijections(): Set[Array[Int]]

Apply a graph pattern matching algorithm to find subgraphs of data graph g that isomorphically match query graph q. These are represented by a set of single-valued bijections {psi} where each psi function maps each query graph vertex u to a data graph vertices v.

Apply a graph pattern matching algorithm to find subgraphs of data graph g that isomorphically match query graph q. These are represented by a set of single-valued bijections {psi} where each psi function maps each query graph vertex u to a data graph vertices v.

Attributes

Inherited from:
GraphMatcher
def countMappings(φ: Array[Set[Int]]): (Int, Int)

Count the number of mappings between query graph vertices u_i and their sets of data graph vertices {v}, giving the number of distinct vertices and edges.

Count the number of mappings between query graph vertices u_i and their sets of data graph vertices {v}, giving the number of distinct vertices and edges.

Value parameters

φ

the set-valued mapping function

Attributes

Inherited from:
GraphMatcher
def feasibleMates: Array[Set[Int]]

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

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

Attributes

Inherited from:
GraphMatcher
def filterGraph(φ: Array[Set[Int]]): Graph

Filter the data graph by consider only those vertices and edges which are part of feasible matches after performing initial dual simulation. Note, used by strict and tight simulation.

Filter the data graph by consider only those vertices and edges which are part of feasible matches after performing initial dual simulation. Note, used by strict and tight simulation.

Value parameters

φ

mappings from a query vertex u_q to { graph vertices v_g }

Attributes

Inherited from:
GraphMatcher
def mappings(ignoreEdgeLabels: Boolean): Array[Set[Int]]

Apply a graph pattern matching algorithm to find the mappings from the query graph q to the data graph g. These are represented by a multi-valued function φ that maps each query graph vertex u to a set of data graph vertices {v}.

Apply a graph pattern matching algorithm to find the mappings from the query graph q to the data graph g. These are represented by a multi-valued function φ that maps each query graph vertex u to a set of data graph vertices {v}.

Value parameters

ignoreEdgeLabels

whether to ingore edge labels during matching

Attributes

Inherited from:
GraphMatcher
def showMappings(φ: Array[Set[Int]]): Unit

Show all mappings between query graph vertices u_i and their sets of data graph vertices {v}.

Show all mappings between query graph vertices u_i and their sets of data graph vertices {v}.

Value parameters

φ

the set-valued mapping function

Attributes

Inherited from:
GraphMatcher
def test(name: String, ans: Array[Set[Int]], ignore: Boolean): Array[Set[Int]]

Test the Graph Pattern Matcher.

Test the Graph Pattern Matcher.

Value parameters

ans

the correct answer

ignore

whether to ignore the edge labels during matching

mName

the name of graph pattern matcher

Attributes

Inherited from:
GraphMatcher

Inherited fields

protected val CHECK: Int

Attributes

Inherited from:
GraphMatcher
protected val LIMIT: Double

Attributes

Inherited from:
GraphMatcher
protected val SELF_LOOPS: Boolean

Attributes

Inherited from:
GraphMatcher
protected val gRange: Range

Attributes

Inherited from:
GraphMatcher
protected val qRange: Range

Attributes

Inherited from:
GraphMatcher
Generated with