Page Index Toggle Pages: 1 Send TopicPrint
Hot Topic (More than 10 Replies) Bug in Layouting Algo (Read 7872 times)
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Bug in Layouting Algo
Oct 20th, 2006 at 11:01am
Print Post  
I am evaluating MidFusion for a possible purchase for my requirement.

I have been playing around with layouts and one interesting thing i noticed.

When i have high number of connections than the number of shapes (e.g. 200 Shapes, 450 Connections), Grid Layout causes a machine crash. I checked in the Memory allocation, and when i start Grid layouting, it starts allocating memory. From 414 M it went upto 1.47 GB. I had to terminate the process manually and the Grid layout never finished.

Other layouts also took up a lot of time ... some upto 7 mins, and then came up with a solution.

On Progress function on all layouts, go to 0 from 100 and repeat this cycle for 10 - 12 times.

Has this bugs been known and a solution available in the next release?

I would be using the layouts feature a lot and i need a robust solution.

Otherwise your component is OK.

Cheers

Phil Jacques
  
Back to top
 
IP Logged
 
Stoyo
God Member
*****
Offline


MindFusion support

Posts: 13230
Joined: Jul 20th, 2005
Re: Bug in Layouting Algo
Reply #1 - Oct 20th, 2006 at 12:48pm
Print Post  
It seems there is not enough memory for the algorithm to complete then  Shocked GridLayout and LayeredLayout try to arrange a graph around the longest path in the graph, and finding that time takes a long time for 450 arrows. Probably the LayeredLayout completes successfully because it has a TimeLimit property, and when the path-finding reaches the timeout, the algorithm will use the longest path found up till then. So the GridLayout might complete too if we add a TimeLimit property to it.

You will probably get best times with a TreeLayout, for which the Root property is explicitly specified, so the algorithm does not try to find a root automatically. Also set IgnoreArrowDirection = true. After Arrange(), you might call the Route() method of arrows that go up in the tree, so that they do not cross any nodes.

Stoyan
  
Back to top
 
IP Logged
 
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Re: Bug in Layouting Algo
Reply #2 - Oct 20th, 2006 at 1:31pm
Print Post  
Hello Stoyan,

Well ... my machine is 1 Gig RAM with a huge PageFile. I understand this is good enough for any component.

I see a random memorz allocation in the Memory, when the Grid Layout is invoked.

how do i set a time limit to the Grid Layout?
Also you said the Tree Lazout is the fastest because it has a root node set, so if that is the case can i set the root node in other layouts, since i know the root node.

Tree lazout does not work for my requirement, i would be mostly using Spring and Grid Layouts.

I would be working with 600 - 1200 Shapes and 800 - 1600 Connections ... Min max values. I am also not sure about the zoom as i am finding some problems in it. Will do some more R & D and post if i find anzthing related to that.

If you can suggest me ways of reducing the time taken for Grid layout, it would be wonderful. I waited for 2 hrs, but the Grid layout still did not appear.  Cry

Cheers

Phil
  
Back to top
 
IP Logged
 
Stoyo
God Member
*****
Offline


MindFusion support

Posts: 13230
Joined: Jul 20th, 2005
Re: Bug in Layouting Algo
Reply #3 - Oct 20th, 2006 at 4:29pm
Print Post  
Hi,

I guess the algorithm runs into a combinatorial explosion while looking for the longest path. And it stores some of the found paths in order to check for cycles later, so the memory allocation grows...

It does not matter how much RAM and page file you have - a 32-bit Windows process can use at most 2GB of memory.

Currently you can't set a limit on the grid layout path-finding part; first we will have to add a new GridLayout property to let you do that.

There is some chance that the grid layout will work faster and with less memory allocations if you explicitly set StartNode and EndNode.

Stoyan
« Last Edit: Oct 21st, 2006 at 4:18pm by Stoyo »  
Back to top
 
IP Logged
 
Slavcho
YaBB Moderator
*****
Offline


tech.support

Posts: 3380
Joined: Oct 19th, 2005
Re: Bug in Layouting Algo
Reply #4 - Oct 21st, 2006 at 3:12pm
Print Post  
Hi there,

The grid layout produces better results if it starts from the longest graph path as a diagonal in the grid. Now it seems that looking for that path is not such a good idea when there are more than 30-40 edges in the graph Cry

This updated dll adds an UseLongestPath property to GridLayout. Set UseLongestPath = false and the layout will run faster.

https://mindfusion.org/_beta/gridlt.zip

g.
  
Back to top
 
IP Logged
 
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Re: Bug in Layouting Algo
Reply #5 - Oct 22nd, 2006 at 7:08pm
Print Post  
Heyy Glavcho,

Thanks a lot for the DLL
Well i am working on case studies of ore than 600 shapes and 800 connections and that would be more edges ...

Well i will certainly try out my tests using new dlls.

Whats funny is that, as i go on increasing the number fo shapes and connections, all layouts except Spring and tree seem to get sluggish. Anneal layout is too bad on timing, it takes a full 35 mins to rearrange and hangs on 88% completion for eternity.

For large nuber of shapes and connections, anneal layout does not even show the progress.

Frankly i would like to know if layouting would work for more complex diagrams like 600 - 800 shapes and upto 1000 connections?

What would be the implications?

Cheers

Phil
  
Back to top
 
IP Logged
 
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Re: Bug in Layouting Algo
Reply #6 - Oct 23rd, 2006 at 8:44am
Print Post  
Update :
For a diagram with 500 boxes and 750 connections, the Grid layout took 7 mins from what was infinite.

So thats really good. bu i still want it to be faster.

Any more suggestions??

Cheers

Phil.
  
Back to top
 
IP Logged
 
Slavcho
YaBB Moderator
*****
Offline


tech.support

Posts: 3380
Joined: Oct 19th, 2005
Re: Bug in Layouting Algo
Reply #7 - Oct 23rd, 2006 at 5:55pm
Print Post  
Hey Phil

Can't think of anything right now, apart from decreasing the number of iterations run by the grid or anneal layout functions. A part of the grid layout relies on the arrows routing feature, so increasing the GridSize property of FlowChart.RoutingOptions might speed it up a bit too. We can try to optimize the layouts in the following couple of weeks. we'll start with GridLayout if it's what you are most interested in.

g.
  
Back to top
 
IP Logged
 
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Re: Bug in Layouting Algo
Reply #8 - Oct 24th, 2006 at 8:57am
Print Post  
Heyy Glavcho,

I played around with the Grid Layout a bit. I tried reducing the interations from 3000 to 50 and increasing the grid size.

It did speed up the algo.

But i think there are 2 parts here. The above actions speeds up the computation part, but the control still hangs till the diagram is displayed. Sometimes it is like waiting for more than 2 mins (Reading from System.Diagnostics.Stopwatch) after the computation has become 100% and before the diagram is displayed on the control.

Maybe something in the Painting routine makes it wait for such a long time.

Best part is that the layout works with 1000 shapes and 2000 connections. So not bad Smiley

Cheers

Phil
  
Back to top
 
IP Logged
 
Slavcho
YaBB Moderator
*****
Offline


tech.support

Posts: 3380
Joined: Oct 19th, 2005
Re: Bug in Layouting Algo
Reply #9 - Oct 24th, 2006 at 9:25am
Print Post  
oh well, the progress reaches 100% just before starting the arrow-routing part. me thinks we should run some progress counting there too  Grin

g.
  
Back to top
 
IP Logged
 
Phil Jacques
Junior Member
**
Offline


.NET 2.0 Rocks!!!

Posts: 70
Joined: Oct 20th, 2006
Re: Bug in Layouting Algo
Reply #10 - Oct 24th, 2006 at 11:11am
Print Post  
Oh ... that would be great.

hopefully there would not be a need of progress counting on Progress counters ...  Grin

Cheers

Phil
  
Back to top
 
IP Logged
 
Page Index Toggle Pages: 1
Send TopicPrint