trazado de grafos mediante métodos dirigidos por fuerzas revisión del estado del arte y...

Trazado de grafos mediante métodos dirigidos por fuerzas

Revisión del estado del arte y presentación de algoritmos para grafos

donde los vértices son regiones geográficas

Tesistas: Andrés Aiello y Rodrigo I. Silveira

{aaiello, rsilveir}@dc.uba.ar

Directores: Manuel Abellanas y Gregorio Hernández Peñalver

Universidad Politécnica de Madrid

Tesis de Licenciatura en Ciencias de la Computación

Departamento de ComputaciónFacultad de Ciencias Exactas y Naturales

Universidad de Buenos Aires

Andrés Aiello y Rodrigo I. Silveira


2

Sobre este trabajo

Esta tesis es sobre trazado de grafos. Acerca de métodos dirigidos por fuerzas.

Está compuesta por dos partes: Una completa revisión del estado del arte. Un conjunto de algoritmos para un nuevo

problema: cuando los vértices del grafo representan regiones geográficas.



3

Contenido

Introducción al trazado de grafos. Revisión del estado del arte de los

métodos dirigidos por fuerzas. Algoritmos para grafos donde los

vértices son regiones geográficas. Conclusiones y trabajo futuro.



4

Consiste en encontrar para cada vértice del grafo una posición en el plano. Si las aristas se dibujan como segmentos,

esto define un dibujo o trazado del grafo. Hay infinitas formas de dibujar un grafo. La intención es que el dibujo resultante sea

estéticamente bueno.

Qué es el trazado de grafosGraph drawing is the best possible field I can think of: it merges

aesthetics, mathematical beauty and wonderful algorithms. It therefore provides a harmonic balance between the left and right brain parts

Donald Knuth, Simposio Graph Drawing '96.



5

Ejemplo

Dos trazados del mismo grafo:



6

Criterios estéticos

Definen qué hace que un trazado sea estéticamente bueno.

Los más comunes: Minimizar cruces. Minimización de área.

Distribuir vértices uniformemente. Maximización del ángulo entre ejes. Mostrar simetría. Longitud uniforme de aristas.



7

Pueden entrar en conflicto

Ej. simetría vs. evitar cruces.



8

Familias de algoritmos

Para clases específicas de grafos Arboles. Grafos dirigidos. Planares.

Para grafos generales Para trazado ortogonal. Algoritmos dirigidos por fuerzas. Algoritmos espectrales.

Métodos dirigidos por fuerzas:revisión del estado del arte

Parte 1



10

Métodos dirigidos por fuerzas Modelan al grafo con un sistema

físico. El trazado es obtenido buscando un

equilibrio de ese sistema físico.

Tienen dos partes bien diferenciadas: Un modelo físico. Un algoritmo para buscar un equilibrio.



11

Métodos dirigidos por fuerzas (2) El primero fue el spring embedder. Plantea

una analogía con resortes (Eades, 84).

Veinte años después del algoritmo de Eades, existen cientos de variantes distintas. El objetivo de la primer parte del trabajo es

presentar de manera organizada todas las publicaciones relevantes de la literatura.



12

Ventajas

Intuitivos Sencillos de programar:

AlgoritmoDF(Grafo G)1. Asignar posición inicial a los vértices.2. Repetir hasta que el sistema esté en equilibrio:

1. Seleccionar un vértice v en G.2. Mover v de manera que las fuerzas del sistema disminuyan.

Dan buenos resultados Muy flexibles ¿Desventajas? Más adelante…



13

Spring embedder (Eades, 84) Presentó la analogía de los resortes. Modelo físico:

Fuerzas atractivas:

Fuerza repulsivas: Criterios estéticos que considera:

Distribución de nodos uniforme. Longitud de aristas uniforme.



14

Spring embedder (2)

Algoritmo:

SpringEmbedder(Grafo G)1. Asignar una posición al azar a cada vértice de G.2. Repetir M veces:

1. Para cada vV1. Calcular f(v) (usando las fuerzas de la diapositiva

anterior)

2. Para cada vV1. pv= pv+C4f(v)

Complejidad: O(n3)



15

Mejoras del SE

FR (Fruchterman y Reingold, 91) Otras fuerzas

Atractivas: cuadráticas en la distancia (sin logaritmo).

Repulsivas: inversas a la distancia. Temperatura global para acelerar convergencia.

GEM (Frick et al., 95) Fuerzas similares a las de FR. Temperatura local para cada vértice. Detección de oscilaciones y rotaciones. Misma complejidad que FR y SE.

Pero en la práctica es uno de los más rápidos.



16

Mejoras del SE (2)

SM (Sugiyama y Misue, 95) Algunos resortes están magnetizados. Hay campos magnéticos que influyen

en la dirección de esos resortes.



17

KK (Kamada y Kawai, 89)

Un único tipo de fuerzas (resortes) entre todos los pares de vértices, con longitudes ideales distintas.

Criterio estético que considera: La distancia entre vértices debe ser

igual a la distancia teórica. Mantiene implícitamente los dos criterios

anteriores.



18

KK (2)

Enfoque basado en energía:

Equivalente a usar fuerzas lineales. Para encontrar el mínimo de la

energía usan Newton-Raphson.



19

DH (Davidson y Harel, 89)

Enfoque basado en energía. Modelo: definido por una suma de

potenciales Distribución de nodos. Longitud de aristas. Cruces de aristas. Distancia nodo arista. Espacio de dibujo.

Extremadamente flexible.



20

DH (2)

Algoritmo: utiliza Simulated Annealing Idea básica:Para cada vV

Elegir al azar una nueva posición para v.Si la energía disminuye con esa posición, la acepto.Sino, con cierta probabilidad, la acepto igual.

Cuánto moverse en cada paso depende de una temperatura que va decreciendo. Al comienzo los movimientos son grandes. Y se van haciendo cada vez más cortos.

Es de los algoritmos más lentos.



21

Comparación

No hay muchos estudios que los comparen.

Los pocos que hay (Brandenburg, 95), (Behzadi, 99) concluyen que: Todos obtienen trazados estéticamente

agradables. El más flexible es DH. GEM y KK son los más rápidos, mientras que DH

es el más lento. Conclusión: no hay un ganador universal.



22

Ejemplos

Mismo grafo, distintos algoritmos

GEM

FR

SE

DH KK



23

Desventajas

Tres puntos débiles: Alto costo computacional (en tiempo). Pueden caer en mínimos locales pobres.

Encontrar los óptimos globales es NP-Hard.

Falta de fundamentos teóricos.



24

Aspectos numéricos

Todos los algoritmos dirigidos por fuerzas minimizan una función.

La forma en que lo hacen marca las diferencias entre cada uno.

Todos usan alguna técnica numérica. Aunque en la mayoría de los casos,

está implícita. ¡Hacerla explícita es importante!



25

Fuerzas vs. energía

Los algoritmos se dedican a: Buscar un equilibrio de un sistema físico (ej.

spring embedder, FR, GEM). O a minimizar una función de energía (ej. KK,

DH). Pero son equivalentes

La fuerza neta que afectan a un nodo constituye el gradiente (negativo) de su energía.

Mínimos de energía son equilibrios del sistema de fuerzas.



26

Método del gradiente

Consiste en moverse siempre hacia (menos) la dirección del gradiente. La función que estamos minimizando es la

energía del trazado. El spring embedder mueve cada nodo en

la dirección de la fuerza neta Que es igual a moverse en la dirección opuesta

al gradiente. El spring embedder y sus derivados (FR,

SM, etc.) usan el método del gradiente.



27

Otros métodos de optimización KK usa Newton-Raphson para buscar un

equilibrio. DH usa Simulated Annealing. Tunkelang (99) usa gradiente conjugado. Branke et al. (96) usan algoritmos

genéticos. El algoritmo baricéntrico de Tutte resuelve

un sistema lineal con Gauss-Seidel. ¡Muchos otros son posibles!



28

Trazados 3D

En lugar de buscar posiciones en el plano, buscamos en el espacio.

Ventajas: Más libertad “de movimiento”.

Es más fácil llegar a un equilibrio Los cruces de aristas no son un problema.

Desventajas: Es necesario proyectar los resultados a

2D. ¡Pueden aparecer cruces!



29

A pesar de todo...

Pruebas empíricas indican que se puede trasmitir más información (Dwyer, 00)

El uso de programas interactivos de visualización hace que el usuario visualice el trazado 3D desde cualquier ángulo.

Se hace necesario diseñar algoritmos para trazar grafos en 3D.



30

Adaptar algoritmos a 3D

Algunos son difíciles de llevar a 3D (ej. ortogonales, por capas)

¡Los dirigidos por fuerzas no requieren casi adaptaciones! Los que modelan con resortes no tienen

ningún problema. Tampoco los que usan funciones

generales Otros como KK, GEM y SM requieren

adaptar algunas partes. Pero sigue siendo relativamente fácil.



31

Hay muchas otras adaptaciones posibles Para trazar grafos dinámicos. Para trazar grafos con restricciones:

Vértices con forma y tamaño. Aristas especiales (curvas, con pesos). Restricciones en la posición de los vértices.

Para trazar grafos con clusters. Para trazar grafos grandes.

Comentaremos muy brevemente sobre ellos.



32

Grafos dinámicos

Grafos que cambian a lo largo del tiempo

Se quiere ir trazando el grafo a medida que cambia.

Preservando el “mapa mental”:2 7

1

6

4

3

5

ti

2

7

6

4

3

15

ti+1

2 7

6

4

3

5

1

ti+1, preservandoel mapa mental



33

Grafos dinámicos (2)

Los algoritmos dirigidos por fuerzas se adaptan muy bien a esta situación: Se pueden agregar vértices ficticios (fijos) en las

posiciones anteriores de cada vértices, conectados por resortes a sus respectivos vértices (Brandes et al., 00).

Si se usa DH o similar, se agrega un potencial que penalice ubicar a un vértice lejos de su posición anterior.

También suelen animarse los movimientos El spring embedder y derivados son ideales para

esto.



34

Restricciones

Los grafos que se deben trazar en las aplicaciones concretas suelen “venir” con restricciones.

Una muy común es forma y tamaño: los vértices suelen ser dibujados con figuras geométricas. El tamaño y la forma deben ser

considerados por los algoritmos, sino: Algunos vértices pueden solaparse Algunas aristas pueden atravesar vértices



35

Restricciones (2)

Ejemplo:

A lgor itm os clásicos Spr ing E mbedder

G E M

B ar icéntr ico

F R

D H

Tu

SM



36

Restricciones (3)

Posibles soluciones: Adaptar las longitudes ideales de los

resortes para contemplar forma y tamaño (Wang y Miyamoto, 95), (Harel y Koren, 02).

Agregar potenciales o fuerzas que penalicen el solapamiento de vértices (Kamps et al., 95).

Trazar el grafo normalmente, luego “arreglar” los solapamientos (Gasner y North, 98).

Usar campos potenciales (Chuang et. al, 04).



37

Restricciones (4)

Otras consideraciones: Aristas con pesos.

Se pueden adaptar las longitudes ideales para contemplarlos (Ej. Erbacher et. al, 04).

Aristas curvas. Se toman los puntos de control de las

curvas como vértices, y se traza el grafo “normalmente”. (Ej. Finkel, 04)



38

Restricciones (5)

También puede haber restricciones en la posición de los vértices: Un vértice debe estar fijo. Un vértice debe estar dentro de una región. La distancia entre dos vértices debe ser fija. Y muchas otras.

Muchas soluciones posibles: Son fáciles de integrar al spring embedder. Ej:

Antes de mover cada vértice, controlo que no se viole ninguna restricción.

Si uso DH o similar, puedo agregar un potencial que penalice la violación de las restricciones.



39

Ejemplos

Aristas curvas(Finkel, 04)

Restricciones en los vértices (He y Marriot, 98)



40

Grafos con clusters

Los grafos pueden tener clusters. Objetivo: que el trazado refleje las

agrupaciones entre vértices. Solución sencilla: agregar vértices

atractores (ej. Huang y Eades, 00):



41

Clusters (2)

Ejemplos:(Wang y Miyamoto, 95)

(Huang y Eades, 00)



42

Grafos grandes

La complejidad cúbica de los algoritmos “clásicos” los hace poco prácticos para grafos de más de unos pocos cientos de nodos.

Dos formas de lidiar con grafos grandes: Simulación de N-cuerpos. Algoritmos

multinivel/multidimensionales.



43

Grafos grandes (2)

Simulación de N-cuerpos Problema común en la física.

En nuestro caso, los cuerpos son los vértices.

Objetivo: evitar calcular todas las fuerzas repulsivas, que es O(n2).

Motivación: a medida que los vértices se alejan, las fuerzas repulsivas dejan de tener peso en la fuerza neta.

No calcular todos los pares de fuerzas, sino sólo los de los vértices “más cercanos”.



44

Grafos grandes (3)

Algoritmos multinivel Separan el grafo en distintos niveles de

abstracción. Partiendo del grafo original, se lo va

simplificando hasta llegar a un grafo de unos pocos vértices.

Se hace el trazado de ese grafo simple, se fijan los nodos ubicados y se agregan los del nivel siguiente (Gajer, 00), (Walshaw, 03) (Hachul 04).

La cantidad de nodos “no fijos” es siempre pequeña.



45

Ejemplos

Grafos de unos 1.000 vértices (Gajer et al., 00)

Grafos de 5.000, 15.000 y 88.000 vértices (Walshaw, 03):



46

Trazado inicial

La mayoría de los algoritmos parten de un trazado inicial al azar.

El trazado inicial influye en dos factores: Velocidad de convergencia. Calidad del resultado. Ej.:



47

Trazado inicial (2)

Se pueden realizar trazados más elaborados. Ej.: Para obtener trazados planos de grafos

planares (Harel y Sardas, 95). Para evitar mínimos pobres (Behzadi,

99). Para acelerar la convergencia (Mutton y

Rodgers, 02).



48

Comentarios

La flexibilidad y sencillez de los algoritmos dirigidos por fuerzas ha hecho que surgieran cientos de variantes. Sin existir (hasta ahora) un compendio ordenado

y completo de los algoritmos existentes. En esta tesis se intentó abarcar a todos los

trabajos relevantes. En esta presentación sólo hemos

mencionado algunas de las principales variantes.

Algoritmos para grafos donde los vértices son regiones

geográficas

Parte 2



50

Contenido

Introducción. Análisis y definición de los criterios

estéticos. Algoritmos propuestos.



51

Nuestro problema

“Dado un grafo G = (V,E) y un conjunto de regiones R, donde R es la región (no vacía) del plano representada por el vértice , encontrar un trazado de G en el plano que sea estéticamente bueno y donde para todo vértice ”

Vvvr

vv rp Vv



52

Nuestro problema (2)

Consideraciones generales Regiones representadas por polígonos

o discos. Presentamos nuevas soluciones. Los algoritmos se basaron en SE y DH

pero pueden utilizarse las mismas ideas en cualquier otro.



53

Nuestro problema (3)

Trabajo previo No encontramos trabajos previos para

nuestra problema particular, sino para restricciones parecidas pero que no alcanzan.

Restricciones sobre la posición de vértices Restricciones respecto a otros vértices. (Kamps

et al., 95) (Wang y Miyamoto, 82). Restricciones lineales arbitrarias. (He y Marriot,

98). Restricciones no lineales. (Hansen et al., 02). Limitar los movimientos. (DiBattista et al., 99).



54

Nuestro problema (4) Ejemplo:



55

Similitudes y diferencias

Representar una región vs. estar dentro.

Criterios estéticos. Algoritmos.



56


Análisis de criterios previos. Presentación de nuevos criterios. Criterios especiales para

segmentos.



57

Criterios estéticos: previos

Minimizar cruces entre aristas. Maximizar el ángulo entre aristas

adyacentes. Maximizar el ángulo entre aristas

que se cruzan. Mostrar simetría. Distribución uniforme de los vértices. Longitud uniforme de aristas.



58


Análisis de criterios previos. Presentación de nuevos

criterios. Criterios especiales para

segmentos.



59

Criterios estéticos: nuevos

Los vértices deben estar ubicados cerca del centro de sus regiones.

Los vértices no deben estar cerca de los bordes.



60

Criterios estéticos: nuevos

Análisis de criterios previos. Presentación de nuevos criterios. Criterios especiales para

segmentos.



61

Algoritmos propuestos

¿Por qué no utilizar los algoritmos ya presentados?

Algoritmos utilizados Spring Embedder. DH.



62

Adaptaciones

Forma de proyectar. Longitud ideal de las aristas.

Longitudes fijas ¡NO! Longitudes variables…

Fuerzas centrípetas. Evitar vértices muy cercanos a

los bordes. Minimizar cruces entre aristas.



63

Adaptaciones: aristas de longitud variable (2) Longitud ideal de aristas

Distancia mínima Distancia máxima Distancia entre centros Distancia de compromiso

22 ||||)1(|||| vuvuuv rrccK



64

Adaptaciones: fuerzas hacia el centro (SE) Fuerza centrípeta:

Idea de nodo ficticio

vvvc

c cpd

Cvf v )log()( 1



65

Adaptaciones: fuerzas hacia el centro (DH) Penalizar distancia entre un vértice y su

centro. Potencial: 3)( vcc v

dvU



66

Adaptaciones: evitar vértices muy cercanos a los bordes Implementado en DH. Primera idea:

Segunda idea:

¿Por qué elegir la segunda?

distABordecvU distABorde /)(

)*2()( distABordedistABordeecvU



67

Adaptaciones: minimizar cruces entre aristas

Implementado sobre DH.

Distancia entre todo par de aristas.

221

21

1),(

eeee d

eeU



68

Adaptaciones: minimizar cruces entre aristas (2) Distancia mínima entre vértices y cruces.

2

},,,{21 ||||min),(

2211

vxeeUvuvuv

cr



69

Adaptaciones: SER2 y DHR2

Implementación en Java. Incluyen todas las ideas presentadas. Pueden probarse en http://www

.luchemos.org.ar/rodrigo/tesis.



70

Adaptaciones: SET

Criterio que intenta cumplir: los nodos no deben estar cerca de las aristas.

Agrega fuerza de repulsión nodo-arista. Distancia ideal es la formada por el

triángulo equilátero.



71

Ejemplos

Malla 4x4 utilizando DHR2 y SER2



72

Ejemplos (2)

DH, SER2 y DHR2



73

Ejemplos (3) República Argentina: SER2 y DHR2



74

Conclusiones y aportes

Revisión del estado del arte Abarca la mayor parte de los trabajos

publicados hasta el momento. Incluye los trabajos más recientes. Provee una visión consistente,

comparativa y transversal del tema.



75

Conclusiones y aportes (2)

Algoritmos para grafos donde los vértices son regiones geográficas Se presenta y analiza un nuevo

problema. Se estudian criterios estéticos generales

y se presentan los propios del problema. Se proponen algoritmos para los

criterios definidos. Nuevo potencial para evitar cruces de

aristas.



76

Trabajo futuro

Optimización de los algoritmos. Problema de grafos grandes. Otros tipos de regiones. Trazado inicial. ¡Y muchos más!

¡Muchas gracias!

¿Preguntas?

Para más información: http://www.luchemos.org.ar/rodrigo/tesis

trazado de grafos mediante métodos dirigidos por fuerzas revisión del estado del arte y...

Documents