Determine the positions of nodes inside of a graph
I've attatched some images to show what I mean. One shows how the current (not implemented by me) algorithm sorts the nodes. It is very suboptimal as it has a lot of crossings and very cluttering connections. The other picture shows how I rearranged it manually to be way easier to understand. My question now is: How do I figure out the positions for those nodes?
As for the structure of the code:
The last one (with only connections entering on the left side of the node) is the "Root" that has children and each children then also has children etc.
While I wouldn't mind a pre written algorithm, if there isn't one readily available, I'd appreciate some guidance on what steps the algorithm should have.
Thanks in advance!
21 Replies
What you might be looking for is a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph ca...
Can one node be the child of multiple distinct "parent" nodes? Like
If not, then it sounds like it's just a tree, which is a simpler case of planar graphs
I'm not 100% sure. In the current implementation I think it is not possible since this is recursively iterating through the childs which would make that impossible. However, one thing I considered was combining for example resource extraction steps (the ones that only have an item and quantity on the right side of the node) of the same type together in which case they would then have multiple parent nodes right?
You definitely got some good solving chances because that stuff is not crazy interconnected
It's rather tree-like like ParaLogia mentioned
Assuming I figure out anything cause right now I'm a bit lost
There might be easier algs for that
The Reingold-Tilford algo might be worth a lookup
If I was going to tackle this, I'd follow something like:
1. Work out how many columns we need. Easy.
2. Assign nodes to columns. Easy to do naively, but you might up with something a bit more nuanced to avoid too many things in the same column, etc
3. Position blocks within their columns. I'd first attempt this by:
a. Start at the root node and walk the middle children until you find the leaf: these go in the middles of their columns.
b. For each half of the graph (top half vs bottom half), walk from the leaf nodes back up to the root, and place in each one's column. This is the bit that would take some experimentation, but something naive is probably fairly easy
Ah hello, Reingold-Tilford looks perfect actually. Ignore that above
I think that's basically what the Tilford algo is doing
You were on the right track :blobthumbsup:
Yeah, except it looks like it's a bit smarter about trying to center stuff under their parents
I'll look into that one, also if you could have a quick check since the following one also seems to be quite fitting for my purpose and not too complicated:
https://www.cs.unc.edu/techreports/89-034.pdf
Looks not dissimilar -- it references Tilford
I've found this blog post here:
https://rachel53461.wordpress.com/2014/04/20/algorithm-for-drawing-trees/
Which seems to be enough for my understanding. I'm looking through the code right now and it looks like I can relatively easily adapt my current code to work with this implementation
Rachel
Rachel Lim's Blog
Algorithm for Drawing Trees
I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree. At the time, I thought “This will be easy, I’ll just Google for an alg…
I played around with it a bit but I'm having some problems:
This obviously doesn't look anything like I want it to look. My suspicion is that the algorithm is somehow trying to draw it vertically but failing miserably at that. So, I need to figure out two things:
1. How do I convert the code to be oriented the way I want it
2. No idea why the x values are getting so big so I'll have to find out whats happening there too.
If anyone wants to have a look, I've linked the repo down below. The relevant files are:
FactoryTreeGraphGenerator.cs (Main algorithm)
ProductionStep.cs (Tree node)
The tree itself is generated in FactoryTreeGenerator.cs
Main.cs contains a lot of random code that I've yet to clean up so sorry for that. That is where I'm calling the relevant functions and creating the physical nodes of the tree (ll. 71-77, parseTreeAsGraph)
If you want to test a version of your code, you need the Godot Game Engine Version 4.2.2 Mono
Import it into the editor and just press F5, that should do everything needed for you
Repo: https://github.com/Kaenguruu24/SatisfactoryFactoryBuilderGitHub
Releases · godotengine/godot
Godot Engine – Multi-platform 2D and 3D game engine - godotengine/godot
GitHub
Kaenguruu24/SatisfactoryFactoryBuilder
Contribute to Kaenguruu24/SatisfactoryFactoryBuilder development by creating an account on GitHub.
@Kaenguruu24 what library do you use to create, execute graphs? i'm looking for library where i can create graphs like your, i don't need visual part of graph, i will code it myself