r/computerscience • u/[deleted] • May 20 '20
What underlying data structures are commonly used to optimally support large graph-like interfaces like this? Thanks.
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
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
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:
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
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.
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
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/CavemanKnuckles May 20 '20
https://github.com/blender/blender/blob/master/source/blender/makesdna/DNA_shader_fx_types.h
I think it's a struct with pointers to other structs.
2
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
1
u/baby__groot May 21 '20
one more classification could be figuring out the `strongly connected componenets`
1
209
u/cramzable May 20 '20
Well a graph would be a good start