Essential isomorphism functions are not documented

[szhorvat]

When looking for isomorphism and subisomorphism functions that return actual mappings, I can only find isomorphisms() and subgraph_isomorphisms() in the documentation. These functions have a huge limitation: they can only list all isomorphisms, not merely some of them, or ideally just one of them. This makes them unusable for anything but tiny graphs. Furthermore, isomorphisms() only supports VF2, not the much more efficient Bliss.

Finally, I found that there are much more flexible functions, but they are not documented:

• graph.isomorphic
• graph.isomorphic.vf
• graph.isomorphic.bliss
• graph.subisomorphic.lad
• graph.subisomorphic.vf

It is only these that are able to find a single mapping (instead of all mappings).

Are these deprecated and replaced by underscore versions? Are these considered low-level or internal functions?

Whatever the reason, we need functions which have the same capabilities, ideally a modern naming, and most importantly, proper documentation to make them discoverable. Am I missing some existing functions with modern naming?

Ref: https://stackoverflow.com/questions/74646363/how-can-i-plot-a-hamiltonian-graph-in-r#comment131760636_74647534

[ntamas]

• graph.isomorphic() is an alias to isomorphic() as far as I know, with an implied auto method.
• isomorphic() calls graph.isomorphic.vf2() if method == "vf2" so it does not have to be exposed or documented separately.
• isomorphic() calls graph.isomorphic.bliss() if method == "bliss" so it does not have to be exposed or documented separately either.

However, you have a point with graph.subisomorphic.lad() and graph.subisomorphic.vf2(). I think the intention was that these functions should be replaced with a higher-level subgraph_isomorphic() function that has a method=... argument, but while doing so the library lost the ability to look for only a single mapping.

I was wondering whether we should add a map argument to subgraph_isomorphic() just like the original graph.subisomorphic.lad() function has it. The default would be map = FALSE to remain backward-compatible, but one could add map = TRUE, in which case one would either return the entire result object from graph.subisomorphic.lad() untouched, or only the $map component (I don't know which one would be better).

[szhorvat]

isomorphic() returns a boolean. graph.isomorphic.vf2() and graph.isomorphic.bliss() return a lot more information than that: not just a boolean result but also a mapping. isomorphic() only extracts the boolean part of that information.

[maelle]

I didn't know one could skip the docs of exported functions without R CMD check complaining, so I looked a bit, it's "thanks" to

https://github.com/igraph/rigraph/blob/6bff8652a9af6fcbd9748805b5d2809bc8785fb4/R/topology.R#L271

[maelle]

If functions like graph.isomorphic.vf2() are really meant to be user-facing should I

• create functions "correctly" named like graph_isomorphic_vf2()
• add docs, examples, test
• soft-deprecate the dot-named versions?

[maelle]

@szhorvat any opinion on the question above?

[szhorvat]

@maelle For me, the easiest would be to have a Zoom meeting sometime and talk them through. I would need to take some time to think about what is the best API here, and doing it together makes it much easier.

It seems that currently the new-style functions (which use a unified interface) lack important features that the old functions have. Could these features be added to the new-style interface? Or do we need to update the old function? That's the question.

[maelle]

But asynchronously (faster I think) wouldn't it make sense for me to do what I outline in https://github.com/igraph/rigraph/issues/588#issuecomment-2383208897, for functions whose name start with graph.isomorphic.? I was thinking about them again because of #1623