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

Run Details

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.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::path::PathBuf;

use anyhow::{Context, Result};
use clap::Parser;
use dsi_bitstream::prelude::*;
use dsi_progress_logger::prelude::*;
use webgraph::prelude::*;
use webgraph::utils::Converter;

#[derive(Parser, Debug)]
#[command(about = "Re-encode a graph with custom codes", long_about = None)]
struct Args {
    // The basename of the graph.
    basename: PathBuf,
    /// The destination of the graph.
    dst: PathBuf,
}

/// The custom encoder
pub struct CustomEncoder<E: Endianness, W: CodesWrite<E>> {
    pub encoder: W,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, W: CodesWrite<E>> CustomEncoder<E, W> {
    pub fn new(encoder: W) -> Self {
        Self {
            encoder,
            _marker: std::marker::PhantomData,
        }
    }

    pub fn into_inner(self) -> W {
        self.encoder
    }
}

impl<E: Endianness, W: CodesWrite<E>> Encode for CustomEncoder<E, W> {
    type Error = W::Error;
    #[inline(always)]
    fn write_outdegree(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_gamma(value)
    }
    #[inline(always)]
    fn write_reference_offset(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_unary(value)
    }
    #[inline(always)]
    fn write_block_count(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_gamma(value)
    }
    #[inline(always)]
    fn write_block(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_gamma(value)
    }
    #[inline(always)]
    fn write_interval_count(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_gamma(value)
    }
    #[inline(always)]
    fn write_interval_start(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_pi(value, 2)
    }
    #[inline(always)]
    fn write_interval_len(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_gamma(value)
    }
    #[inline(always)]
    fn write_first_residual(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_pi(value, 3)
    }
    #[inline(always)]
    fn write_residual(&mut self, value: u64) -> Result<usize, Self::Error> {
        self.encoder.write_pi(value, 2)
    }
    #[inline(always)]
    fn flush(&mut self) -> Result<usize, Self::Error> {
        self.encoder.flush()
    }
    #[inline(always)]
    fn start_node(&mut self, _node: usize) -> Result<usize, Self::Error> {
        Ok(0)
    }
    #[inline(always)]
    fn end_node(&mut self, _node: usize) -> Result<usize, Self::Error> {
        Ok(0)
    }
}

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

    let args = Args::parse();
    let graph = BvGraph::with_basename(&args.basename).load()?;

    // create the offsets file while we re-encode the graph so we avoid
    // having to scan the graph afterwards. We can't do an Elias–Fano yet
    // because we don't know the length of the final graph.
    let offsets_path = args.dst.with_extension(OFFSETS_EXTENSION);
    let mut offsets_writer = buf_bit_writer::from_path::<BE, usize>(&offsets_path)
        .with_context(|| format!("Could not create {}", offsets_path.display()))?;

    // create a bitstream writer for the target graph
    let target_graph_path = args.dst.with_extension(GRAPH_EXTENSION);
    let writer = buf_bit_writer::from_path::<LE, usize>(&target_graph_path)
        .with_context(|| format!("Could not create {}", target_graph_path.display()))?;
    let encoder = CustomEncoder::new(writer);

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

    // wrap the offset degrees iterator, which reads every code but doesn't
    // resolve references, so it's much faster if we only need to scan the codes
    let mut iter = graph
        .offset_deg_iter()
        .map_decoder(move |decoder| Converter {
            decoder,
            encoder,
            offset: 0,
        });
    // consume the graph iterator reading all codes and writing them to the encoder
    // through [`Converter`]
    let mut offset = 0;
    for _ in 0..graph.num_nodes() {
        // write the offset to the offsets file
        let new_offset = iter.get_decoder().offset;
        offsets_writer
            .write_gamma((new_offset - offset) as u64)
            .context("Could not write gamma")?;
        offset = new_offset;

        iter.next_degree()?; // read to next node
        pl.light_update();
    }
    // write the last offset
    let new_offset = iter.get_decoder().offset;
    offsets_writer
        .write_gamma((new_offset - offset) as u64)
        .context("Could not write gamma")?;
    pl.light_update();
    pl.done();

    log::info!(
        "Done re-encoding, the graph is {} bits ({} bytes) long.",
        iter.get_decoder().offset,
        iter.get_decoder().offset.div_ceil(8),
    );
    log::info!(
        "Now you should build elias-fano with `cargo run --release build ef '{}' {}`",
        args.dst.display(),
        graph.num_nodes()
    );
    log::info!(
        "Then you can run a BFS on it using `cargo run --release --example custom_codes_bfs '{}' {} {}`",
        args.dst.display(),
        graph.num_nodes(),
        graph.num_arcs(),
    );

    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::path::PathBuf;
9
10	use anyhow::{Context, Result};
11	use clap::Parser;
12	use dsi_bitstream::prelude::*;
13	use dsi_progress_logger::prelude::*;
14	use webgraph::prelude::*;
15	use webgraph::utils::Converter;
16
17	#[derive(Parser, Debug)]
18	#[command(about = "Re-encode a graph with custom codes", long_about = None)]
19	struct Args {
20	// The basename of the graph.
21	basename: PathBuf,
22	/// The destination of the graph.
23	dst: PathBuf,
24	}
25
26	/// The custom encoder
27	pub struct CustomEncoder<E: Endianness, W: CodesWrite<E>> {
28	pub encoder: W,
29	_marker: std::marker::PhantomData<E>,
30	}
31
32	impl<E: Endianness, W: CodesWrite<E>> CustomEncoder<E, W> {
33	pub fn new(encoder: W) -> Self {	×
34	Self {
35	encoder,
36	_marker: std::marker::PhantomData,
37	}
38	}
39
40	pub fn into_inner(self) -> W {	×
41	self.encoder	×
42	}
43	}
44
45	impl<E: Endianness, W: CodesWrite<E>> Encode for CustomEncoder<E, W> {
46	type Error = W::Error;
47	#[inline(always)]
48	fn write_outdegree(&mut self, value: u64) -> Result<usize, Self::Error> {	×
49	self.encoder.write_gamma(value)	×
50	}
51	#[inline(always)]
52	fn write_reference_offset(&mut self, value: u64) -> Result<usize, Self::Error> {	×
53	self.encoder.write_unary(value)	×
54	}
55	#[inline(always)]
56	fn write_block_count(&mut self, value: u64) -> Result<usize, Self::Error> {	×
57	self.encoder.write_gamma(value)	×
58	}
59	#[inline(always)]
60	fn write_block(&mut self, value: u64) -> Result<usize, Self::Error> {	×
61	self.encoder.write_gamma(value)	×
62	}
63	#[inline(always)]
64	fn write_interval_count(&mut self, value: u64) -> Result<usize, Self::Error> {	×
65	self.encoder.write_gamma(value)	×
66	}
67	#[inline(always)]
68	fn write_interval_start(&mut self, value: u64) -> Result<usize, Self::Error> {	×
69	self.encoder.write_pi(value, 2)	×
70	}
71	#[inline(always)]
72	fn write_interval_len(&mut self, value: u64) -> Result<usize, Self::Error> {	×
73	self.encoder.write_gamma(value)	×
74	}
75	#[inline(always)]
76	fn write_first_residual(&mut self, value: u64) -> Result<usize, Self::Error> {	×
77	self.encoder.write_pi(value, 3)	×
78	}
79	#[inline(always)]
80	fn write_residual(&mut self, value: u64) -> Result<usize, Self::Error> {	×
81	self.encoder.write_pi(value, 2)	×
82	}
83	#[inline(always)]
84	fn flush(&mut self) -> Result<usize, Self::Error> {	×
85	self.encoder.flush()	×
86	}
87	#[inline(always)]
88	fn start_node(&mut self, _node: usize) -> Result<usize, Self::Error> {	×
89	Ok(0)	×
90	}
91	#[inline(always)]
92	fn end_node(&mut self, _node: usize) -> Result<usize, Self::Error> {	×
93	Ok(0)	×
94	}
95	}
96
97	fn main() -> Result<(), Box<dyn std::error::Error>> {
98	let _ = env_logger::builder()
99	.filter_level(log::LevelFilter::Debug)
100	.try_init();
101
102	let args = Args::parse();
103	let graph = BvGraph::with_basename(&args.basename).load()?;
104
105	// create the offsets file while we re-encode the graph so we avoid
106	// having to scan the graph afterwards. We can't do an Elias–Fano yet
107	// because we don't know the length of the final graph.
108	let offsets_path = args.dst.with_extension(OFFSETS_EXTENSION);
109	let mut offsets_writer = buf_bit_writer::from_path::<BE, usize>(&offsets_path)
110	.with_context(\|\| format!("Could not create {}", offsets_path.display()))?;
111
112	// create a bitstream writer for the target graph
113	let target_graph_path = args.dst.with_extension(GRAPH_EXTENSION);
114	let writer = buf_bit_writer::from_path::<LE, usize>(&target_graph_path)
115	.with_context(\|\| format!("Could not create {}", target_graph_path.display()))?;
116	let encoder = CustomEncoder::new(writer);
117
118	let mut pl = ProgressLogger::default();
119	pl.display_memory(true)
120	.item_name("node")
121	.expected_updates(Some(graph.num_nodes()));
122	pl.start("Re-encoding...");
123
124	// wrap the offset degrees iterator, which reads every code but doesn't
125	// resolve references, so it's much faster if we only need to scan the codes
126	let mut iter = graph
127	.offset_deg_iter()
128	.map_decoder(move \|decoder\| Converter {
129	decoder,
130	encoder,
131	offset: 0,
132	});
133	// consume the graph iterator reading all codes and writing them to the encoder
134	// through [`Converter`]
135	let mut offset = 0;
136	for _ in 0..graph.num_nodes() {
137	// write the offset to the offsets file
138	let new_offset = iter.get_decoder().offset;
139	offsets_writer
140	.write_gamma((new_offset - offset) as u64)
141	.context("Could not write gamma")?;
142	offset = new_offset;
143
144	iter.next_degree()?; // read to next node
145	pl.light_update();
146	}
147	// write the last offset
148	let new_offset = iter.get_decoder().offset;
149	offsets_writer
150	.write_gamma((new_offset - offset) as u64)
151	.context("Could not write gamma")?;
152	pl.light_update();
153	pl.done();
154
155	log::info!(
156	"Done re-encoding, the graph is {} bits ({} bytes) long.",
157	iter.get_decoder().offset,
158	iter.get_decoder().offset.div_ceil(8),
159	);
160	log::info!(
161	"Now you should build elias-fano with `cargo run --release build ef '{}' {}`",
162	args.dst.display(),
163	graph.num_nodes()
164	);
165	log::info!(
166	"Then you can run a BFS on it using `cargo run --release --example custom_codes_bfs '{}' {} {}`",
167	args.dst.display(),
168	graph.num_nodes(),
169	graph.num_arcs(),
170	);
171
172	Ok(())
173	}

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