堆叠线性代数图

使用稀疏线性代数嵌入内存的图。

功能

架构

堆叠线性代数图实现了一个带权重的有向图，每个顶点和边都有一个权重。图将顶点和邻接矩阵分别建模为 GraphBLAS 稀疏矢量和矩阵。图使用 GraphBLAS 操作符对其顶点矢量和邻接矩阵进行操作。

索引

图为每个新顶点、顶点矢量和邻接矩阵分配一个无符号整数索引。在索引被删除后，图可能会重复使用索引。

数值顶点索引在所有顶点矢量和邻接矩阵中引用相同的坐标。因此，所有顶点矢量和邻接矩阵都具有兼容的大小。

每个顶点矢量和邻接矩阵的组合定义了一个独立的图。所有图共享相同的坐标。

随着新顶点的添加，图自动扩展顶点矢量和邻接矩阵的大小。图无法减小它们的大小。

数据类型

图在顶点和边中存储以下 Rust 原始数值类型：bool; i8; i16; i32; i64; u8; u16; u32; u64; f32; f64; isize; usize

类型转换

每个顶点矢量和邻接矩阵具有单一的数据数据类型。数据类型是在将顶点矢量和邻接矩阵添加到图中时设置的。

涉及不同值类型的操作将根据 ANSI C 进行类型转换，但有以下例外

• +-Inf 或超出其最大范围的整数值将被截断
• NaN 转换为零

线性代数操作

图操作应用于任何适用的顶点矢量和邻接矩阵组合。

事务

图不实现 ACID 数据库事务。

持久性

图位于内存中，不存在于持久存储中。

最小示例

use graphblas_sparse_linear_algebra::operators::binary_operator::{Assignment, Plus};
use graphblas_sparse_linear_algebra::operators::index_unary_operator::IsValueEqualTo;
use graphblas_sparse_linear_algebra::operators::options::OperatorOptions;
use graphblas_sparse_linear_algebra::operators::semiring::PlusTimes;

use stacked_linear_algebra_graph::graph::edge::{DirectedEdgeCoordinate, WeightedDirectedEdge};
use stacked_linear_algebra_graph::graph::graph::Graph;
use stacked_linear_algebra_graph::graph::indexing::{VertexIndex, VertexTypeIndex};
use stacked_linear_algebra_graph::operators::add::{AddEdge, AddEdgeType, AddVertex, AddVertexType};
use stacked_linear_algebra_graph::operators::apply_operator::ApplyIndexUnaryOperatorToVertexVector;
use stacked_linear_algebra_graph::operators::element_wise_multiplication::BinaryOperatorElementWiseVertexVectorMultiplication;
use stacked_linear_algebra_graph::operators::multiplication::VertexVectorAdjacencyMatrixMultiplication;
use stacked_linear_algebra_graph::operators::options::OptionsForOperatorWithAdjacencyMatrixAsRightArgument;
use stacked_linear_algebra_graph::operators::read::GetVertexValue;

fn main() {
    let mut graph = Graph::with_initial_capacity(&5, &5, &5).unwrap();

    let numbers_vertex_type_index: VertexTypeIndex =
        AddVertexType::<i32>::apply(&mut graph).unwrap();
    let odd_number_sequence_edge_type_index = AddEdgeType::<i32>::apply(&mut graph).unwrap();

    // Add vertices
    let mut vertex_indices: Vec<VertexIndex> = Vec::new();
    for n in 0..12 {
        vertex_indices.push(
            graph
                .add_vertex(&numbers_vertex_type_index, n as u8)
                .unwrap(),
        );
    }

    // Define a sequence of subsequent odd numbers
    for i in [1, 3, 5, 7, 9] {
        let edge = WeightedDirectedEdge::new(
            DirectedEdgeCoordinate::new(
                odd_number_sequence_edge_type_index,
                vertex_indices[i],
                vertex_indices[i + 2],
            ),
            true,
        );

        graph.add_or_replace_edge_from_edge(edge).unwrap();
    }

    // Find the fourth number in the sequence, starting at 1
    let selected_vertices_index: VertexTypeIndex = AddVertexType::<i32>::apply(&mut graph).unwrap();

    ApplyIndexUnaryOperatorToVertexVector::<u8>::apply(
        &mut graph,
        &numbers_vertex_type_index,
        &IsValueEqualTo::<u8>::new(),
        &1,
        &Assignment::new(),
        &selected_vertices_index,
        None,
        &OperatorOptions::new_default(),
    )
    .unwrap();

    for _i in 0..2 {
        VertexVectorAdjacencyMatrixMultiplication::<u8>::by_index(
            &mut graph,
            &selected_vertices_index,
            &PlusTimes::<u8>::new(),
            &odd_number_sequence_edge_type_index,
            &Assignment::new(),
            &selected_vertices_index,
            None,
            &&OptionsForOperatorWithAdjacencyMatrixAsRightArgument::new_default(),
        )
        .unwrap();
    }

    BinaryOperatorElementWiseVertexVectorMultiplication::<u8>::apply(
        &mut graph,
        &selected_vertices_index,
        &Plus::<u8>::new(),
        &numbers_vertex_type_index,
        &Assignment::new(),
        &selected_vertices_index,
        None,
        &OperatorOptions::new_default(),
    )
    .unwrap();

    assert_eq!(
        GetVertexValue::<u8>::vertex_value(&graph, &numbers_vertex_type_index, &vertex_indices[7])
            .unwrap(),
        Some(7u8)
    )
}

要求

请确保满足构建 graphblas_sparse_linear_algebra 的要求。

贡献

太棒了，欢迎贡献。stacked_linear_algebra_graph 和您的贡献将来可能被重新许可并集成到商业软件中。因此，当您发起拉取请求时，将被要求同意贡献者许可协议。

许可

stacked_linear_algebra_graph 在Creative Commons Attribution Non Commercial 4.0 国际下许可。如需其他许可选项，请联系Sam Dekker。

致谢

Stacked Linear Algebra Graph 受LAGraph的启发，并使用了来自Timothy A. Davis的相同底层GraphBLAS实现。