15928155839

Committed 27 Jun 2025 02:01PM UTC coverage: 50.358% (+0.004%) from 50.354%

Build # 15928155839

Build Type

push

github

Committed by

zommiommy

Commit Message

Fixed ArcListGraph

Run Details

2 of 3 new or added lines in 1 file covered. (66.67%)

147 existing lines in 11 files now uncovered.

3870 of 7685 relevant lines covered (50.36%)

24375193.78 hits per line

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

30.51

/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()?;
    log::info!(
        "Creating a temporary directory for the sorted pairs: {}",
        dir.path().display()
    );

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

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

vigna / webgraph-rs / 15928155839

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