# Visual Analytics Course

### Site Tools

chicoutimi_2016:dessin_d_arbres

# Differences

This shows you the differences between two versions of the page.

 chicoutimi_2016:dessin_d_arbres [2016/05/05 17:16]melancon chicoutimi_2016:dessin_d_arbres [2016/05/12 03:59] (current)melancon Both sides previous revision Previous revision 2016/05/12 03:59 melancon 2016/05/05 17:16 melancon 2016/05/05 14:52 melancon [Dessin d'arbres] 2016/05/05 14:39 melancon [Dessin d'arbres] 2016/05/05 14:38 melancon [Dessin d'arbres] 2016/05/05 14:32 melancon created 2016/05/12 03:59 melancon 2016/05/05 17:16 melancon 2016/05/05 14:52 melancon [Dessin d'arbres] 2016/05/05 14:39 melancon [Dessin d'arbres] 2016/05/05 14:38 melancon [Dessin d'arbres] 2016/05/05 14:32 melancon created Line 69: Line 69: * Gibbons, J. (1996). "​Deriving tidy drawings of trees."​ Journal of Functional Programming 6(3). * Gibbons, J. (1996). "​Deriving tidy drawings of trees."​ Journal of Functional Programming 6(3). * {{::​buchheim_2002.pdf|Buchheim,​ C., M. Jünger, et al. (2002). Improving Walker'​s Algorithm to Run in Linear Time. International Symposium on Graph Drawing,​ Springer,​ 344-353.}} * {{::​buchheim_2002.pdf|Buchheim,​ C., M. Jünger, et al. (2002). Improving Walker'​s Algorithm to Run in Linear Time. International Symposium on Graph Drawing,​ Springer,​ 344-353.}} + + === Code example === + + Le code suivant implémente l'​algorithme naif décrit ici. + + ​ + 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() + ​ +