# Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures:

Node:
labels: []   # lexicographic ordered
out_arrows: []  # ordered by ordering of the nodes
in_arrows: []   # ordered by ordering of the nodes


Then how should we order the nodes that have equal degree? Or am I approaching this the wrong way? My end goal is to have O(Q) to O(log N) graph lookup where N is the size of my library and Q is the size of a much smaller query graph. Not only that but once you convert the serialized data to a hashable type such as a string, then you can perform the search using a standard data structure (dictionary or map).

What is some work done in this area, i.e. have people already thought of this standard form serialization and search method?

Note that the key graphs my library will hold are relatively small (5-50) nodes, but their may be a million of them in the library. So it's not advised to perform a usual subgraph isomorphism search of the whole library say using Ullmann's algorithm, because for the most part, the graph is disconnected.

• What do you mean by "should"? You can do it any way you want. Are you asking about en.wikipedia.org/wiki/Graph_canonization?
– D.W.
Nov 16, 2021 at 22:32
• @D.W. I mean graph-to-string canonization. Labels will need to match exactly. But any two label-matched, isomorphic graphs will have the same resulting string, so therefore you can key them into a dictionary (Python) or map (C++/STL) Nov 16, 2021 at 22:46
• Check out Nauty Nov 16, 2021 at 23:01
• @PålGD that's nice, but I'm going to be implementing a solution in Python. I will post the code of SerializedObject / Arrow / Label, mostly to explain more of what I mean. I think it's an elegant solution to my library search problems. Here is my project repository: github.com/enjoysmath/abstract-spacecraft What's neat about this solution is that dictionary lookup in python is incredibly fast relative to for-loops in Python, so this solution shouldn't be much slower than an equivalent C++ version. Now my project can be entirely Python-based without having to put in a C++ backend Nov 16, 2021 at 23:12