#By Paul Raff 3/24/05
with(networks);

#This checks if this is indeed a tree and the vertices are labelled 1-n for some n.
CheckTree:=proc(G)
local i,verts,eds,n_verts,n_eds,max_vert;

verts:=vertices(G);
eds:=edges(G);

n_verts:=nops(verts);
n_eds:=nops(eds);

max_vert:=max(op(verts));

if (n_verts<>max_vert) or (verts minus {seq(i,i=1..max_vert)} <> {}) then
	printf("max vertex: %d, number of vertices: %d",n_verts,max_vert);
	return false;
fi:

if (mindegree(G) = 0) or (n_eds<>n_verts-1) then
	printf("min degree: %d, number of edges: %d",mindegree(G),n_eds);
	return false;
fi:

return true;
end:

#This returns the number of the least-valued leaf in the tree
LowestLeaf:=proc(G)
local verts,n_verts,i,min;

verts:=[op(vertices(G))];
n_verts:=nops(verts);
min:=max(op(verts));

for i from 1 to n_verts do
	if (vdegree(verts[i],G) = 1) and (verts[i]<min) then
		min:=verts[i];
	fi:
od:

return min;
end:

RemoveLowestLeaf:=proc(G)
local leaf:
leaf:=LowestLeaf(G);
delete(leaf,G);
return G;
end:

#This takes a tree, first checks if it is legit, and then returns the Prufer Code
PruferCode:=proc(G)
local i,verts, eds, n_verts,n_eds,code,current_lowest_leaf,lowest_leaf_neighbor;

verts:=vertices(G);
eds:=edges(G);
n_verts:=nops(verts);
n_eds:=nops(eds);

code:=[];

for i from 1 to (n_verts-2) do
	current_lowest_leaf:=LowestLeaf(G);
	lowest_leaf_neighbor:=op(neighbors(current_lowest_leaf,G));
	printf("Lowest leaf neighbor is %d\n",lowest_leaf_neighbor);
	code:=[op(code),lowest_leaf_neighbor]:
	G:=delete(current_lowest_leaf,G);
od:

code;
end:

RandomTree:=proc(n)
local G,roll,i,start,finish,e;

roll:=rand(1..n);

G:=new(G);
addvertex({seq(i,i=1..n)},G);
i:=0;                               #edge counter
while i<n-1 do
	start:=roll();
	finish:=roll();
	e:=addedge({start,finish},G);
	i:=i+1;
	if type(girth(G),finite) then     #means we have a cycle
		delete(e,G);
		i:=i-1;
	fi:
od:

return G:
end:

NumToList:=proc(n)
local l,m;

m:=n;
l:=[];
while m<>0 do
	l:=[m mod 10,op(l)];
	m:=floor(evalf(m/10));
od:
l:
end:

TreeFromCode:=proc(code_list)
local G,i,n,in_set,not_in_set,one_to_n,a_1,b_1,last_vertices,code;

code:=code_list;
n:=nops(code)+2;                    #Number of vertices in the graph
one_to_n:={seq(i,i=1..n)};

G:=new(G);
addvertex({seq(i,i=1..n)},G);


while nops(code)<>0 do
	in_set:=convert(code,set);
	not_in_set:=one_to_n minus in_set;
	a_1:=code[1];
	b_1:=min(op(not_in_set));
	connect(a_1,b_1,G);
	one_to_n:=one_to_n minus {b_1};
	code:=[op(2..nops(code),code)];
od:
last_vertices:=convert(one_to_n,list);
connect(last_vertices[1],last_vertices[2],G);
return G:
	
end: