Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/drawing/layout.py: 6%

1"""

2******

3Layout

4******

6Node positioning algorithms for graph drawing.

8For `random_layout()` the possible resulting shape

9is a square of side [0, scale] (default: [0, 1])

10Changing `center` shifts the layout by that amount.

12For the other layout routines, the extent is

13[center - scale, center + scale] (default: [-1, 1]).

15Warning: Most layout routines have only been tested in 2-dimensions.

17"""

18import networkx as nx

19from networkx.utils import np_random_state

21__all__ = [

22 "bipartite_layout",

23 "circular_layout",

24 "kamada_kawai_layout",

25 "random_layout",

26 "rescale_layout",

27 "rescale_layout_dict",

28 "shell_layout",

29 "spring_layout",

30 "spectral_layout",

31 "planar_layout",

32 "fruchterman_reingold_layout",

33 "spiral_layout",

34 "multipartite_layout",

35 "arf_layout",

36]

39def _process_params(G, center, dim):

40 # Some boilerplate code.

41 import numpy as np

43 if not isinstance(G, nx.Graph):

44 empty_graph = nx.Graph()

45 empty_graph.add_nodes_from(G)

46 G = empty_graph

48 if center is None:

49 center = np.zeros(dim)

50 else:

51 center = np.asarray(center)

53 if len(center) != dim:

54 msg = "length of center coordinates must match dimension of layout"

55 raise ValueError(msg)

57 return G, center

60@np_random_state(3)

61def random_layout(G, center=None, dim=2, seed=None):

62 """Position nodes uniformly at random in the unit square.

64 For every node, a position is generated by choosing each of dim

65 coordinates uniformly at random on the interval [0.0, 1.0).

67 NumPy (http://scipy.org) is required for this function.

69 Parameters

70 ----------

71 G : NetworkX graph or list of nodes

72 A position will be assigned to every node in G.

74 center : array-like or None

75 Coordinate pair around which to center the layout.

77 dim : int

78 Dimension of layout.

80 seed : int, RandomState instance or None optional (default=None)

81 Set the random state for deterministic node layouts.

82 If int, `seed` is the seed used by the random number generator,

83 if numpy.random.RandomState instance, `seed` is the random

84 number generator,

85 if None, the random number generator is the RandomState instance used

86 by numpy.random.

88 Returns

89 -------

90 pos : dict

91 A dictionary of positions keyed by node

93 Examples

94 --------

95 >>> G = nx.lollipop_graph(4, 3)

96 >>> pos = nx.random_layout(G)

98 """

99 import numpy as np

100

101 G, center = _process_params(G, center, dim)

102 pos = seed.rand(len(G), dim) + center

103 pos = pos.astype(np.float32)

104 pos = dict(zip(G, pos))

105

106 return pos

107

108

109def circular_layout(G, scale=1, center=None, dim=2):

110 # dim=2 only

111 """Position nodes on a circle.

112

113 Parameters

114 ----------

115 G : NetworkX graph or list of nodes

116 A position will be assigned to every node in G.

117

118 scale : number (default: 1)

119 Scale factor for positions.

120

121 center : array-like or None

122 Coordinate pair around which to center the layout.

123

124 dim : int

125 Dimension of layout.

126 If dim>2, the remaining dimensions are set to zero

127 in the returned positions.

128 If dim<2, a ValueError is raised.

129

130 Returns

131 -------

132 pos : dict

133 A dictionary of positions keyed by node

134

135 Raises

136 ------

137 ValueError

138 If dim < 2

139

140 Examples

141 --------

142 >>> G = nx.path_graph(4)

143 >>> pos = nx.circular_layout(G)

144

145 Notes

146 -----

147 This algorithm currently only works in two dimensions and does not

148 try to minimize edge crossings.

149

150 """

151 import numpy as np

152

153 if dim < 2:

154 raise ValueError("cannot handle dimensions < 2")

155

156 G, center = _process_params(G, center, dim)

157

158 paddims = max(0, (dim - 2))

159

160 if len(G) == 0:

161 pos = {}

162 elif len(G) == 1:

163 pos = {nx.utils.arbitrary_element(G): center}

164 else:

165 # Discard the extra angle since it matches 0 radians.

166 theta = np.linspace(0, 1, len(G) + 1)[:-1] * 2 * np.pi

167 theta = theta.astype(np.float32)

168 pos = np.column_stack(

169 [np.cos(theta), np.sin(theta), np.zeros((len(G), paddims))]

170 )

171 pos = rescale_layout(pos, scale=scale) + center

172 pos = dict(zip(G, pos))

173

174 return pos

175

176

177def shell_layout(G, nlist=None, rotate=None, scale=1, center=None, dim=2):

178 """Position nodes in concentric circles.

179

180 Parameters

181 ----------

182 G : NetworkX graph or list of nodes

183 A position will be assigned to every node in G.

184

185 nlist : list of lists

186 List of node lists for each shell.

187

188 rotate : angle in radians (default=pi/len(nlist))

189 Angle by which to rotate the starting position of each shell

190 relative to the starting position of the previous shell.

191 To recreate behavior before v2.5 use rotate=0.

192

193 scale : number (default: 1)

194 Scale factor for positions.

195

196 center : array-like or None

197 Coordinate pair around which to center the layout.

198

199 dim : int

200 Dimension of layout, currently only dim=2 is supported.

201 Other dimension values result in a ValueError.

202

203 Returns

204 -------

205 pos : dict

206 A dictionary of positions keyed by node

207

208 Raises

209 ------

210 ValueError

211 If dim != 2

212

213 Examples

214 --------

215 >>> G = nx.path_graph(4)

216 >>> shells = [[0], [1, 2, 3]]

217 >>> pos = nx.shell_layout(G, shells)

218

219 Notes

220 -----

221 This algorithm currently only works in two dimensions and does not

222 try to minimize edge crossings.

223

224 """

225 import numpy as np

226

227 if dim != 2:

228 raise ValueError("can only handle 2 dimensions")

229

230 G, center = _process_params(G, center, dim)

231

232 if len(G) == 0:

233 return {}

234 if len(G) == 1:

235 return {nx.utils.arbitrary_element(G): center}

236

237 if nlist is None:

238 # draw the whole graph in one shell

239 nlist = [list(G)]

240

241 radius_bump = scale / len(nlist)

242

243 if len(nlist[0]) == 1:

244 # single node at center

245 radius = 0.0

246 else:

247 # else start at r=1

248 radius = radius_bump

249

250 if rotate is None:

251 rotate = np.pi / len(nlist)

252 first_theta = rotate

253 npos = {}

254 for nodes in nlist:

255 # Discard the last angle (endpoint=False) since 2*pi matches 0 radians

256 theta = (

257 np.linspace(0, 2 * np.pi, len(nodes), endpoint=False, dtype=np.float32)

258 + first_theta

259 )

260 pos = radius * np.column_stack([np.cos(theta), np.sin(theta)]) + center

261 npos.update(zip(nodes, pos))

262 radius += radius_bump

263 first_theta += rotate

264

265 return npos

266

267

268def bipartite_layout(

269 G, nodes, align="vertical", scale=1, center=None, aspect_ratio=4 / 3

270):

271 """Position nodes in two straight lines.

272

273 Parameters

274 ----------

275 G : NetworkX graph or list of nodes

276 A position will be assigned to every node in G.

277

278 nodes : list or container

279 Nodes in one node set of the bipartite graph.

280 This set will be placed on left or top.

281

282 align : string (default='vertical')

283 The alignment of nodes. Vertical or horizontal.

284

285 scale : number (default: 1)

286 Scale factor for positions.

287

288 center : array-like or None

289 Coordinate pair around which to center the layout.

290

291 aspect_ratio : number (default=4/3):

292 The ratio of the width to the height of the layout.

293

294 Returns

295 -------

296 pos : dict

297 A dictionary of positions keyed by node.

298

299 Examples

300 --------

301 >>> G = nx.bipartite.gnmk_random_graph(3, 5, 10, seed=123)

302 >>> top = nx.bipartite.sets(G)[0]

303 >>> pos = nx.bipartite_layout(G, top)

304

305 Notes

306 -----

307 This algorithm currently only works in two dimensions and does not

308 try to minimize edge crossings.

309

310 """

311

312 import numpy as np

313

314 if align not in ("vertical", "horizontal"):

315 msg = "align must be either vertical or horizontal."

316 raise ValueError(msg)

317

318 G, center = _process_params(G, center=center, dim=2)

319 if len(G) == 0:

320 return {}

321

322 height = 1

323 width = aspect_ratio * height

324 offset = (width / 2, height / 2)

325

326 top = dict.fromkeys(nodes)

327 bottom = [v for v in G if v not in top]

328 nodes = list(top) + bottom

329

330 left_xs = np.repeat(0, len(top))

331 right_xs = np.repeat(width, len(bottom))

332 left_ys = np.linspace(0, height, len(top))

333 right_ys = np.linspace(0, height, len(bottom))

334

335 top_pos = np.column_stack([left_xs, left_ys]) - offset

336 bottom_pos = np.column_stack([right_xs, right_ys]) - offset

337

338 pos = np.concatenate([top_pos, bottom_pos])

339 pos = rescale_layout(pos, scale=scale) + center

340 if align == "horizontal":

341 pos = pos[:, ::-1] # swap x and y coords

342 pos = dict(zip(nodes, pos))

343 return pos

344

345

346@np_random_state(10)

347def spring_layout(

348 G,

349 k=None,

350 pos=None,

351 fixed=None,

352 iterations=50,

353 threshold=1e-4,

354 weight="weight",

355 scale=1,

356 center=None,

357 dim=2,

358 seed=None,

359):

360 """Position nodes using Fruchterman-Reingold force-directed algorithm.

361

362 The algorithm simulates a force-directed representation of the network

363 treating edges as springs holding nodes close, while treating nodes

364 as repelling objects, sometimes called an anti-gravity force.

365 Simulation continues until the positions are close to an equilibrium.

366

367 There are some hard-coded values: minimal distance between

368 nodes (0.01) and "temperature" of 0.1 to ensure nodes don't fly away.

369 During the simulation, `k` helps determine the distance between nodes,

370 though `scale` and `center` determine the size and place after

371 rescaling occurs at the end of the simulation.

372

373 Fixing some nodes doesn't allow them to move in the simulation.

374 It also turns off the rescaling feature at the simulation's end.

375 In addition, setting `scale` to `None` turns off rescaling.

376

377 Parameters

378 ----------

379 G : NetworkX graph or list of nodes

380 A position will be assigned to every node in G.

381

382 k : float (default=None)

383 Optimal distance between nodes. If None the distance is set to

384 1/sqrt(n) where n is the number of nodes. Increase this value

385 to move nodes farther apart.

386

387 pos : dict or None optional (default=None)

388 Initial positions for nodes as a dictionary with node as keys

389 and values as a coordinate list or tuple. If None, then use

390 random initial positions.

391

392 fixed : list or None optional (default=None)

393 Nodes to keep fixed at initial position.

394 Nodes not in ``G.nodes`` are ignored.

395 ValueError raised if `fixed` specified and `pos` not.

396

397 iterations : int optional (default=50)

398 Maximum number of iterations taken

399

400 threshold: float optional (default = 1e-4)

401 Threshold for relative error in node position changes.

402 The iteration stops if the error is below this threshold.

403

404 weight : string or None optional (default='weight')

405 The edge attribute that holds the numerical value used for

406 the edge weight. Larger means a stronger attractive force.

407 If None, then all edge weights are 1.

408

409 scale : number or None (default: 1)

410 Scale factor for positions. Not used unless `fixed is None`.

411 If scale is None, no rescaling is performed.

412

413 center : array-like or None

414 Coordinate pair around which to center the layout.

415 Not used unless `fixed is None`.

416

417 dim : int

418 Dimension of layout.

419

420 seed : int, RandomState instance or None optional (default=None)

421 Set the random state for deterministic node layouts.

422 If int, `seed` is the seed used by the random number generator,

423 if numpy.random.RandomState instance, `seed` is the random

424 number generator,

425 if None, the random number generator is the RandomState instance used

426 by numpy.random.

427

428 Returns

429 -------

430 pos : dict

431 A dictionary of positions keyed by node

432

433 Examples

434 --------

435 >>> G = nx.path_graph(4)

436 >>> pos = nx.spring_layout(G)

437

438 # The same using longer but equivalent function name

439 >>> pos = nx.fruchterman_reingold_layout(G)

440 """

441 import numpy as np

442

443 G, center = _process_params(G, center, dim)

444

445 if fixed is not None:

446 if pos is None:

447 raise ValueError("nodes are fixed without positions given")

448 for node in fixed:

449 if node not in pos:

450 raise ValueError("nodes are fixed without positions given")

451 nfixed = {node: i for i, node in enumerate(G)}

452 fixed = np.asarray([nfixed[node] for node in fixed if node in nfixed])

453

454 if pos is not None:

455 # Determine size of existing domain to adjust initial positions

456 dom_size = max(coord for pos_tup in pos.values() for coord in pos_tup)

457 if dom_size == 0:

458 dom_size = 1

459 pos_arr = seed.rand(len(G), dim) * dom_size + center

460

461 for i, n in enumerate(G):

462 if n in pos:

463 pos_arr[i] = np.asarray(pos[n])

464 else:

465 pos_arr = None

466 dom_size = 1

467

468 if len(G) == 0:

469 return {}

470 if len(G) == 1:

471 return {nx.utils.arbitrary_element(G.nodes()): center}

472

473 try:

474 # Sparse matrix

475 if len(G) < 500: # sparse solver for large graphs

476 raise ValueError

477 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="f")

478 if k is None and fixed is not None:

479 # We must adjust k by domain size for layouts not near 1x1

480 nnodes, _ = A.shape

481 k = dom_size / np.sqrt(nnodes)

482 pos = _sparse_fruchterman_reingold(

483 A, k, pos_arr, fixed, iterations, threshold, dim, seed

484 )

485 except ValueError:

486 A = nx.to_numpy_array(G, weight=weight)

487 if k is None and fixed is not None:

488 # We must adjust k by domain size for layouts not near 1x1

489 nnodes, _ = A.shape

490 k = dom_size / np.sqrt(nnodes)

491 pos = _fruchterman_reingold(

492 A, k, pos_arr, fixed, iterations, threshold, dim, seed

493 )

494 if fixed is None and scale is not None:

495 pos = rescale_layout(pos, scale=scale) + center

496 pos = dict(zip(G, pos))

497 return pos

498

499

500fruchterman_reingold_layout = spring_layout

501

502

503@np_random_state(7)

504def _fruchterman_reingold(

505 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None

506):

507 # Position nodes in adjacency matrix A using Fruchterman-Reingold

508 # Entry point for NetworkX graph is fruchterman_reingold_layout()

509 import numpy as np

510

511 try:

512 nnodes, _ = A.shape

513 except AttributeError as err:

514 msg = "fruchterman_reingold() takes an adjacency matrix as input"

515 raise nx.NetworkXError(msg) from err

516

517 if pos is None:

518 # random initial positions

519 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)

520 else:

521 # make sure positions are of same type as matrix

522 pos = pos.astype(A.dtype)

523

524 # optimal distance between nodes

525 if k is None:

526 k = np.sqrt(1.0 / nnodes)

527 # the initial "temperature" is about .1 of domain area (=1x1)

528 # this is the largest step allowed in the dynamics.

529 # We need to calculate this in case our fixed positions force our domain

530 # to be much bigger than 1x1

531 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1

532 # simple cooling scheme.

533 # linearly step down by dt on each iteration so last iteration is size dt.

534 dt = t / (iterations + 1)

535 delta = np.zeros((pos.shape[0], pos.shape[0], pos.shape[1]), dtype=A.dtype)

536 # the inscrutable (but fast) version

537 # this is still O(V^2)

538 # could use multilevel methods to speed this up significantly

539 for iteration in range(iterations):

540 # matrix of difference between points

541 delta = pos[:, np.newaxis, :] - pos[np.newaxis, :, :]

542 # distance between points

543 distance = np.linalg.norm(delta, axis=-1)

544 # enforce minimum distance of 0.01

545 np.clip(distance, 0.01, None, out=distance)

546 # displacement "force"

547 displacement = np.einsum(

548 "ijk,ij->ik", delta, (k * k / distance**2 - A * distance / k)

549 )

550 # update positions

551 length = np.linalg.norm(displacement, axis=-1)

552 length = np.where(length < 0.01, 0.1, length)

553 delta_pos = np.einsum("ij,i->ij", displacement, t / length)

554 if fixed is not None:

555 # don't change positions of fixed nodes

556 delta_pos[fixed] = 0.0

557 pos += delta_pos

558 # cool temperature

559 t -= dt

560 if (np.linalg.norm(delta_pos) / nnodes) < threshold:

561 break

562 return pos

563

564

565@np_random_state(7)

566def _sparse_fruchterman_reingold(

567 A, k=None, pos=None, fixed=None, iterations=50, threshold=1e-4, dim=2, seed=None

568):

569 # Position nodes in adjacency matrix A using Fruchterman-Reingold

570 # Entry point for NetworkX graph is fruchterman_reingold_layout()

571 # Sparse version

572 import numpy as np

573 import scipy as sp

574

575 try:

576 nnodes, _ = A.shape

577 except AttributeError as err:

578 msg = "fruchterman_reingold() takes an adjacency matrix as input"

579 raise nx.NetworkXError(msg) from err

580 # make sure we have a LIst of Lists representation

581 try:

582 A = A.tolil()

583 except AttributeError:

584 A = (sp.sparse.coo_array(A)).tolil()

585

586 if pos is None:

587 # random initial positions

588 pos = np.asarray(seed.rand(nnodes, dim), dtype=A.dtype)

589 else:

590 # make sure positions are of same type as matrix

591 pos = pos.astype(A.dtype)

592

593 # no fixed nodes

594 if fixed is None:

595 fixed = []

596

597 # optimal distance between nodes

598 if k is None:

599 k = np.sqrt(1.0 / nnodes)

600 # the initial "temperature" is about .1 of domain area (=1x1)

601 # this is the largest step allowed in the dynamics.

602 t = max(max(pos.T[0]) - min(pos.T[0]), max(pos.T[1]) - min(pos.T[1])) * 0.1

603 # simple cooling scheme.

604 # linearly step down by dt on each iteration so last iteration is size dt.

605 dt = t / (iterations + 1)

606

607 displacement = np.zeros((dim, nnodes))

608 for iteration in range(iterations):

609 displacement *= 0

610 # loop over rows

611 for i in range(A.shape[0]):

612 if i in fixed:

613 continue

614 # difference between this row's node position and all others

615 delta = (pos[i] - pos).T

616 # distance between points

617 distance = np.sqrt((delta**2).sum(axis=0))

618 # enforce minimum distance of 0.01

619 distance = np.where(distance < 0.01, 0.01, distance)

620 # the adjacency matrix row

621 Ai = A.getrowview(i).toarray() # TODO: revisit w/ sparse 1D container

622 # displacement "force"

623 displacement[:, i] += (

624 delta * (k * k / distance**2 - Ai * distance / k)

625 ).sum(axis=1)

626 # update positions

627 length = np.sqrt((displacement**2).sum(axis=0))

628 length = np.where(length < 0.01, 0.1, length)

629 delta_pos = (displacement * t / length).T

630 pos += delta_pos

631 # cool temperature

632 t -= dt

633 if (np.linalg.norm(delta_pos) / nnodes) < threshold:

634 break

635 return pos

636

637

638def kamada_kawai_layout(

639 G, dist=None, pos=None, weight="weight", scale=1, center=None, dim=2

640):

641 """Position nodes using Kamada-Kawai path-length cost-function.

642

643 Parameters

644 ----------

645 G : NetworkX graph or list of nodes

646 A position will be assigned to every node in G.

647

648 dist : dict (default=None)

649 A two-level dictionary of optimal distances between nodes,

650 indexed by source and destination node.

651 If None, the distance is computed using shortest_path_length().

652

653 pos : dict or None optional (default=None)

654 Initial positions for nodes as a dictionary with node as keys

655 and values as a coordinate list or tuple. If None, then use

656 circular_layout() for dim >= 2 and a linear layout for dim == 1.

657

658 weight : string or None optional (default='weight')

659 The edge attribute that holds the numerical value used for

660 the edge weight. If None, then all edge weights are 1.

661

662 scale : number (default: 1)

663 Scale factor for positions.

664

665 center : array-like or None

666 Coordinate pair around which to center the layout.

667

668 dim : int

669 Dimension of layout.

670

671 Returns

672 -------

673 pos : dict

674 A dictionary of positions keyed by node

675

676 Examples

677 --------

678 >>> G = nx.path_graph(4)

679 >>> pos = nx.kamada_kawai_layout(G)

680 """

681 import numpy as np

682

683 G, center = _process_params(G, center, dim)

684 nNodes = len(G)

685 if nNodes == 0:

686 return {}

687

688 if dist is None:

689 dist = dict(nx.shortest_path_length(G, weight=weight))

690 dist_mtx = 1e6 * np.ones((nNodes, nNodes))

691 for row, nr in enumerate(G):

692 if nr not in dist:

693 continue

694 rdist = dist[nr]

695 for col, nc in enumerate(G):

696 if nc not in rdist:

697 continue

698 dist_mtx[row][col] = rdist[nc]

699

700 if pos is None:

701 if dim >= 3:

702 pos = random_layout(G, dim=dim)

703 elif dim == 2:

704 pos = circular_layout(G, dim=dim)

705 else:

706 pos = dict(zip(G, np.linspace(0, 1, len(G))))

707 pos_arr = np.array([pos[n] for n in G])

708

709 pos = _kamada_kawai_solve(dist_mtx, pos_arr, dim)

710

711 pos = rescale_layout(pos, scale=scale) + center

712 return dict(zip(G, pos))

713

714

715def _kamada_kawai_solve(dist_mtx, pos_arr, dim):

716 # Anneal node locations based on the Kamada-Kawai cost-function,

717 # using the supplied matrix of preferred inter-node distances,

718 # and starting locations.

719

720 import numpy as np

721 import scipy as sp

722

723 meanwt = 1e-3

724 costargs = (np, 1 / (dist_mtx + np.eye(dist_mtx.shape[0]) * 1e-3), meanwt, dim)

725

726 optresult = sp.optimize.minimize(

727 _kamada_kawai_costfn,

728 pos_arr.ravel(),

729 method="L-BFGS-B",

730 args=costargs,

731 jac=True,

732 )

733

734 return optresult.x.reshape((-1, dim))

735

736

737def _kamada_kawai_costfn(pos_vec, np, invdist, meanweight, dim):

738 # Cost-function and gradient for Kamada-Kawai layout algorithm

739 nNodes = invdist.shape[0]

740 pos_arr = pos_vec.reshape((nNodes, dim))

741

742 delta = pos_arr[:, np.newaxis, :] - pos_arr[np.newaxis, :, :]

743 nodesep = np.linalg.norm(delta, axis=-1)

744 direction = np.einsum("ijk,ij->ijk", delta, 1 / (nodesep + np.eye(nNodes) * 1e-3))

745

746 offset = nodesep * invdist - 1.0

747 offset[np.diag_indices(nNodes)] = 0

748

749 cost = 0.5 * np.sum(offset**2)

750 grad = np.einsum("ij,ij,ijk->ik", invdist, offset, direction) - np.einsum(

751 "ij,ij,ijk->jk", invdist, offset, direction

752 )

753

754 # Additional parabolic term to encourage mean position to be near origin:

755 sumpos = np.sum(pos_arr, axis=0)

756 cost += 0.5 * meanweight * np.sum(sumpos**2)

757 grad += meanweight * sumpos

758

759 return (cost, grad.ravel())

760

761

762def spectral_layout(G, weight="weight", scale=1, center=None, dim=2):

763 """Position nodes using the eigenvectors of the graph Laplacian.

764

765 Using the unnormalized Laplacian, the layout shows possible clusters of

766 nodes which are an approximation of the ratio cut. If dim is the number of

767 dimensions then the positions are the entries of the dim eigenvectors

768 corresponding to the ascending eigenvalues starting from the second one.

769

770 Parameters

771 ----------

772 G : NetworkX graph or list of nodes

773 A position will be assigned to every node in G.

774

775 weight : string or None optional (default='weight')

776 The edge attribute that holds the numerical value used for

777 the edge weight. If None, then all edge weights are 1.

778

779 scale : number (default: 1)

780 Scale factor for positions.

781

782 center : array-like or None

783 Coordinate pair around which to center the layout.

784

785 dim : int

786 Dimension of layout.

787

788 Returns

789 -------

790 pos : dict

791 A dictionary of positions keyed by node

792

793 Examples

794 --------

795 >>> G = nx.path_graph(4)

796 >>> pos = nx.spectral_layout(G)

797

798 Notes

799 -----

800 Directed graphs will be considered as undirected graphs when

801 positioning the nodes.

802

803 For larger graphs (>500 nodes) this will use the SciPy sparse

804 eigenvalue solver (ARPACK).

805 """

806 # handle some special cases that break the eigensolvers

807 import numpy as np

808

809 G, center = _process_params(G, center, dim)

810

811 if len(G) <= 2:

812 if len(G) == 0:

813 pos = np.array([])

814 elif len(G) == 1:

815 pos = np.array([center])

816 else:

817 pos = np.array([np.zeros(dim), np.array(center) * 2.0])

818 return dict(zip(G, pos))

819 try:

820 # Sparse matrix

821 if len(G) < 500: # dense solver is faster for small graphs

822 raise ValueError

823 A = nx.to_scipy_sparse_array(G, weight=weight, dtype="d")

824 # Symmetrize directed graphs

825 if G.is_directed():

826 A = A + np.transpose(A)

827 pos = _sparse_spectral(A, dim)

828 except (ImportError, ValueError):

829 # Dense matrix

830 A = nx.to_numpy_array(G, weight=weight)

831 # Symmetrize directed graphs

832 if G.is_directed():

833 A += A.T

834 pos = _spectral(A, dim)

835

836 pos = rescale_layout(pos, scale=scale) + center

837 pos = dict(zip(G, pos))

838 return pos

839

840

841def _spectral(A, dim=2):

842 # Input adjacency matrix A

843 # Uses dense eigenvalue solver from numpy

844 import numpy as np

845

846 try:

847 nnodes, _ = A.shape

848 except AttributeError as err:

849 msg = "spectral() takes an adjacency matrix as input"

850 raise nx.NetworkXError(msg) from err

851

852 # form Laplacian matrix where D is diagonal of degrees

853 D = np.identity(nnodes, dtype=A.dtype) * np.sum(A, axis=1)

854 L = D - A

855

856 eigenvalues, eigenvectors = np.linalg.eig(L)

857 # sort and keep smallest nonzero

858 index = np.argsort(eigenvalues)[1 : dim + 1] # 0 index is zero eigenvalue

859 return np.real(eigenvectors[:, index])

860

861

862def _sparse_spectral(A, dim=2):

863 # Input adjacency matrix A

864 # Uses sparse eigenvalue solver from scipy

865 # Could use multilevel methods here, see Koren "On spectral graph drawing"

866 import numpy as np

867 import scipy as sp

868

869 try:

870 nnodes, _ = A.shape

871 except AttributeError as err:

872 msg = "sparse_spectral() takes an adjacency matrix as input"

873 raise nx.NetworkXError(msg) from err

874

875 # form Laplacian matrix

876 # TODO: Rm csr_array wrapper in favor of spdiags array constructor when available

877 D = sp.sparse.csr_array(sp.sparse.spdiags(A.sum(axis=1), 0, nnodes, nnodes))

878 L = D - A

879

880 k = dim + 1

881 # number of Lanczos vectors for ARPACK solver.What is the right scaling?

882 ncv = max(2 * k + 1, int(np.sqrt(nnodes)))

883 # return smallest k eigenvalues and eigenvectors

884 eigenvalues, eigenvectors = sp.sparse.linalg.eigsh(L, k, which="SM", ncv=ncv)

885 index = np.argsort(eigenvalues)[1:k] # 0 index is zero eigenvalue

886 return np.real(eigenvectors[:, index])

887

888

889def planar_layout(G, scale=1, center=None, dim=2):

890 """Position nodes without edge intersections.

891

892 Parameters

893 ----------

894 G : NetworkX graph or list of nodes

895 A position will be assigned to every node in G. If G is of type

896 nx.PlanarEmbedding, the positions are selected accordingly.

897

898 scale : number (default: 1)

899 Scale factor for positions.

900

901 center : array-like or None

902 Coordinate pair around which to center the layout.

903

904 dim : int

905 Dimension of layout.

906

907 Returns

908 -------

909 pos : dict

910 A dictionary of positions keyed by node

911

912 Raises

913 ------

914 NetworkXException

915 If G is not planar

916

917 Examples

918 --------

919 >>> G = nx.path_graph(4)

920 >>> pos = nx.planar_layout(G)

921 """

922 import numpy as np

923

924 if dim != 2:

925 raise ValueError("can only handle 2 dimensions")

926

927 G, center = _process_params(G, center, dim)

928

929 if len(G) == 0:

930 return {}

931

932 if isinstance(G, nx.PlanarEmbedding):

933 embedding = G

934 else:

935 is_planar, embedding = nx.check_planarity(G)

936 if not is_planar:

937 raise nx.NetworkXException("G is not planar.")

938 pos = nx.combinatorial_embedding_to_pos(embedding)

939 node_list = list(embedding)

940 pos = np.row_stack([pos[x] for x in node_list])

941 pos = pos.astype(np.float64)

942 pos = rescale_layout(pos, scale=scale) + center

943 return dict(zip(node_list, pos))

944

945

946def spiral_layout(G, scale=1, center=None, dim=2, resolution=0.35, equidistant=False):

947 """Position nodes in a spiral layout.

948

949 Parameters

950 ----------

951 G : NetworkX graph or list of nodes

952 A position will be assigned to every node in G.

953 scale : number (default: 1)

954 Scale factor for positions.

955 center : array-like or None

956 Coordinate pair around which to center the layout.

957 dim : int, default=2

958 Dimension of layout, currently only dim=2 is supported.

959 Other dimension values result in a ValueError.

960 resolution : float, default=0.35

961 The compactness of the spiral layout returned.

962 Lower values result in more compressed spiral layouts.

963 equidistant : bool, default=False

964 If True, nodes will be positioned equidistant from each other

965 by decreasing angle further from center.

966 If False, nodes will be positioned at equal angles

967 from each other by increasing separation further from center.

968

969 Returns

970 -------

971 pos : dict

972 A dictionary of positions keyed by node

973

974 Raises

975 ------

976 ValueError

977 If dim != 2

978

979 Examples

980 --------

981 >>> G = nx.path_graph(4)

982 >>> pos = nx.spiral_layout(G)

983 >>> nx.draw(G, pos=pos)

984

985 Notes

986 -----

987 This algorithm currently only works in two dimensions.

988

989 """

990 import numpy as np

991

992 if dim != 2:

993 raise ValueError("can only handle 2 dimensions")

994

995 G, center = _process_params(G, center, dim)

996

997 if len(G) == 0:

998 return {}

999 if len(G) == 1:

1000 return {nx.utils.arbitrary_element(G): center}

1001

1002 pos = []

1003 if equidistant:

1004 chord = 1

1005 step = 0.5

1006 theta = resolution

1007 theta += chord / (step * theta)

1008 for _ in range(len(G)):

1009 r = step * theta

1010 theta += chord / r

1011 pos.append([np.cos(theta) * r, np.sin(theta) * r])

1012

1013 else:

1014 dist = np.arange(len(G), dtype=float)

1015 angle = resolution * dist

1016 pos = np.transpose(dist * np.array([np.cos(angle), np.sin(angle)]))

1017

1018 pos = rescale_layout(np.array(pos), scale=scale) + center

1019

1020 pos = dict(zip(G, pos))

1021

1022 return pos

1023

1024

1025def multipartite_layout(G, subset_key="subset", align="vertical", scale=1, center=None):

1026 """Position nodes in layers of straight lines.

1027

1028 Parameters

1029 ----------

1030 G : NetworkX graph or list of nodes

1031 A position will be assigned to every node in G.

1032

1033 subset_key : string (default='subset')

1034 Key of node data to be used as layer subset.

1035

1036 align : string (default='vertical')

1037 The alignment of nodes. Vertical or horizontal.

1038

1039 scale : number (default: 1)

1040 Scale factor for positions.

1041

1042 center : array-like or None

1043 Coordinate pair around which to center the layout.

1044

1045 Returns

1046 -------

1047 pos : dict

1048 A dictionary of positions keyed by node.

1049

1050 Examples

1051 --------

1052 >>> G = nx.complete_multipartite_graph(28, 16, 10)

1053 >>> pos = nx.multipartite_layout(G)

1054

1055 Notes

1056 -----

1057 This algorithm currently only works in two dimensions and does not

1058 try to minimize edge crossings.

1059

1060 Network does not need to be a complete multipartite graph. As long as nodes

1061 have subset_key data, they will be placed in the corresponding layers.

1062

1063 """

1064 import numpy as np

1065

1066 if align not in ("vertical", "horizontal"):

1067 msg = "align must be either vertical or horizontal."

1068 raise ValueError(msg)

1069

1070 G, center = _process_params(G, center=center, dim=2)

1071 if len(G) == 0:

1072 return {}

1073

1074 layers = {}

1075 for v, data in G.nodes(data=True):

1076 try:

1077 layer = data[subset_key]

1078 except KeyError:

1079 msg = "all nodes must have subset_key (default='subset') as data"

1080 raise ValueError(msg)

1081 layers[layer] = [v] + layers.get(layer, [])

1082

1083 # Sort by layer, if possible

1084 try:

1085 layers = sorted(layers.items())

1086 except TypeError:

1087 layers = list(layers.items())

1088

1089 pos = None

1090 nodes = []

1091 width = len(layers)

1092 for i, (_, layer) in enumerate(layers):

1093 height = len(layer)

1094 xs = np.repeat(i, height)

1095 ys = np.arange(0, height, dtype=float)

1096 offset = ((width - 1) / 2, (height - 1) / 2)

1097 layer_pos = np.column_stack([xs, ys]) - offset

1098 if pos is None:

1099 pos = layer_pos

1100 else:

1101 pos = np.concatenate([pos, layer_pos])

1102 nodes.extend(layer)

1103 pos = rescale_layout(pos, scale=scale) + center

1104 if align == "horizontal":

1105 pos = pos[:, ::-1] # swap x and y coords

1106 pos = dict(zip(nodes, pos))

1107 return pos

1108

1109

1110def arf_layout(

1111 G,

1112 pos=None,

1113 scaling=1,

1114 a=1.1,

1115 etol=1e-6,

1116 dt=1e-3,

1117 max_iter=1000,

1118):

1119 """Arf layout for networkx

1120

1121 The attractive and repulsive forces (arf) layout [1]

1122 improves the spring layout in three ways. First, it

1123 prevents congestion of highly connected nodes due to

1124 strong forcing between nodes. Second, it utilizes the

1125 layout space more effectively by preventing large gaps

1126 that spring layout tends to create. Lastly, the arf

1127 layout represents symmetries in the layout better than

1128 the default spring layout.

1129

1130 Parameters

1131 ----------

1132 G : nx.Graph or nx.DiGraph

1133 Networkx graph.

1134 pos : dict

1135 Initial position of the nodes. If set to None a

1136 random layout will be used.

1137 scaling : float

1138 Scales the radius of the circular layout space.

1139 a : float

1140 Strength of springs between connected nodes. Should be larger than 1. The greater a, the clearer the separation ofunconnected sub clusters.

1141 etol : float

1142 Gradient sum of spring forces must be larger than `etol` before successful termination.

1143 dt : float

1144 Time step for force differential equation simulations.

1145 max_iter : int

1146 Max iterations before termination of the algorithm.

1147

1148 References

1149 .. [1] "Self-Organization Applied to Dynamic Network Layout", M. Geipel,

1150 International Journal of Modern Physics C, 2007, Vol 18, No 10, pp. 1537-1549.

1151 https://doi.org/10.1142/S0129183107011558 https://arxiv.org/abs/0704.1748

1152

1153 Returns

1154 -------

1155 pos : dict

1156 A dictionary of positions keyed by node.

1157

1158 Examples

1159 --------

1160 >>> G = nx.grid_graph((5, 5))

1161 >>> pos = nx.arf_layout(G)

1162

1163 """

1164 import warnings

1165

1166 import numpy as np

1167

1168 if a <= 1:

1169 msg = "The parameter a should be larger than 1"

1170 raise ValueError(msg)

1171

1172 pos_tmp = nx.random_layout(G)

1173 if pos is None:

1174 pos = pos_tmp

1175 else:

1176 for node in G.nodes():

1177 if node not in pos:

1178 pos[node] = pos_tmp[node].copy()

1179

1180 # Initialize spring constant matrix

1181 N = len(G)

1182 # No nodes no computation

1183 if N == 0:

1184 return pos

1185

1186 # init force of springs

1187 K = np.ones((N, N)) - np.eye(N)

1188 node_order = {node: i for i, node in enumerate(G)}

1189 for x, y in G.edges():

1190 if x != y:

1191 idx, jdx = (node_order[i] for i in (x, y))

1192 K[idx, jdx] = a

1193

1194 # vectorize values

1195 p = np.asarray(list(pos.values()))

1196

1197 # equation 10 in [1]

1198 rho = scaling * np.sqrt(N)

1199

1200 # looping variables

1201 error = etol + 1

1202 n_iter = 0

1203 while error > etol:

1204 diff = p[:, np.newaxis] - p[np.newaxis]

1205 A = np.linalg.norm(diff, axis=-1)[..., np.newaxis]

1206 # attraction_force - repulsions force

1207 # suppress nans due to division; caused by diagonal set to zero.

1208 # Does not affect the computation due to nansum

1209 with warnings.catch_warnings():

1210 warnings.simplefilter("ignore")

1211 change = K[..., np.newaxis] * diff - rho / A * diff

1212 change = np.nansum(change, axis=0)

1213 p += change * dt

1214

1215 error = np.linalg.norm(change, axis=-1).sum()

1216 if n_iter > max_iter:

1217 break

1218 n_iter += 1

1219 return dict(zip(G.nodes(), p))

1220

1221

1222def rescale_layout(pos, scale=1):

1223 """Returns scaled position array to (-scale, scale) in all axes.

1224

1225 The function acts on NumPy arrays which hold position information.

1226 Each position is one row of the array. The dimension of the space

1227 equals the number of columns. Each coordinate in one column.

1228

1229 To rescale, the mean (center) is subtracted from each axis separately.

1230 Then all values are scaled so that the largest magnitude value

1231 from all axes equals `scale` (thus, the aspect ratio is preserved).

1232 The resulting NumPy Array is returned (order of rows unchanged).

1233

1234 Parameters

1235 ----------

1236 pos : numpy array

1237 positions to be scaled. Each row is a position.

1238

1239 scale : number (default: 1)

1240 The size of the resulting extent in all directions.

1241

1242 Returns

1243 -------

1244 pos : numpy array

1245 scaled positions. Each row is a position.

1246

1247 See Also

1248 --------

1249 rescale_layout_dict

1250 """

1251 import numpy as np

1252

1253 # Find max length over all dimensions

1254 pos -= pos.mean(axis=0)

1255 lim = np.abs(pos).max() # max coordinate for all axes

1256 # rescale to (-scale, scale) in all directions, preserves aspect

1257 if lim > 0:

1258 pos *= scale / lim

1259 return pos

1260

1261

1262def rescale_layout_dict(pos, scale=1):

1263 """Return a dictionary of scaled positions keyed by node

1264

1265 Parameters

1266 ----------

1267 pos : A dictionary of positions keyed by node

1268

1269 scale : number (default: 1)

1270 The size of the resulting extent in all directions.

1271

1272 Returns

1273 -------

1274 pos : A dictionary of positions keyed by node

1275

1276 Examples

1277 --------

1278 >>> import numpy as np

1279 >>> pos = {0: np.array((0, 0)), 1: np.array((1, 1)), 2: np.array((0.5, 0.5))}

1280 >>> nx.rescale_layout_dict(pos)

1281 {0: array([-1., -1.]), 1: array([1., 1.]), 2: array([0., 0.])}

1282

1283 >>> pos = {0: np.array((0, 0)), 1: np.array((-1, 1)), 2: np.array((-0.5, 0.5))}

1284 >>> nx.rescale_layout_dict(pos, scale=2)

1285 {0: array([ 2., -2.]), 1: array([-2., 2.]), 2: array([0., 0.])}

1286

1287 See Also

1288 --------

1289 rescale_layout

1290 """

1291 import numpy as np

1292

1293 if not pos: # empty_graph

1294 return {}

1295 pos_v = np.array(list(pos.values()))

1296 pos_v = rescale_layout(pos_v, scale=scale)

1297 return dict(zip(pos, pos_v))