I have an idea to generate every possible connected graph without any that are isomorphic (same structure). It hinges on a canonical graph data structure that stores the automorphisms (or internal symmetries) so that new graphs that create or break those symmetries are easily recognized. This should save time because a new node need only be connected to one of the symmetries and we know all the permutations are isomorphic. For really large graphs, this could be built in Spark. Each record could hold a distinct graph or very large graphs could be distributed over their nodes. Nearly isomorphic graphs might also be mapped so obviously distinct ones don't need to be compared even after adding a node.
check-isomorphism(G, H): brute-force: check for edge-matching in every ordering of the nodes top-down:
- first check number of nodes
- then check number of nodes of each degree (max first?)
- then check number of nodes within each degree
- then check symmetries structure (to be defined)
- then check edges matching in each remaining ordering bottom-up:
- probably less efficient, but could start by looking for symmetric subgraphs find-internal-symmetries(G): brute-force: check every automorphism candidate top-down: like above bottom-up:
- find (or recall in generation) small symmetries first (e.g. swap two nodes)
- the trick will be finding a general way to express all symmetries
- for example, what about when 2 symmetries are connected or one is built on top of another? find-graphs(): brute-force: all possible graphs of size (filter connected and find isomorphisms) bottom-up: like above, generating all possible from smallest to largest