23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Coverage Stats

6655 of 9754 relevant lines covered (68.23%)

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

vigna / webgraph-rs / 23365769388

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