3
$\begingroup$

I have a c++ program that generates large numbers of small graphs (millions). I would like to remove graphs that are isomorphic to each other so I am thinking about trying to use the callable interface to mathematica to do this. I see there is something called WSTP with essentially string interfaces. I see mentions here of MathLink but that isn't in the list of topics when I look in help so maybe that's an older interface. I am wondering if it's realistic to call mathematica a large number of times via the WSTP interface to essentially just check if two small graphs are isomorphic. My graphs are acyclic multi-digraphs with a single source and sink. My notion of isomorphic is a path-edge incidence matrix that is a row and column permutation of another path-edge incidence matrix. So I will generate a kind of line graph that has a vertex for an edge and a vertex for a path and a directed edge if the edge is in the path and test these for isomorphism. Maybe ~100 paths and ~10 edges. A naive isomorphism test like in boost or my own code is too slow.

$\endgroup$
1
  • 1
    $\begingroup$ WSTP and MathLink are the exact same thing. $\endgroup$
    – Szabolcs
    Commented Feb 7, 2020 at 19:16

1 Answer 1

11
$\begingroup$

You should not test pairs of graphs for isomorphism, as that is quadratic in the number of graphs, and it's hopeless. You should compute a canonical labelling of each graph with a suitable library (bliss, nauty, traces, etc.—not Boost which only has VF2 for testing pairs of graphs), then use a set data structure to remove duplicates.

I do not recommend trying to call Mathematica to do this. It will be very slow. I know this as I created IGraph/M and suffered plenty of frustration due to Mathematica's lack of performant facilities to convert a Graph to/from some format that is friendly to C++. They didn't add this even after years of requests.

Just use a C or a C++ library from your C++ program. It'll be faster than what Mathematica has anyway. I believe Mathematica may be using an old version of nauty.

$\endgroup$
5
  • $\begingroup$ Thanks for this. I am familiar with the concept of a canonical labeling. Since I am currently running on Windows I thought mathematica might be the path of least resistance but that doesn't seem likely now. I'll shift to trying to get my program running in the linux subsystem. $\endgroup$ Commented Feb 7, 2020 at 19:58
  • $\begingroup$ @NeillClift why do you think that running in Linus will improve the difficulty of what you are trying to do now? $\endgroup$ Commented Feb 13, 2020 at 4:01
  • $\begingroup$ I am not exactly sure what your asking. My thinking is that since mathematica doesn't seem to offer functionality I can use for this problem I should probably try and get nauty working. As far as I can see this only runs in unix. $\endgroup$ Commented Feb 14, 2020 at 5:13
  • $\begingroup$ @NeillClift It's not Unix-specific. If you are going to use an automorphism finder from C++ code, I would recommend Bliss over Nauty: it has an easier to use API. $\endgroup$
    – Szabolcs
    Commented Feb 14, 2020 at 7:55
  • $\begingroup$ Szabolcs, thanks for that suggestion. I got bliss working quite quickly and doing the isomorphism test on my graphs. Looks fast enough for my experiments. $\endgroup$ Commented Feb 14, 2020 at 23:23

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.