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

DualIso

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

The DualIso class provides an implementation for Subgraph Isomorphism that uses Dual Graph Simulation for pruning.

Value parameters

g

the data graph G(V, E, l)

q

the query graph Q(U, D, k)

Attributes

Graph
Supertypes
trait GraphMatcher
class Object
trait Matchable
class Any

Members list

Value members

Concrete methods

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

Apply the Dual Subgraph Isomorphism 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 the Dual Subgraph Isomorphism 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

Definition Classes
override def mappings(ignoreEdgeLabels: Boolean): Array[Set[Int]]

Apply the Dual Subgraph Isomorphism 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 the Dual Subgraph Isomorphism 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 // FIX - check this

Attributes

Definition Classes
def numMatches: Int

Return the count of the number of matches.

Return the count of the number of matches.

Attributes

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

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

Given the mappings φ produced by the feasibleMates method, prune mappings u -> v where 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]]

The prune0 and prune are not needed, pruning is delegated to incorporated graph simulation algorithms.

The prune0 and prune are not needed, pruning is delegated to incorporated graph simulation algorithms.

Value parameters

φ

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

Attributes

def setLimit(_limit: Int): Unit

Set an upper bound on the number matches to allow before quitting.

Set an upper bound on the number matches to allow before quitting.

Value parameters

_limit

the number of matches before quitting

Attributes

Inherited methods

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 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