Forum

VL.ForceDirected

Hey, I’ve tried to re-build the classic Force Directed Graph contribution by @tonfilm & @gregsn. It kinda works. I think there is still something wrong with the parents / children lists of the FDNodes or the order of From/To inside FDEdge respectively.
Also not quite sure if the forces are “translated” correctly.

The real problem is the performance (of calculating the Repulsion) though. The whole thing is way slower than the beta version and totally fails for spreadcounts >=200 on my machine.

Any feedback and ideas for improvement very much appreciated.

VL.ForceDirected.7z (55.1 KB)

3 Likes

That you use delegates at the very core of the nested loop is probably not a good idea. The Repulse node is also a process node even though there’s no state involved - honestly the system should have given you an error/warning there, because that state gets re-created for each iteration. So my suggestion for a starter would be to get rid of that one.

Regarding the delegates, there’re two options - use an interface to pass the models (Attract/Repulse) or use adaptive nodes. Only found time for the adaptive version (which in theory should be the fastest), see attached patch. (not happy how I did it, as all those FD nodes became generic due to the attract operation - wanted to only have the graph generic over the used model, but out of time)

(Btw, your patch also shows an issue with the bang io boxes - will be fixed in upcoming builds, sorry for that)

VL.ForceDirected_Adaptive.7z (73.5 KB)

2 Likes

You’ve done that already, when using an adaptive operation, havn’t you? Or do you mean to somehow get rid of the nested loop?

Ähm yes - in my patch that’s already done.

Hey, played with it some more and made some minor changes. Still it performs worse than the beta version and breaks completely for larger spreadcounts and I really don’t get were the differences come from.

Don’t know it the ticks displayed in gamma and beta can be compared directly:

Perf

image

image

Graph Update

beta:

	        public void Update()
	        {
		        var edgeCount = FEdges.Count;
		        var nodeCount = FNodes.Count;
		
		        //attraction along edges
		        for(int i=0; i<edgeCount; i++)
		        {
			        FEdges[i].Update();
		        }
		
		        var nodeCountRep = 1.0/nodeCount;
		
		        //repulsion of the nodes
		        for(int i=0; i<nodeCount; i++)
		        {
			        var n = FNodes[i];
			        n.Velocity += CalcRepulsion(n);
			        n.Velocity *= Speed;
		        }
		
		        //update position
		        for(int i=0; i<nodeCount; i++)
		        {
                    var n = FNodes[i];
                    n.Update(GetTime());
		        }
	        }

gamma:

image

CalcRepulsion

beta:

	        private Vector3D CalcRepulsion(FDNode n)
	        {
		        var rep = new Vector3D(0);
	
		        if(n.Parent.Count == 0) return rep;
		
		        var oCount = FNodes.Count;
		        for(int i=0; i<oCount; i++)
		        {
			        var o = FNodes[i];
			
			        if (o != n)
			        {
				        var diff = n.Position - o.Position;
				        rep += Forces.Repulse(diff);
			        }
		        }
		
		        return rep/oCount;
	        }

gamma:

image

Fruchterman Reingold repulsion

beta:

	        private static Vector3D RepulseFR(Vector3D diff)
	        {
		        var l = !diff;
		        diff /= l;
		        return diff * ((ConstantsFR.y*ConstantsFR.y) / l);
	        }

gamma:

image

The ticks can be compared directly - both represent µs. Just did a quick comparison and for N = 200, it’s ~900µs in beta vs ~2200µs in gamma. Reason is that the emitted code when running inside the editor is not as good as it could be. To name a few things which are different:

  • A class in VL comes with one level of indirection (proxy and target) in order to quickly exchange them in the object graph (hotswap) - in this case we pay for that one a lot I wager as it affects the inequality check, the position and model access.
  • The root patch carries the actual implementation of the Attract and Repulse methods (at least in the patch I posted they were implemented using the adaptive mechanism). But since it gets emitted in debug mode, also the JIT compilation of those generic methods will happen in debug → certain optimizations won’t apply. With a little workaround I was able to avoid this an the timings dropped to 1700µs.

Therefor a fair comparison would be to do an export and see how that performs compared to the plugin. I must admit it would be nice to have some sort of switch in the settings to enforce that everything tries to run as fast as possible (obviously losing any debugging features).

But all that being said, I’d say that for high spread counts this algorithm will perform poorly since it’s O(N²). Much better results would probably be achieved using Barnes-Hut algorithm for example The Barnes-Hut Galaxy Simulator

1 Like

Oh yes, please!
I want to propose 2 things here:

  • a toggle in the settings pane
  • a command-line parameter

the first one for testing while developing the latter if you want to start a project in the runtime. Both should be connected to the same property, so one’s able to start with the command-line-flag but has the possibility to escape it later without restarting the HDE.

1 Like

btw. did a small profiling. the editor had the definitions patch open while screenshotting so that debug affects as little as possible.

and the situation here somehow improves when changing EadesModel to be a record:


again, when the EadesModel was a class:

it looks like the “getter” aka Split operation of the vector3 field costs too much?

1 Like

Yeah was already looking into Barnes Hut (and Fast Multipole which is way over my head…). Found this explanation really nice.

See also my post here:

But before starting that I wanted to make sure that there aren’t any “errors” in the basic implementation.

@sebl Indeed there’s room for improvement regarding the Split operation - I’ll write it up.

1 Like

Hello again, sorry to keep pestering you :)

Out of curiosity I’ve tried to adapt a “textual version” of the Force Directed graph from the beta version.
Seemed pretty straight forward. But I am running into an issue I really can’t wrap my head around.

The graph has a List of Edges and a List of Nodes. When building the graph these lists are cleared and then Edges added. When an Edge is added it checks if the Nodes making up the Edge (From, To) already exist, if so fetch the existing Node, otherwise create a new one with random Position and an ID and add it to the nodes list. So far so good.

But when I add multiple Edges/Nodes at once the resulting nodes all have the same Position even though their IDs are correct.

When I do the same in Debug mode in Visual Studio, stepping through the Process of adding, the resulting Positions are also distinct. It also works when adding the Edges one after the other (frame by frame).
Any ideas?

AtOnce

StepByStep

And how is that position generated? Maybe frame time dependent?

Like so:

           public void AddEdge(string f, string t)
            {
                if (f == t) return;
                if (EdgeExists(f, t)) return;

                var fn = GetNode(f);
                var tn = GetNode(t);

                if (fn == null)
                {
                    fn = new FDNode(f, IDToPos(f));
                    FNodes.Add(fn);
                }

                if (tn == null)
                {
                    tn = new FDNode(t, IDToPos(t));
                    FNodes.Add(tn);
                }

                FEdges.Add(new FDEdge(fn, tn));

            }

            protected Vector3 IDToPos(string id)
            {
                var pos = new Vector3(0);

                if (id == RootID) return pos;

                var rand = new Random();

                pos.X = (float)rand.NextDouble();
                pos.Y = (float)rand.NextDouble();
                pos.Z = (float)rand.NextDouble();

                return pos;
            }

grafik

You need to hold on to the Random instance. Place it in a field of the containing class (I guess the FDGraph).

Damn, I used random because I thought there were problems with the

original code.
protected Vector3D IDToPos(string id)
{
			var hash = id.GetHashCode();
			var pos = new Vector3D(0);
		
			if(id == RootID) return pos;
		
			unchecked
			{
				pos.x = ((hash & 0x00FF0000) >> 16)/255.0;
				pos.y = ((hash & 0x0000FF00) >> 8)/255.0;
				pos.z = ((hash & 0x000000FF))/255.0;
			}
		
			pos = pos * 4 - 2;
			return pos;
}

Eigentor … Thanks. Will try it tomorrow.

Ok here is a version that uses the (slightly adapted) beta code:

VL.ForceDirected-0.2.7z (264.6 KB)

2 Likes

Really cool! Ive used this a lot in vvvv-beta :)
While testing your version ive edited the help patch a bit


(warning: screenshot may contain a spread of coronavirus)
HowTo create a Force Directed Graph.vl (89.1 KB)

3 Likes

great work! btw 2021.4 and preview 675 throw an error, but it still works:

I think both helppatches would be nice to include. one that shows the basic components and one that demonstrate how to spawn and render multiple viruses.

@schlonzo That’s the patched version we discussed further up. Björn replaced it with one written in C#, so I guess that error can be ignored as it’s not used anymore anyways.