User Tools

Site Tools


chicoutimi_2016:dessin_d_arbres

Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Dessin d'arbres

Les arbres sont des objets privilégiés de l'informatique. Les graphes appelés arbres ici sont ceux munis d'une racine et dont les arêtes peuvent être considérés orientés, de la racine vers les feuilles, et d'arité arbitraire (par opposition aux arbres binaires, par exemple).

Parce qu'ils peuvent être parcourus en temps linéaire, ils admettent des algorithmes dessin qui sont les plus rapides. Leur structure, souvent facile à interpréter, autorise la production de représentations esthétiquement plaisante à l'oeil – ce n'est pas négligeable pour l'utilisateur.

La littérature oublie souvent de souligner l'algorithme de base (implicitement utilisé pour le calcul de diverses représentations).

  • C'est celui où les sommets sont ordonnés selon leur profondeur dans l'arbre, la racine placée au haut du dessin, définissant ainsi leur ordonnnée (coordonnée en ).
  • L'abcisse des sommets est déterminée selon les feuilles dans l'arbre.
    • Les feuilles sont naturellement ordonnée de gauche à droite (par un parcours préfixe de l'arbre, par exemple) et hérite de ce fait leur abcisse.
    • Les sommet internes (ceux ayant au moins un fils) sont placés au barycentre (en abcisse) de leurs fils.
# cette fonction doit etre appelee depuis la racine de l'arbre

# on suppose disposer d'une variable globale coord_x_courante
# initialisee a 0.0
# on peut aussi envisager de passer cette variable par reference
# et charger la fonction de la modifier

# les abcisses des sommets sont stockes dans une table coords_x

fonction abcisse(sommet) # retourne une valeur d'abcisse pour le sommet
    si sommet est une feuille
    coords_x[sommet] = coord_x_courante
    coords_x_courante += increment
   
    sinon
        child_coords = []
        iterer sur les fils du sommet (ses sommets sortants)
	    ajouter abcisse(fils) a child_coords
	coords_x[sommet] = min(child_coords) +
                          (max(child_coords) - min(child_coords)) / 2
    retourner x_coords[sommet]
# cette fonction doit etre appelee depuis la racine de l'arbre
# en passant le parametre profondeur_courante a 0
 
# les ordonnees des sommets sont stockes dans une table coords_y

fonction ordonnee(sommet, profondeur_courante)
    coords_y[sommet] = profondeur_courante
    iterer sur les fils du sommet (ses sommets sortants)
	ordonnee(fils, profondeur_courante + 1)

Pour aller plus loin:

Code example

Le code suivant implémente l'algorithme naif décrit ici.

HierarchicalTree.py
from tulip import *
from Queue import *
import math
 
 
class HierarchicalTree(object):
	'''
	HierarchicalTree prodices a traditional top down layout
	of a tree with the root at the top
	The algorithm lays out nodes computing their y coordinates based on their
	depth (height) in the tree.
	The x coordinates of nodes is computed for leaves according to their rank,
	parent nodes are positioned at the x-barycenter position of their siblings.
 
	The graph is assumed to be a tree, that is a directed graph,
	with a single node (the root) with incoming degree 0,
	'''
	def __init__(self, graph):
		super(HierarchicalTree, self).__init__()
		self.graph = graph
		self.in_deg = self.graph.getDoubleProperty('incoming_degree')
		dataset = tlp.getDefaultPluginParameters('Degree',self.graph)
		dataset['type'] = 'In'
		self.graph.applyDoubleAlgorithm('Degree', self.in_deg, dataset)
 
		'''
		finds and sets the root of the tree
		'''
		self.root = None
		for n in self.graph.getNodes():
			if self.in_deg[n] == 0:
				self.root = n
 
		self.out_deg = None # will be set when is_leaf is called the first time
		self.out_deg = self.graph.getDoubleProperty('out_going_degree')
		self.number_of_leaves()
		dataset = tlp.getDefaultPluginParameters('Degree',self.graph)
		dataset['type'] = 'Out'
		self.graph.applyDoubleAlgorithm('Degree', self.out_deg, dataset)
 
		self.brother_map = {}
		self.x_coords = {}
		self.current_x_coord = 0.0
		self.theta_coords = {}
		self.current_theta_coord = 0.0
		self.y_coords = {}
		self.rho_coords = {}
 
	def build_brother_map(self):
		q = Queue()
		self.brother_map[self.get_root()] = None
		q.put(self.get_root())
		while not q.empty():
			node = q.get()
			brother_node = None
			for child in self.graph.getInOutNodes(node):
				q.put(child)
				self.brother_map[child] = brother_node
				brother_node = child
 
	def number_of_leaves(self):
		self.nb_leaves = 0
		for n in self.graph.getNodes():
			if self.is_leaf(n):
				self.nb_leaves += 1
 
	def is_leaf(self, node):
		return self.out_deg[node] == 0
 
	def set_x_coordinates(self, node):
		if self.is_leaf(node):
			self.x_coords[node] = self.current_x_coord
			self.current_x_coord += 2.0
		else:
			child_coords = []
			for child in self.graph.getOutNodes(node):
				child_coords.append(self.set_x_coordinates(child))
			self.x_coords[node] = min(child_coords) + (max(child_coords) - min(child_coords)) / 2
		return self.x_coords[node]
 
	def set_y_coordinates(self, node, depth_of_node):
		depth = self.graph.getDoubleProperty('depth')
		self.y_coords[node] = depth_of_node
		for child in self.graph.getOutNodes(node):
			self.set_y_coordinates(child, depth_of_node + 2.0)
 
	def run(self):
		self.set_x_coordinates(self.root)
		self.set_y_coordinates(self.root, 0.0)
		layoutProp = self.graph.getLayoutProperty('viewLayout')
		for n in graph.getNodes():
			layoutProp[n] = tlp.Coord(self.x_coords[n], - self.y_coords[n], 0.0)
		updateVisualization()
 
def main(graph):
	ht = HierarchicalTree(graph)
	ht.run()
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/dessin_d_arbres.txt · Last modified: 2016/05/12 03:59 by melancon