Module pattern_matching 

Pattern matching on graphs.

The problem being solved here is finding subgraphs matching a given subgraph pattern in a larger base graph. The subgraph pattern is a graph where each element weight is a condition on a base graph element. A valid match is a subgraph of the base graph that is isomorphic to the pattern where each element fulfils the condition of the corresponding pattern element.

It is also possible to add hidden subgraph elements, that are removed from the matches before returning them to the caller.

While the architecture is designed to eventually support multiple matching implementations, currently only one VF based algorithm is implemented. The easiest way to use it is creating a new pattern with pattern_matching::new_pattern and passing that pattern to pattern_matching::solve_vf. Conditions in the pattern graph can be either constructed as function closures or with the matcher macro.

For examples see the unit tests for this module (located in the tests folder of the crate source).

Modules

vf_algorithms

Module that contains an implementation for subgraph algorithms.

Macros

matcher

Creates a Matcher function from a given pattern

Structs

PatternElement

Struct that holds all relevant matching information for a single node/edge.

Traits

PatternGraph

Defines a pattern graph, i.e. a specification for subgraphs that we want to find. This trait extends the Graph trait, to allow for navigation & getting subgraph info.

SubgraphAlgorithm

The SubgraphAlgorithm trait specifies any algorithm that can solve the subgraph isomorphism problem. Solving this problem lies at the core of graph pattern matching.

Functions

new_pattern

Creates an empty new graph pattern.

solve_vf

Solve a graph matching problem instance using an approach based the VF algorithms.

Type Aliases

MatchedGraph

Type definition of MatchedGraph.

Matcher

The Matcher type stands for any function that evaluates, given an element in the base graph with the type Weight, if the pattern graph accepts this element.