ForceDirectedLayouter issues

[evilC]

I have taken the Calculator demo and set up a simple network programmaticaly:

            var input1 = new ConstantNodeViewModel();
            NetworkViewModel.Nodes.Add(input1);

            var input2 = new ConstantNodeViewModel();
            NetworkViewModel.Nodes.Add(input2);

            var sum = new SumNodeViewModel();
            NetworkViewModel.Nodes.Add(sum);

            var output = new OutputNodeViewModel();
            NetworkViewModel.Nodes.Add(output);

            NetworkViewModel.Connections.Add(NetworkViewModel.ConnectionFactory(sum.Input1, input1.Output));
            NetworkViewModel.Connections.Add(NetworkViewModel.ConnectionFactory(sum.Input2, input2.Output));
            NetworkViewModel.Connections.Add(NetworkViewModel.ConnectionFactory(output.ResultInput, sum.Output));

Here is what it looks like manually laid out:

I then added the buttons to perform Auto-Layout (Both Layout and LayoutAsync)

With the suggested value for maxIterations (As in what the sample CodeGenerator app uses) value of 10000, Layout gets nowhere near laying out the nodes.

Some results using various values (Intel i7-7820X @ 4Ghz, 32GB RAM): I tweaked and found that it needs about 2 million iterations to complete, and takes about 15 seconds

10,000 iterations (<1 second):

2,000,000 iterations (~15 seconds):

2,500,000 iterations (~20 seconds) Normally I get:

Although sometimes I get:

In all cases, CPU utilization was about 20%

Furthermore, maxIterations appears to not be a maximum at all - I have never seen it take less iterations. Fr example, if, after the 2,000,000 iteration example above that resulted in an almost perfect layout, I click Auto-Layout again, it still takes ~20 secs to complete, and yields what appears to be an identical result (ie it did not appear to make any changes, but still took 20 secs)

If I then swap the two inputs like so: and re-run, it takes another 20 seconds and yields:

If I use LayoutAsync, it starts off really fast, but then drastically slows down after a couple of seconds - I waited a good couple of minutes for it to complete, then gave up - I don't know how long it takes to complete.

It's maybe also worth mentioning that I am not really sure I see the point in Layout - unless a sensible value for maxIterations (ie one that takes a couple of seconds) can lay out most networks to a reasonable degree, then it would be impossible at code-time to pick a sensible value.

[Wouterdek]

With the suggested value for maxIterations (As in what the sample CodeGenerator app uses) value of 10000, Layout gets nowhere near laying out the nodes.

You can tweak the values in the Configuration object you pass to Layout. These affect various properties of the system. Broadly speaking, the values are a tradeoff between physics stability, speed and various esthetic preferences.

If I use LayoutAsync, it starts off really fast, but then drastically slows down after a couple of seconds - I waited a good couple of minutes for it to complete, then gave up - I don't know how long it takes to complete.

As the documentation states, the process does not end until you request it:

This method, contrary to Layout(), lets users see the simulation as it happens. The cancellation token should be used to end the simulation.

It's maybe also worth mentioning that I am not really sure I see the point in Layout - unless a sensible value for maxIterations (ie one that takes a couple of seconds) can lay out most networks to a reasonable degree, then it would be impossible at code-time to pick a sensible value.

That is a valid point. Some sort of heuristic could be used to determine if the layout will not change much with more iterations. This is more difficult than it sounds. For example: The simulation can be start in or enter local, but not global, optima that require some small delta updates to gain inertia. These local optima tend to confuse the heuristic into stopping the simulation too early, making it unreliable.

This is also why I added LayoutAsync. Instead of trying to figure out when the layout is complete, it lets the user decide whatever he/she thinks is an OK state.

Doing layout is pretty hard. I added this feature because it is nice to have when you start out with a bunch of piled up nodes and want some general structure. It's important to note that you will never get as good results as doing it manually, 100% of the time. As a nice-to-have, I'm also not interested in spending lots of development time on it. If you have great solution, I always welcome PR's ;)

[evilC]

Yes, I figured that this was a non-trivial problem, and I wholly agree that it is probably not really worth taking dev time away from more important tasks. As a noob trying to get to grips with this library and associated technologies (I'm new to WPF in general, and Reactive), what I would find way more useful would be a concrete example of Serialize / Deserialize to a file, so that I don't have to either manually lay things out each time in order to test what I have written, or set up networks in the constructor of the MainViewModel using NetworkViewModel.Nodes.Add and NetworkViewModel.Connections.Add You did give a brief overview of a technique that could be used in #9, but I feel that it would make a good addition to the examples to help people hit the ground running. eg maybe a sample implementation which sets up the Calculator example with a basic calculation

[Wouterdek]

Makes sense, I'll put that on the TODO list. Not sure when I'll get to it though, next few months are very busy for me.