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?
Is it hard(feasible) to modify the API by adding some form of predicate
comparison of nodes?
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.