14999125721

Committed 13 May 2025 02:22PM UTC coverage: 49.654% (-5.7%) from 55.382%

Build # 14999125721

Build Type

push

github

Committed by

zommiommy

Commit Message

wip hyperball cli

Run Details

4 of 147 new or added lines in 4 files covered. (2.72%)

477 existing lines in 46 files now uncovered.

3663 of 7377 relevant lines covered (49.65%)

25650535.86 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

32.14

/webgraph/src/transform/perm.rs

/*
 * SPDX-FileCopyrightText: 2023 Inria
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use crate::graphs::arc_list_graph;
use crate::prelude::sort_pairs::{BatchIterator, KMergeIters};
use crate::prelude::*;
use anyhow::{ensure, Context, Result};
use dsi_progress_logger::prelude::*;
use lender::*;
use rayon::ThreadPool;
use sux::traits::BitFieldSlice;
use tempfile::Builder;

/// Returns a [sequential](crate::traits::SequentialGraph) permuted graph.
///
/// Note that if the graph is [splittable](SplitLabeling),
/// [`permute_split`] will be much faster.
///
/// This assumes that the permutation is bijective. For the meaning of the
/// additional parameter, see
/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
#[allow(clippy::type_complexity)]
pub fn permute(
    graph: &impl SequentialGraph,
    perm: &impl BitFieldSlice<usize>,
    batch_size: usize,
) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
    ensure!(
        perm.len() == graph.num_nodes(),
        "The given permutation has {} values and thus it's incompatible with a graph with {} nodes.",
        perm.len(),
        graph.num_nodes(),
    );
    let dir = Builder::new().prefix("permute_").tempdir()?;

    // create a stream where to dump the sorted pairs
    let mut sorted = SortPairs::new(batch_size, dir)?;

    // get a premuted view
    let pgraph = PermutedGraph { graph, perm };

    let mut pl = ProgressLogger::default();
    pl.item_name("node")
        .expected_updates(Some(graph.num_nodes()));
    pl.start("Creating batches...");
    // create batches of sorted edges
    for_!( (src, succ) in pgraph.iter() {
        for dst in succ {
            sorted.push(dst, src)?;
        }
        pl.light_update();
    });

    // get a graph on the sorted data
    let edges = sorted.iter().context("Could not read arcs")?;
    let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), edges);
    pl.done();

    Ok(Left(sorted))
}

/// Returns a [sequential](crate::traits::SequentialGraph) permuted graph
/// starting from a [splittable](SplitLabeling) graph.
///
/// Note that if the graph is not [splittable](SplitLabeling) you must use
/// [`permute`], albeit it will be slower.
///
/// This assumes that the permutation is bijective. For the meaning of the
/// additional parameter, see
/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
#[allow(clippy::type_complexity)]
pub fn permute_split<S, P>(
    graph: &S,
    perm: &P,
    batch_size: usize,
    threads: &ThreadPool,
) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>>
where
    S: SequentialGraph + SplitLabeling,
    P: BitFieldSlice<usize> + Send + Sync + Clone,
    for<'a> <S as SequentialLabeling>::Lender<'a>: Send + Sync + Clone + ExactSizeLender,
{
    ensure!(
        perm.len() == graph.num_nodes(),
        "The given permutation has {} values and thus it's incompatible with a graph with {} nodes.",
        perm.len(),
        graph.num_nodes(),
    );

    // get a premuted view
    let pgraph = PermutedGraph { graph, perm };

    let num_threads = threads.current_num_threads();
    let mut dirs = vec![];

    let edges = threads.in_place_scope(|scope| {
        let (tx, rx) = std::sync::mpsc::channel();

        for (thread_id, iter) in pgraph.split_iter(num_threads).enumerate() {
            let tx = tx.clone();
            let dir = Builder::new()
                .prefix(&format!("permute_split_{}_", thread_id))
                .tempdir()
                .expect("Could not create a temporary directory");
            let dir_path = dir.path().to_path_buf();
            dirs.push(dir);
            scope.spawn(move |_| {
                log::debug!("Spawned thread {}", thread_id);
                let mut sorted = SortPairs::new(batch_size / num_threads, dir_path).unwrap();
                for_!( (src, succ) in iter {
                    for dst in succ {
                        sorted.push(src, dst).unwrap();
                    }
                });
                tx.send(sorted.iter().context("Could not read arcs").unwrap())
                    .expect("Could not send the sorted pairs");
                log::debug!("Thread {} finished", thread_id);
            });
        }
        drop(tx);

        // get a graph on the sorted data
        log::debug!("Waiting for threads to finish");
        rx.iter().sum()
    });

    log::debug!("All threads finished");
    Ok(Left(arc_list_graph::ArcListGraph::new_labeled(
        graph.num_nodes(),
        edges,
    )))
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use crate::graphs::arc_list_graph;
8	use crate::prelude::sort_pairs::{BatchIterator, KMergeIters};
9	use crate::prelude::*;
10	use anyhow::{ensure, Context, Result};
11	use dsi_progress_logger::prelude::*;
12	use lender::*;
13	use rayon::ThreadPool;
14	use sux::traits::BitFieldSlice;
15	use tempfile::Builder;
16
17	/// Returns a [sequential](crate::traits::SequentialGraph) permuted graph.
18	///
19	/// Note that if the graph is [splittable](SplitLabeling),
20	/// [`permute_split`] will be much faster.
21	///
22	/// This assumes that the permutation is bijective. For the meaning of the
23	/// additional parameter, see
24	/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
25	#[allow(clippy::type_complexity)]
26	pub fn permute(	×
27	graph: &impl SequentialGraph,
28	perm: &impl BitFieldSlice<usize>,
29	batch_size: usize,
30	) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
31	ensure!(	×
32	perm.len() == graph.num_nodes(),	×
33	"The given permutation has {} values and thus it's incompatible with a graph with {} nodes.",	×
34	perm.len(),	×
35	graph.num_nodes(),	×
36	);
37	let dir = Builder::new().prefix("permute_").tempdir()?;	×
38
39	// create a stream where to dump the sorted pairs
40	let mut sorted = SortPairs::new(batch_size, dir)?;	×
41
42	// get a premuted view
43	let pgraph = PermutedGraph { graph, perm };	×
44
45	let mut pl = ProgressLogger::default();	×
46	pl.item_name("node")	×
47	.expected_updates(Some(graph.num_nodes()));	×
48	pl.start("Creating batches...");	×
49	// create batches of sorted edges
50	for_!( (src, succ) in pgraph.iter() {	×
51	for dst in succ {	×
52	sorted.push(dst, src)?;	×
53	}
54	pl.light_update();	×
55	});
56
57	// get a graph on the sorted data
58	let edges = sorted.iter().context("Could not read arcs")?;	×
59	let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), edges);	×
60	pl.done();	×
61
62	Ok(Left(sorted))	×
63	}
64
65	/// Returns a [sequential](crate::traits::SequentialGraph) permuted graph
66	/// starting from a [splittable](SplitLabeling) graph.
67	///
68	/// Note that if the graph is not [splittable](SplitLabeling) you must use
69	/// [`permute`], albeit it will be slower.
70	///
71	/// This assumes that the permutation is bijective. For the meaning of the
72	/// additional parameter, see
73	/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
74	#[allow(clippy::type_complexity)]
75	pub fn permute_split<S, P>(	4✔
76	graph: &S,
77	perm: &P,
78	batch_size: usize,
79	threads: &ThreadPool,
80	) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>>
81	where
82	S: SequentialGraph + SplitLabeling,
83	P: BitFieldSlice<usize> + Send + Sync + Clone,
84	for<'a> <S as SequentialLabeling>::Lender<'a>: Send + Sync + Clone + ExactSizeLender,
85	{
86	ensure!(	4✔
87	perm.len() == graph.num_nodes(),	12✔
88	"The given permutation has {} values and thus it's incompatible with a graph with {} nodes.",	×
89	perm.len(),	×
90	graph.num_nodes(),	×
91	);
92
93	// get a premuted view
94	let pgraph = PermutedGraph { graph, perm };	4✔
95
UNCOV 96	let num_threads = threads.current_num_threads();	×
UNCOV 97	let mut dirs = vec![];	×
98
99	let edges = threads.in_place_scope(\|scope\| {	4✔
100	let (tx, rx) = std::sync::mpsc::channel();	12✔
101
102	for (thread_id, iter) in pgraph.split_iter(num_threads).enumerate() {	32✔
103	let tx = tx.clone();	×
104	let dir = Builder::new()	×
105	.prefix(&format!("permute_split_{}_", thread_id))	×
106	.tempdir()	×
107	.expect("Could not create a temporary directory");	×
108	let dir_path = dir.path().to_path_buf();	×
109	dirs.push(dir);	×
110	scope.spawn(move \|_\| {	16✔
111	log::debug!("Spawned thread {}", thread_id);	16✔
112	let mut sorted = SortPairs::new(batch_size / num_threads, dir_path).unwrap();	80✔
113	for_!( (src, succ) in iter {	1,302,244✔
114	for dst in succ {	27,031,444✔
115	sorted.push(src, dst).unwrap();	×
116	}
117	});
118	tx.send(sorted.iter().context("Could not read arcs").unwrap())	96✔
119	.expect("Could not send the sorted pairs");	32✔
120	log::debug!("Thread {} finished", thread_id);	16✔
121	});
122	}
123	drop(tx);	8✔
124
125	// get a graph on the sorted data
126	log::debug!("Waiting for threads to finish");	4✔
127	rx.iter().sum()	12✔
128	});
129
130	log::debug!("All threads finished");	×
131	Ok(Left(arc_list_graph::ArcListGraph::new_labeled(	×
132	graph.num_nodes(),	×
133	edges,	×
134	)))
135	}

vigna / webgraph-rs / 14999125721

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous