prob

3310 days ago by butler

def find_prob(G,coloring): """ INPUTS: G - a graph on n vertices coloring - a list of size n with two values 0 (prob. p) and 1 (prob. 1-p) OUTPUT: probability (as a function of p) of having final coloring for G """ p,q = var('p,q') if (not G.is_connected()) or (G.order() < 3): print "Need a connected graph on at least three vertices!" return edges_list = [] for e in G.edges(): if coloring[e[0]] == coloring[e[1]]: edges_list.append([e[0],e[1]]) if len(edges_list) == 0: return 0 output = [0] for e in edges_list: to_be_sorted=deepcopy(edges_list) to_be_sorted.remove(e) for v in G.vertices(): if not v in e: to_be_sorted.append(v) to_delete=[] for ee in edges_list: if set(ee).intersection(set(e)) and not (e == ee): to_delete.append(ee) for ee in to_delete: to_be_sorted.remove(ee) find_prob_recurse([e],to_be_sorted,output,G,coloring) return output[0] def find_prob_recurse(reversed,to_be_sorted,output,G,coloring): p,q = var('p,q') if len(to_be_sorted) == 0: output[0] += compute_prob_insertion(reversed,G,coloring) else: for x in to_be_sorted: if type(x) == list: new_reversed = deepcopy(reversed) new_reversed.append(x) new_to_be_sorted = deepcopy(to_be_sorted) new_to_be_sorted.remove(x) for w in x: new_to_be_sorted.remove(w) for w in to_be_sorted: if (type(w) == list) and ((x[0] in w) or (x[1] in w)) and (not x == w): new_to_be_sorted.remove(w) find_prob_recurse(new_reversed,new_to_be_sorted,output,G,coloring) else: if can_add(x,reversed,G): new_reversed = deepcopy(reversed) new_reversed.append(x) new_to_be_sorted = deepcopy(to_be_sorted) new_to_be_sorted.remove(x) for w in to_be_sorted: if (type(w) == list) and (x in w): new_to_be_sorted.remove(w) find_prob_recurse(new_reversed,new_to_be_sorted,output,G,coloring) def can_add(x,reversed,G): pool=set([]) for t in reversed: if not type(t) == list: pool.add(t) else: pool.add(t[0]) pool.add(t[1]) return len(pool.intersection(set(G.neighbors(x)))) > 0 def compute_prob_insertion(reversed,G,coloring): p,q = var('p,q') delta = 1 for t in reversed: if not type(t) == list: if coloring[t] == 0: delta = delta * p else: delta = delta * q else: if coloring[t[0]] == 0: delta = delta * p else: delta = delta * q pool=[] popper=deepcopy(reversed) while len(popper) > 1: t=popper.pop() if not type(t) == list: edges_with_t = 0 for e in G.edges(): if (e[0] not in pool) and (e[1] not in pool) and (t in e): edges_with_t += 1 if type(t) == list: delta = delta / G.size() else: delta = delta * edges_with_t / G.size() if len(popper)>1: if not type(t) == list: pool.append(t) else: pool.append(t[0]) pool.append(t[1]) valid_edges=0 for e in G.edges(): if (e[0] not in pool) and (e[1] not in pool): valid_edges += 1 delta = delta*G.size()/(G.size() - valid_edges) delta = delta/(G.size() - 1) return delta def tree_probabilities(G, stats=True): f = find_prob(G,[0]*G.order()) Q = f.coefficients() trees = {} for q in Q: trees[G.order()-q[1]] = q[0] if stats: G.show() print "\ttrees\tProbability" ind = trees.keys() ind.sort() for i in range(len(ind)): print "\t"+str(ind[i])+"\t"+str(trees[ind[i]]) return trees 
       
html('<!--notruncate-->') for n in [3,4,5,6]: for G in graphs.nauty_geng(str(n)+" -c"): q = tree_probabilities(G) print "===================================" 
       
	trees	Probability
	1	1
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	2/3
	2	1/3
===================================
	trees	Probability
	1	5/6
	2	1/6
===================================
	trees	Probability
	1	2/3
	2	1/3
===================================
	trees	Probability
	1	4/5
	2	1/5
===================================
	trees	Probability
	1	4/5
	2	1/5
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	7/12
	2	5/12
===================================
	trees	Probability
	1	23/30
	2	7/30
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	19/30
	2	11/30
===================================
	trees	Probability
	1	41/60
	2	19/60
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	23/35
	2	12/35
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	5/12
	2	7/12
===================================
	trees	Probability
	1	8/15
	2	7/15
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	17/30
	2	13/30
===================================
	trees	Probability
	1	17/30
	2	13/30
===================================
	trees	Probability
	1	13/20
	2	7/20
===================================
	trees	Probability
	1	62/105
	2	43/105
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	8/15
	2	7/15
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	11/20
	2	9/20
===================================
	trees	Probability
	1	11/15
	2	4/15
===================================
	trees	Probability
	1	1/4
	2	3/4
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	13/30
	2	17/30
===================================
	trees	Probability
	1	11/20
	2	9/20
===================================
	trees	Probability
	1	131/210
	2	79/210
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	2/5
	2	3/5
===================================
	trees	Probability
	1	39/70
	2	31/70
===================================
	trees	Probability
	1	23/40
	2	17/40
===================================
	trees	Probability
	1	2/5
	2	3/5
===================================
	trees	Probability
	1	5/9
	2	4/9
===================================
	trees	Probability
	1	3/10
	2	17/30
	3	2/15
===================================
	trees	Probability
	1	7/18
	2	97/180
	3	13/180
===================================
	trees	Probability
	1	32/63
	2	142/315
	3	13/315
===================================
	trees	Probability
	1	11/30
	2	17/30
	3	1/15
===================================
	trees	Probability
	1	7/30
	2	7/10
	3	1/15
===================================
	trees	Probability
	1	7/15
	2	7/15
	3	1/15
===================================
	trees	Probability
	1	491/1260
	2	719/1260
	3	5/126
===================================
	trees	Probability
	1	149/315
	2	307/630
	3	5/126
===================================
	trees	Probability
	1	85/168
	2	197/420
	3	1/40
===================================
	trees	Probability
	1	2/15
	2	11/15
	3	2/15
===================================
	trees	Probability
	1	41/180
	2	113/180
	3	13/90
===================================
	trees	Probability
	1	7/45
	2	139/180
	3	13/180
===================================
	trees	Probability
	1	13/45
	2	23/36
	3	13/180
===================================
	trees	Probability
	1	3/10
	2	7/10
===================================
	trees	Probability
	1	89/315
	2	40/63
	3	26/315
===================================
	trees	Probability
	1	34/105
	2	41/70
	3	19/210
===================================
	trees	Probability
	1	451/1260
	2	757/1260
	3	13/315
===================================
	trees	Probability
	1	23/56
	2	15/28
	3	3/56
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	31/126
	2	85/126
	3	5/63
===================================
	trees	Probability
	1	1/3
	2	37/60
	3	1/20
===================================
	trees	Probability
	1	31/70
	2	53/105
	3	11/210
===================================
	trees	Probability
	1	377/840
	2	221/420
	3	1/40
===================================
	trees	Probability
	1	79/210
	2	4/7
	3	11/210
===================================
	trees	Probability
	1	85/189
	2	3901/7560
	3	37/1080
===================================
	trees	Probability
	1	47/120
	2	7/12
	3	1/40
===================================
	trees	Probability
	1	433/840
	2	193/420
	3	1/40
===================================
	trees	Probability
	1	85/168
	2	401/840
	3	1/60
===================================
	trees	Probability
	1	11/30
	2	3/5
	3	1/30
===================================
	trees	Probability
	1	2242/4725
	2	2371/4725
	3	16/675
===================================
	trees	Probability
	1	109/315
	2	181/315
	3	5/63
===================================
	trees	Probability
	1	2/5
	2	11/20
	3	1/20
===================================
	trees	Probability
	1	97/210
	2	53/105
	3	1/30
===================================
	trees	Probability
	1	2/15
	2	11/15
	3	2/15
===================================
	trees	Probability
	1	16/63
	2	197/315
	3	38/315
===================================
	trees	Probability
	1	11/35
	2	127/210
	3	17/210
===================================
	trees	Probability
	1	67/315
	2	223/315
	3	5/63
===================================
	trees	Probability
	1	118/315
	2	184/315
	3	13/315
===================================
	trees	Probability
	1	193/630
	2	206/315
	3	5/126
===================================
	trees	Probability
	1	523/1680
	2	171/280
	3	131/1680
===================================
	trees	Probability
	1	207/560
	2	97/168
	3	89/1680
===================================
	trees	Probability
	1	19/60
	2	19/30
	3	1/20
===================================
	trees	Probability
	1	295/756
	2	527/945
	3	197/3780
===================================
	trees	Probability
	1	3/10
	2	3/5
	3	1/10
===================================
	trees	Probability
	1	67/210
	2	22/35
	3	11/210
===================================
	trees	Probability
	1	343/1080
	2	83/135
	3	73/1080
===================================
	trees	Probability
	1	1357/3780
	2	541/945
	3	37/540
===================================
	trees	Probability
	1	2129/5400
	2	21089/37800
	3	226/4725
===================================
	trees	Probability
	1	617/1512
	2	527/945
	3	37/1080
===================================
	trees	Probability
	1	689/1512
	2	482/945
	3	37/1080
===================================
	trees	Probability
	1	9043/18900
	2	9409/18900
	3	16/675
===================================
	trees	Probability
	1	2707/7560
	2	1117/1890
	3	11/216
===================================
	trees	Probability
	1	17/42
	2	59/105
	3	1/30
===================================
	trees	Probability
	1	8191/18900
	2	10033/18900
	3	169/4725
===================================
	trees	Probability
	1	1207/2772
	2	1469/2772
	3	8/231
===================================
	trees	Probability
	1	3/10
	2	3/5
	3	1/10
===================================
	trees	Probability
	1	517/1575
	2	946/1575
	3	16/225
===================================
	trees	Probability
	1	1709/4725
	2	2792/4725
	3	32/675
===================================
	trees	Probability
	1	115/308
	2	177/308
	3	4/77
===================================
	trees	Probability
	1	97/231
	2	125/231
	3	3/77
===================================
	trees	Probability
	1	101/420
	2	281/420
	3	19/210
===================================
	trees	Probability
	1	11/63
	2	247/315
	3	13/315
===================================
	trees	Probability
	1	241/840
	2	277/420
	3	3/56
===================================
	trees	Probability
	1	41/140
	2	43/70
	3	13/140
===================================
	trees	Probability
	1	13/36
	2	367/630
	3	71/1260
===================================
	trees	Probability
	1	1/4
	2	7/10
	3	1/20
===================================
	trees	Probability
	1	65/216
	2	35/54
	3	11/216
===================================
	trees	Probability
	1	41/108
	2	1067/1890
	3	211/3780
===================================
	trees	Probability
	1	37/108
	2	572/945
	3	197/3780
===================================
	trees	Probability
	1	89/270
	2	113/189
	3	137/1890
===================================
	trees	Probability
	1	256/675
	2	21593/37800
	3	1871/37800
===================================
	trees	Probability
	1	212/675
	2	431/675
	3	32/675
===================================
	trees	Probability
	1	752/1925
	2	9784/17325
	3	773/17325
===================================
	trees	Probability
	1	11/40
	2	13/20
	3	3/40
===================================
	trees	Probability
	1	41/168
	2	19/28
	3	13/168
===================================
	trees	Probability
	1	163/540
	2	17/27
	3	37/540
===================================
	trees	Probability
	1	109/315
	2	187/315
	3	19/315
===================================
	trees	Probability
	1	4/15
	2	2/3
	3	1/15
===================================
	trees	Probability
	1	1496/4725
	2	2948/4725
	3	281/4725
===================================
	trees	Probability
	1	238/675
	2	2833/4725
	3	226/4725
===================================
	trees	Probability
	1	4211/11550
	2	641/1100
	3	1217/23100
===================================
	trees	Probability
	1	3221/8316
	2	1178/2079
	3	383/8316
===================================
	trees	Probability
	1	3299/9450
	2	11149/18900
	3	1153/18900
===================================
	trees	Probability
	1	88/225
	2	883/1575
	3	76/1575
===================================
	trees	Probability
	1	6123/15400
	2	8599/15400
	3	339/7700
===================================
	trees	Probability
	1	271/630
	2	671/1260
	3	47/1260
===================================
	trees	Probability
	1	1807/3850
	2	1941/3850
	3	51/1925
===================================
	trees	Probability
	1	2309/5544
	2	377/693
	3	73/1848
===================================
	trees	Probability
	1	320/819
	2	1847/3276
	3	149/3276
===================================
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
===================================
	trees	Probability
	1	101/275
	2	1116/1925
	3	102/1925
===================================
	trees	Probability
	1	1948/5775
	2	1158/1925
	3	353/5775
===================================
	trees	Probability
	1	223/616
	2	541/924
	3	97/1848
===================================
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
===================================
	trees	Probability
	1	904/2457
	2	1429/2457
	3	124/2457
===================================
	trees	Probability
	1	8/21
	2	4/7
	3	1/21
===================================
	trees	Probability
	1	8/21
	2	4/7
	3	1/21
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	2/3
	2	1/3
===================================
	trees	Probability
	1	5/6
	2	1/6
===================================
	trees	Probability
	1	2/3
	2	1/3
===================================
	trees	Probability
	1	4/5
	2	1/5
===================================
	trees	Probability
	1	4/5
	2	1/5
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	7/12
	2	5/12
===================================
	trees	Probability
	1	23/30
	2	7/30
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	19/30
	2	11/30
===================================
	trees	Probability
	1	41/60
	2	19/60
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	23/35
	2	12/35
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	5/12
	2	7/12
===================================
	trees	Probability
	1	8/15
	2	7/15
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	17/30
	2	13/30
===================================
	trees	Probability
	1	17/30
	2	13/30
===================================
	trees	Probability
	1	13/20
	2	7/20
===================================
	trees	Probability
	1	62/105
	2	43/105
===================================
	trees	Probability
	1	1/2
	2	1/2
===================================
	trees	Probability
	1	8/15
	2	7/15
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	1
===================================
	trees	Probability
	1	11/20
	2	9/20
===================================
	trees	Probability
	1	11/15
	2	4/15
===================================
	trees	Probability
	1	1/4
	2	3/4
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	13/30
	2	17/30
===================================
	trees	Probability
	1	11/20
	2	9/20
===================================
	trees	Probability
	1	131/210
	2	79/210
===================================
	trees	Probability
	1	1/3
	2	2/3
===================================
	trees	Probability
	1	2/5
	2	3/5
===================================
	trees	Probability
	1	39/70
	2	31/70
===================================
	trees	Probability
	1	23/40
	2	17/40
===================================
	trees	Probability
	1	2/5
	2	3/5
===================================
	trees	Probability
	1	5/9
	2	4/9
===================================
	trees	Probability
	1	3/10
	2	17/30
	3	2/15
===================================
	trees	Probability
	1	7/18
	2	97/180
	3	13/180
===================================
	trees	Probability
	1	32/63
	2	142/315
	3	13/315
===================================
	trees	Probability
	1	11/30
	2	17/30
	3	1/15
===================================
	trees	Probability
	1	7/30
	2	7/10
	3	1/15
===================================
	trees	Probability
	1	7/15
	2	7/15
	3	1/15
===================================
	trees	Probability
	1	491/1260
	2	719/1260
	3	5/126
===================================
	trees	Probability
	1	149/315
	2	307/630
	3	5/126
===================================
	trees	Probability
	1	85/168
	2	197/420
	3	1/40
===================================
	trees	Probability
	1	2/15
	2	11/15
	3	2/15
===================================
	trees	Probability
	1	41/180
	2	113/180
	3	13/90
===================================
	trees	Probability
	1	7/45
	2	139/180
	3	13/180
===================================
	trees	Probability
	1	13/45
	2	23/36
	3	13/180
===================================
	trees	Probability
	1	3/10
	2	7/10
===================================
	trees	Probability
	1	89/315
	2	40/63
	3	26/315
===================================
	trees	Probability
	1	34/105
	2	41/70
	3	19/210
===================================
	trees	Probability
	1	451/1260
	2	757/1260
	3	13/315
===================================
	trees	Probability
	1	23/56
	2	15/28
	3	3/56
===================================
	trees	Probability
	1	7/15
	2	8/15
===================================
	trees	Probability
	1	4/7
	2	3/7
===================================
	trees	Probability
	1	31/126
	2	85/126
	3	5/63
===================================
	trees	Probability
	1	1/3
	2	37/60
	3	1/20
===================================
	trees	Probability
	1	31/70
	2	53/105
	3	11/210
===================================
	trees	Probability
	1	377/840
	2	221/420
	3	1/40
===================================
	trees	Probability
	1	79/210
	2	4/7
	3	11/210
===================================
	trees	Probability
	1	85/189
	2	3901/7560
	3	37/1080
===================================
	trees	Probability
	1	47/120
	2	7/12
	3	1/40
===================================
	trees	Probability
	1	433/840
	2	193/420
	3	1/40
===================================
	trees	Probability
	1	85/168
	2	401/840
	3	1/60
===================================
	trees	Probability
	1	11/30
	2	3/5
	3	1/30
===================================
	trees	Probability
	1	2242/4725
	2	2371/4725
	3	16/675
===================================
	trees	Probability
	1	109/315
	2	181/315
	3	5/63
===================================
	trees	Probability
	1	2/5
	2	11/20
	3	1/20
===================================
	trees	Probability
	1	97/210
	2	53/105
	3	1/30
===================================
	trees	Probability
	1	2/15
	2	11/15
	3	2/15
===================================
	trees	Probability
	1	16/63
	2	197/315
	3	38/315
===================================
	trees	Probability
	1	11/35
	2	127/210
	3	17/210
===================================
	trees	Probability
	1	67/315
	2	223/315
	3	5/63
===================================
	trees	Probability
	1	118/315
	2	184/315
	3	13/315
===================================
	trees	Probability
	1	193/630
	2	206/315
	3	5/126
===================================
	trees	Probability
	1	523/1680
	2	171/280
	3	131/1680
===================================
	trees	Probability
	1	207/560
	2	97/168
	3	89/1680
===================================
	trees	Probability
	1	19/60
	2	19/30
	3	1/20
===================================
	trees	Probability
	1	295/756
	2	527/945
	3	197/3780
===================================
	trees	Probability
	1	3/10
	2	3/5
	3	1/10
===================================
	trees	Probability
	1	67/210
	2	22/35
	3	11/210
===================================
	trees	Probability
	1	343/1080
	2	83/135
	3	73/1080
===================================
	trees	Probability
	1	1357/3780
	2	541/945
	3	37/540
===================================
	trees	Probability
	1	2129/5400
	2	21089/37800
	3	226/4725
===================================
	trees	Probability
	1	617/1512
	2	527/945
	3	37/1080
===================================
	trees	Probability
	1	689/1512
	2	482/945
	3	37/1080
===================================
	trees	Probability
	1	9043/18900
	2	9409/18900
	3	16/675
===================================
	trees	Probability
	1	2707/7560
	2	1117/1890
	3	11/216
===================================
	trees	Probability
	1	17/42
	2	59/105
	3	1/30
===================================
	trees	Probability
	1	8191/18900
	2	10033/18900
	3	169/4725
===================================
	trees	Probability
	1	1207/2772
	2	1469/2772
	3	8/231
===================================
	trees	Probability
	1	3/10
	2	3/5
	3	1/10
===================================
	trees	Probability
	1	517/1575
	2	946/1575
	3	16/225
===================================
	trees	Probability
	1	1709/4725
	2	2792/4725
	3	32/675
===================================
	trees	Probability
	1	115/308
	2	177/308
	3	4/77
===================================
	trees	Probability
	1	97/231
	2	125/231
	3	3/77
===================================
	trees	Probability
	1	101/420
	2	281/420
	3	19/210
===================================
	trees	Probability
	1	11/63
	2	247/315
	3	13/315
===================================
	trees	Probability
	1	241/840
	2	277/420
	3	3/56
===================================
	trees	Probability
	1	41/140
	2	43/70
	3	13/140
===================================
	trees	Probability
	1	13/36
	2	367/630
	3	71/1260
===================================
	trees	Probability
	1	1/4
	2	7/10
	3	1/20
===================================
	trees	Probability
	1	65/216
	2	35/54
	3	11/216
===================================
	trees	Probability
	1	41/108
	2	1067/1890
	3	211/3780
===================================
	trees	Probability
	1	37/108
	2	572/945
	3	197/3780
===================================
	trees	Probability
	1	89/270
	2	113/189
	3	137/1890
===================================
	trees	Probability
	1	256/675
	2	21593/37800
	3	1871/37800
===================================
	trees	Probability
	1	212/675
	2	431/675
	3	32/675
===================================
	trees	Probability
	1	752/1925
	2	9784/17325
	3	773/17325
===================================
	trees	Probability
	1	11/40
	2	13/20
	3	3/40
===================================
	trees	Probability
	1	41/168
	2	19/28
	3	13/168
===================================
	trees	Probability
	1	163/540
	2	17/27
	3	37/540
===================================
	trees	Probability
	1	109/315
	2	187/315
	3	19/315
===================================
	trees	Probability
	1	4/15
	2	2/3
	3	1/15
===================================
	trees	Probability
	1	1496/4725
	2	2948/4725
	3	281/4725
===================================
	trees	Probability
	1	238/675
	2	2833/4725
	3	226/4725
===================================
	trees	Probability
	1	4211/11550
	2	641/1100
	3	1217/23100
===================================
	trees	Probability
	1	3221/8316
	2	1178/2079
	3	383/8316
===================================
	trees	Probability
	1	3299/9450
	2	11149/18900
	3	1153/18900
===================================
	trees	Probability
	1	88/225
	2	883/1575
	3	76/1575
===================================
	trees	Probability
	1	6123/15400
	2	8599/15400
	3	339/7700
===================================
	trees	Probability
	1	271/630
	2	671/1260
	3	47/1260
===================================
	trees	Probability
	1	1807/3850
	2	1941/3850
	3	51/1925
===================================
	trees	Probability
	1	2309/5544
	2	377/693
	3	73/1848
===================================
	trees	Probability
	1	320/819
	2	1847/3276
	3	149/3276
===================================
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
===================================
	trees	Probability
	1	101/275
	2	1116/1925
	3	102/1925
===================================
	trees	Probability
	1	1948/5775
	2	1158/1925
	3	353/5775
===================================
	trees	Probability
	1	223/616
	2	541/924
	3	97/1848
===================================
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
===================================
	trees	Probability
	1	904/2457
	2	1429/2457
	3	124/2457
===================================
	trees	Probability
	1	8/21
	2	4/7
	3	1/21
===================================
	trees	Probability
	1	8/21
	2	4/7
	3	1/21
===================================
q = tree_probabilities(graphs.CompleteMultipartiteGraph([2,2])) q = tree_probabilities(graphs.CompleteMultipartiteGraph([2,2,2])) q = tree_probabilities(graphs.CompleteMultipartiteGraph([2,2,2,2])) q = tree_probabilities(graphs.CompleteMultipartiteGraph([2,2,2,2,2])) 
       
	trees	Probability
	1	2/3
	2	1/3
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
	trees	Probability
	1	9824/72105
	2	40264/72105
	3	4220/14421
	4	917/72105
	trees	Probability
	1	9660544/197358525
	2	71303864/197358525
	3	30719348/65786175
	4	23633369/197358525
	5	602704/197358525
	trees	Probability
	1	2/3
	2	1/3
	trees	Probability
	1	26/77
	2	47/77
	3	4/77
	trees	Probability
	1	9824/72105
	2	40264/72105
	3	4220/14421
	4	917/72105
	trees	Probability
	1	9660544/197358525
	2	71303864/197358525
	3	30719348/65786175
	4	23633369/197358525
	5	602704/197358525
q = tree_probabilities(graphs.CompleteMultipartiteGraph([3,3,3])) 
       
	trees	Probability
	1	1992/26125
	2	11724/26125
	3	10951/26125
	4	1458/26125
	trees	Probability
	1	1992/26125
	2	11724/26125
	3	10951/26125
	4	1458/26125
html('<!--notruncate-->') conincedences = {} for n in [3,4,5,6,7]: for G in graphs.nauty_geng(str(n)+" -c"): q = tree_probabilities(G,stats=False) w = [0,0,0,0,0] for x in q: w[x] = q[x] w = tuple(w) if w in conincedences: conincedences[w].append(G.graph6_string()) else: conincedences[w] = [G.graph6_string()] for q in conincedences: if len(conincedences[q])>1: print q for x in conincedences[q]: Graph(x).show() print "======================" 
       
(0, 1, 0, 0, 0)
======================
(0, 1/2, 1/2, 0, 0)
======================
(0, 2/45, 26/45, 17/45, 0)
======================
(0, 5/12, 7/12, 0, 0)
======================
(0, 8/15, 7/15, 0, 0)
======================
(0, 3/10, 7/10, 0, 0)
======================
(0, 8/33, 20/33, 5/33, 0)
======================
(0, 2/15, 11/15, 2/15, 0)
======================
(0, 7/15, 8/15, 0, 0)
======================
(0, 11/20, 9/20, 0, 0)
======================
(0, 1/5, 3/5, 1/5, 0)
======================
(0, 17/30, 13/30, 0, 0)
======================
(0, 4/7, 3/7, 0, 0)
======================
(0, 17/80, 71/120, 47/240, 0)
======================
(0, 3/10, 3/5, 1/10, 0)
======================
(0, 2/5, 3/5, 0, 0)
======================
(0, 2/3, 1/3, 0, 0)
======================
(0, 737/2520, 817/1260, 149/2520, 0)
======================
(0, 8/21, 4/7, 1/21, 0)
======================
(0, 4/5, 1/5, 0, 0)
======================
(0, 43/252, 83/126, 43/252, 0)
======================
(0, 197/1080, 65/108, 233/1080, 0)
======================
(0, 26/77, 47/77, 4/77, 0)
======================
(0, 1/3, 2/3, 0, 0)
======================
(0, 1/4, 3/4, 0, 0)
======================
(0, 1, 0, 0, 0)
======================
(0, 1/2, 1/2, 0, 0)
======================
(0, 2/45, 26/45, 17/45, 0)
======================
(0, 5/12, 7/12, 0, 0)
======================
(0, 8/15, 7/15, 0, 0)
======================
(0, 3/10, 7/10, 0, 0)
======================
(0, 8/33, 20/33, 5/33, 0)
======================
(0, 2/15, 11/15, 2/15, 0)
======================
(0, 7/15, 8/15, 0, 0)
======================
(0, 11/20, 9/20, 0, 0)
======================
(0, 1/5, 3/5, 1/5, 0)
======================
(0, 17/30, 13/30, 0, 0)
======================
(0, 4/7, 3/7, 0, 0)
======================
(0, 17/80, 71/120, 47/240, 0)
======================
(0, 3/10, 3/5, 1/10, 0)
======================
(0, 2/5, 3/5, 0, 0)
======================
(0, 2/3, 1/3, 0, 0)
======================
(0, 737/2520, 817/1260, 149/2520, 0)
======================
(0, 8/21, 4/7, 1/21, 0)
======================
(0, 4/5, 1/5, 0, 0)
======================
(0, 43/252, 83/126, 43/252, 0)
======================
(0, 197/1080, 65/108, 233/1080, 0)
======================
(0, 26/77, 47/77, 4/77, 0)
======================
(0, 1/3, 2/3, 0, 0)
======================
(0, 1/4, 3/4, 0, 0)
======================