SCOTT goes GO

[drew-512]

Hi SCOTT friends,

I'm leading development on an exciting physics project and it seems like SCOTT has a lot going for it and we think it makes sense to adapt for our Go project. I wanted to get y'alls blessing before I started on a port to Go and of course offer full credits. I expect we'll make it MIT as well and how nice it would be to to add to your stable.

It would be helpful if I could direct any questions as I go into this thread in the coming weeks as I take this on, does that work?

Separately, if there are any design or arch tweaks that you'd like to change or insert, this would be the time to chit chat about it. I see that parallelization will be able to riiiiip under Go and I look forward to blowing y'all away.

Best,
Drew O'Meara

[theplatypus]

Hey, Drew

I’m Nicolas, main author of Scott, speaking both for me and for other authors with whom I’m still in touch, glad to read you.
It is always a pleasure to know that Scott could be of interest in a domain other than ours, and to be honest I’d be very curious about use cases you imagined for it in physics ! Obviously you have all our blessings to fork it and adapt it to your needs.

I don’t know Go further than its solid reputation for being efficient and easy to parallelize, so while it seems like a very pertinent choice, I unfortunately cannot give you very specific implementation recommandations.
Nonetheless, what I can still tell you :

• the current Python implementation only uses Python standard library, so it should be easy to port it in any langage, as basis data structures (V, E) are mainly hashmaps ; but maybe there is a graphs-related library in Go (like networks for Python) upon which you would like to build your implementation ?

• as multi threading in Python is not so native and is subject to some limitations, efficient multi threading would be of great help here, as there are parallelisation axis on both :

  • the computing of trees rooted on a candidate node
  • performing rewritings in a given level, given rooted tree

• store in cache some intermediate traces and rewritings results is critical, so each node should be associated with some results during the process

• writing the whole process as a recursive loop led me to some limitations in Python for processing large graphs, hitting recursions limits - maybe Go deals better with recursion, but for Python it was probably a mistake

Anyway, I can re-dive into the code if necessary to give you more specific help :)
Also, do you have an idea where to start ?

Feel free to reach me by email (I've just added in on GitHub) if you want to, I'm available for a call as well, otherwise I'll look on this thread ;)

Best, hope to read some news soon !

Nicolas

[drew-512]

Hi and Bonjour Nicolas et al, happy to hear from you.

I was in the process of going through Scott in detail and your paper in preparation for a port to Go when I had a novel insight for a canonicalization algorithm. I'm currently about halfway through a dynamic programming solution that runs in pseudo-polynomial time: O(EVG) where E is edges, V is vertices and G is the number of internal/interior subgraph symmetries. So for a highly asymmetric graph, G is in the single digits, while for, say E8, there are many more interior internal symmetries. Of course, this rhymes with the behavior of Scott as this is a natural reflection of a graph's structure. The algorithm is also a "demand-pull" (i.e. "lazy" evaluation) so it can evaluate the DAG that emerges in ways that (deterministically) avoid the harder subproblems (versus having to evaluate all sub-problems before the canonicalization can be produced).

I am happy to discuss here or email me at [email protected] and we can go from there. In another week I should hopefully have it up and running, and I wanted to offer to work together on it if you are interested. So I wanted to offer to share as our focus is on the physics project that will be consuming this canonicalization algorithm (that I had planned to use Scott for). I think there is very exciting potential and coupled with a Go implementation, I think I could pull off canonicalization benchmarks 1-2 orders of magnitude better than what's out there. Of course, like Scott and unlike many others, the algorithm supports edge color as well as vertex color (both are int64 so the sky is the limit). Go is easy to learn, is syntactically "small" like C and Python, the syntactical power of C++ and Python (and then some), type safety, and the performance of C/C++.

More about me: https://www.linkedin.com/in/drew-o-meara-6930b21/

Best Regards,
Drew