hoechp
commented
7 years ago The algorithm above is a bit sketchy. Another version of this would be to know all isomorphisms from a graph to itself. While doing the standard backtracking (finding places of application for GTR), the values for variables being found or dismissed as a solution could be replaced using any known self-isomorphism, having the same result. This way solutions can potentially be replicated and parts of the search space that failed or got skipped can be skipped as well in other configurations. Example: There's two isomorphisms from a graph to itself {A1 -> A1, B1 -> B1, A2 -> A2, B2 -> B2} and {A1 -> A2, B1 -> B2, A2 -> A1, B2 -> B1}. Having a GTR match with {GTR.A -> A1, GTR.B -> B2} means there's also the solution {GTR.A -> A2, GTR.B -> B1}. And while backtracking and testing GTR.A -> A1, there's no possible match for GTR.B - this also means for GTR.A -> A2, there will be no possible match for GTR.B either. This knowledge could be used, to skip values from being tested or maybe even to backjump in certain cases (see #33). Like with the above example, this would only help, when the graph has multiple isomorphisms to itself and preferably tons of GTR are used on the very same graph. This technique sounds a lot more feasable and potentially effective then the above one, which would be only a special case of this one as far as I understand.
An implementation of this would be a new 'PatternHandler' - also being used in a specific way by an adapted RG-builder. Isomorphism checks would need to optionally support finding all isomorphisms, too - not just one. Until now, only the IsomorphismHandlers were dynamically interchangeable. It might be wise, to work out a proper concept on how to make pattern matching and rg-building dynamically interchangable, too. For example RG-building should usually just use the standard methods of a pattern matching and isomorphism handler, but for specific combinations of isomorphism handlers and pattern matching handlers, specific specialized RG-building handlers could be registered. For example the sort-/nf-algorithm needs a special RG-building to harness the advantages of the NF - and this new pattern matching handler would need a special treatment independently from what isomorphism handler is used. If it's just a few variants of isomorphism or pattern matching handlers, needing special treatment, the RG-building could just stay static and keept track of the possible combinations - but more dynamic concept for the RG-builder would probably be wise, too. Maybe a RG-builder could have a handler implemented that specifically chooses a combination of isomorphism handler and pattern matching handler - and just work for those, or alternatively have a list of supported handlers, that can be registered inside of it. There's still a lot to work out...
Like with anything related to graphs, probably somebody already did this - but here's my idea:
In cases like seen in the example, this can drastically reduce the size of the problem - potentially boosting performance, too. If it's generally good for performance is doubtable, though. Still it would be nice to implement and just try out.
edit: This could be used for isomorphism checks, too - but it's practically guaranteed to be slower than even the sort-/nf-based isomorphism check, that kind of does the same thing, but eventually just compares the resulting serialized strings instead of utilizing knowledge on what sets of nodes may be 'isomorph' to other sets of nodes. This whole thing may be a dead end performance-wise, but I would almost like to still go and try it out - at least for pattern matching, maybe in context of RG, where the knowledge about the graph could be reused across multiple GTR pattern matchings. For many GTR and a graph with lots of 'node-isomorphisms', this really could be useful.