User Tools

Site Tools


chicoutimi_2016:focus_context

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / May 3, 3pm course

Vue Focus + Context

Voir la portion de cours sur l'indice DOI.

Cet algorithme calcule une vue abstraite d'un graphe en regroupant certains sommets au sein de méta-sommets (MetaNode). Il s'appuie sur le calcul d'un arbre binaire associé au graphe et décrivant un clustering hiérarchique sur ce graphe (obtenu à l'aide de l'algorithme de clustering hiérarchique ascendant, par exemple).

Il utilise l'un des indices DOI ou DOA calculé sur l'arbre (associé aux indices obtenus du clustering hiérarchique dans le cas du DOA).

FocusContext.py
from tulip import *
from Furnas import *
from DOA import *
import Queue
 
class FocusContext(object):
	'''
	Implements in a rude fashion, the various focus + context approaches from Furnas (DOI)
	and others. See Furnas' original paper:
 
	Furnas, G. W. (1986). Generalized Fisheye Views.
	Human Factors in Computing Systems CHI '86, ACM Press, 16-23.
 
	See also van Ham's papers:
 
	van Ham, F. and J. J. van Wijk (2004).
	Interactive Visualization of Small World Graphs.
	IEEE Symposium on Information Visualisation, Austin, TX, USA, IEEE Computer Science press, 199-206.
 
	van Ham, F. and A. Perer (2009).
	Search, Show Context, Expand on Demand": Supporting Large Graph Exploration with Degree-of-Interest.
	IEEE Transactions on Visualization and Computer Graphics 15(6): 953-960.
 
	The plugin requires two crucial ingredient:
	- a graph (named 'original_graph')
	- and a cluster tree (hierarchical clustering) (named 'cluster_tree')
 
	Nodes of the original graph are leaves in the cluster tree. The plug in triggers various behaviours
	based on the selection of a node, or multiple nodes (typically forming a maximal antichain in the cluster tree).
 
	Both graphs are subgrpahs of the root graphs and must be strictly named for the plugin to work.
	'''
	def __init__(self, super_graph, method = 'Furnas', name_original_graph = 'original_graph', name_cluster_tree = 'cluster_tree'):
 
		#super(FocusContext, self).__init__()
		self.super_graph = super_graph
		self.original_graph = self.super_graph.getSubGraph(name_original_graph)
		self.cluster_tree = self.super_graph.getSubGraph(name_cluster_tree)
		# need to keep track of internal nodes in cluster tree that map to metanodes
		self.meta_map = {}
 
		self.method = method
		if self.method == 'Furnas':
			self.doa_engine = Furnas(self.cluster_tree)
		else:
			self.doa_engine = DOA(self.cluster_tree)
 
	def select_leaves(self, tree_node):
		'''
		Starts from a node in the cluster tree. Returns the set of leaves beneath tree_node
		as nodes of the *original graph*.
		'''
		queue = Queue.Queue()
		queue.put(tree_node)
		node_set = set()
		while not queue.empty():
			n = queue.get()
			if self.cluster_tree.outdeg(n) == 0:
				node_set.add(n)
				continue
			for child in self.cluster_tree.getOutNodes(n):
					queue.put(child)
		return node_set
 
	def group_nodes(self, level_of_details = 4):
		'''
		We assume one node is selected in the cluster tree. The view on the original
		graph is then adjusted according to the DOI, closing nodes with larger DOI values
		into metanodes)
		'''
		tree_sel = self.cluster_tree.getLocalBooleanProperty('cluster_selection')
		if self.method == 'Furnas':
			self.doa_engine.performDOI(level_of_details, tree_sel)
		else:
			self.doa_engine.performDOA(level_of_details, tree_sel)
		# expand selection on path to root of cluster tree
		# needed for metanode creation to be coherent -> we need a maximal antichain
		# this only is useful if applying Furnas
		n =None
		for n in self.cluster_tree.getNodes():
			if tree_sel[n]:
				break
		while self.cluster_tree.indeg(n) != 0:
			tree_sel[n] = True
			for pn in self.cluster_tree.getInNodes(n):
				n = pn
				continue
		# traverse the tree and list all internal nodes that will turn into groups 
		queue = Queue.Queue()
		queue.put(self.cluster_tree.getSource())
		group_nodes = []
		while not queue.empty():
			n = queue.get()
			if self.cluster_tree.outdeg(n) == 0:
				continue
			for child in self.cluster_tree.getOutNodes(n):
				if tree_sel[child]:
					queue.put(child)
				else:
					if self.cluster_tree.outdeg(child) > 1:
						group_nodes.append(child)
 
		tree_sel.setAllNodeValue(False)
		for gn in group_nodes:
			tree_sel[n] = True
 
		for gn in group_nodes:
			mn = self.original_graph.createMetaNode(self.select_leaves(gn))
			self.meta_map[gn] = mn
 
def doa_const(p1, p2):
    return 0.55
 
def doa_linear(p1, p2):
    print 'dao for pts ', p1, ', ', p2
    doa_bound = 0.3
    dist = p1.dist(p2)
    if dist <  100.0:
        return doa_bound * dist / 100.0
    else:
        return doa_bound
 
def main(graph):
	fc = FocusContext(graph, 'DOA') # DOI si second param pas renseigne
	fc.group_nodes(doa_linear) # valeur entiere si DOI
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/focus_context.txt · Last modified: 2016/05/26 21:59 by melancon