Am 03.08.22 um 12:50 schrieb Sergey Mironov:
Hi. I'm interested in finding subgraph isomorphisms on graphs representing tensor networks. Nodes of such graphs contain expressions (but here one could think of arithmetic expressions over +-/* and variables). Let's say I want to find an isomorphism between my graph and a pattern graph, which contains more generic expressions. Comparing expressions directly doesn't make much sense because of variables, so some form of unification[1] should be used instead.
What strategy could I use to fit the existing API of subgraph_isomorphism which currently only allows me to calculate some fixed labels for nodes?
The simplest strategy would be for you to define a hash function that maps your arithmetic expressions to integers. You need only to make sure that no collisions exist, but that should be very easy to enforce. The simplest way to do this is to list all the different expressions in all nodes in arbitrary order, and use the order index as a hash value.
Is it hard(feasible) to modify the API by adding some form of predicate comparison of nodes?
It is feasible, but such an API would be extremely slow, since this predicate would need to be computed in the inner loop of the algorithm. The hash approach outlined above is far faster, and easy to implement in general. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>