Node graph architecture

Last updated

Node graph architecture is a software design structured around the notion of a node graph. Both the source code as well as the user interface is designed around the editing and composition (or linking) of atomic functional units.

Contents

The source code for the software application is organized into atomic functional units called nodes. This is typically done using classes derived from a base class for all nodes. Each node can have inputs and outputs, which are typically also implemented using classes derived from base classes for all inputs and all outputs. Outputs and inputs can refer to each other, typically by holding pointers to instances of other outputs or inputs. When a node executes its functionality, it retrieves its inputs by following the pointers stored in its inputs to retrieve data output by other nodes. The node then executes its operation on these inputs to produce its own outputs. The ability to link nodes together in this way allows complex tasks or problems to be broken down into atomic nodal units that are easier to understand.

The user interface of the software application will often visually display the node graph to the user. This is often accomplished by using the GPU to perform the rendering which is subsequently displayed on the desktop to the user. Common APIs for the GPU are OpenGL and DirectX. Nodes are often drawn as rectangles, and connections between nodes are drawn with lines or splines.

The use of node graph architecture started in the 1960s.[ citation needed ] Today the use of node graphs has exploded. The fields of graphics, games, and machine learning are the main adopters of this software design with the majority of tools using node graph architecture.[ citation needed ]

To this day, there is some debate as to the benefits of visual programming and node graph architecture. Advocates highlight how the abstraction that node graphs provide makes the tool easier to use. Critics highlight how visual programming is too restrictive and how they must resort to modifying source code or scripts to accomplish their tasks.

History

There is an ongoing effort by Eric Hosick on Twitter to collect snapshots of all node graph user interfaces in most software applications. The effort attempts to document the evolution and explosion of node graph user interfaces starting from their initial roots. This visual history is hosted on a blog page called Visual Programming Languages - Snapshots. Work leading to node graph architectures and visual programming seems to have started in the 1960s, in the area known as "man-machine communications".

In William Robert Sutherland's MIT thesis (1966) "Online Graphical Specification of Procedures", he describes and analyses topics around a 2D pictorial language. This is one of the first investigations in dataflow-based workflows or programs. Since then his thesis has been used as "prior art" in order to quash lawsuits about dataflow ideas today. His work is often thought to have led the way to what is known as computer-aided design (CAD) today.

  1. A pictorial program is a natural way of expressing parallel processes. The two-dimensional nature of the language helps in visualizing many things happening at once. [1]
  2. The ease of debugging programs, particularly parallel ones, will be enhanced by a pictorial language form. Being able to attach data probes and to see a program run gives one a grasp of detail that is hard to obtain in any other way. [1]
  3. A program's execution need not be controlled by the usual explicit sequential flow conventions. The movement of data through a program may determine its operation. A data controlled convention corresponds closely to our intuitive ideas of how a graphical program should operate and also allows parallel programming without explicit flow designations. [1]

In 1969, T. O. Ellis, J. F. Heafner, and W. L. Sibley published a paper concerning a Graphical Input Language (GRAIL). Their work was related to the RAND Tablet which began with research on Sketchpad, a system where users could write computer commands directly on a tablet, conducted by Ivan Sutherland. The GRAIL system used a flowchart-based graphical programming language and could recognize handwritten letters and gestures. [2] Alan Kay has given a number of demos of the GRAIL system, however, he was not involved with the creation of the system.

  1. Important organizational concepts in the GRAIL system are the sequential flow of control, the hierarchy of subroutines, and the language (flow diagrams) for pictorially relating the organization within the concepts of the first two. [2]
  2. The sequential nature of control allows the man to envision isolated processes that are adapted to specific functions--which, in turn, allow the organizer to think of the total program in terms of manageable subparts. [2]
  3. The subroutine hierarchy emphasizes the notion of isolated processes even more strongly. [2]
  4. Flow diagrams help the man to picture his control options and the relationship between processes by expressing these interrelationships in two dimensions. [2]
Blender node graph, 2006 Working with Nodes Blender.PNG
Blender node graph, 2006

Some of the more recent uses of node graph architectures started around 2005. Node graphs in this time frame start to develop paradigms to deal with complexity in the node graph. The complexity arose as the number of nodes and links in the graph increased. One of the main ideas dealing with complexity was the concept of a group or package node which hid nodes inside of itself, only exposing the inputs and outputs of the group.

Abstraction and Complexity

In the paper Hierarchical Small Worlds in Software Architecture [3] author Sergi Valverde argues that most large software systems are built in a modular and hierarchical fashion, and that node graphs can be used to analyze large software systems. Many other software analysis papers often use node graphs to analyze large software systems suggesting that node graphs are good models of the internal structure and operation of the software. [4]

Visual Programming Debate

Node graphs are a subset of the broader class of visual programming languages. Node graphs allow you to design programs in a visual and structured way instead of through the authoring of source code. In the film and video game industries node graphs are synonymous with visual programming. There is currently some debate on the power, abstraction, and need of node graphs and visual programming languages.

This remains an active area of debate with new discussions occurring in open forums to this day. The following are a few of the largest discussions to date.

Research studies tend to shed more details on these discussions and highlight more of the advantages and disadvantages of node graphs. They indicate that node graphs and visual programming are easy to understand for new users, but as the users move to more complex tasks they often need to resort to authoring textual source code. [7] Another survey focuses on peoples beliefs on the cognitive effects of visual programming, in which they found that professional programmers are the most skeptical of visual programming. [8] Other studies have shown in psychological experiments that visual programming can have significant positive effects on performance in cognitive tasks. [9]

Node Graph

An example node graph NodegraphSketch3.png
An example node graph

A node graph in the context of software architecture refers to an organization of software functionality into atomic units known as nodes, and where nodes can be connected to each other via links. The manipulation of nodes and links in the node graph can be often be accomplished through a programmable API or through a visual interface by using the mouse. In the diagram above, the node graph appears on the right-hand side.

In modern-day usage, the term "node graph" is an open compound word. However, in older software it was referred to as a "nodegraph", a closed compound word.

Node

Nodes perform some type of computation. They encapsulate this executable functionality and will often take inputs and produce outputs as a by-product of execution. A simple example is a node that adds two numbers together. The inputs are the two numbers to add and the output is the sum of the two numbers.

Nodes are analogous to mathematical functions of the following form.

,

where is the node's computation, is a vector of the node's input values and is a vector of the node's output values.

Visually nodes are often represented by rectangles. However, this is not a convention that is followed by all applications. In the diagram above there are three nodes labeled "Video", "Add Star" and "Add Circle".

Node Parameters

Nodes often have additional parameters, that define their execution. These parameters are backed by data types in the node's source code.

Mathematically they can be thought of as additional input values to the node's compute function. The only difference is that these values are controlled directly by the user instead of being output by another node as a by-product of its execution. For example, in the simple example above regarding a node that adds two numbers, we can introduce a bias parameter on the node so that the node can add an extra fixed number onto the sum.

Visually the node's parameters are often exposed after the user clicks on the node. This helps to reduce visually cluttering the node graph. In the diagram above we see a parameter window opening up beside the "Add Star" node.

Node Inputs and Outputs

Nodes often have inputs and outputs, as discussed above. Inputs and outputs are backed by data types in the node's source code. Inputs and outputs are crucial to storing values before and after the node's execution.

Mathematically the node's inputs and outputs are analogous to input and output values of functions.

,

where is the node's computation, is a vector of the node's input values and is a vector of the node's output values.

Visually the inputs and outputs of nodes are often represented with circles.

Links transfer the values stored in data types between different nodes. They are analogous to mathematical composition. For example, if node A is feeding its outputs to node B, this can be represented mathematically as follows.

,

where and are the operations performed by node B and node A, is a vector of the node A's input values and is a vector of the node B's output values.

Node Types

The type of a node indicates which compute operation it will perform when executed. There are often many different node types participating in the node graph. The following are some examples:

The most important node type for managing complexity is the group node. This node type does not execute software code in the same as other nodes. This node simply groups a subset of connected nodes together and manages the inputs and outputs into or out of the group. This hides complexity inside of the group nodes and limits their coupling with other nodes outside the group. This leads to a hierarchy where smaller graphs are embedded in group nodes. The following are examples of group nodes which are used to group a subset of connected nodes and to help simplify the graph.

User Interface

Software applications using node graph architecture will typically expose the node graph visually or graphically to the user, allowing the user to make changes to the node graph. Using the mouse, users will typically be able to:

With the increasing usage of node graphs, there is currently increased attention on creating user-friendly interfaces. Often these new interfaces are being designed by user interface specialists and graphical designers. The following are some user interfaces designed by artists and designers.

Directed Acyclic Graphs

Example directed acyclic graph Directed acyclic graph.png
Example directed acyclic graph

Many theoretical results from graph theory apply to node graphs, especially with regards to topology. This subject area where Nodes are linked together to form graphs is well studied.

One particular area of concern during node graph evaluation is cycles. When cycles are present in the node graph, the evaluation never ends as nodes are continually executed by following links. To avoid these problems many node graphs architectures restrict themselves to a subset of graphs known as directed acyclic graphs.

Use in Computer Graphics

An example of a node graph based user interface NodeGraphScreenshot.png
An example of a node graph based user interface

The use of node graph architecture in software design is especially popular in the film and video game industries. The diagram above shows a simplified user interface for an artistic tool for editing and creating videos. The nodes are represented as rectangles and are connected to each other through curved lines (Bézier curves). In this software's operational model, a video sequence is being passed through the lines onto the next node, and each node performs some additional modifications to the video sequence. In this example one video is translated in 2D, another is pixelated, and finally, both streams are merged.

The following are some examples of software using node graph architecture in the film and video game industries.

Use in Machine Learning

Simple neural network layers Colored neural network.svg
Simple neural network layers

The use of node graph architecture in software design has recently become very popular in machine learning applications. The diagram above shows a simple neural network composed of 3 layers. The 3 layers are the input layer, the hidden layer, and the output layer. The elements in each layer are weights and are connected to weights in other layers. During inference, the machine learning algorithm evaluates the weights in the output layer through a sequence of functional evaluations over the weights from previous layers. During training, the machine learning algorithm uses optimization to minimize a loss function, where the loss function depends on the difference between the weights in the output layer and the expected values. Node graphs are used to visualize, configure and debug these neural network layers.

The following are examples of machine learning software using node graph architecture without a graphical interface for the node graphs.

The following are some examples of machine learning software using node graph architecture.

Notes

  1. 1 2 3 Sutherland, William Robert (1966). The on-line graphical specification of computer procedures (Thesis). Massachusetts Institute of Technology. hdl:1721.1/13474?show=full.
  2. 1 2 3 4 5 "GRAIL Graphical Input Language" (PDF).
  3. Valverde, Sergi; Sole, Ricard V. (11 July 2003). "Hierarchical Small Worlds in Software Architecture". arXiv: cond-mat/0307278 .
  4. "Representation and Analysis of Software". CiteSeerX   10.1.1.394.4865 .{{cite journal}}: Cite journal requires |journal= (help)
  5. "Visual Programming Doesn't Suck".
  6. "Visual Programming - Why it's a Bad Idea". October 2018.
  7. "Strengths and weaknesses of a visual programming language in a learning context with children" (PDF).
  8. "Visual programming: the outlook from academia and industry". 1997. doi:10.1145/266399.266415. S2CID   18983760.{{cite journal}}: Cite journal requires |journal= (help)
  9. Blackwell, A.F. (1996). "Metacognitive theories of visual programming: what do we think we are doing?". Proceedings 1996 IEEE Symposium on Visual Languages. pp. 240–246. doi:10.1109/VL.1996.545293. ISBN   0-8186-7508-X. S2CID   36822160.
  10. "Nuke Reference Guide". learn.foundry.com. Retrieved 2020-12-21.
  11. "Katana Reference Guide". learn.foundry.com. Retrieved 2020-12-21.
  12. "Mari Reference Guide". learn.foundry.com. Retrieved 2020-12-21.
  13. "Nuke: Grouping Nodes with the Group Node". learn.foundry.com. Retrieved 2020-12-21.
  14. "Katana: Grouping Nodes". learn.foundry.com. Retrieved 2020-12-21.

Related Research Articles

<span class="mw-page-title-main">Digital compositing</span>

Digital compositing is the process of digitally assembling multiple images to make a final image, typically for print, motion pictures or screen display. It is the digital analogue of optical film compositing.

<span class="mw-page-title-main">User interface</span> Means by which a user interacts with and controls a machine

In the industrial design field of human–computer interaction, a user interface (UI) is the space where interactions between humans and machines occur. The goal of this interaction is to allow effective operation and control of the machine from the human end, while the machine simultaneously feeds back information that aids the operators' decision-making process. Examples of this broad concept of user interfaces include the interactive aspects of computer operating systems, hand tools, heavy machinery operator controls and process controls. The design considerations applicable when creating user interfaces are related to, or involve such disciplines as, ergonomics and psychology.

The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by L. R. Ford Jr. and D. R. Fulkerson. The name "Ford–Fulkerson" is often also used for the Edmonds–Karp algorithm, which is a fully defined implementation of the Ford–Fulkerson method.

<span class="mw-page-title-main">Perceptron</span> Algorithm for supervised learning of binary classifiers

In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers. A binary classifier is a function which can decide whether or not an input, represented by a vector of numbers, belongs to some specific class. It is a type of linear classifier, i.e. a classification algorithm that makes its predictions based on a linear predictor function combining a set of weights with the feature vector.

In software engineering, the terms frontend and backend refer to the separation of concerns between the presentation layer (frontend), and the data access layer (backend) of a piece of software, or the physical infrastructure or hardware. In the client–server model, the client is usually considered the frontend and the server is usually considered the backend, even when some presentation work is actually done on the server itself.

<span class="mw-page-title-main">Visual programming language</span> Programming language written graphically by a user

In computing, a visual programming language or block coding is a programming language that lets users create programs by manipulating program elements graphically rather than by specifying them textually. A VPL allows programming with visual expressions, spatial arrangements of text and graphic symbols, used either as elements of syntax or secondary notation. For example, many VPLs are based on the idea of "boxes and arrows", where boxes or other screen objects are treated as entities, connected by arrows, lines or arcs which represent relations.

<span class="mw-page-title-main">LabVIEW</span> System-design platform and development environment

Laboratory Virtual Instrument Engineering Workbench (LabVIEW) is a system-design platform and development environment for a visual programming language from National Instruments.

<span class="mw-page-title-main">Graphical widget</span> Element of interaction in a graphical user interface

A graphical widget in a graphical user interface is an element of interaction, such as a button or a scroll bar. Controls are software components that a computer user interacts with through direct manipulation to read or edit information about an application. User interface libraries such as Windows Presentation Foundation, Qt, GTK, and Cocoa, contain a collection of controls and the logic to render these.

<span class="mw-page-title-main">Backpropagation</span> Optimization algorithm for artificial neural networks

In machine learning, backpropagation is a widely used algorithm for training feedforward artificial neural networks. Generalizations of backpropagation exist for other artificial neural networks (ANNs), and for functions generally. These classes of algorithms are all referred to generically as "backpropagation". In fitting a neural network, backpropagation computes the gradient of the loss function with respect to the weights of the network for a single input–output example, and does so efficiently, unlike a naive direct computation of the gradient with respect to each weight individually. This efficiency makes it feasible to use gradient methods for training multilayer networks, updating weights to minimize loss; gradient descent, or variants such as stochastic gradient descent, are commonly used. The backpropagation algorithm works by computing the gradient of the loss function with respect to each weight by the chain rule, computing the gradient one layer at a time, iterating backward from the last layer to avoid redundant calculations of intermediate terms in the chain rule; this is an example of dynamic programming.

<span class="mw-page-title-main">Multilayer perceptron</span> Type of feedforward neural network

A multilayer perceptron (MLP) is a fully connected class of feedforward artificial neural network (ANN). The term MLP is used ambiguously, sometimes loosely to mean any feedforward ANN, sometimes strictly to refer to networks composed of multiple layers of perceptrons ; see § Terminology. Multilayer perceptrons are sometimes colloquially referred to as "vanilla" neural networks, especially when they have a single hidden layer.

String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories. They are a prominent tool in applied category theory. When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation. This has led to the development of categorical quantum mechanics where the axioms of quantum theory are expressed in the language of monoidal categories.

<span class="mw-page-title-main">Common Lisp Interface Manager</span>

The Common Lisp Interface Manager (CLIM) is a Common Lisp-based programming interface for creating user interfaces, i.e., graphical user interfaces (GUIs). It provides an application programming interface (API) to user interface facilities for the programming language Lisp. It is a fully object-oriented programming user interface management system, using the Common Lisp Object System (CLOS) and is based on the mechanism of stream input and output. There are also facilities for output device independence. It is descended from the GUI system Dynamic Windows of Symbolics' Lisp machines between 1988 and 1993.

... you can check out Common Lisp Interface Manager (CLIM). A descendant of the Symbolics Lisp machines GUI framework, CLIM is powerful but complex. Although many commercial Common Lisp implementations actually support it, it doesn't seem to have seen a lot of use. But in the past couple years, an open-source implementation of CLIM, McCLIM – now hosted at Common-Lisp.net – has been picking up steam lately, so we may be on the verge of a CLIM renaissance. – From Practical Common Lisp

In software engineering, graphical user interface testing is the process of testing a product's graphical user interface (GUI) to ensure it meets its specifications. This is normally done through the use of a variety of test cases.

A signal-flow graph or signal-flowgraph (SFG), invented by Claude Shannon, but often called a Mason graph after Samuel Jefferson Mason who coined the term, is a specialized flow graph, a directed graph in which nodes represent system variables, and branches represent functional connections between pairs of nodes. Thus, signal-flow graph theory builds on that of directed graphs, which includes as well that of oriented graphs. This mathematical theory of digraphs exists, of course, quite apart from its applications.

In game theory, the common ways to describe a game are the normal form and the extensive form. The graphical form is an alternate compact representation of a game using the interaction among participants.

This glossary of computer hardware terms is a list of definitions of terms and concepts related to computer hardware, i.e. the physical and structural components of computers, architectural issues, and peripheral devices.

<span class="mw-page-title-main">Parametric design</span> Engineering design method

Parametric design is a design method where features are shaped according to algorithmic processes, in contrast to being designed directly. In this method, parameters and rules determine the relationship between design intent and design response. The term parametric refers to input parameters fed into the algorithms.

<span class="mw-page-title-main">SAMSON</span>

SAMSON is a computer software platform for molecular design being developed by OneAngstrom and previously by the NANO-D group at the French Institute for Research in Computer Science and Automation (INRIA).

An artificial neural network (ANN) combines biological principles with advanced statistics to solve problems in domains such as pattern recognition and game-play. ANNs adopt the basic model of neuron analogues connected to each other in a variety of ways.

<span class="mw-page-title-main">Graph neural network</span> Class of artificial neural networks

A Graph neural network (GNN) is a class of artificial neural networks for processing data that can be represented as graphs.

References