r/computerscience • • May 20 '20

What underlying data structures are commonly used to optimally support large graph-like interfaces like this? Thanks.

Post image
174 Upvotes

25 comments sorted by

209

u/cramzable May 20 '20

Well a graph would be a good start

16

u/[deleted] May 20 '20

Yes, thanks, I figured. I was wondering, though, if there are further optimizations to be made since each node in the graph could be connected to a large number of other nodes, either directly or indirectly in this specific use case.

13

u/cramzable May 20 '20

It's too complicated for me to think of anything else, I have no idea. Each node could have a collection of pointers to other nodes and then that link is symbolized as a line?

4

u/[deleted] May 20 '20

That's similar to what I had in mind. Thanks for your time.

4

u/PlayfulRemote9 May 20 '20

I’m shocked I don’t see this anywhere, but you would use a hashmap where the key points to a list of nodes it connects too.

0

u/[deleted] May 20 '20

[deleted]

1

u/PlayfulRemote9 May 20 '20

I would think so, but the commenter said “it’s too complicated to think about” and no one mentioned how much better this would be than his answer (each node holding a collection of pointers) or an array approach.

It’s not semantics because the optimization is due to the maps get(key) runtime

2

u/aragonSkywalker May 21 '20

Instead of having your own graph implementation, you could use an existing library

1

u/vitkarpov May 21 '20

It depends on what operations you are going to apply on the DS most of the time. Optimisations are about trade-offs, aren’t they?

1

u/HolyWurst May 21 '20

Well you can store the outgoing edges as a list. If the degree of your graph nodes is too high(>1000) maybe you can optimize the look up times at that edge list.

2

u/codeAligned May 21 '20

Not sure is cramzable is trying to be a wise crack but obviously a graph is involved. But a graph is an abstract data structure, I think we are more interested in the implementation of the graph i.e. adjacency matrix vs adjacency list.

39

u/tobyase May 20 '20

This isn't very large at all. You could store all the nodes in a linked list and all the connections in a different list. It would be horrible from an efficiency standpoint but it would still do the job and be decently fast. You really need a graph data structure when there are thousands and millions of nodes. The most classic example is representing a street grid (or more general maps) and finding paths.

4

u/[deleted] May 20 '20

Thanks very much. That is really helpful. I appreciate it.

4

u/afnanenayet1 May 20 '20

It think it would actually be easier to work with a hashset of nodes and and adjacency lists to represent their neighbors.

For op:

Something like HashSet for your vertices, then a hashmap of verticices to an array or set of neighboring nodes.

It’s efficient but still relatively simple

2

u/[deleted] May 20 '20

Thanks to everyone who provided a solution or some advice. I'll be looking through all of the comments properly tonight and then responding. Thanks again.

8

u/J_Peanut May 20 '20

For representing graphs you have basically three options:

  1. A linked-list like structure where every vertice in the graph is a node in the list and the edges are a list of "next" pointers. However, this is not efficient but can be used for small problems

  2. an adjacency matrix. In this structure you create a two dimensional matrix of all nodes. This matrix is filled with binary values. If there is an edge between node A and B the representative location in the graph is set to true. This data structure gives you a good access to the edges of the graph and inserting, deleting, and finding edges is fast. Inserting vertices is rather slow on the other hand because you need to create a new matrix for that.

  3. an adjacency list. In this structure you create a list of length n where n is the number of vertices. The ith entry in the list has a representation of the vertices adjacent to the ith vertice. This is usually done by using a linked list for each vertice which contains the adjacent nodes. The advantages of the adjacency list is the high speed for vertice operations.

The adjacency list can also be adapted to have a doubly linked list for the linked list below each node representing a vertice. The doubly linked element is here the inverse direction of the edge which is represented under the adjacent node.

Assume you have a graph with vertices {A, B, C} and A connects to B, C, B connects A, and C connects to A. In the adjacency list the entry for A has the list B->C and B as well as C have the list containing A. If you have delete the edge between A and B, you have to change find the entry under A to B and the entry under B to A and delete those. A doubly linked list would also store a pointer to the inverse edge. In this case you would only need to find the entry for B under A and you could also find the entry to A under B. For this to work the linked lists under the vertices also need to be doubly linked otherwise inserting is hard.

7

u/yodduj May 20 '20 edited May 20 '20

I made a node graph ui for an application built in wpf. I’m not going to say I’m an expert, or that I designed it perfectly, but it may help to have a starting point.

I made a node base class with virtual functions for retrieving data. Each node type inherits from the base class and adds specific input and output elements to a list. Each i/o element has a reference to a wire(s) and each wire has references to 2 I/o elements.

So data traverses from a node type’s I/o element, to a wire, to an I/o element within another node. For instance, an if statement node evaluates the Boolean input when the overwritten function “execute” is called. If the bool is true, then the node goes to the primary output element’s wire, goes to the wire’s end I/o element, and calls the execute function in the node that contains it.

4

u/valbaca Sr. Software Engineer (10+ yoe) May 20 '20

“The Algorithm Design Manual” (Skiena) has a chapter (or three) on this:

15.10. Drawing Graphs Nicely

Related to 15.11 Drawing Trees and 15.12 planarity testing

To answer the question: yes, graph data structures.

Look at GraphViz.

3

u/nandy02 May 20 '20

Graph? I mean you said it yourself...

2

u/NotThatGuyAnother1 May 20 '20

I could imagine how a relational database would store it. Table for node-types, inputs, outputs, workspace, nodes, property types, etc, etc with their various relationships.

2

u/[deleted] May 20 '20

I would think you would have nodes and children. Then to have a dependency graph there is an algorithm that figures that out. I can not remember it from the top of my head but I think it involves two stacks.

The algo would be something like A points to C, B points to C and D Points to A

The algo can figure out that from left to right, left being most independent it would look something like

D -> A->C B->C I'm sure you can add features that detect circular dependency and therefore cause an error. Really cool algo I'll try to find it.

EDIT: Topological Sort Algorithm

1

u/AlexJaeger May 20 '20

From a rendering perspective, you can increase performance by doing occlusion culling as most people would not be viewing the entire graph. The performance benefit improves when the graph size gets larger and larger, not sure of the benefit with a graph this small

1

u/[deleted] May 20 '20

As others have stated on here, ya, likely some form of nonlinear node-based structure

1

u/baby__groot May 21 '20

one more classification could be figuring out the `strongly connected componenets`

1

u/SimDeBeau May 21 '20

Sparse graph