19278972970

Committed 11 Nov 2025 09:25PM UTC coverage: 62.316% (+14.3%) from 48.052%

Build # 19278972970

Build Type

push

github

Committed by

zommiommy

Commit Message

BatchCodec print stats and encoding time

Run Details

40 of 53 new or added lines in 4 files covered. (75.47%)

814 existing lines in 46 files now uncovered.

5252 of 8428 relevant lines covered (62.32%)

29580067.92 hits per line

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

0.0

/webgraph/examples/custom_codes_bfs.rs

/*
 * SPDX-FileCopyrightText: 2025 Tommaso Fontana
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use std::collections::VecDeque;
use std::path::PathBuf;

use anyhow::Result;
use clap::Parser;
use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
use dsi_progress_logger::prelude::*;
use epserde::deser::{Deserialize, Flags, MemCase};
use mmap_rs::MmapFlags;
use sux::{
    bits::BitVec,
    traits::{BitVecOpsMut, IndexedSeq},
};
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(about = "Reads a graph encoded with custom codes and does a BFS on it.", long_about = None)]
struct Args {
    // The basename of the graph.
    basename: PathBuf,

    /// The number of nodes in the graph
    num_nodes: usize,

    /// The number of arcs in the graph
    num_arcs: u64,

    #[clap(long, default_value = "false")]
    /// Whether to use mmap for the graph, otherwise it will be load in memory
    mmap: bool,
}

/// This is the factory that we can plug in BVGraph to read the custom codes
pub struct CustomDecoderFactory<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> {
    pub factory: F,
    // The [`MemCase`]` here is needed to memory-map the offsets, otherwise
    // it can just be `OFF`
    pub offsets: MemCase<OFF>,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> CustomDecoderFactory<E, F, OFF> {
    pub fn new(factory: F, offsets: MemCase<OFF>) -> Self {
        Self {
            factory,
            offsets,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> RandomAccessDecoderFactory
    for CustomDecoderFactory<E, F, OFF>
where
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
{
    type Decoder<'a>
        = CustomDecoder<E, F::CodesReader<'a>>
    where
        Self: 'a;
    fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {
        let mut code_reader = self.factory.new_reader();
        code_reader.set_bit_pos(self.offsets.uncase().get(node) as u64)?;
        Ok(CustomDecoder::new(code_reader))
    }
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> SequentialDecoderFactory
    for CustomDecoderFactory<E, F, OFF>
where
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
{
    type Decoder<'a>
        = CustomDecoder<E, F::CodesReader<'a>>
    where
        Self: 'a;
    fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {
        Ok(CustomDecoder::new(self.factory.new_reader()))
    }
}

/// This is the decoder that will decode our custom codes and give them to BVGraph
pub struct CustomDecoder<E: Endianness, R: CodesRead<E>> {
    pub decoder: R,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, R: CodesRead<E>> CustomDecoder<E, R> {
    pub fn new(decoder: R) -> Self {
        Self {
            decoder,
            _marker: std::marker::PhantomData,
        }
    }

    pub fn into_inner(self) -> R {
        self.decoder
    }
}

impl<E: Endianness, R: CodesRead<E>> Decode for CustomDecoder<E, R> {
    #[inline(always)]
    fn read_outdegree(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_reference_offset(&mut self) -> u64 {
        self.decoder.read_unary().unwrap()
    }
    #[inline(always)]
    fn read_block_count(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_block(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_interval_count(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_interval_start(&mut self) -> u64 {
        self.decoder.read_pi(2).unwrap()
    }
    #[inline(always)]
    fn read_interval_len(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_first_residual(&mut self) -> u64 {
        self.decoder.read_pi(3).unwrap()
    }
    #[inline(always)]
    fn read_residual(&mut self) -> u64 {
        self.decoder.read_pi(2).unwrap()
    }
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let _ = env_logger::builder()
        .filter_level(log::LevelFilter::Debug)
        .try_init();

    let args = Args::parse();

    let offsets =
        unsafe { EF::load_mmap(args.basename.with_extension(EF_EXTENSION), Flags::default()) }?;

    if args.mmap {
        let graph = BvGraph::new(
            CustomDecoderFactory::<LE, _, _>::new(
                // This is MMap
                MmapHelper::mmap(
                    args.basename.with_extension(GRAPH_EXTENSION),
                    MmapFlags::empty(),
                )?,
                offsets,
            ),
            args.num_nodes,
            args.num_arcs,
            7, // default
            4, // default
        );

        visit(graph)?;
    } else {
        let graph = BvGraph::new(
            CustomDecoderFactory::new(
                MemoryFactory::<LE, _>::new_mmap(
                    args.basename.with_extension(GRAPH_EXTENSION),
                    MemoryFlags::default(),
                )?,
                offsets,
            ),
            args.num_nodes,
            args.num_arcs,
            7, // default
            4, // default
        );

        visit(graph)?;
    }

    Ok(())
}

fn visit(graph: impl RandomAccessGraph) -> Result<()> {
    let num_nodes = graph.num_nodes();
    let mut seen = BitVec::new(num_nodes);
    let mut queue = VecDeque::new();

    let mut pl = ProgressLogger::default();
    pl.display_memory(true)
        .item_name("node")
        .local_speed(true)
        .expected_updates(Some(num_nodes));
    pl.start("Visiting graph...");

    for start in 0..num_nodes {
        if seen[start] {
            continue;
        }
        queue.push_back(start as _);
        seen.set(start, true);

        while !queue.is_empty() {
            pl.light_update();
            let current_node = queue.pop_front().unwrap();
            for succ in graph.successors(current_node) {
                if !seen[succ] {
                    queue.push_back(succ);
                    seen.set(succ as _, true);
                }
            }
        }
    }

    pl.done();

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Tommaso Fontana
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use std::collections::VecDeque;
8	use std::path::PathBuf;
9
10	use anyhow::Result;
11	use clap::Parser;
12	use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
13	use dsi_progress_logger::prelude::*;
14	use epserde::deser::{Deserialize, Flags, MemCase};
15	use mmap_rs::MmapFlags;
16	use sux::{
17	bits::BitVec,
18	traits::{BitVecOpsMut, IndexedSeq},
19	};
20	use webgraph::prelude::*;
21
22	#[derive(Parser, Debug)]
23	#[command(about = "Reads a graph encoded with custom codes and does a BFS on it.", long_about = None)]
24	struct Args {
25	// The basename of the graph.
26	basename: PathBuf,
27
28	/// The number of nodes in the graph
29	num_nodes: usize,
30
31	/// The number of arcs in the graph
32	num_arcs: u64,
33
34	#[clap(long, default_value = "false")]
35	/// Whether to use mmap for the graph, otherwise it will be load in memory
36	mmap: bool,
37	}
38
39	/// This is the factory that we can plug in BVGraph to read the custom codes
40	pub struct CustomDecoderFactory<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> {
41	pub factory: F,
42	// The [`MemCase`]` here is needed to memory-map the offsets, otherwise
43	// it can just be `OFF`
44	pub offsets: MemCase<OFF>,
45	_marker: std::marker::PhantomData<E>,
46	}
47
48	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> CustomDecoderFactory<E, F, OFF> {
UNCOV 49	pub fn new(factory: F, offsets: MemCase<OFF>) -> Self {	×
50	Self {
51	factory,
52	offsets,
53	_marker: std::marker::PhantomData,
54	}
55	}
56	}
57
58	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> RandomAccessDecoderFactory
59	for CustomDecoderFactory<E, F, OFF>
60	where
61	for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
62	{
63	type Decoder<'a>
64	= CustomDecoder<E, F::CodesReader<'a>>
65	where
66	Self: 'a;
67	fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {	×
UNCOV 68	let mut code_reader = self.factory.new_reader();	×
UNCOV 69	code_reader.set_bit_pos(self.offsets.uncase().get(node) as u64)?;	×
UNCOV 70	Ok(CustomDecoder::new(code_reader))	×
71	}
72	}
73
74	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> SequentialDecoderFactory
75	for CustomDecoderFactory<E, F, OFF>
76	where
77	for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
78	{
79	type Decoder<'a>
80	= CustomDecoder<E, F::CodesReader<'a>>
81	where
82	Self: 'a;
UNCOV 83	fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {	×
UNCOV 84	Ok(CustomDecoder::new(self.factory.new_reader()))	×
85	}
86	}
87
88	/// This is the decoder that will decode our custom codes and give them to BVGraph
89	pub struct CustomDecoder<E: Endianness, R: CodesRead<E>> {
90	pub decoder: R,
91	_marker: std::marker::PhantomData<E>,
92	}
93
94	impl<E: Endianness, R: CodesRead<E>> CustomDecoder<E, R> {
UNCOV 95	pub fn new(decoder: R) -> Self {	×
96	Self {
97	decoder,
98	_marker: std::marker::PhantomData,
99	}
100	}
101
UNCOV 102	pub fn into_inner(self) -> R {	×
UNCOV 103	self.decoder	×
104	}
105	}
106
107	impl<E: Endianness, R: CodesRead<E>> Decode for CustomDecoder<E, R> {
108	#[inline(always)]
UNCOV 109	fn read_outdegree(&mut self) -> u64 {	×
110	self.decoder.read_gamma().unwrap()	×
111	}
112	#[inline(always)]
UNCOV 113	fn read_reference_offset(&mut self) -> u64 {	×
114	self.decoder.read_unary().unwrap()	×
115	}
116	#[inline(always)]
UNCOV 117	fn read_block_count(&mut self) -> u64 {	×
118	self.decoder.read_gamma().unwrap()	×
119	}
120	#[inline(always)]
UNCOV 121	fn read_block(&mut self) -> u64 {	×
122	self.decoder.read_gamma().unwrap()	×
123	}
124	#[inline(always)]
UNCOV 125	fn read_interval_count(&mut self) -> u64 {	×
126	self.decoder.read_gamma().unwrap()	×
127	}
128	#[inline(always)]
UNCOV 129	fn read_interval_start(&mut self) -> u64 {	×
130	self.decoder.read_pi(2).unwrap()	×
131	}
132	#[inline(always)]
UNCOV 133	fn read_interval_len(&mut self) -> u64 {	×
134	self.decoder.read_gamma().unwrap()	×
135	}
136	#[inline(always)]
UNCOV 137	fn read_first_residual(&mut self) -> u64 {	×
138	self.decoder.read_pi(3).unwrap()	×
139	}
140	#[inline(always)]
UNCOV 141	fn read_residual(&mut self) -> u64 {	×
UNCOV 142	self.decoder.read_pi(2).unwrap()	×
143	}
144	}
145
146	fn main() -> Result<(), Box<dyn std::error::Error>> {
147	let _ = env_logger::builder()
148	.filter_level(log::LevelFilter::Debug)
149	.try_init();
150
151	let args = Args::parse();
152
153	let offsets =
154	unsafe { EF::load_mmap(args.basename.with_extension(EF_EXTENSION), Flags::default()) }?;
155
156	if args.mmap {
157	let graph = BvGraph::new(
158	CustomDecoderFactory::<LE, _, _>::new(
159	// This is MMap
160	MmapHelper::mmap(
161	args.basename.with_extension(GRAPH_EXTENSION),
162	MmapFlags::empty(),
163	)?,
164	offsets,
165	),
166	args.num_nodes,
167	args.num_arcs,
168	7, // default
169	4, // default
170	);
171
172	visit(graph)?;
173	} else {
174	let graph = BvGraph::new(
175	CustomDecoderFactory::new(
176	MemoryFactory::<LE, _>::new_mmap(
177	args.basename.with_extension(GRAPH_EXTENSION),
178	MemoryFlags::default(),
179	)?,
180	offsets,
181	),
182	args.num_nodes,
183	args.num_arcs,
184	7, // default
185	4, // default
186	);
187
188	visit(graph)?;
189	}
190
191	Ok(())
192	}
193
194	fn visit(graph: impl RandomAccessGraph) -> Result<()> {	×
UNCOV 195	let num_nodes = graph.num_nodes();	×
196	let mut seen = BitVec::new(num_nodes);	×
197	let mut queue = VecDeque::new();	×
198
UNCOV 199	let mut pl = ProgressLogger::default();	×
200	pl.display_memory(true)	×
201	.item_name("node")
202	.local_speed(true)
203	.expected_updates(Some(num_nodes));	×
204	pl.start("Visiting graph...");	×
205
UNCOV 206	for start in 0..num_nodes {	×
207	if seen[start] {	×
208	continue;	×
209	}
210	queue.push_back(start as _);	×
211	seen.set(start, true);	×
212
213	while !queue.is_empty() {	×
214	pl.light_update();	×
215	let current_node = queue.pop_front().unwrap();	×
216	for succ in graph.successors(current_node) {	×
UNCOV 217	if !seen[succ] {	×
UNCOV 218	queue.push_back(succ);	×
UNCOV 219	seen.set(succ as _, true);	×
220	}
221	}
222	}
223	}
224
UNCOV 225	pl.done();	×
226
UNCOV 227	Ok(())	×
228	}

vigna / webgraph-rs / 19278972970

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