# Graph, GraphTrace and GraphView

> Graph holds named nodes and edges, directed or not.

Page: https://fframes-kit.pages.dev/docs/computer-science/graph-graph-trace-and-graph-view/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`Graph` holds named nodes and edges, directed or not. `Graph::new(&names, &edges, directed)`
gives every edge weight 1; `Graph::weighted` takes `(from, to, weight)` and shows the
weights. Nodes are placed in layers along the edges with `layout::layered`; `at` places
them yourself, in the same slots and layers (fractions are fine), and
`layout(&GraphLayout::KamadaKawai, 2.0)` places them with one of the shared graph layouts
(`Circular`, `KamadaKawai`, `Planar`, `Random`, `Shell`, `Spectral`, `Spiral`, `Spring`,
`Partite`, `Tree` or a function of your own), the farthest node `scale` slots and layers from
the middle.

`GraphTrace` records a search over a graph, one `GraphStep` per visit or discovery: the
current node, the frontier, the finished nodes, the tree edges that reached each node, the
edge being looked at, the distances and a note.

- `GraphTrace::bfs(&graph, start)` keeps a queue and visits by distance in edges;
- `GraphTrace::dfs(&graph, start)` keeps a stack, goes deep first and backs out;
- `GraphTrace::dijkstra(&graph, start)` takes the closest unfinished node each time and
  notes each relaxation (`T: 3 + 5 is not below 4`).

`order()` is the order nodes were finished in. `GraphView` draws the trace: the frontier,
current and finished nodes in the cell colours, tree edges in `tree_color`, the active edge
in `active_color`, distances above the nodes (`∞` until reached) for Dijkstra, and the
frontier (`queue: B, C`) and the note under the graph. Weights sit on the middle of their
edge, on a small `weight_fill` plate (the distances have one too), so the edge never runs
through the digits. With `curved` every edge is an arc. In a directed graph, a backward edge
(one that closes a cycle, found by a depth first search from the first node; the layered
layout points these up) always curves, by a third of its length, so it passes beside the
forward edges instead of over them; two edges between the same nodes bend apart. Gallery
scenes: `GraphView` (BFS and DFS side by side), `Dijkstra`, `WeightedGraph` (Dijkstra on a
graph with backward edges, and on a ring placed by `GraphLayout::Circular` with `curved`).

Gallery clip of `GraphView`: https://fframes-kit.pages.dev/media/scenes/GraphView-229f12e2.mp4

Gallery clip of `Dijkstra`: https://fframes-kit.pages.dev/media/scenes/Dijkstra-e612a7c0.mp4

Gallery clip of `WeightedGraph`: https://fframes-kit.pages.dev/media/scenes/WeightedGraph-ff802e35.mp4

```rust
use fframes_kit::prelude::*;

let graph = Graph::new(&["A", "B", "C", "D"], &[(0, 1), (0, 2), (1, 3)], false);
let bfs = GraphTrace::bfs(&graph, 0);
assert_eq!(bfs.order(), [0, 1, 2, 3]);

let ring = Graph::new(&["A", "B", "C"], &[(0, 1), (1, 2), (2, 0)], true)
    .layout(&GraphLayout::Circular, 1.0);
// on a circle of radius 1, the first node on the right
assert!(ring.positions.iter().all(|&(x, y)| (x.hypot(y) - 1.0).abs() < 1e-9));
assert!(ring.positions[0].0 > 0.99);

fn search<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a GraphTrace) -> Svgr<'a> {
    ui.show(GraphView {
        trace: Some(trace),
        step_time: 0.6,
        ..ui.defaults()
    })
}
```

## API

Components are plain structs. Set the fields you need and fill the rest with `..ui.defaults()`: the defaults below come from the current theme (`theme.` values are fields of `Theme`).

### GraphView

A graph search: round nodes `radius` pixels with their names, `spacing` pixels between slots and `level` pixels between layers, centred on `center` (units of `ui.space`). It plays a `GraphTrace`, one step every `step_time` seconds from `delay`: the current node lights up, nodes waiting in the frontier take `colors.moved`, finished ones `colors.sorted`, the edge followed lights up and the search tree's edges thicken. A long edge bends round the nodes in its way, and the two edges of a pair that point both ways bend apart. With `curved` every edge is an arc. A backward edge of a directed graph (one that points up against the layers, or left within a layer) always curves, wide enough to pass beside the forward edges instead of over them. Weights sit on the middle of their edge, on a small `weight_fill` plate. Distances (Dijkstra) are written above the nodes, the frontier (`queue: A, B`) and the note under the graph. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | `Option<&GraphTrace>` | `None` | The recorded search steps to play (`GraphTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.8` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the graph, in units of `ui.space`. |
| `spacing` | `f32` | `170.0` | Pixels between neighbouring node slots in a layer. |
| `level` | `f32` | `150.0` | Pixels between layers. |
| `radius` | `f32` | `34.0` | Radius of a node in pixels. |
| `frontier` | `bool` | `true` | Whether the frontier (`queue: A, B`) is written under the graph. |
| `notes` | `bool` | `true` | Whether the step's note is written under the graph. |
| `curved` | `bool` | `false` | Every edge an arc, not only the backward ones and the pairs. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the nodes in each state (current, waiting, finished). |
| `edge_color` | `Color` | `theme.colors.muted` | Colour of the edges. |
| `tree_color` | `Color` | `theme.colors.accent` | Colour of the edges of the search tree built so far. |
| `active_color` | `Color` | `theme.colors.highlight` | Colour of the edge being followed. |
| `dist_color` | `Color` | `theme.colors.highlight` | Colour of the distances written above the nodes. |
| `weight_fill` | `Color` | `theme.colors.background` | The plate behind a weight, so the edge does not run through the digits. |
| `value_style` | `TextStyle` | `value_style` | The font of the node names and weights. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the distances, frontier and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/graph.rs#L355)