Graph, GraphTrace and GraphView

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).

GraphView 10.5 sPlayUnmuteCopy render command

Dijkstra 13 sPlayUnmuteCopy render command

WeightedGraph 9 sPlayUnmuteCopy render command

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