This Bugzilla instance is a read-only archive of historic NetBeans bug reports. To report a bug in NetBeans please follow the project's instructions for reporting issues.

Bug 183568

Summary: VMD Slowness
Product: platform Reporter: estevan.diedrich
Component: GraphAssignee: issues@platform <issues>
Status: NEW ---    
Severity: normal CC: dev, shanbo, users
Priority: P3 Keywords: PERFORMANCE
Version: 6.x   
Hardware: PC   
OS: Windows Vista   
URL: http://forums.netbeans.org/post-64144.html
Issue Type: DEFECT Exception Reporter:
Bug Depends on: 119999    
Bug Blocks:    
Attachments: Project to simulate the issue

Description estevan.diedrich 2010-04-06 13:46:07 UTC
Name: AWT-EventQueue-1
State: RUNNABLE
Total blocked: 168  Total waited: 6.363

Stack trace: 
org.netbeans.modules.visual.router.OrthogonalSearchRouterRegion.cloneWithEdge(OrthogonalSearchRouterRegion.java:275)
org.netbeans.modules.visual.router.OrthogonalSearchRouterRegion.cloneWithClockwiseEdge(OrthogonalSearchRouterRegion.java:265)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:223)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:222)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:222)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:222)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:229)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.search(OrthogonalSearchRouterCore.java:222)
org.netbeans.modules.visual.router.OrthogonalSearchRouterCore.route(OrthogonalSearchRouterCore.java:107)
org.netbeans.modules.visual.router.OrthogonalSearchRouter.routeConnection(OrthogonalSearchRouter.java:163)
org.netbeans.api.visual.widget.ConnectionWidget.calculateRouting(ConnectionWidget.java:527)
org.netbeans.modules.visual.layout.ConnectionWidgetLayout.layout(ConnectionWidgetLayout.java:109)
org.netbeans.api.visual.widget.Widget.layout(Widget.java:1350)
org.netbeans.api.visual.widget.Widget.layout(Widget.java:1342)
org.netbeans.api.visual.widget.LayerWidget.layout(LayerWidget.java:86)
org.netbeans.api.visual.widget.Widget.layout(Widget.java:1342)
org.netbeans.api.visual.widget.Scene.layoutScene(Scene.java:315)
org.netbeans.api.visual.widget.Scene.validate(Scene.java:396)
org.netbeans.modules.vmd.flow.FlowAccessController$1$1.run(FlowAccessController.java:97)
org.openide.util.Mutex.readAccess(Mutex.java:362)
org.netbeans.modules.vmd.api.model.TransactionManager$1.run(TransactionManager.java:87)
org.openide.util.Mutex.readAccess(Mutex.java:362)
org.netbeans.modules.vmd.api.model.DescriptorRegistry$2.run(DescriptorRegistry.java:121)
org.openide.util.Mutex.readAccess(Mutex.java:362)
org.netbeans.modules.vmd.api.model.GlobalDescriptorRegistry.readAccess(GlobalDescriptorRegistry.java:159)
org.netbeans.modules.vmd.api.model.DescriptorRegistry.readAccess(DescriptorRegistry.java:119)
org.netbeans.modules.vmd.api.model.TransactionManager.readAccess(TransactionManager.java:85)
org.netbeans.modules.vmd.flow.FlowAccessController$1.run(FlowAccessController.java:83)
java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:209)
java.awt.EventQueue.dispatchEvent(EventQueue.java:597)
org.netbeans.core.TimableEventQueue.dispatchEvent(TimableEventQueue.java:125)
java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:273)
java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:183)
java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:173)
java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:168)
java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:160)
java.awt.EventDispatchThread.run(EventDispatchThread.java:121)
Comment 1 Karol Harezlak 2010-04-06 13:49:19 UTC
Could you provide more information about issue and how to reproduce it. Thanks.
Comment 2 estevan.diedrich 2010-04-06 13:59:11 UTC
(In reply to comment #1)
> Could you provide more information about issue and how to reproduce it. Thanks.

Hi Karol Harezlak,

Follows a fragment taken from this link http://forums.netbeans.org/post-64144.html

"Hello,
yesterday I adopted the example from http://wiki.netbeans.org/VisualDatabaseExplorer and changed it for my needs. My database has about 30 tables (which are rendered as VMDNodeWidgets) with a lot of foreign keys (which are rendered as edges). With its default router the application completely hangs. Even after 10 minutes the app was absolutely inresponsive. I changed the router to one which directly connects the pins (I don't remember its class name), then it worked but was really really slow.
So I decided to stop this adventure. In my mind VMD is only usable with a very limited number of nodes. For my requirements it make no sense.

I'm disappointed
Hermann"

So, my problem is when my graph in VMD have 30 nodes or more.

Thanks,
Diedrich.
Comment 3 Karol Harezlak 2010-04-06 14:04:40 UTC
Is it possible to add your ziped Mobility project to this issue?
Comment 4 David Kaspar 2010-04-06 14:28:51 UTC
This issue is caused by:
http://netbeans.org/bugzilla/show_bug.cgi?id=119999
Comment 5 estevan.diedrich 2010-04-06 14:30:33 UTC
Created attachment 96781 [details]
Project to simulate the issue

This project is using the Floggy Framework, http://floggy.sourceforge.net/
At floggy page you can find how to configure floggy in this project.

thanks,
Diedrich.
Comment 6 estevan.diedrich 2010-04-06 15:06:06 UTC
(In reply to comment #4)
> This issue is caused by:
> http://netbeans.org/bugzilla/show_bug.cgi?id=119999

Hi Kaspar,

I followed the link you sent and i replace my jar by that available, but my netbeans throws the follows exception:

can you help me ?

thanks,
Diedrich.

java.lang.NoSuchMethodError: org.netbeans.api.visual.anchor.Anchor.allowsArbitraryConnectionPlacement()Z
	at org.netbeans.modules.visual.router.OrthogonalSearchRouter.routeConnection(OrthogonalSearchRouter.java:143)
	at org.netbeans.api.visual.widget.ConnectionWidget.calculateRouting(ConnectionWidget.java:523)
	at org.netbeans.modules.visual.layout.ConnectionWidgetLayout.layout(ConnectionWidgetLayout.java:112)
	at org.netbeans.api.visual.widget.Widget.layout(Widget.java:1350)
	at org.netbeans.api.visual.widget.Widget.layout(Widget.java:1342)
	at org.netbeans.api.visual.widget.LayerWidget.layout(LayerWidget.java:86)
	at org.netbeans.api.visual.widget.Widget.layout(Widget.java:1342)
	at org.netbeans.api.visual.widget.Scene.layoutScene(Scene.java:315)
	at org.netbeans.api.visual.widget.Scene.validate(Scene.java:396)
	at org.netbeans.modules.vmd.flow.FlowAccessController$1$1.run(FlowAccessController.java:97)
	at org.openide.util.Mutex.readAccess(Mutex.java:362)
	at org.netbeans.modules.vmd.api.model.TransactionManager$1.run(TransactionManager.java:87)
	at org.openide.util.Mutex.readAccess(Mutex.java:362)
	at org.netbeans.modules.vmd.api.model.DescriptorRegistry$2.run(DescriptorRegistry.java:121)
	at org.openide.util.Mutex.readAccess(Mutex.java:362)
	at org.netbeans.modules.vmd.api.model.GlobalDescriptorRegistry.readAccess(GlobalDescriptorRegistry.java:159)
	at org.netbeans.modules.vmd.api.model.DescriptorRegistry.readAccess(DescriptorRegistry.java:119)
	at org.netbeans.modules.vmd.api.model.TransactionManager.readAccess(TransactionManager.java:85)
[catch] at org.netbeans.modules.vmd.flow.FlowAccessController$1.run(FlowAccessController.java:83)
	at java.awt.event.InvocationEvent.dispatch(InvocationEvent.java:209)
	at java.awt.EventQueue.dispatchEvent(EventQueue.java:597)
	at org.netbeans.core.TimableEventQueue.dispatchEvent(TimableEventQueue.java:125)
	at java.awt.EventDispatchThread.pumpOneEventForFilters(EventDispatchThread.java:273)
	at java.awt.EventDispatchThread.pumpEventsForFilter(EventDispatchThread.java:183)
	at java.awt.EventDispatchThread.pumpEventsForHierarchy(EventDispatchThread.java:173)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:168)
	at java.awt.EventDispatchThread.pumpEvents(EventDispatchThread.java:160)
	at java.awt.EventDispatchThread.run(EventDispatchThread.java:121)
Comment 7 David Kaspar 2010-04-06 16:02:59 UTC
Replacing the JAR is not good idea since the JAR provided by einself@netbeans.org is compiled against NetBeans 6.1 beta. The Anchor.allowsArbitraryConnectionPlacement has been introduced in NB 6.5. It would be better to ask the author mentioned above for a newer version of the JAR.

Regarding the original issue: This "slowness" issue is hard to fix. Maybe it would be easier work around it in the VMD tool by having a special ToggleButton in its toolbar or somewhere for switching between Direct and OrthogonalSearch routing algorithms.

Sorry for that - this algorithm was not meant to be used in such a "large" scenes. P.S.: Another possibility it to split your design file into one Visual MIDlet and several VisualDesign files. Each of them can be edited separately and you can connect them using Entry Point and Call Point components.
Comment 8 estevan.diedrich 2010-04-06 16:39:49 UTC
(In reply to comment #7)
> Replacing the JAR is not good idea since the JAR provided by
> einself@netbeans.org is compiled against NetBeans 6.1 beta. The
> Anchor.allowsArbitraryConnectionPlacement has been introduced in NB 6.5. It
> would be better to ask the author mentioned above for a newer version of the
> JAR.
> 
> Regarding the original issue: This "slowness" issue is hard to fix. Maybe it
> would be easier work around it in the VMD tool by having a special ToggleButton
> in its toolbar or somewhere for switching between Direct and OrthogonalSearch
> routing algorithms.
> 
> Sorry for that - this algorithm was not meant to be used in such a "large"
> scenes. P.S.: Another possibility it to split your design file into one Visual
> MIDlet and several VisualDesign files. Each of them can be edited separately
> and you can connect them using Entry Point and Call Point components.

Hi Kaspar,

I think a good idea split my Visual MIDlet in several VisualDesign files because it would make my project more modular.

Unfortunitly i dont think about this before.

Thanks for your help.
Diedrich.
Comment 9 _ tboudreau 2010-04-06 16:54:19 UTC
Probably OrthogonalSearchRouterCore.search could be passed a "depth" int value which each recursive call increments.  If the depth hits some threshold level, throw an exception which ConnectionWidget.calculateRouting() can catch, in which case it replaces the router with a direct one and tries again.  Or perhaps the choice can be precomputed based on the number of scene elements.
Comment 10 David Kaspar 2010-04-07 07:53:11 UTC
(In reply to comment #9)
> Probably OrthogonalSearchRouterCore.search could be passed a "depth" int value
> which each recursive call increments.  If the depth hits some threshold level,
> throw an exception which ConnectionWidget.calculateRouting() can catch, in
> which case it replaces the router with a direct one and tries again.  Or
> perhaps the choice can be precomputed based on the number of scene elements.

The OrthogonalSearchRouterCore.search has OSRRegion parameter which has depth property that represents the depth in search. Currently the maximal depth is defined by OrthogonalSearchRouterCore.MAXIMAL_DEPTH constant. Additionally there are other constants that can may improve the performance.

The biggest part of the "slowness" is caused by the edges (not nodes). Since a typical edge is represented as 2-3 vertical and 2-3 horizontal collision region i.e. similarly as +- 2-3 nodes. Therefore it would significantly improve performance if the edges would not be incorporated to the collision-collection. Note that the edges may (and in a common scenario will) overlap each other. This may be implemented directly in the VMD by replacing the Router creation with the following code:
edgeRouter = RouterFactory.createOrthogonalSearchRouter (new OrthogonalCollisionsCollector (mainLayer));
// NOTE - the connectionLayer is not inspected for collisions to improve router performance

The core issue is that the algorithm itself has exponential complexity so it will never scale - we can just postpone the "slowness".
Comment 11 estevan.diedrich 2010-04-07 13:00:58 UTC
(In reply to comment #10)
> (In reply to comment #9)
> > Probably OrthogonalSearchRouterCore.search could be passed a "depth" int value
> > which each recursive call increments.  If the depth hits some threshold level,
> > throw an exception which ConnectionWidget.calculateRouting() can catch, in
> > which case it replaces the router with a direct one and tries again.  Or
> > perhaps the choice can be precomputed based on the number of scene elements.
> 
> The OrthogonalSearchRouterCore.search has OSRRegion parameter which has depth
> property that represents the depth in search. Currently the maximal depth is
> defined by OrthogonalSearchRouterCore.MAXIMAL_DEPTH constant. Additionally
> there are other constants that can may improve the performance.
> 
> The biggest part of the "slowness" is caused by the edges (not nodes). Since a
> typical edge is represented as 2-3 vertical and 2-3 horizontal collision region
> i.e. similarly as +- 2-3 nodes. Therefore it would significantly improve
> performance if the edges would not be incorporated to the collision-collection.
> Note that the edges may (and in a common scenario will) overlap each other.
> This may be implemented directly in the VMD by replacing the Router creation
> with the following code:
> edgeRouter = RouterFactory.createOrthogonalSearchRouter (new
> OrthogonalCollisionsCollector (mainLayer));
> // NOTE - the connectionLayer is not inspected for collisions to improve router
> performance
> 
> The core issue is that the algorithm itself has exponential complexity so it
> will never scale - we can just postpone the "slowness".

Hi Caspar, yesterday i tried split my Visual MIDlet in several VisualDesign files
but a can't do it because the netbeans was very much slow.
So i downloaded netbeans 6.1 and i replaced the original org-netbeans-api-visual.jar by developed by einself@netbeans.org available to download at http://netbeans.org/bugzilla/show_bug.cgi?id=119999 and now i can continue work.
The approach used to solve this problem is totally wrong, because this problem is the Traveling Salesman Problem-TSP which is NP-hard.
To solve this problem is necessary use some Artificial Inteligence algoritms like Evolutionary Computation by example. 
I'm very interested in try solve this problem, but i dont have time now.
how can i help ?

thanks,
Diedrich.
Comment 12 David Kaspar 2010-04-07 13:38:21 UTC
(In reply to comment #11)
> The approach used to solve this problem is totally wrong, because this problem
> is the Traveling Salesman Problem-TSP which is NP-hard.

Agree but it was relatively easy to implement such algorithm and produces relatively nice routing even - it is "just" ;-) slow.

> To solve this problem is necessary use some Artificial Inteligence algoritms
> like Evolutionary Computation by example. 

That would be great.

> I'm very interested in try solve this problem, but i dont have time now.
> how can i help ?

You can help us by writing a better algorithm for routing connections.

If you would have some time, please, look at the documentation and JavaDoc of the library that is used for rendering:
http://bits.netbeans.org/dev/javadoc/org-netbeans-api-visual/org/netbeans/api/visual/widget/doc-files/documentation.html

Basically all we need is to have a good implementation of org.netbeans.api.visual.router.Router interface.

You can use examples listed at:
http://platform.netbeans.org/graph/examples.html
for checking your Router implementation.
Comment 13 Karol Harezlak 2010-04-29 13:46:50 UTC
*** Bug 155232 has been marked as a duplicate of this bug. ***