C#•4mo ago

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

qqdev•4mo ago

What you might be looking for is a planar graph

qqdev•4mo ago

https://en.wikipedia.org/wiki/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...

ParaLogia•4mo ago

Can one node be the child of multiple distinct "parent" nodes? Like

   B
 /   \
A     D
 \   /
   C

   B
 /   \
A     D
 \   /
   C

If not, then it sounds like it's just a tree, which is a simpler case of planar graphs

Kaenguruu24OP•4mo ago

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?

qqdev•4mo ago

You definitely got some good solving chances because that stuff is not crazy interconnected It's rather tree-like like ParaLogia mentioned

Kaenguruu24OP•4mo ago

Assuming I figure out anything cause right now I'm a bit lost

qqdev•4mo ago

There might be easier algs for that The Reingold-Tilford algo might be worth a lookup

canton7•4mo ago

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

qqdev•4mo ago

I think that's basically what the Tilford algo is doing You were on the right track :blobthumbsup:

canton7•4mo ago

Yeah, except it looks like it's a bit smarter about trying to center stuff under their parents

Kaenguruu24OP•4mo ago

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

canton7•4mo ago

Looks not dissimilar -- it references Tilford

Kaenguruu24OP•4mo ago

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…

Kaenguruu24OP•4mo ago

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/SatisfactoryFactoryBuilder

GitHub

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.

CrosRoad95•2mo ago

@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

Kaenguruu24OP•2mo ago

Could you elaborate on what you mean with that exactly? The code I use to generate the graph looks like this:

message.txt

CrosRoad95•2mo ago

i want to create unreal engine like blueprints in code, just in code, without visuals

Kaenguruu24OP•2mo ago

So in my code, the FactoryTree class looks like this:

public class FactoryTree
{
  ProductionStep root;
  Recipe recipe;

  public FactoryTree(Recipe recipe)
  {
    this.recipe = recipe;
    root = new ProductionStep(recipe, 1);
  }
}

public class FactoryTree
{
  ProductionStep root;
  Recipe recipe;

  public FactoryTree(Recipe recipe)
  {
    this.recipe = recipe;
    root = new ProductionStep(recipe, 1);
  }
}

And then the ProductionStep class looks like this (there are some more specific parts removed, but for the basic understanding this should be enough):

public class ProductionStep
{
  public Recipe Recipe;
  public List<ProductionStep> Children;
  public ProductionStep Parent;

  public ProductionStep(Recipe recipe, float count)
  {
    Recipe = recipe;
    Children = new List<ProductionStep>();
  }
}

public class ProductionStep
{
  public Recipe Recipe;
  public List<ProductionStep> Children;
  public ProductionStep Parent;

  public ProductionStep(Recipe recipe, float count)
  {
    Recipe = recipe;
    Children = new List<ProductionStep>();
  }
}

This is basically enough. If you have multiple inputs (so multiple parent nodes) you would replace ProductionStep Parent with List<ProductionStep> Parents etc.

CrosRoad95•2mo ago

Also looking for reference how make such thing

Kaenguruu24OP•2mo ago

The graph structure comes through how you build the references between instances of these classes. So your "On Component Begin Overlap (Box)" would be a ProductionStep instance that has in it's Children list the == and the "Branch" node as instances of ProductionStep. The == has in their Parents list the "On Component Begin Overlap (Box)" and "Get Player Pawn" and the "Branch" node as child and so on and so forth Unfortunately I don't know any good references for this, I'm mostly just trying stuff. If you take a look at the links I provided, you'll probably find that the authors of these articles/papers used a similar data structure

CrosRoad95•2mo ago

I tried few moments ago achieve it using exrpessions, basicly turn graphs into expressions

Gaming

Programming

Determine the positions of nodes inside of a graph