## Grove calculator¶

In [1]:
def Grove(G,parti):
grove=0
v_partitions=SetPartitions(Set(G.vertices())).list()
for v_parti in v_partitions:
count=0
forest_poly=1
if len(v_parti)==len(parti):
v_parti_list=list(v_parti)[:]
for i in parti:
subcount=0
for j in v_parti_list:
if len(j)>0:
j=set(list(j))
else:
j={}
if i in Subsets(j).list():
#print(i,'in',j,type(j),v_parti_list)
subcount+=1
if j in v_parti_list:
v_parti_list.remove(j)
if subcount>0:
count+=1
if count==len(parti):
#print(parti,'and',v_parti)
for part in v_parti:
if len(part)>1:
tree_poly=0
subG=G.subgraph(list(part))
trees=subG.spanning_trees()
for tree in trees:
sub_tree_poly=1
for eg in tree.edges():
sub_tree_poly*=G.edge_label(eg[0],eg[1])
tree_poly+=sub_tree_poly
else:
tree_poly=1
forest_poly*=tree_poly
else:
forest_poly=0
else:
forest_poly=0
grove+=forest_poly
return grove


In [2]:
def make_graph():
E=[(4,1,'a'),(4,2,'b'),(4,3,'c'),(1,3,'e'),(1,2,'f'),(2,3,'g')]
return E

def Graff(E):
G=[]
for i in E:
G+=[(i[0],i[1],var(i[2]))]
graph=Graph(G)
return graph

myGraph=Graff(make_graph())

myGraph.graphplot(edge_labels=True,layout='planar').show()


## Some examples¶

In [3]:
Grove(myGraph,[{1,2,3},{4}])

Out[3]:
e*f + e*g + f*g
In [4]:
Grove(myGraph,[{1},{2},{3}])

Out[4]:
a + b + c
In [5]:
Grove(myGraph,[{1,2},{3,4}])

Out[5]:
c*f
In [6]:
Grove(myGraph,[{1},{2}])

Out[6]:
a*c + b*c + a*e + b*e + c*e + a*g + b*g + c*g
In [7]:
Grove(myGraph,[{1},{2,3}])

Out[7]:
b*c + a*g + b*g + c*g
In [8]:
Grove(myGraph,[{1},{3,4}])

Out[8]:
b*c + c*f + b*g + c*g
In [9]:
Grove(myGraph,[{1}])

Out[9]:
a*b*c + a*b*e + b*c*e + a*c*f + b*c*f + a*e*f + b*e*f + c*e*f + a*b*g + a*c*g + a*e*g + b*e*g + c*e*g + a*f*g + b*f*g + c*f*g