1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
//! # BitDag
//!
//! A fast, memory-efficient Directed Acyclic Graph (DAG) representation utilizing bit matrices.
//!
//! This crate computes the transitive closure of a graph upon construction, translating the
//! hierarchy into a dense bit matrix. This architecture provides O(1) time complexity for
//! immediate ancestry or descendant checks, and allows bulk relationship queries (like finding
//! common descendants) to be highly parallelized using bitwise operations.
//!
//! Included in this crate are the core [`bitdag::BitDag`] structure, fundamental elements like
//! [`edge::Edge`], and standard traits such as [`traits::ToEdges`] to facilitate parsing
//! industry-standard formats into a digestible graph structure.
//!
//! ## Feature Flags
//!
//! This crate provides several optional features to tailor functionality and manage dependencies:
//!
//! * **`serde`** — Implements standard serialization and deserialization traits for core structures.
//! * **`miniserde`** — Implements lightweight serialization traits via `miniserde` for minimal binary overhead.
//! * **`obo`** — Enables the OBO format adapter, unlocking the `adapters::obo` module (requires `fastobo`).
//! * **`json_ontology`** — Enables the JSON ontology adapter, unlocking the `adapters::json` module (requires `ontolius`).
//! ## Examples
//!
//! ```rust
//! use bitdag::bitdag::BitDag;
//! use bitdag::edge::Edge;
//!
//! 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"]
//! }
//! ```
//! If you are working with external ontologies, you can use the built-in adapters (ensure you have the correct feature
//! flags enabled).
//!
//! ```rust
//! // Requires the `json_ontology` feature
//! use ontolius::io::OntologyLoaderBuilder;
//! use ontolius::ontology::csr::FullCsrOntology;
//! use bitdag::traits::ToEdges;
//! use bitdag::bitdag::BitDag;
//! use std::path::PathBuf;
//! use std::str::FromStr;
//!
//! let loader = OntologyLoaderBuilder::new().obographs_parser().build();
//! let manifest_dir = PathBuf::from_str(env!("CARGO_MANIFEST_DIR")).unwrap();
//! let test_ontology = manifest_dir.join("tests/assets/mini_hp_2025-09-01.json");
//! let ontology: FullCsrOntology = loader.load_from_path(test_ontology).unwrap();
//!
//! // Convert directly into a BitDag starting from a root node
//! let dag = BitDag::from_graph(&ontology, "ROOT:0000000").unwrap();
//! ```
/// A specialized `Result` type for `BitDag` operations.
///
/// This alias is used throughout the crate to standardize error handling, particularly
/// for failed graph traversals and unknown identifier lookups.
pub type Result<T> = Result;
pub use BitDag;
pub use Edge;
pub use BitDagError;
pub use *;