1

Given a line in a 2d coordinate system, we can create a dependency graph like this:

Graph 1

The black nodes represent a logical graph that is a-cyclic and therefore "stable" in the sense that if we provide real number values at all of the blue text nodes, we can parse resulting "Point" structures and a "Line" structure.

The orange node represents an external observer interested in the Y value it is pointing at. In this graph, the orange node would observe whatever real number is provided in the Y node.

Now if we introduce the concept of transformation, let's say we logically want to rotate the line. We modify the graph to show the transformation (see below image). The line node is now dependent on the transformation. BUT, as the edges are shown, all of the nodes are now dependent on the transformation.

Given real numbers at the blue text nodes, the orange observer will expect to see the transformed value, because the node's value changes upstream at the transformation node.This image proves the graph can be drawn to maintain stability (a-cyclic).

Graph 2

In the first image, the space complexity is linear, but in this second image, the space complexity becomes worse, (appears to be O(mn)) along with the time complexity to assign edges.

Let's add another transformation.

Graph 3

In the above image, the stability is maintained, such that the orange observer will now expect to see the rotated and translated Y value. But in practical terms, we needed to update 7 edges to point at the new head transformation node.

Given an arbitrary number of transforms, we would be forced to visit 7 edges per each transform, which appears to me to be O(mn) time complexity where m is the number of nodes and n is the number of transforms.

My current understanding is the below image. The better solution is to store parent references in each node such that when the orange node is created, the graph is walked upstream until the head is reached. Therefore the orange node dependency is a "logical" dependency on Y but a practical dependency on the translate node.

Graph 4

Even if this is a better solution, it has a flaw in my application, which is the temporal aspect. In my application, there is no guarantee all of the transform nodes have been resolved before the orange node. Which means that the orange node would need to be updated every time a transform node is added. In my application, there could be an arbitrary number of orange observers, so we are back to O(mn) where m is the number of observers and n is the total number of transform nodes. Every time a transform node is added, all observers have to be updated to the new "Head".

My question is if an elegant solution in graph theory or graph algorithms exists to make this more elegant. At a further stage in my application, I am successfully performing a topological sort, but the issue I am struggling with is as this post shows, i'm struggling to represent my graph a-cylically which is necessary for the topological sort.

EDIT: If you would like to give me a sketch in your response, I used tldraw, the original sketches can be found here:

Graph Sketches

EDIT 2: Filip asked if I can dynamically calculate the orange nodes target value.

instead of dynamically fetching value I perform a topological sort of the dependencies. That puts the list of all nodes in such an order that the value of the preceeding dependency has already been calculated at the perfect correct time for the next node to use. O(n) time complexity to sort versus O(mn) to fetch/calculate dynamically where m is number of orange nodes and n is number of ancestor transforms to iterate.

My proposed solution of walking the parents didn’t fully explain that I believe the intersection of lineages of the orange target lineage (not shown) and the Y node lineage is the architecturally correct ancestor to call the “practical dependency”. If an orange node is deeply nested in a sibling object graph, it seems i have no choice but to walk the two lineages to find the common root which is the earliest point that all transforms are complete. I can sketch this in a few days to help with the visualizing.

Improve this question
4
  • Is your problem actually a 2d coordination problem? If so, you might want to consider replacing your graph with linear matrix algebra. That should allow you to condense any transforms to a fixed set of matrix's. Commented Jul 12 at 23:40
  • So, just to get it out of the way, cause I don't know all the details of what you're trying to do, I guess my first question would be: Are you sure there isn't a simpler way to model the problem that you may have overlooked? E.g, what people's first pass would usually be is something like, create a Line data structure that has two Point-s as data members. Then you'd have each transform be an independent object (Line has no dependency on it), that can be applied to a line (or that produces a transformed copy); you may then have an open-ended list of such transforms. 1/2 Commented Jul 13 at 15:13
  • Then you might have some higher level object that knows internally about the transform list, and provides a function to apply the combined transform to a line, or to the endpoints (or one particular endpoint) of that line (again, it could also return a copy of the original line). And then your observer would just call this function. Now, it's possible that this or a similar approach might not be suitable for your problem, but if so, it would help if you could elaborate on why. Like, what constraints or aspects of the problem go against this? 2/2 Commented Jul 13 at 15:13
  • I see one vote to close as needing focus, and another as needing details or clarity - this post certainly doesn't need details; we have LOTS of good information here. I'm just struggling to find the question. What exactly are you asking about? Commented Jul 17 at 18:03

1 Answer 1

Reset to default
2

it has a flaw in my application, which is the temporal aspect. In my application, there is no guarantee all of the transform nodes have been resolved before the orange node.

Your flaw is treating the observed y like it is only one node. There is a different y node for every modification.

In your first picture ? points at line.point1.y

You want us to believe in the second picture that ? points at rotate20.line.point1.y. But it doesn't. It's still pointing at line.point1.y and whatever value that had before hasn't changed. rotate20.line.point1.y is a different y node, with a different value, that you didn't draw.

Yes the observer only cares about that y on the first point. But it must be pointing at the correct y. There is a new y for the first point for every modification. The last picture just shows two different ways to get the information about which y to look at.

Given that system, the simple solution is to update the observer when you make a new y.

What you've created here is a snapshot, command log, replay system. Databases use a similar system for recovery. With a snapshot of the database (in your case the original line), and a log of every command issued since the snapshot (in your case your rotate and translate nodes) you can recreate the DB (in your case the final line state).

Since your graph is a graph of dependencies, and your observer wants to observe the final line (even if only part of it) the original line and all modifications to that original line must be dependencies.

Improve this answer
9
  • "What you've created here is a snapshot, command log, replay system" - this could be the case, but I'm wondering if the OP hasn't gone down an approach that has made things more complicated than they need to be, by making the representation in code be a literal graph. E.g. maybe the "history" (or the "log") of transforms is of no interest in and of itself, maybe all they care about is having a way to make a complicated transform by composing simpler ones, the way people who are in 3D graphics do (matrix algebra). Like, it could be that this is better represented as a mesh + transform matrices? Commented Jul 13 at 15:30
  • @FilipMilovanović those are simply implementation details. I took the subject to be analyzing the dependencies. How you calculate is a different issue. Unless I’m missing something this became needlessly complex when what you call mesh + transform got mixed with navigating to the observed Y. That last bit is about structure not dependency. Commented Jul 13 at 15:47
  • Right, that's why I asked the OP to clarify; again, you might be perfectly correct in your interpretation of the question, but I'm wondering if the OP is coming, say, from a math or physics background, and if the way they naturally think about the problem is leading them to a particular implementation strategy (actual graph data structure), and if that is what's causing them difficulties. Of course, I could be wrong. Commented Jul 13 at 16:05
  • Without going too detailed, i'm creating a runtime system where users can instantiate new "slots" with the option of the "slot" being within an existing "slot". So a natural graph structure results, with nested slots within slots. Each "slot" can be assigned a primitive value or a tranform. My app starts at the deepest nested slots i.e. the leaves and analyzes the primitive values to determine the outer/parent slot "type" based on the nested types. So there is a recursive, depth-first analysis. The user manipulates the slots at runtime to create their own graph-like structure. Commented Jul 13 at 19:56
  • A key feature of the system is to to give users the ability to refer to an existing slot and obtain a deep-copy of said slot. Which is exemplified by the orange node. That is practically the entire design. Commented Jul 13 at 20:15

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.