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

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 

5 

6"""Ported from Manim CE 0.21 (MIT).""" 

7 

8from __future__ import annotations 

9 

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) 

26 

27import numpy as np 

28from typing_extensions import TypedDict 

29 

30if TYPE_CHECKING: 

31 import networkx as nx 

32 

33 from manimgx.typing import Point3D, Point3DLike 

34 

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 

41 

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 

55 

56 

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()} 

62 

63 

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

67 

68 

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

73 

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

82 

83 

84class Positions[V](Protocol): 

85 """Where vertices go: anything a vertex looks its point up in (a dict, a layout's result).""" 

86 

87 def __getitem__(self, vertex: V, /) -> Point3DLike: ... 

88 

89 

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

96 

97 

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 

105 

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) 

123 

124 

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 

133 

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 

145 

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 

157 

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()} 

206 

207 

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 

221 

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

256 

257 

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. 

267 

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 

277 

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 

369 

370 

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

385 

386 

387def _layout(name: LayoutName) -> LayoutFunction[Hashable]: 

388 import networkx as nx 

389 

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] 

401 

402 

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

408 

409 

410def _is_function[V](layout: Layout[V]) -> TypeIs[LayoutFunction[V]]: 

411 return callable(layout) 

412 

413 

414def _is_name(layout: object) -> TypeIs[LayoutName]: 

415 return isinstance(layout, str) and layout in get_args(LayoutName) 

416 

417 

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

422 

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

438 

439 

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

445 

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

477 

478 

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

482 

483 # any key type: a Mapping's key type is invariant 

484 

485 def items(self) -> AbstractSet[tuple[object, object]]: ... 

486 

487 

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 

503 

504 

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. 

509 

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. 

517 

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. 

524 

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 """ 

550 

551 edges: dict[Edge[V], Mobject] 

552 """The edges' mobjects, by pair of vertices.""" 

553 

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) 

609 

610 @staticmethod 

611 def _empty_networkx_graph() -> NxGraph: 

612 raise NotImplementedError("To be implemented in concrete subclasses") 

613 

614 def _make_edge(self, edge_type: Maker, u: V, v: V, config_: Config) -> Mobject: 

615 raise NotImplementedError("To be implemented in concrete subclasses") 

616 

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. 

620 

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. 

624 

625 Args: 

626 graph: The mobject the updater runs for (the graph); unused. 

627 """ 

628 raise NotImplementedError("To be implemented in concrete subclasses") 

629 

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 } 

635 

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

644 

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 

679 

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 

695 

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 ] 

726 

727 def add_vertices(self, *vertices: V, **kwargs: Unpack[VertexOptions[V]]) -> Group: 

728 """Add vertices to the graph, without edges. 

729 

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. 

733 

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`, …. 

738 

739 Returns: 

740 A new group of the new vertices' mobjects. 

741 

742 Examples: 

743 ```python 

744 import manimgx as m 

745 

746 

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 ) 

769 

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) 

782 

783 def remove_vertices(self, *vertices: V) -> Group: 

784 """Remove vertices from the graph, and the edges that touch them. 

785 

786 A vertex not in the graph raises a ValueError. 

787 

788 Args: 

789 *vertices: The vertices to remove. 

790 

791 Returns: 

792 A new group of the removed mobjects (for each vertex, its edges, then the 

793 vertex), to fade out, for instance. 

794 

795 Examples: 

796 ```python 

797 import manimgx as m 

798 

799 

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

813 

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) 

824 

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. 

833 

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. 

838 

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. 

847 

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) 

864 

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 

872 

873 def remove_edges(self, *edges: Edge[V]) -> Group: 

874 """Remove edges from the graph, keeping their vertices. 

875 

876 An edge not in the graph raises a ValueError. 

877 

878 Args: 

879 *edges: The edges to remove, each a pair of vertices. 

880 

881 Returns: 

882 A new group of the removed edges' mobjects. 

883 """ 

884 return Group(*(self._remove_edge(edge) for edge in edges)) 

885 

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. 

889 

890 Args: 

891 nxgraph: The NetworkX graph (a `Graph`, or a `DiGraph`). 

892 **kwargs: [Graph keywords][manimgx.Graph]: `layout`, 

893 `labels`, `vertex_config`, …. 

894 

895 Returns: 

896 A new graph. 

897 

898 Examples: 

899 ```python 

900 import networkx as nx 

901 

902 import manimgx as m 

903 

904 

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) 

918 

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. 

928 

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. 

932 

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. 

935 

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. 

945 

946 Examples: 

947 ```python 

948 import manimgx as m 

949 

950 

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 ) 

973 

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 

1013 

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 ) 

1022 

1023 

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. 

1027 

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. 

1031 

1032 Examples: 

1033 ```python 

1034 import manimgx as m 

1035 

1036 

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 """ 

1054 

1055 @staticmethod 

1056 def _empty_networkx_graph() -> NxGraph: 

1057 import networkx as nx 

1058 

1059 return nx.Graph() 

1060 

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 ) 

1066 

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 

1078 

1079 

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. 

1083 

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. 

1089 

1090 Examples: 

1091 ```python 

1092 import manimgx as m 

1093 

1094 

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 """ 

1116 

1117 @staticmethod 

1118 def _empty_networkx_graph() -> NxGraph: 

1119 import networkx as nx 

1120 

1121 return nx.DiGraph() 

1122 

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 

1132 

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