1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
* SPDX-FileCopyrightText: 2023 Tommaso Fontana
*
* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
*/
//! Transformations on labelings and graphs.
//!
//! This module provides functions that compute common graph transformations. All
//! functions return the result as a [sequential
//! graph](crate::traits::SequentialGraph), which can then be compressed into a
//! [BvGraph](crate::graphs::bvgraph) using
//! [`BvComp`](crate::graphs::bvgraph::BvComp) or stored in any other format.
//!
//! # Transpose
//!
//! - [`transpose`]: returns the transpose of a graph;
//! - [`transpose_labeled`]: returns the transpose of a labeled graph;
//! - [`transpose_split`]: returns the transpose of a
//! [splittable](crate::traits::SplitLabeling) graph, sorting in parallel;
//! - [`transpose_labeled_split`]: same, for labeled graphs.
//!
//! # Simplify
//!
//! - [`simplify`]: returns a simplified (undirected and loopless) version of a
//! graph;
//! - [`simplify_sorted`]: same, but exploits the fact that the input is already
//! sorted, halving the number of arcs to sort;
//! - [`simplify_split`]: same, using splitting to sort in parallel.
//!
//! # Permute
//!
//! - [`permute`]: returns the graph with nodes permuted according to a given
//! permutation;
//! - [`permute_split`]: same, using splitting to sort in parallel.
//!
//! # Memory Usage
//!
//! The transpose, simplify, and permute functions internally use
//! [`SortPairs`](crate::utils::SortPairs), which sorts arcs by batching them to
//! temporary files and then merging. The amount of memory used for batching is
//! controlled by the [`MemoryUsage`](crate::utils::MemoryUsage) parameter. The
//! `_split` variants sort in parallel using
//! [`ParSortIters`](crate::utils::ParSortIters) and are significantly faster on
//! [splittable](crate::traits::SplitLabeling) graphs.
pub use *;
pub use *;
pub use *;