import sys
#Returns a copy of the list l
def listcopy(l):
    lc=[]
    for a in l:
        lc.append(a)
    return lc

#Returns a list of all graph homomorphisms from f to g. A graph homomorphism is a list [v_1,v_2,...,v_n] where 1+v_i is the image of vertex i+1.
def grafhomgen(f,g):
    ghs=[]
    for a in range(len(g.vertices)**len(f.vertices)):
        b=a
        d=[]
        for c in range(len(f.vertices)):
            d.append(b/(len(g.vertices)**(len(f.vertices)-c-1)))
            b=b-(b/(len(g.vertices)**(len(f.vertices)-c-1)))*(len(g.vertices)**(len(f.vertices)-c-1))
        ghs.append(d)
    ghc=listcopy(ghs)
    for gh in ghs:
        for e in f.edges:
            if g.edges.count([gh[e[0]],gh[e[1]]])+g.edges.count([gh[e[1]],gh[e[0]]])==0 and ghc.count(gh)>0:
                ghc.remove(gh)
    return ghc

#Returns the column (as a list) in the matrix describing the graph homomorphism ideal from f to g coresponding to the homomorphism hom.
def grafhomc(f,g,hom):
    col=[]
    for e in f.edges:
        for h in g.edges:
            if h[0]==h[1]:
                if hom[e[0]]==h[0] and hom[e[1]]==h[1]:
                    col.append(1)
                else:
                    col.append(0)
            else:
                if hom[e[0]]==h[0] and hom[e[1]]==h[1]:
                    col.append(1)
                else:
                    col.append(0)
                if hom[e[1]]==h[0] and hom[e[0]]==h[1]:
                    col.append(1)
                else:
                    col.append(0)
    return col

#Returns an instance of the class graph describing the graph in name.mod
def readgraph(name):
    file=open(name+'.mod')
    lines=file.readlines()
    n=int(lines[0])
    es=[]
    for a in lines[2:len(lines)]:
        b=a.split()
        es.append([int(b[1])-1,int(b[2])-1])
    g=graph(n,es)
    return g

#Creates a file fntogn.mat and fntogn conntaining the matrix coresponding to a graph homomorphism ideal and a file fntogn.hom containing a list of the graph homomorphisms. 
def start(fn,gn):
    f=readgraph(fn)
    g=readgraph(gn)
    ghs=grafhomgen(f,g)
    li=[]
    for gh in ghs:
        li.append(grafhomc(f,g,gh))
    printthis=str(len(li[0]))+' '+str(len(li))+'\n'
    for a in range(len(li[0])):
        for b in range(len(li)):
            printthis=printthis+str(li[b][a])+' '
        printthis=printthis+'\n'
    file=open(fn+'to'+gn+'.mat','w')
    file.write(printthis)
    file.close()
    file=open(fn+'to'+gn,'w')
    file.write(printthis)
    file.close()    
    printthis=''
    for a in ghs:
        for b in a:
            printthis=printthis+' '+str(b+1)
        printthis=printthis+'\n'
    file=open(fn+'to'+gn+'.hom','w')
    file.write(printthis)
    file.close()

#A class describing graphs on {1,2,3,...,n} (but saved as [0,1,....,n-1]) an edge is a list [x,y] (x+1 and y+1 are vertices) and edges is a list of the edges in the graph
class graph:
    def __init__(self,n,el):
        self.vertices=range(n)
        self.edges=el      
start(sys.argv[1],sys.argv[2])