# Graphs

> Nodes, ports and edges as data: what may be joined, changes that undo, and a layout that follows or is pinned against.

A graph is things joined to things: the steps of a pipeline, the nodes of a
flow, the boxes and arrows of a diagram. The things are nodes; where a line may
be attached to one is a port; a line from one port to another is an edge. What
may be joined, what a change to the graph is, and where its nodes are put are
questions about the graph itself, whatever draws it.

## Best practices

**Let ports say what they accept.** A port that only gives is not joined to
another that only gives; a port that carries one kind of thing is not joined to
one that carries another; a port that takes a single edge does not take a
second. Decide these from the ports, before anything is drawn, so that the same
answer is given to a drag, a key and a program.

**Run every edge the way it means.** An edge runs from the port that gives to
the port that takes, whichever of the two it was drawn from. Between ports that
do not say, it runs from where it was begun.

**Refuse with a reason.** A connection that is not made says why: the same two
are already joined, it would make a loop, the port is full. "Nothing happened"
teaches nobody anything.

**Refuse a loop only where a loop means nothing.** A pipeline cannot feed
itself; a state machine returns to where it was all the time. Make it a rule
of the graph, not of graphs.

**Take a node's edges with it.** An edge with nothing at one end is not an
edge. Removing a node removes its edges in the same action, so that one undo
brings back the node and every line that was attached to it.

**Make every change a thing that can be taken back.** Adding, removing, moving,
joining, and moving one end of an edge to another port are each one change,
with what was there before. Several that people think of as one — a node
dropped and everything laid out again around it — are recorded as one. See
[Undo and redo](https://ui.publictheta.com/foundations/history.md).

**Lay out on request, or keep laid out — and say which.** A layout may be
something people ask for, once, and then arrange by hand; or it may be live,
following the graph as it changes, so that a node added takes its place and the
rest make room. Both are right for different work. Never lay out without being
asked in the first mode, and never leave things where they fell in the second.

**Let a node be pinned.** A pinned node stays exactly where it is, whatever the
layout does: the layout is placed about it, and whatever would land on it goes
past it instead. Nothing a layout places ever overlaps another node.

**Believe the hand.** While the layout is live, a node that someone moves stays
where they put it: moving it pins it. The alternative — the node springing back
— tells people their own gesture did not count.

**Keep the whole where it was.** Laying out does not send the graph off to
another part of the plane: with nothing pinned, its top-left corner stays where
it was. Laying out twice changes nothing the second time.

## Conventions

| Rule                 | What is refused                                            |
| -------------------- | ---------------------------------------------------------- |
| Direction            | Two outputs joined; two inputs joined                      |
| Type                 | Ports that each say what they carry, and say differently   |
| Once                 | The same two ports joined a second time                    |
| Limit                | One more edge than a port holds                            |
| Itself               | A port to itself; a node to itself, unless that is allowed |
| No loops, where held | An edge whose target already leads back to its source      |

| State  | Moved by hand | Moved by a layout | Removed |
| ------ | ------------- | ----------------- | ------- |
| Free   | Yes           | Yes               | Yes     |
| Pinned | Yes           | No                | Yes     |
| Locked | No            | No                | No      |

See also [Connecting](https://ui.publictheta.com/foundations/connect.md), [Diagram](https://ui.publictheta.com/components/diagram.md) and
[Layered layout](https://ui.publictheta.com/algorithms/layered-layout.md).

## Behaviour

Each statement is verified by a test in Chromium, Chromium (touch), Firefox, WebKit, WebKit (touch), unless it names the environments it applies to or is marked open.

### Ports

- A port sits on its side of its node; the ports of a side share it evenly.
- A port that says where along its side it is sits there.
- A port's key reads back as the port, whatever its ids hold.
- The edges at a node are those that arrive and those that leave; at a port, those at that port.

### What may be connected

- An edge runs from the port that gives to the port that takes, whichever it was drawn from.
- Between ports that do not say, an edge runs from the one it was drawn from.
- Two ports that both only give, or both only take, are not connected.
- Ports that carry different types are not connected; a port that does not say takes any.
- The same two ports are not connected twice.
- A port that holds as many edges as it may takes no more.
- A node is not connected to itself unless that is allowed, and a port never to itself.
- Where cycles are refused, an edge that would close one is, whichever end it is drawn from.
- An edge is refused as closing a cycle exactly when, with it, no order puts every node after those that lead to it.
- A port that is not there is not connected.
- An application's own rule is asked of the port that gives and the port that takes.
- The ports an edge may be taken to are exactly those that do not refuse it, in the order of the nodes.

### Changes

- Taking a node out takes out every edge at it in the same change; undone, both are back where they were.
- Taking out edges and nodes together takes each once; taking out what is not there is no change.
- Any changes, then their inverses, give back the graph as it was.
- A change shares what it does not touch, and one that changes nothing gives the same graph.
- What is added goes after what is there.
- An end of an edge is moved to another port as one change, which keeps the edge and its way.
- An end is not moved to a port that refuses it, and the edge itself does not stand in its own way.
- An edge that is refused is no change, but the reason.
- A node is put into an edge as changes made together: the edge out, and two in its place, through the node's first ports that take and give.
- A node with no port to take what the edge carries, or none to give it on, or one of the edge's own ends, is not put into it.
- Where loops are refused, a node that the edge's target already leads to is not put into it.

### Layout

- A graph is laid out in layers, its edges reading onward, a gap between one layer and the next.
- With nothing held, the layout begins where the nodes did: the corner of the whole does not move.
- A node that is pinned is not moved, nor one that is locked.
- No node that the layout places overlaps another, held or not.
- Laying out what has just been laid out moves nothing.
- With a node held, the layout is placed about it: it is exactly where the layout wants it, and the rest follow.
- A held node standing where another would go: that one, and those after it in its layer, are pushed past it.
- A graph with nothing in it has nothing to move.

### Kept laid out

- A change is followed by the layout in the same list: one undo takes both back.
- A node moved by hand is pinned where it was put, and the rest laid out about it.
- A change that leaves everything in its place is only itself.

## Reference implementation

React: `npx shadcn@latest add https://ui.publictheta.com/r/graph.json`