User Tools

Site Tools


chicoutimi_2016:focus_context

Differences

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

Link to this comparison view

chicoutimi_2016:focus_context [2016/05/26 21:59] (current)
melancon created
Line 1: Line 1:
 +====== Visual Analytics Course ======
  
 +Instructor: [[http://​www.labri.fr/​perso/​melancon|Guy Melançon]] (email: ''​Guy dot Melancon at labri dot fr''​)
 +
 +{{:​uqac.jpg?​nolink&​100 |}}
 +
 +===== Chicoutimi Summer 2016 roadmap / May 3, 3pm course =====
 +
 +  * [[chicoutimi_2016:​session_by_session_cutdown|Back to the course start page]]
 +    * [[chicoutimi_2016:​code_examples|Back to the code example page]]
 +
 +==== Vue Focus + Context ====
 +---
 +
 +[[chicoutimi_2016:​doi_tree_de_furnas|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 [[chicoutimi_2016:​clustering_hierarchique_ascendant|clustering hiérarchique ascendant]],​ par exemple).
 +
 +Il utilise l'un des indices [[chicoutimi_2016:​doi_de_furnas|DOI]] ou [[chicoutimi_2016:​doa_de_van_ham_et_van_wijk|DOA]] calculé sur l'​arbre (associé aux indices obtenus du clustering hiérarchique dans le cas du DOA).
 +
 +<file python 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
 +</​file>​
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/focus_context.txt · Last modified: 2016/05/26 21:59 by melancon