2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "should"? You can do it any way you want. Are you asking about en.wikipedia.org/wiki/Graph_canonization? $\endgroup$
    – D.W. ♦
    Commented Nov 16, 2021 at 22:32
  • $\begingroup$ @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) $\endgroup$
    – Daniel Donnelly
    Commented Nov 16, 2021 at 22:46
  • 2
    $\begingroup$ Check out Nauty $\endgroup$
    – John Kemeny
    Commented Nov 16, 2021 at 23:01
  • $\begingroup$ @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 $\endgroup$
    – Daniel Donnelly
    Commented Nov 16, 2021 at 23:12

1 Answer 1

Reset to default
2
$\begingroup$

Graph canonization is well-studied, and there are sophisticated algorithms for it; see https://en.wikipedia.org/wiki/Graph_canonization. The standard answer is to use existing, well-tuned software, such as Nauty, rather than trying to invent your own.

How to implement in Python is out of scope of this site (but I would investigate API bindings or running it on the command line).

See also Graph isomorphism problem for labeled graphs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.