1 unstable release
new 0.1.0 | Apr 4, 2025 |
---|
#48 in #incremental
Used in 2 crates
46KB
932 lines
icentral-alg
Overview
icentral-alg
is a Rust crate designed to perform experiments on various graph algorithms, with a primary focus on Betweenness Centrality. This crate provides an implementation for incremental and parallelized algorithms for computing betweenness centrality, including Brandes' algorithm, QUBE, and other experimental techniques for incremental centrality calculation.
The crate also supports distributed computing through MPI, enabling the scaling of experiments across multiple processes.
Key Features
- Incremental Betweenness Centrality: Compute changes in betweenness centrality after edge insertions or deletions.
- Parallel Execution: Scale the computation across multiple threads or processes using MPI.
- Support for Multiple Graph Algorithms: Includes algorithms like Brandes', QUBE, and FUAD.
- Extensible Graph Structures: Works with various graph structures that implement a set of required traits.
Installation
To include icentral-alg
in your project, add the following to your Cargo.toml
:
[dependencies]
icentral-alg = "0.1"
Example Usage
Running Betweenness Centrality Experiments
use icentral_alg::do_paper_exp;
use std::time::Duration;
fn main() -> Result<(), icentral_alg::BetweennessCentralityError> {
let num_edges = 100;
let num_iter = Some(10);
let max_time = Duration::from_secs(3600);
let rand_seed = 42;
let graph_paths = vec![
String::from("/path/to/graph1.net"),
String::from("/path/to/graph2.net"),
];
do_paper_exp::<MyGraphHash>(
num_edges,
num_iter,
max_time,
rand_seed,
graph_paths,
true, // do_inc_brandes
true, // do_qube
false, // do_inc_qube
false // do_fuad
)?;
Ok(())
}
Required Traits for Graphs
To use your own graph structures with icentral-alg
, they must implement the following traits:
BccGraphHashInterface
FindConnectedComponents
FindSingleSourceShortestPaths
InsertNode
,InsertEdgeUpdateMuc
MappedNodes
ExtendWith
ResetWith
Debug
,DebugIterationStep
Functionality
do_paper_exp
The do_paper_exp
function is the central experiment execution function. It allows running different algorithms with incremental updates on graphs and benchmarking their performance under different conditions.
pub fn do_paper_exp<GH>(
num_edges: usize,
num_iter: Option<usize>,
max_time: Duration,
rand_seed: i32,
path_vec: Vec<String>,
do_inc_brandes: bool,
do_qube: bool,
do_inc_qube: bool,
do_fuad: bool
) -> Result<(), BetweennessCentralityError>
where
GH: BccGraphHashInterface + GraphOperations,
Graph<GH>: GraphStructure,
{
// Experiment logic here
}
MPI Support
For distributed computing, the crate supports MPI-based parallelization via icentral_parallel
. This feature allows running betweenness centrality computations across multiple processes in a distributed manner.
Additional Functions
maybe_do_paper_exp_inc_brandes
: Executes incremental Brandes algorithm.maybe_do_paper_exp_inc_qube
: Executes incremental QUBE algorithm.icentral
: Handles incremental betweenness centrality computations with serial and parallel options.
License
This project is licensed under the MIT License.
This crate is in the process of being translated from c++ to rust. Currently, it still needs exhaustive testing. It is likely there currently exist many glitches which need to be fixed before proper usage. This crate is based on the original icentral program developed by Fuad Jamor. Please see the following repository for details: https://github.com/fjamour/icentral.
For progress updates, see the workspacer rust project.
Dependencies
~16–26MB
~396K SLoC