Node graph architecture: Difference between revisions

Content deleted Content added

Inline

Revision as of 03:32, 14 March 2021

Node graph architecture is a software design structured around the concept of a node graph. 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.

Visual History

There is an ongoing effort by Eric Hosick on Twitter to collect snapshots of all node graph user interfaces in all software applications. The effort attempts to document the evolution and explosion of node graph user interfaces starting from the very first known use. This visual history is hosted on his blog page called Visual Programming Languages - Snapshots.

Ivan Sutherland's Sketchpad program, 1963

Some of the earliest uses of node graph architectures started back in the 1960s with the work of Ivan Sutherland and Alan Kay.

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.

Visual Programming Debate

Node graph architecture is 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.

Advocates of visual programming generally emphasize how it simplifies programming because it abstracts away many details and only exposes controls that are necessary for their domain. These controls are the parameters on the nodes which control their behavior and the links between nodes.
Critics of visual programming generally emphasize how it does not offer enough control, and how for more complex tasks it becomes necessary to author source code. However, these more complex tasks often fall outside the intended usage or domain of the node graph.

This remains an active area of debate with new discussions occurring in open forums to this day.

Research studies tend to lean in favor of critics 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. However, in well-defined domains such as the film and video game industries, node graphs remain the default user interface for most digital content creation tools.

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.

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.

{outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})

,

where $f_{nodeA}$ is the node's computation, $inputs_{nodeA}$ is a vector of the node's input values and ${outputs}_{nodeA}$ 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 inputs and outputs analogous to input and output values of functions.

{outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})

,

where $f_{nodeA}$ is the node's computation, $inputs_{nodeA}$ is a vector of the node's input values and ${outputs}_{nodeA}$ is a vector of the node's output values.

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

Node Links

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.

{outputs}_{nodeB}=f_{nodeB}(f_{nodeA}({inputs}_{nodeA}))

,

where $f_{nodeB}$ and $f_{nodeA}$ are the operations performed by node B and node A, $inputs_{nodeA}$ is a vector of the node A's input values and $y_{nodeB}$ is a vector of the node B's output values.

Node Types

There are often many different node types participating in the node graph. For example, Nuke, a popular visual effects compositing program, includes hundreds of nodes.^[1] each performing specific tasks. For example, Nuke's Merge node produces an output image in which a number of input images have been layered. By connecting many different node types together complex image effects can be produced.

The node graph architecture often allows the grouping of nodes inside other group nodes. 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.

In the paper Hierarchical Small Worlds in Software Architecture^[2] 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^[3].

Directed Acyclic Graphs

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.

User Interface

Software applications using node graph architecture will typically expose the node graph visually to the user, allowing the user to make changes to the node graph. Users will be able to visualize new nodes that they create and also manually drag links to connect nodes together using the mouse. In the image above the node graph is displayed in the mid-left panel of the image. The other panels show some of the effects of evaluating the node graph.

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.

Use in Computer Graphics

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 (Bezier 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 together.

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

Use in Machine Learning

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.

References

^ "Nuke Reference Guide". learn.foundry.com. Retrieved 2020-12-21.
^ Valverde, Sergi; Sole, Ricard V. (11 July 2003). "Hierarchical Small Worlds in Software Architecture". arXiv:cond-mat/0307278.
^ "Representation and Analysis of Software". CiteSeerX 10.1.1.394.4865. {{cite journal}}: Cite journal requires |journal= (help)

Metrics of Software Architecture Changes Based on Structural Distance
Representation and Analysis of Software
"Graph Grammars and Constraint Solving for Software Architecture Styles". 1998: 69–72. CiteSeerX 10.1.1.108.9362. {{cite journal}}: Cite journal requires |journal= (help)
"Application of Graph Theory in Computer Science and Enginnering". 2014: 1–4. CiteSeerX 10.1.1.800.2735. {{cite journal}}: Cite journal requires |journal= (help)
"Implementing a Reverse Dictionary, based on word definitions, using a Node-Graph Architecture" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
"Representation and Analysis of Software". CiteSeerX 10.1.1.394.4865. {{cite journal}}: Cite journal requires |journal= (help)
A History of Visual Programming: From Basic to Bubble
Blockly
What is visual programming
What is visual programming

[1] "Nuke Reference Guide". learn.foundry.com. Retrieved 2020-12-21.

[2] Valverde, Sergi; Sole, Ricard V. (11 July 2003). "Hierarchical Small Worlds in Software Architecture". arXiv:cond-mat/0307278.

[3] "Representation and Analysis of Software". CiteSeerX 10.1.1.394.4865. {{cite journal}}: Cite journal requires |journal= (help)

[1]

[2]

[3]

@@ Line 7: / Line 7: @@
 '''Node graph architecture''' is a [[software design]] structured around the concept of a [[Node_graph_architecture#Node_Graph|node graph]]. The [[Source_code|source code]] for the [[Application_software|software application]] is organized into atomic functional units called nodes. This is typically done using [[Class_(computer_programming)|classes]] derived from a [[Inheritance_(object-oriented_programming)#Subclasses_and_superclasses|base class]] for all nodes. Each node can have inputs and outputs, which are typically also implemented using [[Class_(computer_programming)|classes]] derived from [[Inheritance_(object-oriented_programming)#Subclasses_and_superclasses|base classes]] for all inputs and all outputs. Outputs and inputs can refer to each other, typically by holding [[Pointer_(computer_programming)|pointers]] to [[Instance_(computer_science)|instances]] of other outputs or inputs. When a node [[Execution_(computing)|executes]] its functionality, it retrieves its inputs by following the [[Pointer_(computer_programming)|pointers]] stored in its inputs to retrieve data output by other nodes. The node then [[Execution_(computing)|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.
 == Visual History ==
@@ Line 13: / Line 12: @@
 There is an ongoing effort by {{Twitter | id = erichosick | name = Eric Hosick}} to collect snapshots of all node graph user interfaces in all [[Application_software|software applications]]. The effort attempts to document the evolution and explosion of node graph user interfaces starting from the very first known use. This visual history is hosted on his blog page called [http://blog.interfacevision.com/design/design-visual-progarmming-languages-snapshots/ Visual Programming Languages - Snapshots].
+[[File:Sketchpad-Apple.jpg|center|thumb|550px|Ivan Sutherland's Sketchpad program, 1963]]
-[[File:Sketchpad-Apple.jpg|thumb|border|none|upright=3.0|Ivan Sutherland's Sketchpad program, 1963]]
 Some of the earliest uses of node graph architectures started back in the 1960s with the work of [[Ivan_Sutherland|Ivan Sutherland]] and [[Alan_Kay|Alan Kay]].
@@ Line 21: / Line 19: @@
 * [https://www.rand.org/content/dam/rand/pubs/research_memoranda/2005/RM5999.pdf GRAIL Graphical Input Language, Alan Kay, 1968]
+[[File:Working with Nodes Blender.PNG|center|thumb|400px|Blender node graph, 2006]]
-[[File:Working with Nodes Blender.PNG|thumb|border|none|upright=2.0|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.
@@ Line 39: / Line 36: @@
 * Advocates of visual programming generally emphasize how it simplifies programming because it abstracts away many details and only exposes controls that are necessary for their domain. These controls are the parameters on the nodes which control their behavior and the links between nodes.
 * Critics of visual programming generally emphasize how it does not offer enough control, and how for more complex tasks it becomes necessary to author [[Source_code|source code]]. However, these more complex tasks often fall outside the intended usage or domain of the node graph.
 This remains an active area of debate with new discussions occurring in open forums to this day.
@@ Line 46: / Line 42: @@
 * [https://news.ycombinator.com/item?id=19025639 Discussion on Hacker News, 2019]
 * [https://www.reddit.com/r/programming/comments/9kgk75/visual_programming_why_its_a_bad_idea/ Reddit discussion, 2019]
 Research studies tend to lean in favor of critics 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|source code]]. However, in well-defined domains such as the [[Film_industry|film]] and [[Video_game_industry|video game]] industries, node graphs remain the default user interface for most digital content creation tools.
@@ Line 57: / Line 52: @@
 * [https://ieeexplore.ieee.org/abstract/document/545293 Metacognitive theories of visual programming: what do we think we are doing?]
 * [https://www.semanticscholar.org/paper/A-feasibility-study-for-a-general-purpose-visual-Supervisor-Mueller/78448629a9f50b4b6a70eb89d41324461474bee2 A feasibility study for a general-purpose visual programming system]
 == Node Graph ==
+[[Image:NodegraphSketch3.png|center|thumb|400px|An example node graph]]
-Nodes encapsulate some executable functionality and will often take inputs and produce outputs. 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. The inputs and outputs of different nodes can be connected together. This allows the output from one node to flow to the input of another node. Nodes can also have parameters that modify their functionality. For example, in our simple example of an addition node, there could be a parameter on the node called bias, which adds another bias factor to the sum.
+A '''node graph''' in the context of [[Software_architecture|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|API]] or through a visual interface by using the [[Computer_mouse|mouse]]. In the diagram above, the node graph appears on the right-hand side.
+=== Node ===
-[[File:Directed acyclic graph.png|thumb|border|none|upright=1.0|Example directed acyclic graph]]
+Nodes perform some type of computation. They encapsulate this [[Execution_(computing)|executable]] functionality and will often take inputs and produce outputs as a by-product of [[Execution_(computing)|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.
+<center><math>{outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})</math>,</center>
+where <math>f_{nodeA}</math> is the node's computation, <math>inputs_{nodeA}</math> is a vector of the node's input values and <math>{outputs}_{nodeA}</math> 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".
-When nodes are connected together in this way they form a graph, and many theoretical results from graph theory can be applied to the evaluation, update, and maintenance of node graphs. [[Vertex (graph theory)|Nodes]] are linked together to form [[Graph_(discrete mathematics)|graphs]]. One particular area of concern during node graph evaluation is [[Cycle_(graph_theory)|cycles]]. When cycles are present in the node graph, the evaluation never ends as nodes are continually revisited by following links. To avoid these problems many node graphs architectures restrict themselves to a subset of graphs known as [[Directed_acyclic_graph|directed acyclic graphs]].
+=== Node Parameters ===
+Nodes often have additional parameters, that define their [[Execution_(computing)|execution]]. These parameters are backed by [[Data_type|data types]] in the node's [[Source_code|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_(computing)|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.
-[[File:NodegraphSketch3.png|thumb|border|none|upright=2.0|Different types of nodes working together]]
+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_type|data types]] in the node's [[Source_code|source code]]. Inputs and outputs are crucial to storing values before and after the node's [[Execution_(computing)|execution]].
+Mathematically inputs and outputs analogous to input and output values of functions.
+<center><math>{outputs}_{nodeA}=f_{nodeA}({inputs}_{nodeA})</math>,</center>
+where <math>f_{nodeA}</math> is the node's computation, <math>inputs_{nodeA}</math> is a vector of the node's input values and <math>{outputs}_{nodeA}</math> is a vector of the node's output values.
+Visually the inputs and outputs of nodes are often represented with circles.
+=== Node Links ===
+Links transfer the values stored in [[Data_type|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.
+<center><math>{outputs}_{nodeB}=f_{nodeB}(f_{nodeA}({inputs}_{nodeA}))</math>,</center>
+where <math>f_{nodeB}</math> and <math>f_{nodeA}</math> are the operations performed by node B and node A, <math>inputs_{nodeA}</math> is a vector of the node A's input values and <math>y_{nodeB}</math> is a vector of the node B's output values.
+=== Node Types ===
 There are often many different node types participating in the node graph. For example, [[Nuke (software)|Nuke]], a popular [[Digital compositing|visual effects compositing]] program, includes hundreds of nodes.<ref>{{Cite web|title=Nuke Reference Guide|url=https://learn.foundry.com/nuke/12.2/content/reference_guide.html|access-date=2020-12-21|website=learn.foundry.com}}</ref> each performing specific tasks. For example, Nuke's Merge node produces an output image in which a number of input images have been layered. By connecting many different node types together complex image effects can be produced.
@@ Line 78: / Line 98: @@
 In the paper Hierarchical Small Worlds in Software Architecture<ref>{{cite arxiv|eprint=cond-mat/0307278|title=Hierarchical Small Worlds in Software Architecture|first1=Sergi|last1=Valverde|first2=Ricard V.|last2=Sole|date=11 July 2003}}</ref> 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<ref>{{cite journal|citeseerx=10.1.1.394.4865|title=Representation and Analysis of Software}}</ref>.
+=== Directed Acyclic Graphs ===
+[[File:Directed acyclic graph.png|center|thumb|550px|Example directed acyclic graph]]
+Many theoretical results from graph theory apply to node graphs, especially with regards to [[Graph_(topology)|topology]]. This subject area where [[Vertex (graph theory)|Nodes]] are linked together to form [[Graph_(discrete mathematics)|graphs]] is well studied.
-== User Interface ==
-[[Image:NodegraphSketch2.png|thumb|border|none|upright=2.0|An example of a node graph based user interface]]
+One particular area of concern during node graph evaluation is [[Cycle_(graph_theory)|cycles]]. When cycles are present in the node graph, the evaluation never ends as nodes are continually [[Execution_(computing)|executed]] by following links. To avoid these problems many node graphs architectures restrict themselves to a subset of graphs known as [[Directed_acyclic_graph|directed acyclic graphs]].
+=== User Interface ===
 [[Application_software|Software applications]] using node graph architecture will typically expose the node graph visually to the user, allowing the user to make changes to the node graph. Users will be able to visualize new nodes that they create and also manually drag links to connect nodes together using the [[Computer_mouse|mouse]]. In the image above the node graph is displayed in the mid-left panel of the image. The other panels show some of the effects of evaluating the node graph.
@@ Line 88: / Line 112: @@
 * [https://dribbble.com/rfksna/collections/3268905-Node-Graph Node graphs on Dribble]
 * [https://dribbble.com/tags/nodes Nodes on Dribble]
 == Use in Computer Graphics ==
-[[Image:NodeGraphScreenshot.png|thumb|border|none|upright=2.0|An example of a node graph based user interface]]
+[[Image:NodeGraphScreenshot.png|center|thumb|400px|An example of a node graph based user interface]]
 The use of '''node graph architecture''' in [[software design]] is especially popular in the [[Film_industry|film]] and [[Video_game_industry|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_curve|Bezier 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 together.
@@ Line 106: / Line 129: @@
 == Use in Machine Learning ==
-[[File:Colored neural network.svg|thumb|border|none|upright=1.0|Simple neural network layers]]
+[[File:Colored neural network.svg|center|thumb|300px|Simple neural network layers]]
 The use of '''node graph architecture''' in [[software design]] has recently become very popular in [[Machine_learning|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.
@@ Line 123: / Line 146: @@
 * [https://dl.sony.com/ Neural Network Console, Sony]
 * [https://developer.nvidia.com/digits Digits, nVIDIA]
 == References ==