User Tools

Site Tools


veroone:solution_homework2
  • Note: 5/5
  • Votre code est bien, manquerait que de la mettre en OO
  • L'animation est réussie
  • La discussion est des plus intéressante

Guy Melançon 2012/04/18 15:59


Références

Explications

J'ai choisi de me focaliser sur l'application du principe des graphes en oignons sur des arbres. Pour obtenir des Layouts de graphes (dirigés, acycliques), il faudrait appliquer l'algorithmes à l'arborescence optimale de ceux-cis (concept proche des arbres couvrants maximums, appliqué aux graphes non pondérés)/ Cette arborescence peut être obtenue via l'algo de Chu-Liu/Edmonds.

Pour le morphing, j'ai calculé un vecteur déplacement et un vecteur “evolution de taille” en fonction de la granularité souhaitée (nombre d'itérations), et appliqué ceux-ci. J'ai dû corriger à la fin de l'algorithme les tailles et positions pour compenser les erreurs induites par la manipulation de nombres flottants.

La différence avec un TreeMap est qu'ici, la caractéristique du noeud qui préside à la décision de sa taille est sa position dans l'arbre et du nombre de noeuds dans les niveaux supérieurs (plus proches des feuilles), et pas une caractéristique externe.

Code

Veillez à appliquer cet algorithme sur un ARBRE. pour l'appliquer à un DAG (directed acyclic graph) cf explications ci-dessus. Attention, dû au grand nombre de calculs nécéssaires en particulier pour le morphing, veillez à n'utiliser cet algorithme que sur de petits arbres (ne dépassant pas la vingtaine de noeuds) ou d'adapter la granularité au nombre de noeuds.

Fichier tlp :

onion_graph_with_data.zip

onion_graph.py
from tulip import *
 
def main(graph) : 
	graph.delAllSubGraphs(graph)
	apply_layout(graph)
 
 
def apply_layout(graph):
	cleanSubGraphs(graph)
	level = graph.getIntegerProperty("level") # node depth in tree
	endSize = graph.getSizeProperty("endSize") # calculated size
	endPos = graph.getLayoutProperty("endPos") # calculated position
	deltaPX = graph.getDoubleProperty("deltaPX") # atomic X movement
	deltaPY = graph.getDoubleProperty("deltaPY") # atomic Y movement
	deltaSH = graph.getDoubleProperty("deltaSH") # atomic height increase
	deltaSW = graph.getDoubleProperty("deltaSW") # atomic width increase
	morph_iterations = 100 # granularity of the morphing
 
	# 	Calculating rank
	tlp.dagLevel(graph,level)
	top = graph.getIntegerProperty("level").getNodeMin()
	bottom = graph.getIntegerProperty("level").getNodeMax()
 
	##	Aesthetics :
	# Coloring
	colorScale = tlp.ColorScale()
	colorScale.setColorAtPos(0.0, tlp.Color(255,0,0))
	colorScale.setColorAtPos(1.0, tlp.Color(0,0,255))
	for n in graph.getNodes():
		print graph.getIntegerProperty("level").getNodeValue(n)/bottom
		graph.getColorProperty("viewColor").setNodeValue(n,colorScale.getColorAtPos(graph.getIntegerProperty("level").getNodeValue(n)/float(bottom)))
	updateVisualization()
	print  "Please disable edge color interpolation creating artifacts on the view"
 
	# Hiding edges (by setting alpha channel to 0)
	for e in graph.getEdges():
		color = graph.getColorProperty("viewColor").getEdgeValue(e)
		bcolor = graph.getColorProperty("viewBorderColor").getEdgeValue(e)
		color.setA(0)
		bcolor.setA(0)
		graph.getColorProperty("viewColor").setEdgeValue(e,color)
		graph.getColorProperty("viewBorderColor").setEdgeValue(e,bcolor)
	updateVisualization();
 
	##	Calculating node size by level
	# minimum size :
	for n in graph.getNodes():
		endSize.setNodeValue(n,tlp.Size(2,2,1))
	for l in range(bottom-1,top-1,-1): 		# iterating over ranks
		max = countMaxLevelSuccessors(graph,l) # compute maximum of seccessors for this rank
		for n in graph.getNodes():  				# iterate over nodes of this rank
			if level.getNodeValue(n)<=l: 				# increase size of all nodes of superior ranks
				if l%2==1:
					W = endSize.getNodeValue(n).getW()*max+(max+1)
					H = endSize.getNodeValue(n).getH()+2
				else:
					W = endSize.getNodeValue(n).getW()+2
					H = endSize.getNodeValue(n).getH()*max+(max+1)
				endSize.setNodeValue(n,tlp.Size(W,H,1))
 
	##	Calculate node placement
	father = graph.getRoot()
	for l in range(top+1,bottom+1):
		inLevelId = 1	# numbering of nodes among siblings
		for n in graph.getNodes():
			if level.getNodeValue(n)==l:
				if graph.getInNode(n,1)!=father:
					father = graph.getInNode(n,1)
					inLevelId = 1
				fatherCoord = graph.getLayoutProperty("endPos").getNodeValue(father)
				levelNodesCount = countMaxLevelSuccessors(graph, level.getNodeValue(father))
				size = graph.getSizeProperty("endSize").getNodeValue(n)
				# position node against its father & sibling positions
				if levelNodesCount%2==0:
					if l%2==1: #odd => Y
						x = fatherCoord.getX()
						y = fatherCoord.getY()+((inLevelId-levelNodesCount/2)-0.5)*(1+size.getH())
					else: #even => x
						x = fatherCoord.getX()+((inLevelId-levelNodesCount/2)-0.5)*(1+size.getW())
						y = fatherCoord.getY()
				else:
					if l%2==1: #odd => Y
						x = fatherCoord.getX()
						y = fatherCoord.getY()+(inLevelId-(levelNodesCount+1)/2)*(1+size.getH())
					else: #even => x
						x = fatherCoord.getX()+(inLevelId-(levelNodesCount+1)/2)*(1+size.getW())
						y = fatherCoord.getY()
				endPos.setNodeValue(n,tlp.Coord(x,y,l))
				inLevelId+=1
 
	##	Sizing nodes w/ morphing
	# compute atomic size change
	for n in graph.getNodes(): 
		dh = (endSize.getNodeValue(n).getH() - graph.getSizeProperty("viewSize").getNodeValue(n).getH())/morph_iterations
		dw = (endSize.getNodeValue(n).getW() - graph.getSizeProperty("viewSize").getNodeValue(n).getW())/morph_iterations
		deltaSH.setNodeValue(n,dh)
		deltaSW.setNodeValue(n,dw)
	# apply morphing
	for i in range(1,morph_iterations): 
		for n in graph.getNodes():
			newH = graph.getSizeProperty("viewSize").getNodeValue(n).getH() + deltaSH.getNodeValue(n)
			newW = graph.getSizeProperty("viewSize").getNodeValue(n).getW() + deltaSW.getNodeValue(n)
			graph.getSizeProperty("viewSize").setNodeValue(n,tlp.Size(newW,newH))
		updateVisualization()
	# correct final size to match calculations
	for n in graph.getNodes():
		graph.getSizeProperty("viewSize").setNodeValue(n,endSize.getNodeValue(n))
	updateVisualization()
 
	## moving nodes w/ morphing
	# compute atomic positipon change
	for n in graph.getNodes():
		dpx = (endPos.getNodeValue(n).getX() - graph.getLayoutProperty("viewLayout").getNodeValue(n).getX())/morph_iterations
		dpy = (endPos.getNodeValue(n).getY() - graph.getLayoutProperty("viewLayout").getNodeValue(n).getY())/morph_iterations
		deltaPX.setNodeValue(n,dpx)
		deltaPY.setNodeValue(n,dpy)
		# apply morphing
	for i in range(1,morph_iterations):
		for n in graph.getNodes():
			newX = graph.getLayoutProperty("viewLayout").getNodeValue(n).getX() + deltaPX.getNodeValue(n)
			newY = graph.getLayoutProperty("viewLayout").getNodeValue(n).getY() + deltaPY.getNodeValue(n)
			graph.getLayoutProperty("viewLayout").setNodeValue(n,tlp.Coord(newX,newY))
		updateVisualization()
	# correct final size to match calculations
	for n in graph.getNodes():
		graph.getLayoutProperty("viewLayout").setNodeValue(n,endPos.getNodeValue(n))
	updateVisualization()
 
## Return maximum of children of this rank's nodes
def countMaxLevelSuccessors(graph, level):
	levelNodes = tlp.newSubGraph(graph,"level")
	for n in graph.getNodes():
		if graph.getIntegerProperty("level").getNodeValue(n)==level :
			levelNodes.addNode(n)
	max = 0
	for n in levelNodes.getNodes():
		tmax=0
		for n2 in graph.getOutNodes(n):
			tmax+=1
		if tmax>max:
			max=tmax
	return max
 
## remove all subgraphs of [graph]
def cleanSubGraphs(graph):
	for n in graph.getSubGraphs():
		graph.delSubGraph(n)
 
 
#	#	setting edge types : unsued atm
#	black = tlp.Color(0,0,0)
#	blue = tlp.Color(0,0,255)
#	green = tlp.Color(0,255,0)	
#	red = tlp.Color(255,0,0)
#	for e in graph.getEdges():
#		diff = level.getNodeValue(graph.target(e))-level.getNodeValue(graph.source(e))
#		if diff == 0:
#			edgeType.setEdgeValue(e,"cross")
#			viewColor.setEdgeValue(e,red)
#		elif diff == 1:
#			edgeType.setEdgeValue(e,"tree")
#			viewColor.setEdgeValue(e,black)
#		else: # if diff > 1
#			edgeType.setEdgeValue(e,"forward")
#			viewColor.setEdgeValue(e,green)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/veroone/solution_homework2.txt · Last modified: 2012/04/18 16:00 by melancon