Obsidian's graph drawing and other random babbling...
š¶ 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.
Hereās an example of how one of those graphs might look like.
Interesting isnāt it? And I havenāt even told you the best thing about itā¦
it do be jigglinā
But we are a totally professional ātechnicalā blog and you, of course, wouldnāt assume otherwise, wouldnāt you? Listenā¦ I donāt want you to say anythingā¦ Itās 1 AM, Iām tired and still canāt sleepā¦ Just let me have this one, okay?
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. I mean, look at the pic from beforeā¦ š
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.
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) I think that graph shows the difference between those two types of minima pretty wellā¦ But being stuck in such a local minimum isnāt optimal.
Donāt be such a downerā¦ 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 thisā¦
I could watch that for the whole dayā¦
Focus! 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.