BitDag

A fast, memory-efficient Directed Acyclic Graph (DAG) representation in Rust, optimized for lightning-fast relationship queries using dense bit matrices.

By computing the transitive closure of the graph upon construction, BitDag achieves $O(1)$ time complexity for immediate ancestry or descendant checks. For bulk operations—such as finding common descendants or extracting leaf nodes—it leverages rayon to perform highly parallelized bitwise operations across the matrix.

---

Key Features

• $O(1)$ Relationship Checks: Instant is_ancestor_of and is_descendant_of lookups.
• Parallelized Bulk Queries: Uses rayon to execute bitwise AND/OR operations across rows and columns for rapid descendant/ancestor extraction.
• Profile Minimization: Easily filter out redundant ancestor terms from a profile, leaving only the most specific ( deepest) nodes.
• Format Adapters: Built-in support for parsing standard ontology formats (OBO and JSON) directly into a bit matrix.
• Flexible Serialization: Optional support for both serde and miniserde.

---

Feature Flags

This crate is highly modular. You can opt-in to specific dependencies to keep your binary size and compilation times as low as possible.

• serde — Implements standard serialization and deserialization for core structures.
• miniserde — Implements lightweight serialization for minimal binary overhead.
• obo — Enables the OBO format adapter to ingest .obo files (requires fastobo).
• json_ontology — Enables the JSON ontology adapter to ingest JSON-formatted ontologies (requires ontolius).

---

Quick Start

Here is a basic example of building a BitDag from a raw list of edges and querying relationships. use bitdag::edge::Edge; use bitdag::bitdag::BitDag;

fn main() {
    // 1. Define your edges (Parent -> Child)
    let edges: Vec<Edge> = vec![
        ("A", "B").into(),
        ("B", "C").into(),
        ("C", "D").into(),
        ("C", "F").into(),
    ];

    // 2. Build the BitDag (computes transitive closure automatically)
    let dag = BitDag::from_edges(&edges);

    // 3. Perform O(1) checks
    assert_eq!(dag.is_ancestor_of("A", "D").unwrap(), true);
    assert_eq!(dag.is_descendant_of("A", "C").unwrap(), false);

    // 4. Extract generations or sub-graphs
    let descendants = dag.get_descendants("A").unwrap();
    println!("Descendants of A: {:?}", descendants); // ["B", "C", "D", "F"]

    let leaves = dag.get_leaves();
    println!("Leaves in the graph: {:?}", leaves); // ["D", "F"]

}

Using Format Adapters

If you are working with external ontologies, you can use the built-in adapters (ensure you have the correct feature flags enabled).

fn main() {
    // Requires the `json_ontology` feature
    use ontolius::io::OntologyLoaderBuilder;
    use ontolius::ontology::csr::FullCsrOntology;
    use bitdag::traits::ToEdges;
    use bitdag::bitdag::BitDag;

    let loader = OntologyLoaderBuilder::new().obographs_parser().build();
    let ontology: FullCsrOntology = loader.load_from_path("path/to/ontology.json").unwrap();

    // Convert directly into a BitDag starting from a root node
    let dag = BitDag::from_graph(&ontology, "ROOT:0000000").unwrap();
}