Coverage for src/manimgx/mobjects/graph.py: 92%
458 statements
« prev ^ index » next coverage.py v7.16.1, created at 2026-10-26 05:52 +0000
« prev ^ index » next coverage.py v7.16.1, created at 2026-10-26 05:52 +0000
1# SPDX-FileCopyrightText: 2026 Academa, Inc.
2# SPDX-FileCopyrightText: 2024 the Manim Community Developers
3# SPDX-FileCopyrightText: 2018 3Blue1Brown LLC
4# SPDX-License-Identifier: MIT
6"""Ported from Manim CE 0.21 (MIT)."""
8from __future__ import annotations
10__all__ = ["DiGraph", "Graph"]
11import itertools as it
12from collections.abc import Callable, Hashable, Iterable, Mapping, Sequence
13from collections.abc import Set as AbstractSet
14from copy import copy
15from typing import (
16 TYPE_CHECKING,
17 Concatenate,
18 Literal,
19 Protocol,
20 Self,
21 TypeIs,
22 Unpack,
23 cast,
24 get_args,
25)
27import numpy as np
28from typing_extensions import TypedDict
30if TYPE_CHECKING:
31 import networkx as nx
33 from manimgx.typing import Point3D, Point3DLike
35 type NxGraph = nx.classes.graph.Graph | nx.classes.digraph.DiGraph
36from manimgx.drawing.paint import BLACK, ParsableManimColor
37from manimgx.mobject import Group, Mobject, VMobject
38from manimgx.mobjects.annotations import LabeledDot
39from manimgx.mobjects.shapes import ArrowTip, Dot, Line
40from manimgx.mobjects.text import MathTex
42type Edge[V] = tuple[V, V]
43"""An edge: the pair of its vertices, from the first to the second."""
44type Maker = Callable[
45 ..., Mobject
46] # a vertex or edge class: its keywords come from the configs
47"""What makes a vertex or an edge: a class, as [Dot][manimgx.Dot] or
48[Line][manimgx.Line], called with the keywords of its config."""
49type Config = dict[
50 str, object
51] # keywords for a vertex's or an edge's class (checked by it)
52type NxLayout = Callable[
53 ..., Mapping[Hashable, np.ndarray]
54] # networkx's layouts, given our layout configs
57def _nx_layout(
58 layout: NxLayout, graph: NxGraph, **kwargs: object
59) -> dict[Hashable, Point3D]:
60 """A networkx layout with our layout config (networkx checks the keywords)."""
61 return {k: np.asarray(p, dtype=float) for k, p in layout(graph, **kwargs).items()}
64def _make(maker: Maker, config_: Config) -> Mobject:
65 """A vertex or edge from its class and its config (the class checks the keywords)."""
66 return maker(**config_)
69class TipConfig(TypedDict, total=False):
70 """The tip of a [DiGraph][manimgx.DiGraph]'s edge, given as `"tip_config"` in its
71 `edge_config`: for every edge, or an edge's own (see
72 [add_tip][manimgx.TipableVMobject.add_tip])."""
74 tip_shape: type[ArrowTip] | None
75 """The class of the tip (default None:
76 [ArrowTriangleFilledTip][manimgx.ArrowTriangleFilledTip])."""
77 tip_length: float | None
78 """The tip's length, in scene units (default None: the edge's default)."""
79 tip_width: float | None
80 """The tip's width, in scene units, for the default filled triangle (default None:
81 its length)."""
84class Positions[V](Protocol):
85 """Where vertices go: anything a vertex looks its point up in (a dict, a layout's result)."""
87 def __getitem__(self, vertex: V, /) -> Point3DLike: ...
90# A layout: the networkx graph, `scale` and the layout config's keywords, to positions.
91type LayoutFunction[V] = Callable[Concatenate[NxGraph, ...], Positions[V]]
92"""A layout of one's own: a function of the graph (a NetworkX graph), called with its
93`scale` and the keywords of the layout config, that returns each vertex's position.
94Each call receives a fresh graph of the current vertices and edges. Changes to that
95graph affect only this call; keep any persistent layout state in the function itself."""
98def _partite_layout(
99 nx_graph: NxGraph,
100 scale: float = 2,
101 partitions: Sequence[Sequence[Hashable]] | None = None,
102 **kwargs: object,
103) -> dict[Hashable, Point3D]:
104 import networkx as nx
106 if partitions is None or len(partitions) == 0:
107 raise ValueError(
108 "The partite layout requires partitions parameter to contain the partition"
109 " of the vertices"
110 )
111 partition_count = len(partitions)
112 for i in range(partition_count):
113 for v in partitions[i]:
114 if v not in nx_graph:
115 raise ValueError(
116 f"{v!r}, in partition {i}, is not a vertex of the graph"
117 )
118 nx_graph.nodes[v]["subset"] = i
119 for v in nx_graph.nodes:
120 if "subset" not in nx_graph.nodes[v]:
121 nx_graph.nodes[v]["subset"] = partition_count
122 return _nx_layout(nx.layout.multipartite_layout, nx_graph, scale=scale, **kwargs)
125def _tree_layout(
126 T: NxGraph,
127 root_vertex: Hashable | None = None,
128 scale: float | tuple[float | None, float | None] | None = 2,
129 vertex_spacing: tuple[float, float] | None = None,
130 orientation: str = "down",
131) -> dict[Hashable, Point3D]:
132 import networkx as nx
134 if root_vertex is None:
135 raise ValueError("The tree layout requires the root_vertex parameter")
136 if not nx.is_tree(T):
137 raise ValueError("The tree layout must be used with trees")
138 children = {root_vertex: list(T.neighbors(root_vertex))}
139 stack = [list(children[root_vertex]).copy()]
140 stick = [root_vertex]
141 parent = dict.fromkeys(children[root_vertex], root_vertex)
142 pos: dict[Hashable, tuple[float, int]] = {}
143 obstruction = [0.0] * len(T)
144 o = -1 if orientation == "down" else 1
146 def slide(v: Hashable, dx: float) -> None:
147 level = [v]
148 while level:
149 nextlevel = []
150 for u in level:
151 x, y = pos[u]
152 x += dx
153 obstruction[y] = max(x + 1, obstruction[y])
154 pos[u] = (x, y)
155 nextlevel += children[u]
156 level = nextlevel
158 while stack:
159 C = stack[-1]
160 if not C:
161 p = stick.pop()
162 stack.pop()
163 cp = children[p]
164 y = o * len(stack)
165 if not cp:
166 x = obstruction[y]
167 pos[p] = (x, y)
168 else:
169 x = sum(pos[c][0] for c in cp) / float(len(cp))
170 pos[p] = (x, y)
171 ox = obstruction[y]
172 if x < ox:
173 slide(p, ox - x)
174 x = ox
175 obstruction[y] = x + 1
176 continue
177 t = C.pop()
178 pt = parent[t]
179 ct = [u for u in list(T.neighbors(t)) if u != pt]
180 for c in ct:
181 parent[c] = t
182 children[t] = copy(ct)
183 stack.append(ct)
184 stick.append(t)
185 x_min = min(pos.values(), key=lambda t: t[0])[0]
186 x_max = max(pos.values(), key=lambda t: t[0])[0]
187 y_min = min(pos.values(), key=lambda t: t[1])[1]
188 y_max = max(pos.values(), key=lambda t: t[1])[1]
189 center = np.array([x_min + x_max, y_min + y_max, 0]) / 2
190 height = y_max - y_min
191 width = x_max - x_min
192 if vertex_spacing is None:
193 sf: float | np.ndarray
194 if isinstance(scale, (float, int)) and (width > 0 or height > 0):
195 sf = 2 * scale / max(width, height)
196 elif isinstance(scale, tuple):
197 sw = 2 * scale[0] / width if scale[0] is not None and width > 0 else 1
198 sh = 2 * scale[1] / height if scale[1] is not None and height > 0 else 1
199 sf = np.array([sw, sh, 0])
200 else:
201 sf = 1
202 else:
203 sx, sy = vertex_spacing
204 sf = np.array([sx, sy, 0])
205 return {v: (np.array([x, y, 0]) - center) * sf for v, (x, y) in pos.items()}
208def _kamada_kawai_layout(
209 graph: nx.Graph,
210 dist: dict[Hashable, dict[Hashable, float]] | None = None,
211 pos: Mapping[Hashable, Point3DLike] | None = None,
212 weight: str = "weight",
213 scale: float = 1,
214 center: Point3DLike | None = None,
215 dim: int = 2,
216) -> dict[Hashable, np.ndarray]:
217 """networkx's Kamada–Kawai layout without scipy: the same energy from the same circular
218 start, minimized by stress majorization (monotone, deterministic) instead of L-BFGS.
219 """
220 import networkx as nx
222 nodes = list(graph)
223 n = len(nodes)
224 if n == 0:
225 return {}
226 if dist is None:
227 dist = {
228 a: dict(row) for a, row in nx.shortest_path_length(graph, weight=weight)
229 }
230 d = np.full((n, n), 1e6)
231 for i, a in enumerate(nodes):
232 for j, b in enumerate(nodes):
233 if b in dist.get(a, {}):
234 d[i, j] = dist[a][b]
235 np.fill_diagonal(d, 0.0)
236 start = nx.circular_layout(graph, dim=2) if pos is None else pos
237 x = np.array([np.resize(np.asarray(start[v], dtype=float), dim) for v in nodes])
238 w = np.where(d > 0, 1.0 / np.maximum(d, 1e-12) ** 2, 0.0)
239 v_plus = np.linalg.pinv(np.diag(w.sum(axis=1)) - w)
240 stress = np.inf
241 for _ in range(3000):
242 gaps = np.linalg.norm(x[:, None] - x[None], axis=2)
243 b = -w * d / np.where(gaps > 1e-12, gaps, np.inf)
244 np.fill_diagonal(b, -b.sum(axis=1))
245 x = v_plus @ b @ x
246 new = float(np.sum(w * (np.linalg.norm(x[:, None] - x[None], axis=2) - d) ** 2))
247 if stress - new < 1e-12 * max(stress, 1.0):
248 break
249 stress = new
250 x -= x.mean(axis=0)
251 if (limit := np.abs(x).max()) > 0:
252 x *= scale / limit
253 if center is not None:
254 x += np.asarray(center, dtype=float)[:dim]
255 return dict(zip(nodes, x, strict=True))
258def _spectral_layout(
259 graph: NxGraph,
260 weight: str | None = "weight",
261 scale: float = 1,
262 center: Point3DLike | None = None,
263 dim: int = 2,
264 store_pos_as: str | None = None,
265) -> dict[Hashable, np.ndarray]:
266 """Laplacian coordinates with axes fixed by node order, including repeated eigenvalues.
268 An eigensolver chooses arbitrary signs and arbitrary orthonormal bases of repeated
269 eigenspaces. Projecting node coordinate axes into each whole space and choosing the
270 largest remaining projection avoids magnifying a nearly zero coordinate into an axis.
271 Node order breaks numerical ties. Unresolved neighboring spaces are oriented jointly;
272 like any spectral embedding, nearly degenerate weights can make coordinates sensitive
273 to perturbations. The constant direction is removed explicitly, also for disconnected
274 graphs.
275 """
276 import networkx as nx
278 nodes, n = list(graph), len(graph)
279 origin = np.zeros(dim) if center is None else np.asarray(center, dtype=float)
280 if dim < 1 or origin.shape != (dim,):
281 raise ValueError(
282 "a layout needs a positive dimension and a center of that dimension"
283 )
284 if n == 0:
285 return {}
286 points = np.zeros((n, dim))
287 if n > 1:
288 adjacency = nx.to_numpy_array(graph, weight=weight)
289 if not np.isfinite(adjacency).all():
290 raise ValueError("spectral edge weights must be finite")
291 if magnitude := float(np.abs(adjacency).max()):
292 adjacency /= magnitude
293 if graph.is_directed():
294 adjacency += adjacency.T.copy()
295 laplacian = np.diag(adjacency.sum(axis=1)) - adjacency
296 values, vectors = np.linalg.eigh(laplacian)
297 rounding = np.finfo(float).eps * n
298 # Cluster only eigenvalues indistinguishable at this solve's backward error:
299 # its measured residual plus the rounding in an n-term matrix product.
300 error = np.linalg.norm(laplacian @ vectors - vectors * values)
301 error += rounding * np.sqrt(n) * np.linalg.norm(laplacian, ord=np.inf)
302 cuts = [0, *(np.flatnonzero(np.diff(values) > 2 * error) + 1), n]
303 columns: list[np.ndarray] = []
304 group = 0
305 while group + 1 < len(cuts):
306 start, end = cuts[group : group + 2]
307 # A space and its orthogonal complement define the same projector. Use the
308 # smaller basis: a full space is exactly I, independent of a solver's axes.
309 complement = end - start > n // 2
310 space = (
311 np.concatenate((vectors[:, :start], vectors[:, end:]), axis=1)
312 if complement
313 else vectors[:, start:end]
314 )
315 projection = space @ space.T
316 if complement:
317 projection = np.eye(n) - projection
318 orthogonality = np.linalg.norm(space.T @ space - np.eye(space.shape[1]))
319 constant = bool(np.any(np.abs(values[start:end]) <= error))
320 if constant:
321 projection -= np.full((n, n), 1 / n)
322 gap = min(
323 values[start] - values[start - 1] if start else np.inf,
324 values[end] - values[end - 1] if end < n else np.inf,
325 )
326 # Residual/gap estimates the uncertainty of a space, not just its eigenvalue.
327 uncertainty = rounding + orthogonality + error / (gap - error)
328 wanted = min(end - start - int(constant), dim - len(columns))
329 basis: list[np.ndarray] = []
330 projection -= projection.mean(axis=0)
331 for _ in range(2):
332 for previous in columns:
333 projection -= np.outer(previous, previous @ projection)
334 for _ in range(wanted):
335 lengths = np.linalg.norm(projection, axis=0)
336 largest = float(lengths.max())
337 if largest <= 2 * uncertainty:
338 break
339 pivot = int(np.flatnonzero(lengths >= largest - uncertainty)[0])
340 direction = projection[:, pivot] / lengths[pivot]
341 basis.append(direction)
342 # Pivoted, twice-orthogonalized projections keep later axes away from
343 # directions already chosen, without amplifying tiny first-node entries.
344 for _ in range(2):
345 projection -= np.outer(direction, direction @ projection)
346 if len(basis) < wanted:
347 # These directions cannot be resolved from a neighboring space with
348 # this solve's accuracy. Orient their joint space instead of silently
349 # losing a low-frequency coordinate or replacing it with a higher one.
350 neighbors = [i for i in (group, group + 1) if 0 < i < len(cuts) - 1]
351 if not neighbors:
352 raise ValueError("spectral coordinates could not be resolved")
353 boundary = min(
354 neighbors, key=lambda i: values[cuts[i]] - values[cuts[i] - 1]
355 )
356 del cuts[boundary]
357 columns, group = [], 0
358 continue
359 columns.extend(basis)
360 if len(columns) == dim:
361 break
362 group += 1
363 points[:, : len(columns)] = np.array(columns).T
364 points = nx.rescale_layout(points, scale=scale) + origin
365 positions = dict(zip(nodes, points, strict=True))
366 if store_pos_as is not None:
367 nx.set_node_attributes(graph, positions, store_pos_as)
368 return positions
371LayoutName = Literal[
372 "circular",
373 "kamada_kawai",
374 "partite",
375 "planar",
376 "shell",
377 "spectral",
378 "spiral",
379 "spring",
380 "tree",
381]
382"""The names of the layouts a graph is laid out by (see
383[GenericGraph][manimgx.mobjects.graph.GenericGraph]). The spectral layout fixes its axes by
384node order, so an eigensolver's arbitrary choice of basis does not rotate or skew a graph."""
387def _layout(name: LayoutName) -> LayoutFunction[Hashable]:
388 import networkx as nx
390 return {
391 "circular": nx.layout.circular_layout,
392 "kamada_kawai": _kamada_kawai_layout,
393 "partite": _partite_layout,
394 "planar": nx.layout.planar_layout,
395 "shell": nx.layout.shell_layout,
396 "spectral": _spectral_layout,
397 "spiral": nx.layout.spiral_layout,
398 "spring": nx.layout.spring_layout,
399 "tree": _tree_layout,
400 }[name]
403type Layout[V] = (
404 LayoutName | str | Positions[V] | LayoutFunction[V]
405) # a layout's name, checked when used
406"""Where a graph's vertices go: a layout's name, the vertices' positions (a dictionary
407from each vertex to its point), or a layout function."""
410def _is_function[V](layout: Layout[V]) -> TypeIs[LayoutFunction[V]]:
411 return callable(layout)
414def _is_name(layout: object) -> TypeIs[LayoutName]:
415 return isinstance(layout, str) and layout in get_args(LayoutName)
418class VertexOptions[V: Hashable](TypedDict, total=False, closed=True):
419 """[add_vertices][manimgx.mobjects.graph.GenericGraph.add_vertices]' keywords, for
420 the methods that pass them on: where the new vertices go, their labels, their kind
421 and their keywords."""
423 positions: Mapping[V, Point3DLike] | None
424 """Where new vertices go, by vertex (default None: at the graph's center)."""
425 labels: bool | Mapping[V, bool | Mobject]
426 """Whether each new vertex is labeled with its name, typeset as math: True for
427 all, or by vertex, True or a label of one's own (default False)."""
428 label_fill_color: ParsableManimColor
429 """The color of the labels made from names (default black)."""
430 vertex_type: Maker
431 """The class of the new vertices (default [Dot][manimgx.Dot]; a labeled one is a
432 [LabeledDot][manimgx.LabeledDot])."""
433 vertex_config: Configs | None
434 """Keywords for the new vertices, over the graph's: for all of them, and a vertex's
435 own under its name, in place of those for all (default None: none)."""
436 vertex_mobjects: Mapping[V, Mobject] | None
437 """Mobjects to be vertices themselves, by vertex (default None: none)."""
440class GraphOptions[V: Hashable](TypedDict, total=False, closed=True):
441 """A graph's keywords but its vertices and edges, for the methods that pass them on
442 ([from_networkx][manimgx.mobjects.graph.GenericGraph.from_networkx], a
443 [Polyhedron][manimgx.Polyhedron]'s `graph_config`): its labels, layout, and the
444 kinds and keywords of its vertices and edges."""
446 labels: bool | Mapping[V, Mobject]
447 """Whether each vertex is labeled with its name, typeset as math, or a label for
448 each (default False)."""
449 label_fill_color: ParsableManimColor
450 """The color of the labels made from names (default black)."""
451 layout: Layout[V]
452 """Where the vertices go: a layout's name, their positions, or a layout function
453 (default `"spring"`)."""
454 layout_scale: float | tuple[float, float, float]
455 """How far the layout reaches from the center, in scene units (default 2)."""
456 layout_config: Mapping[str, object] | None
457 """Keywords for the layout function: a `"spring"` layout's `seed`, … (default None:
458 none)."""
459 vertex_type: Maker
460 """The class of the vertices (default [Dot][manimgx.Dot]; a labeled one is a
461 [LabeledDot][manimgx.LabeledDot])."""
462 vertex_config: Configs | None
463 """Keywords for the vertices: for all of them, and a vertex's own under its name, in
464 place of those for all (default None: none)."""
465 vertex_mobjects: Mapping[V, Mobject] | None
466 """Mobjects to be vertices themselves, by vertex (default None: none)."""
467 edge_type: Maker
468 """The class of the edges (default [Line][manimgx.Line])."""
469 partitions: Sequence[Sequence[V]] | None
470 """For the `"partite"` layout: the vertices of each column, in order (default None:
471 none)."""
472 root_vertex: V | None
473 """For the `"tree"` layout: the vertex at its top (default None: none)."""
474 edge_config: Configs | None
475 """Keywords for the edges: for all of them, and an edge's own under its pair of
476 vertices, in place of those for all (default None: none)."""
479class Configs(Protocol):
480 """Keywords for vertices (or edges): a dictionary of keywords for all of them, and
481 of a vertex's own keywords under its name (an edge's under its pair of vertices)."""
483 # any key type: a Mapping's key type is invariant
485 def items(self) -> AbstractSet[tuple[object, object]]: ...
488def _split[K: Hashable](
489 configs: Configs | None, items: Iterable[K]
490) -> tuple[Config, dict[K, Config]]:
491 """The keywords for all, and each item's own (given under the item)."""
492 given: dict[object, object] = dict(configs.items()) if configs is not None else {}
493 names = set(items)
494 shared: Config = {
495 k: v for k, v in given.items() if isinstance(k, str) and k not in names
496 }
497 own: dict[K, Config] = {}
498 for k in names & given.keys():
499 if not isinstance(keywords := given[k], Mapping):
500 raise TypeError(f"{k!r}'s own keywords are not a mapping: {keywords!r}")
501 own[k] = dict(keywords)
502 return shared, own
505class GenericGraph[V: Hashable = Hashable](VMobject):
506 """What [Graph][manimgx.Graph] and [DiGraph][manimgx.DiGraph] have in common:
507 vertices and edges, laid out and kept together; white dots and lines unless
508 styled.
510 The vertices are any hashable values (numbers, strings, …): each is made a mobject,
511 a [Dot][manimgx.Dot] by default, and `graph[v]` is the mobject of vertex `v`. The
512 edges are pairs of vertices: each is made a mobject, a [Line][manimgx.Line] by
513 default, drawn behind the vertices (z-index -1), and `graph[(u, v)]` is the mobject
514 of edge `(u, v)`. An updater keeps the edges on their vertices: move a vertex (or
515 animate it) and its edges follow. Vertices and edges can be added and removed, and
516 the whole graph laid out anew.
518 The layout places the vertices: by a name — NetworkX's `"circular"`,
519 `"kamada_kawai"`, `"planar"`, `"shell"`, `"spectral"`, `"spiral"` and `"spring"`
520 (random unless given a `seed` in `layout_config`), or `"partite"` (in columns, by
521 `partitions`) and `"tree"` (down from `root_vertex`) — by a dictionary of positions,
522 or by a function of one's own. It spans about `layout_scale` from the center, the
523 center at the scene's origin; points of two coordinates lie in the plane z = 0.
525 Args:
526 vertices: The vertices: hashable values, each a vertex's name.
527 edges: The edges, each a pair of vertices.
528 labels: Whether each vertex is labeled with its name, typeset as math (a
529 vertex that is a [Dot][manimgx.Dot] becomes a
530 [LabeledDot][manimgx.LabeledDot]); or a label for each, by vertex.
531 label_fill_color: The color of the labels made from names.
532 layout: Where the vertices go: a layout's name, their positions (a dictionary
533 from each vertex to its point), or a layout function, called with the
534 NetworkX graph, `scale` and the keywords of `layout_config`.
535 layout_scale: How far the layout reaches from the center, in scene units.
536 layout_config: Keywords for the layout function; None for none.
537 vertex_type: The class of the vertices, called with each vertex's keywords.
538 vertex_config: Keywords for the vertices: for all of them, and a vertex's own
539 under its name, in place of those for all, as in
540 `{"radius": 0.2, 3: {"color": RED}}`; None for none.
541 vertex_mobjects: Mobjects to be vertices themselves, by vertex; None for none.
542 edge_type: The class of the edges, called with each edge's ends and keywords.
543 partitions: For the `"partite"` layout: the vertices of each column, in order
544 (those of none make a last column); None for none.
545 root_vertex: For the `"tree"` layout: the vertex at its top; None for none.
546 edge_config: Keywords for the edges: for all of them, and an edge's own under
547 its pair of vertices, in place of those for all; a DiGraph's tips under
548 `"tip_config"`. None for none.
549 """
551 edges: dict[Edge[V], Mobject]
552 """The edges' mobjects, by pair of vertices."""
554 def __init__(
555 self,
556 vertices: Sequence[V],
557 edges: Sequence[Edge[V]],
558 labels: bool | Mapping[V, Mobject] = False,
559 label_fill_color: ParsableManimColor = BLACK,
560 layout: Layout[V] = "spring",
561 layout_scale: float | tuple[float, float, float] = 2,
562 layout_config: Mapping[str, object] | None = None,
563 vertex_type: Maker = Dot,
564 vertex_config: Configs | None = None,
565 vertex_mobjects: Mapping[V, Mobject] | None = None,
566 edge_type: Maker = Line,
567 partitions: Sequence[Sequence[V]] | None = None,
568 root_vertex: V | None = None,
569 edge_config: Configs | None = None,
570 ) -> None:
571 super().__init__()
572 if isinstance(labels, Mapping):
573 labels_by_vertex: dict[V, Mobject] = dict(labels)
574 else:
575 labels_by_vertex = (
576 {v: MathTex(str(v), color=label_fill_color) for v in vertices}
577 if labels
578 else {}
579 )
580 if labels_by_vertex and vertex_type is Dot:
581 vertex_type = LabeledDot
582 self.default_vertex_config, own = _split(vertex_config, vertices)
583 vertex_configs: dict[V, Config] = {
584 v: own.get(v, copy(self.default_vertex_config)) for v in vertices
585 }
586 for v, label in labels_by_vertex.items():
587 vertex_configs[v]["label"] = label
588 self.vertices: dict[V, Mobject] = {
589 v: _make(vertex_type, vertex_configs[v]) for v in vertices
590 }
591 """The vertices' mobjects, by vertex."""
592 self.vertices.update(vertex_mobjects or {})
593 self._place_vertices(
594 edges,
595 layout=layout,
596 layout_scale=layout_scale,
597 layout_config=layout_config,
598 partitions=partitions,
599 root_vertex=root_vertex,
600 )
601 self.default_edge_config, own_edges = _split(edge_config, edges)
602 self._edge_config: dict[Edge[V], Config] = {
603 e: own_edges.get(e, copy(self.default_edge_config)) for e in edges
604 }
605 self._populate_edge_dict(edges, edge_type)
606 self.add(*self.vertices.values())
607 self.add(*self.edges.values())
608 self.add_updater(self.update_edges)
610 @staticmethod
611 def _empty_networkx_graph() -> NxGraph:
612 raise NotImplementedError("To be implemented in concrete subclasses")
614 def _make_edge(self, edge_type: Maker, u: V, v: V, config_: Config) -> Mobject:
615 raise NotImplementedError("To be implemented in concrete subclasses")
617 def update_edges(self, graph: Mobject) -> Self:
618 """Put each edge back on its vertices, where they are now: the updater a graph
619 runs every frame, so that its edges follow its vertices.
621 Each kind of graph sets its edges' ends its own way: an undirected graph's from
622 center to center, a directed graph's from outline to outline, with its tip.
623 Only edges that are lines ([Line][manimgx.Line] and its kinds) follow.
625 Args:
626 graph: The mobject the updater runs for (the graph); unused.
627 """
628 raise NotImplementedError("To be implemented in concrete subclasses")
630 def _populate_edge_dict(self, edges: Iterable[Edge[V]], edge_type: Maker) -> None:
631 self.edges = {
632 (u, v): self._make_edge(edge_type, u, v, self._edge_config[u, v])
633 for u, v in edges
634 }
636 def __getitem__( # ty: ignore[invalid-method-override] # CE: a graph is indexed by vertex and edge, not position
637 self, k: V | Edge[V]
638 ) -> Mobject:
639 if k in self.vertices:
640 return self.vertices[cast("V", k)]
641 if k in self.edges:
642 return self.edges[cast("Edge[V]", k)]
643 raise ValueError(f"Could not find {k} in vertices or edges")
645 def _create_vertex(
646 self,
647 vertex: V,
648 position: Point3DLike | None = None,
649 label: bool | Mobject = False,
650 label_fill_color: ParsableManimColor = BLACK,
651 vertex_type: Maker = Dot,
652 vertex_config: Config | None = None,
653 vertex_mobject: Mobject | None = None,
654 ) -> tuple[V, Point3D, Mobject]:
655 np_position: Point3D = (
656 self.get_center() if position is None else np.asarray(position, dtype=float)
657 )
658 if vertex in self.vertices:
659 raise ValueError(
660 f"Vertex identifier '{vertex}' is already used for a vertex in this"
661 " graph."
662 )
663 if label is True:
664 label_mob: Mobject | None = MathTex(str(vertex), color=label_fill_color)
665 else:
666 label_mob = label if isinstance(label, Mobject) else None
667 config_ = copy(self.default_vertex_config) | (vertex_config or {})
668 if label_mob is not None:
669 config_["label"] = label_mob
670 if vertex_type is Dot:
671 vertex_type = LabeledDot
672 mob = (
673 vertex_mobject
674 if vertex_mobject is not None
675 else _make(vertex_type, config_)
676 )
677 mob.move_to(np_position)
678 return vertex, np_position, mob
680 def _add_created_vertex(
681 self,
682 vertex: V,
683 position: Point3DLike,
684 vertex_mobject: Mobject,
685 ) -> Mobject:
686 if vertex in self.vertices:
687 raise ValueError(
688 f"Vertex identifier '{vertex}' is already used for a vertex in this"
689 " graph."
690 )
691 self.vertices[vertex] = vertex_mobject
692 vertex_mobject.move_to(position)
693 self.add(vertex_mobject)
694 return vertex_mobject
696 def _create_vertices(
697 self,
698 *vertices: V,
699 positions: Mapping[V, Point3DLike] | None = None,
700 labels: bool | Mapping[V, bool | Mobject] = False,
701 label_fill_color: ParsableManimColor = BLACK,
702 vertex_type: Maker = Dot,
703 vertex_config: Configs | None = None,
704 vertex_mobjects: Mapping[V, Mobject] | None = None,
705 ) -> list[tuple[V, Point3D, Mobject]]:
706 graph_center = self.get_center()
707 places = {v: (positions or {}).get(v, graph_center) for v in vertices}
708 marks = {
709 v: labels if isinstance(labels, bool) else labels.get(v, False)
710 for v in vertices
711 }
712 shared, own = _split(vertex_config, vertices)
713 base = copy(self.default_vertex_config) | shared
714 return [
715 self._create_vertex(
716 v,
717 position=places[v],
718 label=marks[v],
719 label_fill_color=label_fill_color,
720 vertex_type=vertex_type,
721 vertex_config=own.get(v, copy(base)),
722 vertex_mobject=(vertex_mobjects or {}).get(v),
723 )
724 for v in vertices
725 ]
727 def add_vertices(self, *vertices: V, **kwargs: Unpack[VertexOptions[V]]) -> Group:
728 """Add vertices to the graph, without edges.
730 Each is made as the graph makes its vertices, with the keywords given over the
731 graph's own, and placed at its position, or at the graph's center. A vertex
732 already in the graph raises a ValueError.
734 Args:
735 *vertices: The new vertices: hashable values, each a vertex's name.
736 **kwargs: [Vertex keywords][manimgx.mobjects.graph.VertexOptions]:
737 `positions`, `labels`, `vertex_type`, `vertex_config`, ….
739 Returns:
740 A new group of the new vertices' mobjects.
742 Examples:
743 ```python
744 import manimgx as m
747 class GraphAddVerticesExample(m.Scene):
748 def construct(self) -> None:
749 graph = m.Graph(
750 [1, 2, 3],
751 [(1, 2), (2, 3)],
752 layout={1: [-4, -1, 0], 2: [0, -2, 0], 3: [4, -1, 0]},
753 vertex_config={"radius": 0.15},
754 )
755 self.add(graph)
756 top = graph.add_vertices(
757 4, positions={4: [0, 2.5, 0]}, vertex_config={"color": m.YELLOW}
758 )
759 self.play(m.FadeIn(top, scale=3))
760 self.play(m.Create(graph.add_edges((1, 4), (3, 4))))
761 ```
762 """
763 return Group(
764 *(
765 self._add_created_vertex(*v)
766 for v in self._create_vertices(*vertices, **kwargs)
767 )
768 )
770 def _remove_vertex(self, vertex: V) -> Group:
771 if vertex not in self.vertices:
772 raise ValueError(
773 f"The graph does not contain a vertex with identifier '{vertex}'"
774 )
775 edge_tuples = [e for e in self.edges if vertex in e]
776 for e in edge_tuples:
777 self._edge_config.pop(e)
778 to_remove = [self.edges.pop(e) for e in edge_tuples]
779 to_remove.append(self.vertices.pop(vertex))
780 self.remove(*to_remove)
781 return Group(*to_remove)
783 def remove_vertices(self, *vertices: V) -> Group:
784 """Remove vertices from the graph, and the edges that touch them.
786 A vertex not in the graph raises a ValueError.
788 Args:
789 *vertices: The vertices to remove.
791 Returns:
792 A new group of the removed mobjects (for each vertex, its edges, then the
793 vertex), to fade out, for instance.
795 Examples:
796 ```python
797 import manimgx as m
800 class GraphRemoveVerticesExample(m.Scene):
801 def construct(self) -> None:
802 graph = m.Graph(
803 [1, 2, 3, 4, 5],
804 [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3)],
805 layout="circular",
806 layout_scale=3,
807 )
808 self.add(graph)
809 self.play(m.FadeOut(graph.remove_vertices(3)))
810 ```
811 """
812 return Group(*(m for v in vertices for m in self._remove_vertex(v).submobjects))
814 def _add_edge(
815 self, edge: Edge[V], edge_type: Maker = Line, edge_config: Config | None = None
816 ) -> Group:
817 u, v = edge
818 config_ = self.default_edge_config.copy() | (edge_config or {})
819 self._edge_config[u, v] = config_
820 edge_mobject = self._make_edge(edge_type, u, v, config_)
821 self.edges[u, v] = edge_mobject
822 self.add(edge_mobject)
823 return Group(edge_mobject)
825 def add_edges(
826 self,
827 *edges: Edge[V],
828 edge_type: Maker = Line,
829 edge_config: Configs | None = None,
830 **kwargs: Unpack[VertexOptions[V]],
831 ) -> Group:
832 """Add edges to the graph, and the vertices they name that it lacks.
834 The missing vertices are added first, as
835 [add_vertices][manimgx.mobjects.graph.GenericGraph.add_vertices] adds them, with
836 the vertex keywords given; each edge is then made as the graph makes its edges,
837 with the edge keywords given over the graph's own.
839 Args:
840 *edges: The new edges, each a pair of vertices.
841 edge_type: The class of the new edges.
842 edge_config: Keywords for the new edges, over the graph's: for all of them,
843 and an edge's own under its pair of vertices, in place of those for all;
844 None for none.
845 **kwargs: [Vertex keywords][manimgx.mobjects.graph.VertexOptions] for the
846 vertices the edges name that the graph lacks.
848 Returns:
849 A new group of the new mobjects, the vertices added and then the edges.
850 """
851 shared, own = _split(edge_config, edges)
852 base = self.default_edge_config.copy() | shared
853 new_vertices = [
854 v for v in dict.fromkeys(it.chain(*edges)) if v not in self.vertices
855 ]
856 added = list(self.add_vertices(*new_vertices, **kwargs))
857 for edge in edges:
858 added.extend(
859 self._add_edge(
860 edge, edge_type=edge_type, edge_config=base | own.get(edge, {})
861 )
862 )
863 return Group(*added)
865 def _remove_edge(self, edge: Edge[V]) -> Mobject:
866 if edge not in self.edges:
867 raise ValueError(f"The graph does not contain a edge '{edge}'")
868 edge_mobject = self.edges.pop(edge)
869 self._edge_config.pop(edge, None)
870 self.remove(edge_mobject)
871 return edge_mobject
873 def remove_edges(self, *edges: Edge[V]) -> Group:
874 """Remove edges from the graph, keeping their vertices.
876 An edge not in the graph raises a ValueError.
878 Args:
879 *edges: The edges to remove, each a pair of vertices.
881 Returns:
882 A new group of the removed edges' mobjects.
883 """
884 return Group(*(self._remove_edge(edge) for edge in edges))
886 @classmethod
887 def from_networkx(cls, nxgraph: NxGraph, **kwargs: Unpack[GraphOptions[V]]) -> Self:
888 """Make a graph of a [NetworkX](https://networkx.org) graph's nodes and edges.
890 Args:
891 nxgraph: The NetworkX graph (a `Graph`, or a `DiGraph`).
892 **kwargs: [Graph keywords][manimgx.Graph]: `layout`,
893 `labels`, `vertex_config`, ….
895 Returns:
896 A new graph.
898 Examples:
899 ```python
900 import networkx as nx
902 import manimgx as m
905 class GraphFromNetworkxExample(m.Scene):
906 def construct(self) -> None:
907 petersen = nx.petersen_graph()
908 graph = m.Graph.from_networkx(
909 petersen,
910 layout="shell",
911 layout_scale=3,
912 layout_config={"nlist": [range(5, 10), range(5)]},
913 )
914 self.play(m.Create(graph), run_time=2)
915 ```
916 """
917 return cls(list(nxgraph.nodes), list(nxgraph.edges), **kwargs)
919 def change_layout(
920 self,
921 layout: Layout[V] = "spring",
922 layout_scale: float | tuple[float, float, float] = 2,
923 layout_config: Mapping[str, object] | None = None,
924 partitions: Sequence[Sequence[V]] | None = None,
925 root_vertex: V | None = None,
926 ) -> Self:
927 """Lay the graph out anew: move each vertex to its place in a layout.
929 The vertices move at once, and the edges follow them at the next frame, as the
930 graph's updater moves them. To animate the change, animate each vertex to its
931 place in a changed copy (as below): the edges follow all the way.
933 A layout function gets a fresh NetworkX graph of the current vertices and edges.
934 Its node, edge and graph attributes belong to that call, not to later layouts.
936 Args:
937 layout: Where the vertices go: a layout's name, their positions, or a
938 layout function (see
939 [GenericGraph][manimgx.mobjects.graph.GenericGraph]).
940 layout_scale: How far the layout reaches from the center, in scene units.
941 layout_config: Keywords for the layout function; None for none.
942 partitions: For the `"partite"` layout: the vertices of each column; None
943 for none.
944 root_vertex: For the `"tree"` layout: the vertex at its top; None for none.
946 Examples:
947 ```python
948 import manimgx as m
951 class GraphChangeLayoutExample(m.Scene):
952 def construct(self) -> None:
953 graph = m.Graph(
954 [1, 2, 3, 4, 5, 6],
955 [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (1, 4)],
956 layout={v: [2 * v - 7, 0, 0] for v in range(1, 7)},
957 )
958 circle = graph.copy().change_layout("circular", layout_scale=3)
959 self.add(graph)
960 self.play(
961 *(graph[v].animate.move_to(circle[v]) for v in graph.vertices)
962 )
963 ```
964 """
965 return self._place_vertices(
966 self.edges,
967 layout=layout,
968 layout_scale=layout_scale,
969 layout_config=layout_config,
970 partitions=partitions,
971 root_vertex=root_vertex,
972 )
974 def _place_vertices(
975 self,
976 edges: Iterable[Edge[V]],
977 layout: Layout[V] = "spring",
978 layout_scale: float | tuple[float, float, float] = 2,
979 layout_config: Mapping[str, object] | None = None,
980 partitions: Sequence[Sequence[V]] | None = None,
981 root_vertex: V | None = None,
982 ) -> Self:
983 """Place vertices from the edge keys: supplied before edges are made, otherwise
984 the keys of the graph's edges. A computed layout owns its temporary topology."""
985 config_ = dict(layout_config or {})
986 if partitions is not None:
987 config_.setdefault("partitions", partitions)
988 if root_vertex is not None:
989 config_.setdefault("root_vertex", root_vertex)
990 positions: Positions[V]
991 if _is_function(layout):
992 place = layout
993 elif _is_name(layout):
994 place = _layout(layout)
995 elif isinstance(layout, str):
996 raise ValueError(
997 f"The layout '{layout}' is neither a recognized layout, a layout"
998 " function, nor a vertex placement dictionary."
999 )
1000 else:
1001 place = None
1002 positions = layout
1003 if place is not None:
1004 graph = self._empty_networkx_graph()
1005 graph.add_nodes_from(self.vertices)
1006 graph.add_edges_from(edges)
1007 positions = place(graph, scale=layout_scale, **config_)
1008 points = {v: np.asarray(positions[v], dtype=float) for v in self.vertices}
1009 padded = {v: np.pad(p, (0, 3 - p.size)) for v, p in points.items()}
1010 for v in self.vertices:
1011 self[v].move_to(padded[v])
1012 return self
1014 def _edge_ends(self, edge: Edge[V]) -> tuple[float, float]:
1015 """An edge's buffer and bend, as its config sets them (CE read them from the wrong
1016 dictionary, so edges lost both at the first update)."""
1017 config_ = self._edge_config.get(edge, {})
1018 buff, path_arc = config_.get("buff", 0), config_.get("path_arc", 0)
1019 return (buff if isinstance(buff, (int, float)) else 0), (
1020 path_arc if isinstance(path_arc, (int, float)) else 0
1021 )
1024class Graph[V: Hashable = Hashable](GenericGraph[V]):
1025 """An undirected graph: vertices joined by edges, laid out automatically or by hand;
1026 white dots and lines unless styled.
1028 Each edge runs from the center of one vertex to the center of the other, behind
1029 them, and follows them as they move. It takes the arguments of a
1030 [GenericGraph][manimgx.mobjects.graph.GenericGraph], which lists what a graph can do.
1032 Examples:
1033 ```python
1034 import manimgx as m
1037 class GraphExample(m.Scene):
1038 def construct(self) -> None:
1039 vertices = [1, 2, 3, 4, 5, 6]
1040 edges = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (1, 4), (2, 5)]
1041 graph = m.Graph(
1042 vertices,
1043 edges,
1044 layout="circular",
1045 layout_scale=3,
1046 labels=True,
1047 vertex_config={1: {"fill_color": m.RED}},
1048 edge_config={(1, 4): {"stroke_color": m.YELLOW}},
1049 )
1050 self.play(m.Create(graph))
1051 self.play(graph[3].animate.move_to([0, 0, 0]))
1052 ```
1053 """
1055 @staticmethod
1056 def _empty_networkx_graph() -> NxGraph:
1057 import networkx as nx
1059 return nx.Graph()
1061 def _make_edge(self, edge_type: Maker, u: V, v: V, config_: Config) -> Mobject:
1062 style = {k: v for k, v in config_.items() if k != "tip_config"}
1063 return edge_type(
1064 start=self[u].get_center(), end=self[v].get_center(), z_index=-1, **style
1065 )
1067 def update_edges(self, graph: Mobject) -> Self:
1068 for (u, v), edge in self.edges.items():
1069 if isinstance(edge, Line):
1070 buff, path_arc = self._edge_ends((u, v))
1071 edge.set_points_by_ends(
1072 self[u].get_center(),
1073 self[v].get_center(),
1074 buff=buff,
1075 path_arc=path_arc,
1076 )
1077 return self
1080class DiGraph[V: Hashable = Hashable](GenericGraph[V]):
1081 """A directed graph: vertices joined by arrows, from the first vertex of each edge
1082 to the second; white dots and arrows unless styled.
1084 Each edge runs from the outline of one vertex to the outline of the other and ends
1085 in a tip, which the `"tip_config"` of `edge_config` shapes (see
1086 [TipConfig][manimgx.mobjects.graph.TipConfig]), for every edge or an edge's own; it
1087 follows its vertices as they move. It takes the arguments of a
1088 [GenericGraph][manimgx.mobjects.graph.GenericGraph], which lists what a graph can do.
1090 Examples:
1091 ```python
1092 import manimgx as m
1095 class DiGraphExample(m.Scene):
1096 def construct(self) -> None:
1097 edge_config = {
1098 "stroke_width": 3,
1099 "tip_config": {"tip_length": 0.2, "tip_width": 0.2},
1100 (3, 4): {
1101 "color": m.RED,
1102 "tip_config": {"tip_shape": m.ArrowSquareTip},
1103 },
1104 }
1105 graph = m.DiGraph(
1106 [0, 1, 2, 3, 4],
1107 [(0, 1), (1, 2), (3, 2), (3, 4), (4, 0)],
1108 labels=True,
1109 layout="circular",
1110 layout_scale=3,
1111 edge_config=edge_config,
1112 )
1113 self.play(m.Create(graph))
1114 ```
1115 """
1117 @staticmethod
1118 def _empty_networkx_graph() -> NxGraph:
1119 import networkx as nx
1121 return nx.DiGraph()
1123 def _make_edge(self, edge_type: Maker, u: V, v: V, config_: Config) -> Mobject:
1124 style = config_.copy()
1125 tips = style.pop("tip_config", self.default_edge_config.get("tip_config", {}))
1126 if not isinstance(tips, Mapping):
1127 raise TypeError(f"an edge's tip_config is not a mapping: {tips!r}")
1128 edge = edge_type(start=self[u], end=self[v], z_index=-1, **style)
1129 if isinstance(edge, Line):
1130 edge.add_tip(**tips)
1131 return edge
1133 def update_edges(self, graph: Mobject) -> Self:
1134 for (u, v), edge in self.edges.items():
1135 if isinstance(edge, Line):
1136 tip = edge.pop_tips()[0]
1137 buff, path_arc = self._edge_ends((u, v))
1138 edge.set_points_by_ends(self[u], self[v], buff=buff, path_arc=path_arc)
1139 edge.add_tip(tip)
1140 return self