Բինար ծառեր նկարելու մասին

Մի քանի գրառումներիս մեջ ինձ հարկավոր էր պատկերել բինար ծառեր՝ որոշ ալգորիթմների աշխատանքը ցուցադրելու համար։ Սկզբում ես նկարում էի թղթի վրա, ապա, սկաների օգնությամբ թվայնացնելուց հետո, տեղադրում էի գրառման մեջ։ Բայց դա շատ անհարմար եղանակ է, մանավանդ երբ նկարները շատ են ու մատկերում են ալգորիթմի հաջորդական քայլեր։ Հետո որոշեցի գրել ծրագիր, որը ծառ պատկերը կարտածի որևէ գրաֆիկական ֆորմատով։ Postscript, MetaPost և SVG տարբերակներից ընտրեցի վերջինը, որովհետև․ ա) այն շատ պարզ կառուցվածք ունի, գրաֆիկական պրիմիտիվները ներկայացված են XML լեզվով, որում գեներացնելուց հետո կարելի շտկումներ կատարել, բ) նկարները կարելի է դիտել ժամանակակից կամայական բրաուզերի մեջ։

Երբ ինտերնետում փնտրում էի ծառ նկարելու ալգորիթմի մասին տեղեկություններ, գտա բազմաթիվ գրառումներ, սլայդներ, հոդվածներ, որոնցում դիտարկվում էին ծառերը նկարելու առանձնհատկություները (տարածքի օպտիմալ օգտագործում, կատարման արագություն և այլն)։ Բայց քանի որ այդպիսի փիլիսոփայություններն ինձ չեն հետաքրքրում, ընտրեցի ամենապարզ ալգորիթմը, որը, ինչքան հասկացա, առաջարկել է Դ․ Կնուտը։ Այդ ալգորիթմի կառուցվածքը շատ պարզ է.

1.  Let x = 0
2.  Procedure DrawTree( tree, y )
3.    If Left( tree ) <> Nil Then
4.      DrawTree( Left( tree ), y + 1 )
5.    DrawNode( Data( tree, x, y ) )
6.    Let x = x + 1
7.    If Right( tree ) <> Nil Then
8.      DrawTree( Right( tree ), y + 1 )
9.  End

Այստեղ իրականացված է բինար ծառի ձախ-արմատ-աջ տիպի անցում, որտեղ արմատը նկարվում է ընթացիկ մակարդակի` y, իր կարգին համապատասխան՝ x, դիրքում։ Ստորև բերված նկարում կապույտ գծերով նկարված ու համարակալված են ծառը նկարելու ժամանակ x փոփոխականի հաջորդական արժեքները, իսկ կարմիր գծերով՝ y փոփոխականինը (մակարդակները)։

Ես այս սխեման օգտագործել եմ Common Lisp լեզվով draw-tree փաթեթը սահմանելու համար, որը տրամադրում է ծառի ցուցակային ներկայացումից SVG պատկեր գեներացնող draw-as-svg ֆունկցիան և նկարող ալգորիթմի մի քանի պարամետրեր վերասահմանող setup ֆունկցիան։

(defpackage :draw-tree
  (:use :common-lisp)
  (:export :setup
           :draw-as-svg))

(in-package :draw-tree)

Հետո սահմանում եմ չորս պարամետրեր, որոնք օգտագործվում են ծառի հանգույցները և դրանք միացնող գծերը պատկերելու համար։

(defvar *node-radius* 12 "ծառի հանգույցը պատկերող օղակի շառավիղը")
(defvar *font-size* 12 "տառերի չափը")
(defvar *x-scale* 30 "մասշտաբը X-երի առանցքով")
(defvar *y-scale* 30 "մասշտաբը Y-ների առանցքով")

Նկարելուց առաջ կարելի է setup ֆունկցիայի անվանված արգումենտներով փոփոխել այս պարամետրերից մեկը կամ մի քանիսը։

(defun setup (&key (node-radius 12) (font-size 12) (x-scale 30) (y-scale 30))
  (setq *node-radius* node-radius
        *font-size* font-size
        *x-scale* x-scale
        *y-scale* y-scale))

Հետևյալ հաստատունները SVG ֆայլը գեներացնելու ժամանակ օգտագործվելու են որպես format ֆունկցիայի արգումենտներ։

(defconstant +svg-header+
  "<svg xmlns='http://www.w3.org/2000/svg' version='1.1' width='~d' height='~d'>~%")
(defconstant +svg-circle+
  "    <circle cx='~d' cy='~d' r='~d'/>~%")
(defconstant +svg-text+
  "    <text x='~d' y='~d'>~d</text>~%")
(defconstant +svg-line+
  "    <line x1='~d' y1='~d' x2='~d' y2='~d'/>~%")

Նկարելու ալգորիթմն իրականացված է այնպես, որ նախ հավաքվում են ֆայլը գեներացնելու համար անհրաժեշտ տվյալները, ապա դրանք խմբավորված գրվում են նպատակային ֆայլում։ Հետևյալ փոփոխականները ծառայում են միջանկյալ տվյալները պահելու համար։

(defparameter *edges* '() "հանգույցները միացնող գծերը")
(defparameter *nodes* '() "հանգույցները պատկերող շրջանակները")
(defparameter *texts* '() "շրջանակի մեջ գրված տեքստը")
(defparameter *max-x* 0 "ամենամեծ x կոորդինատը")
(defparameter *max-y* 0 "ամենամեծ y կոորդինատը")

node-svg ֆունկցիան ստեղծում է SVG պատկերի երկու թեգեր՝ circle և text, որոնք ներկայացնում են ծառի հանգույցը։ Այս ֆունկցիան հաշվում է նաև ամենամեղ x և y կոորդինատները։

(defun node-svg (xy text)
  (let ((x (* *x-scale* (car xy))) (y (* *y-scale* (cdr xy))))
    (push (format nil +svg-circle+ x y *node-radius*) *nodes*)
    (push (format nil +svg-text+ x (+ 4 y) text) *texts*)
    (setq *max-x* (max *max-x* x) *max-y* (max *max-y* y))))

edge-svg ֆունկցիան ստեղծում է SVG պատկերի line թեգը, որը ներկայացնում է երկու հանգույցները միացնող կողը։

(defun edge-svg (xyb xye)
  (let ((xb (* *x-scale* (car xyb))) (yb (* *y-scale* (cdr xyb)))
        (xe (* *x-scale* (car xye))) (ye (* *y-scale* (cdr xye))))
    (push (format nil +svg-line+ xb yb xe ye) *edges*)))

Եվ վերջապես, կնուտի ալգորիթմը։ calculate-coordinates ֆունկցիան անցնում է ծառի հանգույցներով և ամեն մի հանգույցում գրված տվյալը փոխարինում է (data (x . y)) տեսքի ցուցակի։ Այս ֆունկցիայի աշխատանքի արդյունքում ստացվում է նոր ծառ՝ կոորդինատներով հարստացված հանգույցներով։

(defparameter *pos* 0)

(defun calculate-coordinates (tree level)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l (setf l (calculate-coordinates l (1+ level))))
      (setf h (list (cons *pos* level) h))
      (incf *pos*)
      (when r (setf r (calculate-coordinates r (1+ level))))
      (list h l r))))

generate-svg-edges և generate-svg-nodes ֆունկցիաները նորից անցնում են ծառի վրայով ու խմբավորում են SVG ֆայլը գեներացնելու համար անհրաժեշտ տվյալները։ Երևի կարելի է այս երկու ֆունկցիաները կոմբինացնել calculate-coordinates ֆունկցիայի հետ, որով կնվազեն ալգորիթմի քայլերը, բայց այս պահին ես իրականացրել եմ այս եղանակով։

(defun generate-svg-edges (tree)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l
        (generate-svg-edges l)
        (edge-svg (car h) (caar l)))
      (when r
        (generate-svg-edges r)
        (edge-svg (car h) (caar r))))))

(defun generate-svg-nodes (tree)
  (when tree
    (let ((h (car tree)) (l (cadr tree)) (r (caddr tree)))
      (when l (generate-svg-nodes l))
      (node-svg (car h) (cadr h))
      (when r (generate-svg-nodes r)))))

draw-as-svg ֆունկցիան նախապատրաստում է ժամանակավոր փոփոխականները, հաշվարկում է ծառի գագաթների կոորդինատները, ապա հավաքած ինֆորմացիան արտածում է տրված անունով ֆայլի մեջ։

(defun draw-as-svg (tree out-file)
  (setq *pos* 1
        *edges* '()
        *nodes* '()
        *texts* '())
  (let ((antree (calculate-coordinates tree 1)))
        (generate-svg-edges antree)
        (generate-svg-nodes antree))
    (with-open-file (osvg out-file :direction :output :if-exists :supersede)
      (format osvg +svg-header+ (+ *max-x* *x-scale*) (+ *max-y* *y-scale*))
      (format osvg "  <g fill='white' stroke='black' stroke-width='2'>~%")
      (dolist (e *edges*) (princ e osvg))
      (dolist (n *nodes*) (princ n osvg))
      (format osvg "  </g>~%~%")
      (format osvg "  <g text-anchor='middle' font-size='~d' stroke-width='0'>~%" *font-size*)
      (dolist (x *texts*) (princ x osvg))
      (format osvg "  </g>~%")
      (format osvg "</svg>~%")))

* * * Վերջում մի օրինակ. պատահական տվյալներից կառուցված AVL ծառ՝ նկարված այս ծրագրով.