Buscar Libreria de grafos

[NicolasDiTomaso]

Luego de un test de carga de springy.js, se nota que es un desastre con solo 500 nodos: http://jsfiddle.net/pj7a3j1g/5/ (en el ejemplo lo deje en 100 para tener cierto control sobre el browser...)

Investigando un poco sobre sigma.js encontre esto: Linkurious Basicamente es una version mejorada de sigma.js, segun ellos con soporte de hasta 2000 nodos

Obviamente tambien esta D3, con sus millones de ejemplos.

En general todos los forced graph parecen ser demasiado lentos con muchos nodos, quiza convenga olvidarse de estos y ver un grafo simple?

Como extra.... quiza se pueda renderizar con webgl? supuestamente solo soportado por equipos con placa de video, pero mucho mas rapido....

ideas?

[eldipa]

yap, lo probe en la netbook y Linkurious es mucho mas rapido. El problema esta en que aun necesitamos resolver las posiciones de los nodos y la solucion general es usar un forced layout.

Dependiendo de que datos mostremos en el grafo se puede tomar esos datos para guiar las posiciones de los nodos: digamos que el grafo es de procesos, como sabemos que hay una relacion entre padre e hijos de 1-a-n y que el grafo no es ciclico, las posiciones podemos asignarlas de forma radial, con el primer proceso en el 0,0; sus hijos posicionados en un radio de R=1; sus nietos en R=2.

Respecto a webgl, si el framework lo soporta webgl seria la opcion mas optima (en teoria). En segundo lugar seria canvas y por ultimo svg (siempre pensandolo en terminos de performance de renderizado) Por default d3 labura con svg aunque hay formas de cambiar el graph de d3 a una implementacion basada en canvas http://vallandingham.me/d3_without_svg.html

Tal vez se puede mixear. Usamos d3 para calcular las posiciones y Linkurious para renderizar... .. quien sabe, tal vez sacamos lo mejor de los 2 mundos.

[NicolasDiTomaso]

Viendo la alternativa de linkurious, el hecho de usar webGL es tan simple como cambiar un atributo, la contra es que se necesita procesamiento grafico. En la maquina vitual no tengo soporte para webGL, en la pc normal el grafo vuela (pero tengo señora placa de video). Podes probar este ejemplo en lo que seria una maquina normal? https://jsfiddle.net/oghonrLk/1/ Son 2000 nodos y 1000 aristas, de funcionar bien, quedaria ver el tema del force graph, pero parece algo bueno por donde empezar.

[NicolasDiTomaso]

Pseudo-decepcion con el linkurious. Si bien grafica muy rapido, el algoritmo de force graph no anda tan bien, 500 nodos ya le duele y sin graficar nada, pura simulacion: http://codepen.io/anon/pen/xZmYGV#0 Casi de casualidad me encontre con este js, dedicado exlusivamente a force graph de altas cantidad de nodos. VivaGraph, usa directamente webgl y grafos locos me uso tranquilamente 25% de gpu (win7 con opengl activo). Aca muestra una comparativa de las distintas librerias, incluyendo sigma y D3: https://www.youtube.com/watch?v=Ax7KSQZ0_hk Por favor, prova algunos de estos ejemplos en tu maquina y comentame los resultados, de este lado se veian prometedores: http://www.yasiv.com/graphs#HB/blckhole

[eldipa]

A mi me consume entre 50% y 90% y luego de un par de minutos sigue corriendo. Digamos que no me dejo una buena impresion :) Use chrome y sin webgl. Aparentemente el cuello de botella seria el renderizado, pero como tampoco termino la simulacion, no se si no hay algo mas.

Es claro que no hay una salida magica, asi que hagamos un TODO list sobre las cosas que si o si deben estar (agrega mas o comenta lo que creas conveniente):

• Forced layout: Si vamos a renderizar cosas variables como procesos e IPC, calcular todas sus posiciones nosotros no parece viable y en ultima instancia seria tan malo como demas libs. Yo aca veo 2 situaciones claramente distintas:
  1. Arrancamos con un grafo vacio al cual le ponemos todos los procesos e IPCs y dejamos que corra el algoritmo para tener una version inicial.
  2. Dado ya un grafo, procesos / IPCs nuevos aparecen y otros desaparecen, pero entiendo yo que son cambios menores.
• De lo anterior saco que la lib debe poder soportar modificaciones al grafo y realizar los ajustes del layout necesarios pero no empezar todo desde cero, como todos los nodos arrancaran con posiciones random otra vez.
  • Debe ser capaz de que nosotros le definamos un xy inicial. De esa manera el lib empezara a mover los nodos partiendo de esa posicion y no de una random. La ventaja de esto esque podemos armar por primer vez el grafo de procesos (sin los IPCs) con posiciones calculadas por nosotros como lo describi en un comentario anterior en este issue. Obviamente luego se iran agregando los IPCs al grafo y sera la lib que reajuste la posicion de todos los nodos, no nosotros, pero estimo que eso es mas facil de alcazar en vez de pedirle a lalib que arranque de cero (basicamente nos aprovechamos de la organizacion jerarquica de los procesos, algo que la lib no puede saber de antemano)
• La lib debe exponer los parametros de amortiguacion, spring, bla bla bla.
• Supongamos que tenemos un grafo ya armado. El drag de un nodo o el panneo de la pantalla tienen lag? Es facil agregar un tooltipo a un nodo y/o arista cosa que nos sea facil agregar data al grafo?
• Dado q un problema grande es el rendering, la lib debe permitirnos decidir cuando renderizar. La lib estara actualizando la posicion de los nodos cada cierto epsilon de tiempo E pero nosotros renderizamos cada 5E, asi no saturamos al render.

[NicolasDiTomaso]

No digo que el el renderizado no pese nada, pero de las pruebas que hago aca, la mayor parte de la culpa se la lleva la simulacion, en el primer ejemplo que pase, el de linkurious, si aumentos la cantidad de nodos, si miras la consola vas a ver que esta mucho mas tiempo calculando la posicion final que calculando la animacion ( y mucho menos dibujandola ). Por que no usaste webgl? la idea era ver si este metodo ayudaba algo o no al render. Me acuerdo que al principio habias hecho un grafo de procesos, te acordas cuando nodos dibujaba? (aprox) Estuve pensando, de no ser posible armar un grafo tan grande con las herramientas que tenemos, hacerlo mas chico y fue. Por ejemplo en un comienzo no mostramos nada, que haya un boton que muestre una lista de procesos (ps -e) de ahi se seleccionan los que se quieren usar y los mismos se agregan al grafo. Podriamos poner como extra, que al agregar un proceso al grafo ademas se agregen padres/hijos (podemos obtener esto?) e ipcs. Obviamente cada vez que se lanza el mismo se agrega al grafo. De esta forma solo graficariamos los procesos que estamos usando, con la posibilidad de agregar los que el usuario quiera pero bajo demanda. En cuanto a la lista no tengo nada que agregar, creo que cubriste ya todos los puntos importantes.

[eldipa]

Si no me equivoco, el grafo original (el hecho en d3) mostraba todos los procesos corriendo. Para tener una idea, en mi maquina ahora hay 189 procesos y se mostraban las relaciones padre-hijo lo que da un total de 189 aristas y 189 nodos.

Bien, entonces que lib usamos? cual encaja mejor con los items de la lista?

[NicolasDiTomaso]

Debido a Edesur esta semana tuve mas dias sin luz que con, por lo que aun me falta probar la libreria de D3 a ver como rinde. Hay cosas que no me contestaste. Repito: Vivagraph lo probaste sin webgl... por que? La idea de webgl es agilizar el renderizado del grafo. La idea de graficar menos nodos que te parece? por lo que me decis, el grafo original tenia mucho menos de los 2000 nodos que estoy intentando usar, si vajamos el limite a 500 nodos con 500 aristas, administrando de alguna manera lo que se esta mostrando (vista de procesos solos, vista de gdbs, vista de inferiors, viste de ipcs), o agregando nodos bajo demanda, podemos hacer que funcionen estas libs. De momento me falta probar D3 y la ganadora entre linkurious y D3 probarla en nodeweb.

[eldipa]

si aca la cosa tambien estuvo "cortada", respecto a webgl logre probarlo. Por alguna razon me tiraba que no habia soporte en mi browser para webgl. Si bien no es super rapido, al menos es usable. Lo unico que me llama la atencion es que luego de la simulacion me queda un cpu casi al palo, a vos te paso lo mismo? Es como si la simulacion continuara.

Respecto a qeu mostrar, es claro que ninguna lib deja una buena impresion con 2000 nodos (algunas zafan, otras no). de momento, renderizar todos los procesos al principio y luego los ipcs bajo demanda es mas acertado, sino se va a colgar todo.

[NicolasDiTomaso]

Luego de probar D3, dado el hecho que se bajo la exigencia de 2000 nodos a 500, la gran cantidad de documentacion que existe del mismo hace que sea la mejor opcion para nuestras necesidades. Con un poco de paciencia logre hacer esta demo: http://codepen.io/anon/pen/qbeOde En la demo el grafo se expande para tomar todo el espacio posible, toma el resize y se ajusta al mismo, evita colisiones entre nodos(que queden superpuestos),permite skipear renderizados, mostrar tooltips, iniciar y detener la animacion a gusto. Me queda ver como lograr como realizar panning y zooming, drag sin renderizar todo (este lo logre hacer con unos errores, lo saque de la demo), ademas del critico test sobre lo mismo andando en node-webkit

Probalo a ver como te corre, y juga con la variable skipFrame para ver la diferencia de tiempos y estetica al saltear renderizados. Se aceptan opiniones, criticas, etc.

[eldipa]

Quedo muy bonito. En la netbook tardo 10segs en renderizar todo (y que la simulacion termine) y quedo con un 7% de cpu, que me imagino que es ruido de la maquina y nada mas.

Ahora hay que hacer la prueba de fuego y ver que en NW funcione.

[NicolasDiTomaso]

Dado que D3 cumple con lo pedido (aun queda algunos detalles por probar). Cierro este ticket, se sigue la discucion del visor de procesos en otro ticket.