Subversion Repositories wimsdev

!if $wims_read_parm!=slib_header

 !goto proc

!endif

slib_title=Random tree

slib_parms=3\

,N approximative number of nodes\

,s maximum degree\

,h height\

, text\

, option words : perfect (all nodes have same degree), middle, point

slib_author=Bernadette PERRIN-RIOU

slib_out=[code for draw of a tree to be used with draw], \

[liste of nodes and children],[position of nodes],\

[position of points on vertices]

slib_comment=option middle : circle on middle of the edges;\

option point : circle on vertices

slib_example= 5,3,3,,perfect middle

!exit

:proc

!distribute item $wims_read_parm into slib_N,slib_s,slib_h,slib_text

slib_option = !item 5 to -1 of $wims_read_parm

!default slib_s=5

!default slib_h =8

!default slib_color1=blue

!default slib_color2=green

!default slib_color3 = yellow

slib_text=!declosing $slib_text

slib_G = 1

slib_cnt = 1

slib_n = $[2*$slib_N]

slib_A1 =0

slib_height1 =1

slib_sizey =1

slib_cnt1 = 0

slib_width1 =15

slib_Sizey = $[$slib_h+1]

slib_choix1=!values 1 for x = 1 to $[$slib_s+3]

slib_choix0=!values 0 for x = 1 to $[$slib_s-3]

slib_noeud= !random 0,1 repeat $n

#permet d'assurer que l'arbre ne part pas avec une seule branche (inutile dans le cas parfait)

slib_noeud = 1,$slib_noeud

slib_choix=$slib_choix1, $slib_choix0

slib_position =$empty

slib_milieu =0,-1

!for slib_k = 1 to $slib_n

	slib_L = !line $slib_k of $slib_G

	!if $slib_L<>$empty

		slib_i=!item 1 of $slib_L

		slib_position_prov=$(slib_A$slib_i),$[-$(slib_height$slib_i)]

		slib_position = !append line  $slib_position_prov to $slib_position

		!if $slib_cnt > $[$slib_N] or $slib_sizey > $slib_Sizey

		!else	

#choix des fils (position et nombre : la position est-elle intéressante pour un arbre non binaire ? )	

			slib_c=!item $slib_k  of $slib_noeud

			!if perfect iswordof of $slib_option or $slib_c = 1

				slib_a =!item 1 to $slib_s of $slib_choix1

			!else

				slib_a =!shuffle $slib_choix

				slib_a=!item 1 to $slib_s of $slib_a

			!endif	

			slib_Li =

			!for slib_j = 1 to $slib_s

				slib_b=!item $slib_j of $slib_a

				!if $slib_b <> 0

#creation d'un fils

					slib_jj =$[$slib_cnt+1]

#sa hauteur

					slib_height$slib_jj= $[$(slib_height$slib_i)+1]

#la hauteur de l'arbre

					slib_sizey=$[max($slib_sizey, $(slib_height$slib_jj))]

# Ne sert à rien ? 				

					slib_cnt$(slib_height$slib_jj)=$[$(slib_cnt$(slib_height$slib_jj))+1]

#on rajoute une ligne pour le fils

					slib_G =!append line $slib_jj to $slib_G

#nombre de sommets

					slib_cnt = $[$slib_cnt +1]

				!else 

					slib_jj=sentinelle

				!endif

#on rajoute le fils sur la ligne du père, rien s'il n'y a rien à cette position

				slib_Li =!append item $slib_jj to $slib_Li

#le calcul suivant sert pour le dessin. Faut-il le mettre ici ? 			

				!if $slib_b <> 0

#position

					slib_A$slib_jj=$[$(slib_A$slib_i)+($slib_j-($slib_s+1)/2)*$(slib_width$slib_i)]

#calcul de la largeur donnée au sommet $slib_jj pour ses fils éventuels

					slib_width$slib_jj=$[$(slib_width$slib_i)/min($slib_s,$slib_s+1)]	

					slib_milieu_prov=$[($(slib_A$slib_i)+2*$(slib_A$slib_jj))/3],$[-($(slib_height$slib_i) +2*$(slib_height$slib_jj))/3]

			 		slib_milieu = !append line $slib_milieu_prov to $slib_milieu

				!endif

			!next slib_j	

#on met la ligne $slib_k définitive

  		slib_G = !replace line number $slib_k by $slib_L,$slib_Li in $slib_G	

		!endif	

  !endif

!next slib_k

#Trace du dessin

slib_dessin =xrange $[-$slib_s*$slib_width1/2],$[$slib_s*$slib_width1/2]\

yrange $[-$slib_Sizey-0.5],-0.5\

linewidth 2

slib_cnt =!linecnt $slib_G

!for slib_k= 1 to $slib_cnt 

	slib_u =!line $slib_k of $slib_G

	slib_i=!item 1 of $slib_u

	slib_position_prov=!line $slib_k of $slib_position

	!for slib_j in $slib_u

		!if $slib_j  notsametext sentinelle

#trace de la droite

			slib_position_prov1=!line $slib_j of $slib_position

			slib_dessin = !append line line  $slib_position_prov,$slib_position_prov1, $slib_color1\

			 to $slib_dessin

#on coupe les segments au milieu pour mettre un cercle et éventuellement du texte			

			!if middle iswordof $slib_option

				slib_milieu_prov=!line $slib_j of $slib_milieu

				slib_dessin = !append line disk $slib_milieu_prov,30,white\

circle $slib_milieu_prov, 30,$slib_color3 to $slib_dessin	

			!endif

		!endif

	!next slib_j		

	!if point iswordof $slib_option

		slib_dessin =!append line disk $slib_position_prov,30,white\

	  circle $slib_position_prov,30,$slib_color2 to $slib_dessin

	!endif

	!if $slib_text <> $empty

		slib_textk=!item $slib_k of $slib_text

		slib_dessin =!append line text black,$slib_position_prov, medium,$slib_textk to $slib_dessin

	!endif

!next slib_k	

slib_out = [$slib_dessin], [$slib_G],[$slib_position],[$slib_milieu]