sgi

package

v0.0.0-...-af33e7b Latest Latest Go to latest Published: May 28, 2023 License: BSD-3-Clause, MIT Imports: 3 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/BuJo/goneo

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

Constants ¶

This section is empty.

Variables ¶

View Source

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

Output:

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
}

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL