User Tools

Site Tools


chicoutimi_2016:modele_masses_ressorts

Visual Analytics Course

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

Chicoutimi Summer 2016 roadmap / May 6, 9am course

Modèle masses-ressorts

L'un des chapitres les mieux écrits sur ce sujet:

  • Brandes Ulrik (2005). Drawing on Physical Analogies, LNCS 2025, Springer, pp. 71-86.
  • Un récent article de S. Kobourov fait le point sur ces approches.

L'idée maitresse est de s'inspirer de la physique et voir le graphe comme un système de masses (qui se repoussent l'une l'autre) retenues entre elles par des ressorts (les arêtes).

Les sommets désignent des points dans le plan (ou l'espace), et l'on calcul des forces agissant sur ces points – calculés à partir de la position des autres sommets.

  • Soit les positions des sommets
  • Le vecteur
  • est un vecteur unitaire allant de vers .
    • Si on l'applique à , il se rapproche de .
    • Si on l'applique à , il s'éloigne de .
  • La force de répulsion (agissant sur , et par rapport à ) est définit comme:
  • La force d'attraction (agissant sur , et par rapport à ) est définit comme:

où sont des constantes à déterminer et est la longueur cible des arêtes dans le dessin.

L'algorithme utilise ces forces pour calculer une suite de positions des sommets convergeant ultimement vers une configuration stable et, idéalement, d'énergie minimum.

  • Les sommets sont initialement placés aux points
  • On calcule pour un sommet , une force faisant le bilan des vecteurs agissant sur (et définit par chacun des autres sommets ):
  • On applique une fraction de ce vecteur de déplacement sur chacun des sommets:
    • , où est une constante à déterminer.

Code example

Cette implémentation python s'appuie sur l'API python et reprend mot pour mot le modèle basique exposé ici.

SpringEmbedder.py
'''
Created on 27 fevr. 2012
 
@author: melancon
'''
 
import math
import numpy
import random
import time
 
class SpringEmbedder:
    '''
    Implements a simple Spring Emebdder following the guidelines from
    (2005) Brandes Ulrik. Drawing on Physical Analogies, LNCS 2025, Springer, pp.  71-86.
 
    For clarity, we borrow Brandes' notation to denote vertices of the graph.
    '''
 
    def __init__(self, graph, desired_length_matrix = None):
        '''
        Constructor
        '''
        self.graph = graph
        self.viewLayout = self.graph.getLayoutProperty('viewLayout')
        self.nodeSize = 1.0
        self.desired_length = self.graph.getDoubleProperty('desired_length')
        self.set_desired_length(desired_length_matrix)
        self.attractiveConstant = 0.3
        self.repulsiveConstant = 0.9
        self.delta = 0.25
        self.force_map = {}
 
        self.color = self.graph.getColorProperty('viewColor')
 
        '''
        for n in self.graph.getNodes():
            print self.viewLayout[n]
        '''
 
    def set_desired_length(self, matrix = None):
        if matrix == None:
            self.desired_length.setAllEdgeValue(10.0)
        else:
            '''
            we assume the lines and colmuns are ordered according
            to the order the implicit order [n for n in self.graph.getNodes()]
            '''
            nodes = [n for n in self.graph.getNodes()]
            for  i in range(self.graph.numberOfNodes()):
                for j in range(i+1, self.graph.numberOfNodes()):
                    e = self.graph.existEdge(nodes[i], nodes[j], False)
                    if e.isValid():
                        self.desired_length[e] = matrix[i,j]
 
    def __repulsiveForce__(self, u, v):
        '''
        computes the amount of force f_rep(p_u, p_v) to move node u away
        from node v in order to satisfy ideal distance constraint
        '''
        coord_u = self.viewLayout[u]
        coord_v = self.viewLayout[v]
        # (coord1 - coord2) points from  node2 to node1
        vect = (coord_v - coord_u)
        if vect.norm() != 0.0:
            vect /= vect.norm()
 
        if (coord_v - coord_u).norm() != 0.0:
            vect *= self.repulsiveConstant / (coord_v - coord_u).norm()**2
        else:
            vect = tlp.Coord(1, 1, 0)
        return vect
 
    def __attractiveForce__(self, u, v, e):
        '''
        computes the amount of force to move node u towards
        node v in order to satisfy ideal distance constraint
        '''
        coord_u = self.viewLayout[u]
        coord_v = self.viewLayout[v]
        # (coord1 - coord2) points from  node2 to node1
        vect = (coord_u - coord_v)
        if vect.norm() != 0.0:
            vect /= vect.norm()
 
        if (coord_v - coord_u).norm() != 0.0:
            vect *= self.attractiveConstant * math.log((coord_v - coord_u).norm() / self.desired_length[e])
        else:
            vect = tlp.Coord(0,0,0)
        return vect
 
    def total_force(self, v):
        total_vect = tlp.Coord(0,0,0)
        for u in self.graph.getNodes():
            e = self.graph.existEdge(u, v, False)
            if e.isValid():
                total_vect += self.__attractiveForce__(u, v, e)
            else:
                total_vect += self.__repulsiveForce__(u, v)
        return total_vect
 
    def permute_nodes(self):
        all_nodes = [n for n in self.graph.getNodes()]
        permut = []
        while len(permut) < self.graph.numberOfNodes():
            v = all_nodes[random.randint(0, self.graph.numberOfNodes() - 1)]
            if v not in permut:
                permut.append(v)
        return permut
 
    def raw_stress(self):
        '''
        square root of sum of squared differences over all pairs of nodes u, v
        sqrt( (d_G(u,v) - d_drawing(u,v))^2 )
        '''
        distances = self.graph.getIntegerProperty('distance')
        nodes = [n for n in self.graph.getNodes()]
 
        raw_stress_value = 0.0
        for i in range(self.graph.numberOfNodes()):
            tlp.maxDistance(self.graph, nodes[i], distances, tlp.UNDIRECTED)
            for j in range(i+1, self.graph.numberOfNodes()):
                euclidean_distance = self.viewLayout[nodes[i]].dist(self.viewLayout[nodes[j]])
                raw_stress_value += (distances[nodes[j]] - euclidean_distance)**2
        return math.sqrt(raw_stress_value)
 
    def run(self, epsilon_precision):
        nb_iter = 0
        previous_stress = 0.0
        current_stress = self.raw_stress()
        while numpy.abs((current_stress - previous_stress)) >  epsilon_precision: # for i in range(max(20 * self.graph.numberOfNodes(), 1000)):
            nodes = self.permute_nodes()
            for v in nodes:
                self.force_map[v] = self.total_force(v)
            for v in nodes:
                self.viewLayout[v] += self.delta * self.force_map[v]
            nb_iter += 1
            if nb_iter % 10 == 0:
                updateVisualization()
                print('Raw stress ', self.raw_stress())
            previous_stress = current_stress
            current_stress = self.raw_stress()
 
def main(graph):
	m = numpy.matrix([[0.0, 2.0, 4.0],[2.0, 0.0, 4.0], [4.0, 4.0, 0.0]])
	se = SpringEmbedder(graph, m)
	se.run(0.01)
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/chicoutimi_2016/modele_masses_ressorts.txt · Last modified: 2016/05/12 03:55 by melancon