Graph Matching#

Aidge introduces a simple and efficient DSL for graph matching, sometimes called “graph regex”. It is possible to write complex textual queries to find a quantified or unquantified set of nodes with specific types, attributes and/or relationships between them. This is particularly useful to implement sophisticated pattern-matching heuristics with no effort!

Here is an example of a query that you can do in Aidge:

graph_regex = aidge_core.GraphRegex()
graph_regex.add_query("(Pad#?->Conv#|Deconv#->Pad#?)->ReLU#?->Add#1?->ReLU#?->MaxPool#?->ReLU#?")
graph_regex.add_query(".->Add#1?")

for match in graph_regex.match(model):
    aidge_core.GraphView.replace(match, MyCustomIPOperator())

You can define your own node test function as well:

def myNodeTestingFunc(node):
    ...
    return predicate

graph_regex = aidge_core.GraphRegex()
graph_regex.set_node_key("test", myNodeTestingFunc)
graph_regex.add_query("Conv->test")

There are two classes to use in order to define a match using graph regex mechanics. The first one, GraphRegex, is used to define queries and to perform the match. The second one, MatchSolution, is there to assist in the exploitation of the results.

GraphRegex#

Python

class aidge_core.GraphRegex#

GraphRegex class describes a regex to test a graph.

__init__(self: aidge_core.aidge_core.GraphRegex) → None#

add_query(self: aidge_core.aidge_core.GraphRegex, query: str, f: Callable[[Aidge::MatchSolution], None] = None) → None#

Return type:: str

match(self: aidge_core.aidge_core.GraphRegex, arg0: aidge_core.aidge_core.GraphView) → Set[Aidge::MatchSolution]#

Parameters:: graphToMatch (aidge_core.GraphView) – The graph to perform the matching algorithm on.

set_key_from_graph(self: aidge_core.aidge_core.GraphRegex, arg0: aidge_core.aidge_core.GraphView) → None#

Parameters:: ref (aidge_core.GraphView) – The graph use to define type of Node.

set_node_key(*args, **kwargs)#

Overloaded function.

set_node_key(self: aidge_core.aidge_core.GraphRegex, key: str, conditionalExpressions: str) -> None

Add a node test :param key: the key of the node test to use in the query. :param conditionalExpressions: the test to do .
set_node_key(self: aidge_core.aidge_core.GraphRegex, key: str, f: Callable[[aidge_core.aidge_core.Node], bool]) -> None

Add a node test :param key: the key of the lambda test to use in the conditional expressions. :param f: bool lambda (nodePtr) .

C++

class GraphRegex

class which is the hight level interface for graph matching, used to simplify match definition

Public Functions

inline GraphRegex()

virtual ~GraphRegex() = default

void addQuery(const std::string query, RecipesFunctionType f = nullptr)

add a topology query to the match

add a topology query to the match and a function for recipe

Parameters:

query – the topology query to find
query – the topology query to find
f – the funct

void setKeyFromGraph(std::shared_ptr<GraphView> ref)

get all the types of a graph and set it as type key in the query

Parameters:: Reference – graph use to get all the node types

void setNodeKey(const std::string key, const std::string conditionalExpressions)

set a node test manually

Parameters:

key – the ref of this test used in the query
ConditionalExpressions – expression to test the node

void setNodeKey(const std::string key, std::function<bool(NodePtr)> f)

set a specific lambda that can be used in setQueryKey

Parameters:

key – ref to the lambda to use in the
f – expression to test the node ConditionalExpressions

std::set<std::shared_ptr<MatchSolution>> match(std::shared_ptr<GraphView> ref)

brief match the queries in the graph

Parameters:: ref – the graph were the querys in search
Returns:: the result

void appliedRecipes(std::shared_ptr<GraphView> ref)

Match Solution#

Python

class aidge_core.MatchSolution#

MatchSolution class contains the result of one match and the associated key, the query and the start node.

__init__(*args, **kwargs)#

at(self: aidge_core.aidge_core.MatchSolution, key: str) → Set[aidge_core.aidge_core.Node]#

Return type:: str

get_all(self: aidge_core.aidge_core.MatchSolution) → Set[aidge_core.aidge_core.Node]#

get_query(self: aidge_core.aidge_core.MatchSolution) → str#

get_start_node(self: aidge_core.aidge_core.MatchSolution) → List[aidge_core.aidge_core.Node]#

C++

class MatchSolution

contained the result of one match and the associate key , the query and the start node

Public Functions

MatchSolution() = delete

MatchSolution(std::vector<std::shared_ptr<FsmRunTimeContext>> &precedence, const std::string query, const std::vector<NodePtr> startNode)

inline const std::set<NodePtr> &at(const std::string &key)

const std::set<NodePtr> getAll()

bool areCompatible(std::shared_ptr<MatchSolution> solution)

inline const std::string &getQuery() const noexcept

inline const std::vector<NodePtr> &getStartNode() const noexcept