User Tools

Site Tools


chicoutimi_2016:dessin_d_arbres

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
chicoutimi_2016:dessin_d_arbres [2016/05/05 17:16]
melancon
chicoutimi_2016:dessin_d_arbres [2016/05/12 03:59] (current)
melancon
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.
 +
 +<file python 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()
 +</​file>​
 +
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/dessin_d_arbres.txt · Last modified: 2016/05/12 03:59 by melancon