Use `forceatlas2` to construct graph layout

finchie

Apr 19, 2024, 4:38 AM

UQJO24KBYI77E4J6LXWX2IUN7VABQKG6PGKBKWEPDCH5CKYBTC4AC

Dependencies

[2] LOR3KOXG Parse JSON output from `cargo build --timings`
[3] JVYWRCPT Add basic chart visualisation
[4] ZPFD3275 Switch from `cargo_metadata`+`petgraph` to `guppy`
[5] Q3Z6XMP5 Migrate dependency tree to `petgraph::Graph`
[*] 7CVIL7UJ Create simple metadata parser

Change contents

edit in src/main.rs at line 1

[7.49]

[3.48]

use std::collections::HashMap;
edit in src/main.rs at line 4

[3.85]

[3.0]

use forceatlas2::Layout;
replacement in src/main.rs at line 6

[3.13]→[3.13:82](∅→∅)

graph::{DependencyDirection, PackageGraph},
MetadataCommand,

[3.13]

[3.123]

graph::{DependencyDirection, PackageGraph, PackageSet},
MetadataCommand, PackageId,
edit in src/main.rs at line 11

[2.2725]

[7.265]

fn graph_layout<'graph>(
package_set: &'graph PackageSet,
) -> impl Iterator<Item = (&'graph PackageId, forceatlas2::Node<f64, 2>)> {
let link_index: HashMap<&PackageId, usize> = package_set
.package_ids(DependencyDirection::Forward)
.enumerate()
.map(|(index, id)| (id, index))
.collect();
edit in src/main.rs at line 21

[7.266]

[3.83]

let edges = package_set
.links(DependencyDirection::Forward)
.map(|link| (link.from(), link.to()))
.map(|(from, to)| (link_index.get(from.id()), link_index.get(to.id())))
.map(|(from, to)| (*from.unwrap(), *to.unwrap()))
.map(|edge| (edge, 1.0))
.collect();
let sizes = package_set
.package_ids(DependencyDirection::Forward)
.map(|_id| 1.0);

let mut layout =
Layout::from_graph_with_degree_mass(edges, sizes, forceatlas2::Settings::default());

for _step in 0..1_000 {
layout.iteration();
}

// TODO: validate that PackageSet::package_ids() is stable; it is used twice (link_index, here)
// so need to validate ordering is consistent (or, find a cleaner solution)
layout
.nodes
.into_iter()
.zip(package_set.package_ids(DependencyDirection::Forward))
.map(|(node, id)| (id, node))
}
edit in src/main.rs at line 52

[3.259]

[3.429]

let package_set = graph.resolve_all();
let layout = graph_layout(&package_set);
replacement in src/main.rs at line 55

[3.430]→[3.260:541](∅→∅)

let nodes = graph
.packages()
.enumerate()
.map(|(coords, package)| charming::series::GraphNode {
id: package.id().repr().to_string(),
name: package.name().to_string(),
x: coords as f64,
y: coords as f64,

[3.430]

[3.541]

let nodes = layout
.map(|(id, node)| charming::series::GraphNode {
id: id.repr().to_string(),
name: graph.metadata(id).unwrap().name().to_string(),
x: node.pos.x(),
y: node.pos.y(),
edit in Cargo.toml at line 9

[3.1656]

[3.1337]

forceatlas2 = "0.6.1"
edit in Cargo.lock at line 17

[3.1621]

[3.1621]

[[package]]
name = "autocfg"
version = "1.2.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f1fdabc7756949593fe60f30ec81974b613357de856987752631dea1e3394c80"
edit in Cargo.lock at line 25

[3.1634]

[3.1670]

name = "bitflags"
version = "1.3.2"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a"

[[package]]
edit in Cargo.lock at line 40

[7.1219]

[7.1219]

name = "bumpalo"
version = "3.16.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "79296716171880943b8470b5f8d03aa55eb2e645a4874bdbb28adb49162e012c"

[[package]]
edit in Cargo.lock at line 111

[3.2542]

[3.2542]

]

[[package]]
name = "crossbeam-deque"
version = "0.8.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "613f8cc01fe9cf1a3eb3d7f488fd2fa8388403e97039e2f73692932e291a770d"
dependencies = [
"crossbeam-epoch",
"crossbeam-utils",
edit in Cargo.lock at line 124

[3.2557]

[3.2557]

name = "crossbeam-epoch"
version = "0.9.18"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "5b82ac4a3c2ca9c3460964f020e1402edd5753411d7737aa39c3714ad1b5420e"
dependencies = [
"crossbeam-utils",
]

[[package]]
name = "crossbeam-utils"
version = "0.8.19"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "248e3bacc7dc6baa3b21e405ee045c3047101a49145e7e9eca583ab4c2ca5345"

[[package]]
edit in Cargo.lock at line 160

[3.2817]

[3.2077]

"forceatlas2",
edit in Cargo.lock at line 193

[3.1841]

[3.3064]

[[package]]
name = "forceatlas2"
version = "0.6.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "fe250dab91fc35c905e42a120108569fa5fde2b5aa8aae357dcb1c47c309061f"
dependencies = [
"bumpalo",
"num-traits",
"parking_lot",
"rand",
"rayon",
]
edit in Cargo.lock at line 313

[3.3798]

[3.3798]

name = "lock_api"
version = "0.4.11"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3c168f8615b12bc01f9c17e2eb0cc07dcae1940121185446edc3744920e8ef45"
dependencies = [
"autocfg",
"scopeguard",
]

[[package]]
edit in Cargo.lock at line 341

[3.3625]

[3.4164]

name = "num-traits"
version = "0.2.18"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "da0df0e5185db44f69b44f26786fe401b6c293d1907744beaa7fa62b2e5a517a"
dependencies = [
"autocfg",
]

[[package]]
edit in Cargo.lock at line 354

[3.4345]

[3.4345]

[[package]]
name = "parking_lot"
version = "0.12.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "3742b2c103b9f06bc9fff0a37ff4912935851bee6d36f3c02bcc755bcfec228f"
dependencies = [
"lock_api",
"parking_lot_core",
]
edit in Cargo.lock at line 366

[3.4358]

[3.3626]

name = "parking_lot_core"
version = "0.9.9"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "4c42a9226546d68acdd9c0a280d17ce19bfe27a46bf68784e4066115788d008e"
dependencies = [
"cfg-if",
"libc",
"redox_syscall",
"smallvec",
"windows-targets",
]

[[package]]
edit in Cargo.lock at line 441

[3.2505]

[3.2505]

[[package]]
name = "ppv-lite86"
version = "0.2.17"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
edit in Cargo.lock at line 467

[7.2695]

[7.2695]

name = "rand"
version = "0.8.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
dependencies = [
"libc",
"rand_chacha",
"rand_core",
]

[[package]]
name = "rand_chacha"
version = "0.3.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
dependencies = [
"ppv-lite86",
"rand_core",
]

[[package]]
name = "rand_core"
version = "0.6.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
dependencies = [
"getrandom",
]

[[package]]
name = "rayon"
version = "1.10.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "b418a60154510ca1a002a752ca9714984e21e4241e804d32555251faf8b78ffa"
dependencies = [
"either",
"rayon-core",
]

[[package]]
name = "rayon-core"
version = "1.12.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "1465873a3dfdaa8ae7cb14b4383657caab0b3e8a0aa9ae8e04b044854c8dfce2"
dependencies = [
"crossbeam-deque",
"crossbeam-utils",
]

[[package]]
name = "redox_syscall"
version = "0.4.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "4722d768eff46b75989dd134e5c353f0d6296e5aaa3132e776cbdb56be7731aa"
dependencies = [
"bitflags",
]

[[package]]
edit in Cargo.lock at line 532

[7.2883]

[7.2883]

name = "scopeguard"
version = "1.2.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49"

[[package]]
edit in Cargo.lock at line 680

[3.4959]

[3.4959]

name = "windows-targets"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "9a2fa6e2155d7247be68c096456083145c183cbbbc2764150dda45a87197940c"
dependencies = [
"windows_aarch64_gnullvm",
"windows_aarch64_msvc",
"windows_i686_gnu",
"windows_i686_msvc",
"windows_x86_64_gnu",
"windows_x86_64_gnullvm",
"windows_x86_64_msvc",
]

[[package]]
name = "windows_aarch64_gnullvm"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "2b38e32f0abccf9987a4e3079dfb67dcd799fb61361e53e2882c3cbaf0d905d8"

[[package]]
name = "windows_aarch64_msvc"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "dc35310971f3b2dbbf3f0690a219f40e2d9afcf64f9ab7cc1be722937c26b4bc"

[[package]]
name = "windows_i686_gnu"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "a75915e7def60c94dcef72200b9a8e58e5091744960da64ec734a6c6e9b3743e"

[[package]]
name = "windows_i686_msvc"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "8f55c233f70c4b27f66c523580f78f1004e8b5a8b659e05a4eb49d4166cca406"

[[package]]
name = "windows_x86_64_gnu"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "53d40abd2583d23e4718fddf1ebec84dbff8381c07cae67ff7768bbf19c6718e"

[[package]]
name = "windows_x86_64_gnullvm"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "0b7b52767868a23d5bab768e390dc5f5c55825b6d30b86c844ff2dc7414044cc"

[[package]]
name = "windows_x86_64_msvc"
version = "0.48.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ed94fce61571a4006852b7389a063ab983c02eb1bb37b47f8272ce92d06d9538"

[[package]]