Smalltalk › Frameworks & Tools › Moose

ForceLayout is slow for too many elements.

‹ Previous Topic Next Topic ›
 
classic Classic list List threaded Threaded
♦
♦
 10 messages Options
Demian Schkolnik
Reply | Threaded
Open this post in threaded view
♦
♦
|

ForceLayout is slow for too many elements.

Demian Schkolnik
Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Peter Uhnak
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Peter Uhnak
You can see a semi-overview of layouts here https://dl.dropboxusercontent.com/u/31543901/AgileVisualization/Layout/0107-Layout.html
or inside image in Roassal Examples > Layouts

It may be my imagination, but I think Natalia Tymchuk was working on a faster version?

In any case, you can specify number of iterations for ForceBasedLayout with nbIterations:

~~~~~~~~~~~~~
RTForceBasedLayout new
nbIterations: 1000;
on: elements.
~~~~~~~~~~~~~

obviously with fewer iterations the layout will get worse.

Also, how many elements is "many"?

Peter

On Wed, Jul 29, 2015 at 8:53 PM, Demian Schkolnik <[hidden email]> wrote:
Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev



_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
abergel
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

abergel
In reply to this post by Demian Schkolnik
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Demian Schkolnik
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Demian Schkolnik
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Demian Schkolnik
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Demian Schkolnik
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Demian Schkolnik
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Demian Schkolnik
I am just using GridLayout. It works really fast.

El mié., 29 de jul. de 2015 a la(s) 5:05 p. m., Demian Schkolnik <[hidden email]> escribió:
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Tudor Girba-2
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Tudor Girba-2
Of course it does. But, perhaps at least you can try circle layout.

Doru

On Wed, Jul 29, 2015 at 10:14 PM, Demian Schkolnik <[hidden email]> wrote:
I am just using GridLayout. It works really fast.

El mié., 29 de jul. de 2015 a la(s) 5:05 p. m., Demian Schkolnik <[hidden email]> escribió:
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev




--

"Every thing has its own flow"

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Peter Uhnak
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Peter Uhnak
Can you send a screenshot?

It's hard to judge the complexity of RTForceBasedLayout since the implementation is quite complex, but I see at least one what looks like O(V^2) (RTForceBasedLayout>>accumulate: method)... and that's just for a single step.

So for 500 nodes that's 0.25M operations per step?
Google tells me that this can be as fast as O(V log(V)) so maybe this is worth looking into sometime. (And Natalia was most certainly talking about this at ESUG).

Peter

On Wed, Jul 29, 2015 at 10:21 PM, Tudor Girba <[hidden email]> wrote:
Of course it does. But, perhaps at least you can try circle layout.

Doru

On Wed, Jul 29, 2015 at 10:14 PM, Demian Schkolnik <[hidden email]> wrote:
I am just using GridLayout. It works really fast.

El mié., 29 de jul. de 2015 a la(s) 5:05 p. m., Demian Schkolnik <[hidden email]> escribió:
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev




--

"Every thing has its own flow"

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev



_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Demian Schkolnik
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

Demian Schkolnik
Sure! Here is a shot of everything in gridLayout time is less than 2 seconds.. as where with grid this takes more than 15 (I am running pharo on a linux VM so consider it extra slow.. but anyway..)graph1.png
El mié., 29 de jul. de 2015 a la(s) 6:23 p. m., Peter Uhnák <[hidden email]> escribió:
Can you send a screenshot?

It's hard to judge the complexity of RTForceBasedLayout since the implementation is quite complex, but I see at least one what looks like O(V^2) (RTForceBasedLayout>>accumulate: method)... and that's just for a single step.

So for 500 nodes that's 0.25M operations per step?
Google tells me that this can be as fast as O(V log(V)) so maybe this is worth looking into sometime. (And Natalia was most certainly talking about this at ESUG).

Peter

On Wed, Jul 29, 2015 at 10:21 PM, Tudor Girba <[hidden email]> wrote:
Of course it does. But, perhaps at least you can try circle layout.

Doru

On Wed, Jul 29, 2015 at 10:14 PM, Demian Schkolnik <[hidden email]> wrote:
I am just using GridLayout. It works really fast.

El mié., 29 de jul. de 2015 a la(s) 5:05 p. m., Demian Schkolnik <[hidden email]> escribió:
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev




--

"Every thing has its own flow"

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
abergel
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: ForceLayout is slow for too many elements.

abergel
In reply to this post by Peter Uhnak
Hi Peter, 

This layout is actually a copy from the layout in D3. It uses a complexity n*log n.
I have just verified this as follows:

Here is what is the function n * log n :

And apparently, the force based layout performance follows the same curve.
Doing the layout on a variable number of nodes (no edges then)
-=-=-=-=-=-=-=-=-=-=-=-=
values := (1 to: 1000 by: 100) collect: [ :it |
[v := RTView new.
es := RTBox elementsOn: (1 to: it).
v addAll: es.
RTForceBasedLayout on: es. ] timeToRun
].
(values collect: #asMilliseconds) plot 
-=-=-=-=-=-=-=-=-=-=-=-=

Making the number of edges varying:
-=-=-=-=-=-=-=-=-=-=-=-=
values := (1 to: 299 by: 10) collect: [ :it |
[v := RTView new.
es := RTBox elementsOn: (1 to: 300).
v addAll: es.
edges := RTEdgeBuilder new
view: v;
elements: es;
connectFrom: [ :aValue | aValue // 2 ].
(edges copyFrom: it to: edges size) do: #remove.
RTForceBasedLayout on: es.
v] timeToRun ].
(values collect: #asMilliseconds) plot 
-=-=-=-=-=-=-=-=-=-=-=-=

All indicates that the algo we use is n log n.

Cheers,
Alexandre

-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 6:21 PM, Peter Uhnák <[hidden email]> wrote:

Can you send a screenshot?

It's hard to judge the complexity of RTForceBasedLayout since the implementation is quite complex, but I see at least one what looks like O(V^2) (RTForceBasedLayout>>accumulate: method)... and that's just for a single step.

So for 500 nodes that's 0.25M operations per step?
Google tells me that this can be as fast as O(V log(V)) so maybe this is worth looking into sometime. (And Natalia was most certainly talking about this at ESUG).

Peter

On Wed, Jul 29, 2015 at 10:21 PM, Tudor Girba <[hidden email]> wrote:
Of course it does. But, perhaps at least you can try circle layout.

Doru

On Wed, Jul 29, 2015 at 10:14 PM, Demian Schkolnik <[hidden email]> wrote:
I am just using GridLayout. It works really fast.

El mié., 29 de jul. de 2015 a la(s) 5:05 p. m., Demian Schkolnik <[hidden email]> escribió:
So, I tried with 10 iterations, and it gets stuck anyway. I counted the elements, and there are ~500 nodes and ~500 edges in my graph... Again, I do not need nothing fancy, with having just all elements NOT clustered together in the middle (like with no layout), I'm ok.. (well, tree layout does not work for me due to the fact that it lays out a row of 500 elements to the side- not bringing visibillity). Thanks again!

El mié., 29 de jul. de 2015 a la(s) 4:16 p. m., Demian Schkolnik <[hidden email]> escribió:
Hello! i will try fewer iterations. I think I may have between 200 and 500 elements total.. I will try it out inmediately and let you know.

El mié., 29 de jul. de 2015 a la(s) 4:13 p. m., Alexandre Bergel <[hidden email]> escribió:
This is a hard problem that many in the graph theory have spent a lot of time on.
Reduce the amount of iterations maybe. This layout is useful when you do not have any apparent structure in your data. What is the structure of your data?

Alexandre
-- 
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:
Alexandre Bergel  http://www.bergel.eu
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

On Jul 29, 2015, at 3:53 PM, Demian Schkolnik <[hidden email]> wrote:

Hi all! 
I want to make a visualization of a graph (nodes and edges), but applying ForceLayout to it takes forever, because the graph has too many elements. if I apply TreeLayout, for example, the view renders almost instantly. Is there some other Layout, similar to ForceLayout, but faster, for so many elements?
Thanks!
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev




--

"Every thing has its own flow"

_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev


_______________________________________________
Moose-dev mailing list
[hidden email]
https://www.iam.unibe.ch/mailman/listinfo/moose-dev
Free forum by Nabble Edit this page