#graph #optimization #speedup #betweenness #minimumunioncycle #calculations

icentral-speedup-calculation

Rust library for efficient graph traversal and speedup calculations using Betweenness Centrality and MUC detection techniques

1 unstable release

new 0.1.0 Apr 4, 2025

#12 in #betweenness


Used in 2 crates

MIT/Apache

19KB
164 lines

iCentral Speedup Calculation

icentral-speedup-calculation is a Rust library designed to perform precise and efficient calculations of ideal speedup in graph-related operations. It leverages sophisticated graph-theoretic concepts, focusing on Betweenness Centrality and Minimum Union Cycle (MUC) detection to optimize algorithmic performance.

Features

  • fuad_ideal_speedup: Computes the ideal speedup of graph traversal operations based on node and edge metrics using the Fuad Ideal Speedup model.
  • time_find_mucs: Benchmarking utility that measures the time elapsed to find Minimum Union Cycles in a graph structure.
  • generate_random_edges: Random edge insertion for graphs, enabling extensive simulation-based performance testing.
  • qube_ideal_speedup_step: Performs a stepwise computation of speedup by assessing real vs ideal scenarios in graph manipulations.
  • qube_ideal_speedup: Integrated function for processing graph structures with ideal speedup evaluations and statistics.

Concepts

This library primarily focuses on graph optimizations:

  • Betweenness Centrality: A measure of a vertex's importance based on its ability to act as a bridge across different parts of the graph.
  • Minimum Union Cycles (MUCs): Utilized in evaluating graph efficient traversals and manipulation scenarios.

Mathematical Background

Optimal speedup computation involves comparisons between complete and partial graph structures, optimizing the node and edge ratio to ascertain efficiency improvements. This is crucial for speeding up computations in dense graphs or networks.

Usage

Add the following to your Cargo.toml:

[dependencies]
icentral-speedup-calculation = "0.1.0"

Use in your Rust code as follows:

use icentral_speedup_calculation::{fuad_ideal_speedup, ...};

fn main() {
    let speedup = fuad_ideal_speedup(0.5, 30.0, 20.0, 40.0, 50.0, 1.5);
    println!("Ideal Speedup: {:?}", speedup);
}

This README.md file was generated by an AI model and may not be 100% accurate. However, it should be pretty good.

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

~17–27MB
~400K SLoC