# Data structures

Similar to a graph, this framework contains data as nodes and edges. One correction: in the editor's terminology, the graph edges are known as connections.

The `NodeEditor` instance stores this data in a normalized format, specifically as two distinct lists containing objects of the following type:

- `{ id: <string> }` for a nodes
- `{ id: <string>, source: <string>, target: <string> }` for a connections

::diagram{caption="NodeEditor" name="editor/node-editor"}
::

Initializing the editor involves using a basic scheme without any supplementary fields to start with:

```ts
import { NodeEditor, BaseSchemes, getUID } from 'rete'

const editor = new NodeEditor<BaseSchemes>()
```

## Add nodes and connections

When dealing with graph data, you have the option to create arbitrary identifiers for nodes and connections, or utilize the existing ones.

```ts
const a = { id: getUID() }
const b = { id: getUID() }
const connection = { id: getUID(), source: a.id, target: b.id }

await editor.addNode(a)
await editor.addNode(b)
await editor.addConnection(connection)
```

## Retrieve nodes and connections

We can now retrieve a list of newly added nodes and connections

```ts
editor.getNodes() // returns [a, b]
editor.getConnections() // returns [connection]
```

You have all the necessary methods to process the graph, such as retrieving a list of input connections or all incoming nodes, as we will discuss in the following sections.

## Incoming/outgoing connections

::diagram
---
caption: Incoming/outgoing connections
name: guides/data-structures/connections
---
::

The following code shows how to retrieve a list of incoming and outgoing connections for `node`:

```ts
const connections = editor.getConnections()

const incomingConnections = connections.filter(connection => connection.target === node.id)
const outgoingConnections = connections.filter(connection => connection.source === node.id)
```

## Incoming/outgoing nodes

::diagram{caption="Incoming/outgoing nodes" name="guides/data-structures/nodes"}
::

We can use variables from the previous section to retrieve incoming or outgoing nodes:

```ts
const incomers = incomingConnections.map(connection => editor.getNode(connection.source))
const outgoers = outgoingConnections.map(connection => editor.getNode(connection.target))
```

In general, this is sufficient for simple cases, but if there are more than one connections between nodes, we will have to remove duplicates:

```ts
Array.from(new Set(incomers))
Array.from(new Set(outgoers))
```

## Advanced methods

The previously mentioned approaches are fairly flexible, but they require the implementation of more advanced methods on your own. Fortunately, the [`rete-structures` package](https://github.com/retejs/structures){rel="nofollow"} offers such methods divided into 4 categories:

- **Mapping**: iterating through a list of nodes while transforming or filtering it
- **Sets**: techniques for working with graphs as sets, including union, difference and intersection.
- **Subgraph**: graphs that have parent-child relationships between nodes.
- **Traverse**: traversing nodes by their connections, such as retrieving only incoming nodes or all predecessors.

::diagram{caption="rete-structures" name="guides/data-structures/structures"}
::

### Usage

Install the dependency

```bash
npm i rete-structures
```

Use the following import statement and declaration

```ts
import { structures } from 'rete-structures'

const graph = structures(editor)

graph.nodes()
graph.connections()
```

There are other `graph` methods that serve distinct purposes, demonstrated below with code and an interactive preview. The resulting nodes are prominent and the preview allows users to select nodes and observe changes.

The execution of any of the methods usually yields nodes that were not discarded, as well as their connections if both of their nodes are present.

### Traverse

#### Roots

Nodes without incoming connections are known as root nodes

```ts
structures(graph).roots()
```

::structures{#roots}
::

#### Leaves

Leaf nodes are those that have no outgoing connections

```ts
structures(graph).leaves()
```

::structures{#leaves}
::

#### Incomers

Incoming nodes directly connected to the selected node

```ts
structures(graph).incomers(selectedNodeId)
```

::structures{#incomers pick="e"}
::

#### Outgoers

Outgoing nodes directly connected to the selected node

```ts
structures(graph).outgoers(selectedNodeId)
```

::structures{#outgoers pick="a"}
::

#### Predecessors

Every incoming node, as well as its own incoming nodes and so on

```ts
structures(graph).predecessors(selectedNodeId)
```

::structures{#predecessors pick="f"}
::

#### Successors

Every outgoing node, as well as its own outgoing nodes and so on

```ts
structures(graph).successors(selectedNodeId)
```

::structures{#successors pick="c"}
::

### Mapping

#### Filter

Filtering can be applied to both nodes and connections

```ts
structures(graph).filter(Boolean, ({ source, target }) => source === selectedNodeId || target === selectedNodeId)
```

::structures{#filter pick="d"}
::

### Sets

The following examples shows the cases where selected node serves as the second graph.

#### Union

The union of a graph and a node from this graph gives the same graph

```ts
structures(editor).union({ nodes: [selectedNode], connections: [] })
```

::structures{#union pick="d"}
::

#### Difference

By subtracting the node from the graph, you can obtain a new graph without that node

```ts
structures(editor).difference({ nodes: [selectedNode], connections: [] })
```

::structures{#union pick="d"}
::

#### Intersection

By intersecting the graph with the node from this graph, you'll get a new graph that includes only the selected node

```ts
structures(editor).intersection({ nodes: [selectedNode], connections: [] })
```

::structures{#intersection pick="d"}
::

### Subgraph

This category pertains to graphs that contain nodes with a parent-child relationship, specifically, nodes that have a `parent` field defined and are nested within other nodes.

#### Children

The list of direct descendant, namely children

```ts
structures(editor).children((n) => n.id === selectedNodeId);
```

::structures{#children pick="nestedParent"}
::

#### Parent

The list of parents

```ts
structures(editor).parents((n) => n.id === selectedNodeId);
```

::structures{#parent pick="a"}
::

#### Descendants

The list of all descendants, including children, grandchildren and successive generations

```ts
structures(editor).descendants((n) => n.id === selectedNodeId);
```

::structures{#descendants pick="rootParent"}
::

#### Ancestors

The list of all ancestors, from parents to great-grandparents and beyond

```ts
structures(editor).ancestors((n) => n.id === selectedNodeId);
```

::structures{#ancestors pick="a"}
::

#### Orphans

Nodes without a specified `parent` property

```ts
structures(editor).orphans();
```

::structures{#orphans}
::

#### Siblings

Nodes that have a common parent with the selected node, even if it has no parent

```ts
structures(editor).siblings((n) => n.id === selectedNodeId)
```

::structures{#siblings pick="b"}
::