Computer program for counting graph homomorphisms

EDIT: I have since found that the Digraphs package sometimes counts homomorphisms incorrectly. Perhaps this problem has been fixed in more recent versions though. I use Minion for counting homomorphisms instead.

The Digraphs package for GAP has several functions for finding homomorphisms of various types between graphs, including functions that will find all such homomorphisms, or all homomorphisms up to symmetries of the target graph. Once you have them all you can just count them to find the number. I really recommend this package, it seems to perform very well. For instance its chromatic number routine seems to be much faster than the chromatic number routine in SAGE.

igraph (available for python, R and C) has a function count_subgraph_isomorphisms. Of course, this function only counts the injective graph homomorphisms.

Together with Carlo Beenakker's suggestion, one could of do the following:

• Given a graph $G$, iterate over all isomorphism classes of smaller graphs $G'$ with fewer vertices.
• If SAGE says that there is a homomorphism $G\to G'$, then compute the number of subgraph isomorphisms $G'\to H'$.
• Sum up to obtain the number of all homomorphisms $G\to H'$.

(To iterate over all isomorphism classes, iterate over all graphs and check whether there is an isomorphism to some graph that was already visited.)