My idea is to write a python program which would take as arguments two finite simple undirected graphs say G,H and returns the number hom(G,H) of graph homomorphisms from G to H.
Examples: If G=K_1 (one-vertex graph) then hom(G,H) equals the number of vertices of H. If G=K_2 (or equivalently, P_2), then hom(G,H) = 2 times the number of edges of H.
Can anyone please help me out? Thanks.
In general it's NP-hard. If the graph G has n vertices and the graph H has m vertices, a naive approach could be to check all n^m possible assignment functions between the two graphes.
This is equivalent to do m chained loops over
range(n)
.I know two ways to do it in python:
1)You can generate m lists [1...n] and use
itertools.product
to get the cartesian product between these lists.2)You can generate a string with these chained loops code and execute it in python with the
exec
built-in function.If you use the first solution, it's highly parallelizable. So you can speed up quite a bit.
An implementation of the first idea without parallelization would be something like this:
Here the graphs
G
andH
are stored as a set of tuples. The tuples represent the edges. This representation is very convenient to test the homomorphism condition and to apply assignment functions in a fast way. The parametersn
andm
are the number of vertices in each graph.For example, if you want G = S4 and H = P4 it would be something like this:
G = {(0, 1), (1, 0), (0, 2), (2, 0), (0, 3), (3, 0)}
andH = {(0, 1), (1, 0), (1, 2), (2, 1), (2, 3), (3, 2)}
. Then you call the functionsolve(G, H, 4, 4)
.I tested it with some examples of the section 2.3 of this paper and it seems to be working well.
As I said, the speed can be improved a lot with parallelization. This code is parallelizable almost everywhere. It needs some testing to see what is worth to execute in parallel.