Possibility of extending `has_homomorphism_to` to support returning all homomorphisms?

[guojing0]

As continuation of PR #36504, I am working on some functionalities related to counting (graph) homomorphisms. Currently, Sage already has has_homomorphism_to function, but it only returns one homomorphism even if multiple exist.

It seems that this function is implemented with some LP solver. Would it be possible to extend it to support returning all homomorphisms?

Edit: This one will be addressed in a new branch.

[dcoudert]

A solution (certainly not the most efficient) is to add a while True loop to repeat solve + extract the solution + add a constraint to prevent finding again the same solution. You end the loop when you have no more solutions or the size of the solution increases (case core == True).

[guojing0]

I searched relevant keywords but couldn't find anything helpful. For hom's from G to H, when G is much smaller than H, other than this brute-force approach, do you know any other algorithms that could potentially be useful, if also relatively easy to implement?

My scenario: I am interested in obtaing all hom's from G' to H, where G' are subgraphs induced by the vertices of some bag in a nice tree decomp. So the size of bags is bounded by the tree-width and often small.

[dcoudert]

I don't know the existing results for the enumeration or for counting graph homomorphisms. I suggest you to do the literature review first.

[guojing0]

I don't know the existing results for the enumeration or for counting graph homomorphisms. I suggest you to do the literature review first.

Will do.

I am actually implementing counting hom's, and the algorithm requires these kinds of enumeration

[guojing0]

@dcoudert If we were to have a homomorphisms.py, should we move has_homomorphism_to function from graphs.py to the new file, since it's related to a homomorphism...

[dcoudert]

yes, but this can be done in a second time.

[guojing0]

@dcoudert Does Sage dev have some policy or guide for when we should make a new class?

For instance, in the following code, you can see that many functions take too many arguments/parameters. I have been thinking about making a class like HomCount, so that we do not necessarily have to pass so many arguments. Or do you have any other suggestions?

Merci.

https://github.com/guojing0/sage/blob/hom-count/src/sage/graphs/hom_count.py https://github.com/guojing0/sage/blob/hom-count/src/sage/graphs/hom_count_int.py

[dcoudert]

Yes, you can create a class.

As I already told you, if you create a new file, please name it homomorphisms.py. Names of files, methods and class must be clear for all users.

[guojing0]

Yes, you can create a class.

As I already told you, if you create a new file, please name it homomorphisms.py. Names of files, methods and class must be clear for all users.

Yes I do intend to, this is not the final product yet. This separation is primarily for development purpose.