sgi

Documentation

Overview

Package sgi implementing graph isomorphism algorithms and helpers.

Index

• Variables
• func FindIsomorphism(initialState State) []map[int]int
• func FindVF2SubgraphIsomorphism(query, target Graph, fsem SemFeasFunc) []map[int]int
• type Edge
• type Graph
• type SemFeasFunc
• type State

Examples

• FindVF2SubgraphIsomorphism

Variables

var NullNode = -1

Functions

func FindIsomorphism

func FindIsomorphism(initialState State) []map[int]int

FindIsomorphism using the given state machine.

func FindVF2SubgraphIsomorphism

func FindVF2SubgraphIsomorphism(query, target Graph, fsem SemFeasFunc) []map[int]int

FindVF2SubgraphIsomorphism finds a graph within another using the VF2 algorithm. It returns numeric mappings between the query and target graphs. Use the SemFeasFunc to further limit the algorithm to the nodes which really should be related.

Example

var db, subgraph *dbGraphMock

FindVF2SubgraphIsomorphism(subgraph, db, func(state State, fromQueryNode, fromTargetNode, toQueryNode, toTargetNode int) bool {

	return isSemanticallyFeasable(state, fromQueryNode, fromTargetNode, toQueryNode, toTargetNode)
})

Types

type Edge

type Edge interface {
	Type() string
}

type Graph

type Graph interface {
	Order() int

	// Contains link from node a to b
	Contains(a, b int) bool

	Successors(n int) []int
	Predecessors(n int) []int
	Relations(n int) []int
}

type SemFeasFunc

type SemFeasFunc func(state State, fromQueryNode, fromTargetNode, toQueryNode, toTargetNode int) bool

SemFeasFunc to describe if it semantically feasable to traverse from one node to another by looking at the describing query nodes and the actual nodes in the graph. This is called if a raw edge between the two nodes exist.

type State

type State interface {
	GetGraph() Graph
	GetSubgraph() Graph

	NextPair() (int, int)

	BackTrack()

	IsFeasablePair(queryNode, targetNode int) bool

	IsGoal() bool
	IsDead() bool

	GetMapping() map[int]int // (partial) mapping of the graphs

	NextState(queryNode, targetNode int) State

	String() string
}