💾 Archived View for denisthiessen.de › blog › force-directed-drawing captured on 2024-06-16 at 12:33:19. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2023-03-20)
-=-=-=-=-=-=-
🎶 Futures. Made of. Virtual Insanity... For useless. Twisting. All the new technology... 🎶
Well... Recently I've been more and more getting into different note-taking tools.
I've got a half-written blog post on that one lying around on that one... whenever I feel like finishing it :D
One of them is a tool called "Obsidian". The main feature of this tool is the interlinkability of different notes and then you can visualize those links with a cool graph.
With this, you can recognize connections between different topics a lot better with plain old notes and even recognize knowledge gaps early, if you keep up your writing. Interesting isn't it?
Graph visualization or graph drawing is a complex mathematical/algorithmic field, and I really don't have the motivation to talk about all of the different methods but I want to take a closer look at the one used in this note-taking tool. Force-Directed graph drawing
Why you may ask? I took a bit of a "deep dive" during my Bachelor's thesis into this field and want to refreshen my knowledge a bit... So come with me. It won't be that bad. *pinky promise*
So... As the name already suggests different forces are involved in this kind of algorithm.
In a nutshell, we run a "physics simulation" on the graph's nodes and lines. This results in different forces affecting the graph components thus the graph having a certain amount of energy due to the different forces.
The goal is now to minimize the overall forces and energy throughout the whole graph and this will result in an aesthetically pleasing graph.
Sounds simple. Give me a second. 😅
For the record... There are multiple ways on how you could go about doing this... I'm just telling you the, for me, "most understandable" method. So yeah... Keep that in mind. 😉
First, imagine this graph from that picture.
Okay. Now we take all of the edges of this graph and replace them with springs.
Sounds weird? Yes. But bear with me.
Technically you can compress (nearly) every material out there, but springs are pretty much commonly known to compress and uncompress with ease. We can also formulate these forces pretty well, but that's just something incidental. 😉
(Also it still kinda looks like a graph edge as well.) 😂
If you've paid attention in your Physics classes, then you can probably recite the formula for calculating the force needed to push a spring together. (For those of you who didn't, I got you...)
F = D * l
With this in mind, it means springs will always have a certain amount of compression, due to their hardness, since objects in our universe tend to be in their state with the least energy possible. If you want to compress or stretch the spring even more, then you'd need to invest energy in this process. This results in all of the different edges of a graph having a certain amount of force and energy due to the springs used. But this would result in a pretty compressed graph drawing since all of the springs were motivated to move into their most energy-efficient state. As you can imagine a very compressed drawing doesn't really look that great, and neither is very readable, so let's fix that.
To do this, we introduce a second source of forces.
Imagine that every single node of the given graph is an electrically charged particle.
With Couloumb's Law ( F = k * ((r1 * r2) / r2) ) we can now calculate the forces between two graph nodes, attracting or repelling each other.
If we give all of the nodes a charge from the same polarity (negative - negative or positive - positive) then the nodes will actively repel each other.
We can use this phenomenon to our advantage, combining it with the spring forces mentioned earlier.
You see, if we combine both of those forces, then both of them are directed exactly opposite to each other. If both of those forces are, by chance, at the exact same strength, then we hit a perfect balance and those two nodes and their shared edge reach an equilibrium. (Yes... Even though I'm not smart, I'm using smart words. I need to keep the facade alive, okay?)
We can even modify how far apart or how close graph elements are by modifying the "electrical charge" of the nodes and the "spring hardness" of the edges.
This behavior can be transferred to the entire graph and not only a set of nodes and edges.
With this, we can calculate the potential forces of an entire graph. 😁
Remember what we said earlier? If we minimize this energy, then we get an aesthetically pleasing graph.
How can we do this? Well... We have a metric ton of equations on our hands and if we move the nodes around, then we can calculate the forces of the graph and look for the lowest final result. How we do this is up to the implementation but this is another topic. You get the idea. 😉
Okay cool. But when do we stop this? That's the best part... We don't. (insert meme reference)
That's also one of the main problems with this type of graph drawing.
It doesn't have a fixed termination point and tries to optimize as much as possible. Since the algorithm can't, without an extreme amount of effort, whether it has reached the minimum amount of energy, a termination point can only be estimated.
Another bad thing is that since we gradually make steps toward the minimum amount of energy, we sometimes into minima, where you'd have to have to increase the amount of energy in the whole graph again, to reach the real minimum. (A so-called local minimum)
Aaaand being stuck in such a local minimum isn't optimal, since all we want in life is to achieve our true potential.
Don't talk such pseudo-inspirational sh.. Talk about some good stuff already... And what about Obsidian?
Yeah right. You're like 3 pages deep already. Give me a moment.
So... Obsidian. Right...
Remember that juicy jiggle I showed you? That's also a cool thing that is easily enabled by this type of graph drawing. Since we perpetually do node movements based on the previous position of all graph elements in the step before, means that interactive graph node movements are easily done, since there is no adaptation for this case needed. I mean. It also means that the performance of this thing is kinda crap but we just ignore that. 😉
This fact enables us to do cool interactive things like drag and drop, or jiggly graph movements for example...
I could watch that for the whole day... But sadly I can't show you a pic that... 😥
Focus! We are nearly done.
Luckily, you don't need that much focus to actually implement such an algorithm compared to other graph-drawing algorithms. I mean. Even I could manage to explain it to you without too much mathematics. (If you are the type of person who would read through this type of blog post in their free time, I think this shouldn't be too much of an issue... And if you got here by me... Well. Hello. Hope you aren't too confused by now.)
But yeah... My desire to write something down, and freshen up my knowledge has been fulfilled quite well and I think you've learned something new in the last few minutes. (as long as I was competent enough to explain it to you in a simple manner)
Since this is quite a deep mathematical field, there would be way more to talk but I think that would be a good end to this precarious adventure in the field of graph drawing.
I hope you don't feel tortured right now and maybe you've learned something new along the way.
Either way. Have a great day and I hope we can "see" each other in the future as well.
See ya.