0

I am interested in using vanilla Javascript objects and arrays to model data that has the data structure of a connected directed graph. One way to do this would be to use multiple object references within a single object tree to represent distinct edges of the graph. However, to use this efficiently, there needs to be a way to easily check what are the incoming edges to a given object (or put another way, for each object to know what all of it's parents are, and to know the property keys from each parent to itself.)

According to this older Stack Overflow post there is no built-in way to do this in Javascript: Get all object references in Javascript.

I've started making my own library called Parent Aware Objects that uses Proxy objects to intercept basic object assignment operations in order to keep track all the references to each object.

Before I go too far down this path, I wanted to ask if there might be an easier way to accomplish this.

This is the functionality I want:

const fido = {
    name: 'Fido'
};

const alan = {
    name: 'Alan',
    pet: fido
}

const sarah = {
    name: 'Sarah',
    dogWalkerFor: fido
}

getParents(fido)

The function call getParents(fido) should return a list of entries that contains the alan object with key "pet" and sarah object with key "dogWalkerFor".

Avi C
  • 297
  • 1
  • 3
  • 7

1 Answers1

0

You would need a collection of all the nodes in the graph to search for:

const graphNodes = [fido, alan, sarah];

Then you can easily get all nodes that reference Fido:

graphNodes.filter(node => Object.values(node).includes(fido))

Of course, searching the entire graph every time is not really efficient. To do that, you would need to store the backedges on the node itself, or in a Map or something where you can easily look them up. This would then require updating that data structure every time you update your graph.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Thanks Bergi. So as you say, I'm looking for a method that is more efficient that searching the whole tree every time. --"This would then require updating that data structure every time you update your graph." That is pretty much what I'm trying to implement using Proxy objects. – Avi C Jul 28 '19 at 22:19
  • Proxies are pretty weird to work with. Why not use a normal implementation with a `class Node`? Do you absolutely *need* the nodes in object shapes? – Bergi Jul 29 '19 at 10:12
  • When you say Proxies are weird to work with, do you mean when writing the handlers for the Proxies or when using a proxy after it is well constructed? My idea is that if the Proxy is done well, then the proxy objects would behave like normal javascript objects but with the added feature of being able to get the parents and paths from parents to child. – Avi C Jul 29 '19 at 15:12
  • I mean that it is easy to mess up the trap handlers so that things will not work or in very unexpected ways. Also, a few native APIs do have problems with proxies. I'm not saying it's not possible, and this in particular should be relatively easy to do well, but I'm not sold on the advantages yet. Btw, you probably still would need to create a `new Graph` instance that manages the nodes (proxies) contained in a particular graph, and have a `graph.createNode()` method that creates such a proxy to which you then can assign properties. – Bergi Jul 29 '19 at 15:25