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:
matches = aidge_core.SinglePassGraphMatching(model).match("(Pad#?->Conv#|Deconv#->Pad#?)->ReLU#?->Add#1?->ReLU#?->MaxPool#?->ReLU#?;.->Add#1?")
for match in matches:
aidge_core.GraphView.replace(match, MyCustomIPOperator())
You can define your own node test function as well:
gm = aidge_core.SinglePassGraphMatching(model)
gm.add_node_lambda("test", lambda node: ...)
matches = gm.match("Conv->test")
- class aidge_core.SinglePassGraphMatching#
- __init__(self: aidge_core.aidge_core.SinglePassGraphMatching, graph: aidge_core.aidge_core.GraphView) None#
- add_node_lambda(self: aidge_core.aidge_core.SinglePassGraphMatching, name: str, func: Callable[[aidge_core.aidge_core.Node], bool]) None#
- match(self: aidge_core.aidge_core.SinglePassGraphMatching, query: str, disjoint: bool = False) List[aidge_core.aidge_core.MatchingResult]#
- Matches a query by direct, single-pass parse and match.
- param query:
The query string to search.
- param disjoint:
If true, only keep the longest disjoint matches.
- return:
A set of MatchingResult instances.
-
class SinglePassGraphMatching#
A simple experimental graph matching class which works by direct, single pass parse and match, without constructing any intermediate representation. Due to its single pass nature, it has some constrains on how the queries must be formulated.
Public Functions
-
SinglePassGraphMatching() = delete#
-
SinglePassGraphMatching(const SinglePassGraphMatching &other)#
-
~SinglePassGraphMatching() noexcept#
-
SinglePassGraphMatching &operator=(const SinglePassGraphMatching &other)#
-
std::set<MatchingResult> match(const std::string &query, bool disjoint = false)#
Matches a query by direct, single pass parse and match. The returned matches are non-ordered and therefore stored in a std::set.
Some rules:
The first node of the first sequence is the root node and cannot be optional WRONG: Conv?->ReLU (will throw an error) GOOD: ReLU<-Conv?
The first node of any further sequence must be an existing anchor (the anchor cannot be in the middle of the sequence) WRONG: Conv->ReLU;Pad->Conv (will throw an error) Pad->Conv;Conv->ReLU (will throw an error) GOOD: Conv#->ReLU;Conv#<-Pad Pad->Conv#;Conv#->ReLU
Any node already matched cannot be matched again (except for anchors)
By default, an edge matches the first output to the first input. EXAMPLE: ReLU->Conv is equivalent to ReLU-0-0>Conv To match the second input, use ReLU-0-1>Conv (or ReLU-1>Conv) To match the second output, use ReLU-1-0>Conv To match any input and/or any output, use *, like ReLU-1-*>Conv or ReLU-*-0>Conv or ReLU-*-*>Conv The same is true for the “<-” edge syntax.
When several nodes could match for a given node query, the first one not already in the matching result is matched, following the childs/parents ordered node list EXAMPLE: Producer in “Conv<*-Producer” will match the weights Producer first EXAMPLE: Producer in “Conv#<1-.;Conv#<*-Producer” will match the bias Producer because the weights Producer has already been matched
One always matches a sub-graph: additional connections can exist anywhere in the matched sub-graph EXAMPLE: “Add<*-.” will match the Add operator and its first input, any additional inputs will not be included in the result EXAMPLE: “(Add#<*-.)+” will match the Add operator and all of its inputs Note that the anchor is required since we intend to match several inputs of the same node!
In Aidge, a node output can be connected to multiple other nodes. In your query, you can allow it or not, with the “~” or “-” modifier. EXAMPLE: “Conv->ReLU” will match the Conv that are only connected to a ReLU node at their output #0. “Conv~>ReLU” will match all the Conv connected to a ReLU even if they are also connected to other nodes at the same output #0. When implementing a match & replace recipe, beware that you don’t break branches in the middle of your matching result if you use “~”!
The matching results can be overlapping, meaning that some nodes may be found in multiple results. Some results may be subsets of other results. EXAMPLE: assume graph Conv#1->ReLU#1->Conv#2->ReLU#2 “Conv->ReLU?->Conv?->ReLU?” will return both Conv#1->ReLU#1->Conv#2->ReLU#2 and Conv#2->ReLU#2 To avoid this behavior, set the disjoint argument to true. In this case, only Conv#1->ReLU#1->Conv#2->ReLU#2 will be kept in the example above.
Whitespaces are allowed anywhere in the query
QUERY = SEQ | NODE_OR_BLOCK (‘;’ (SEQ | NODE_OR_BLOCK))*
- Parameters:
query – The query to search.
disjoint – If true, only keep the longest disjoint (non-overlapping) matches.
- Returns:
std::set<MatchingResult> Set of matches, each stored in a MatchingResult struct.
Same as match() but with a mandatory start node.
- Parameters:
startNode – Mandatory start node for the query.
query – The query to search.
- Returns:
MatchingResult MatchingResult struct, with empty graph if query is not found, or the graph corresponding to the query.
-
std::set<MatchingResult> filterLonguestDisjoint(const std::set<MatchingResult> &matches)#
Filter to keep only the longest disjoint (non-overlapping) matches.
-
struct Context#
-
struct MatchingResult#
Public Functions
-
MatchingResult()#
-
MatchingResult(const MatchingResult &other)#
-
MatchingResult &operator=(const MatchingResult &other)#
-
~MatchingResult() noexcept#
-
MatchingResult()#
-
SinglePassGraphMatching() = delete#