GraphRox

GraphRox 是一个用于高效生成图近似的网络图库。GraphRox 还提供了一个高保真、有损的图形压缩算法。

使用库

Rust

要在 Rust 中使用此库，请在 [dependencies] 的 Cargo.toml 中添加它。

[dependencies]
graphrox = "1.1"

工作原理

近似

近似算法通过对图的邻接矩阵应用平均池化来构建图的近似。该近似将具有比原始图更低的维度。邻接矩阵将被分成指定维度的块，然后对每个分区内的矩阵条目进行平均池化。将应用一个给定的阈值到平均池化条目上，使得每个大于或等于阈值的条目在结果近似的图的邻接矩阵中变为 1。低于阈值的平均池化条目将变为结果近似图中为零。如果需要平均池化的块不适合邻接矩阵，图的邻接矩阵将用零填充。

图形压缩

使用上述提到的相同近似技术，将阈值应用于图的邻接矩阵中的 8x8 块。如果矩阵中的给定块满足阈值，则整个块将以无损失的方式编码为一个无符号 64 位整数。如果块不满足阈值，则整个块将在结果矩阵中表示为 0。由于 GraphRox 将矩阵存储为邻接表，因此 0 条目对存储大小没有影响。

0.0 的阈值基本上是一种无损压缩。

GraphRox 教程

图形基础

结构体 graphrox::Graph 是一个基本的无权图结构，而特质 graphrox::GraphRepresentation 定义了一些基本图操作的方法。可以给图添加或删除边和顶点。图中的每个顶点都有一个ID，从0开始索引。如果从一个ID为3的顶点创建到ID为5的顶点的边，则会隐式创建ID为0、1、2和4的顶点。

use graphrox::{Graph, GraphRepresentation};

let mut graph = Graph::new_directed();
graph.add_edge(3, 5);

// Vertices 0 through 5 have been defined
assert_eq!(graph.vertex_count(), 6);
assert!(graph.does_edge_exist(3, 5));

let edges_to_2 = [4, 0, 5, 1];
graph.add_vertex(2, Some(&edges_to_2));

assert_eq!(graph.edge_count(), 5);

// Add a vertex with ID 8 and no edges. This implicitly defines all vertices IDs less
// than 8
graph.add_vertex(8, None);

assert_eq!(graph.vertex_count(), 9);
assert_eq!(graph.edge_count(), 5);

// Edges can be removed
graph.delete_edge(2, 5);

assert_eq!(graph.edge_count(), 4);
assert!(!graph.does_edge_exist(2, 5));

图近似

可以将图近似为一个具有更低维度的 graphrox::Graph。这是通过在图的邻接矩阵表示中平均池化给定维度的块来实现的，然后对平均池化的矩阵应用阈值，以确定结果图的邻接矩阵中哪些条目将设置为1而不是0。

use graphrox::{Graph, GraphRepresentation};

let mut graph = Graph::new_directed();

graph.add_vertex(0, Some(&[1, 2, 6]));
graph.add_vertex(1, Some(&[1, 2]));
graph.add_vertex(2, Some(&[0, 1]));
graph.add_vertex(3, Some(&[1, 2, 4]));
graph.add_vertex(5, Some(&[6, 7]));
graph.add_vertex(6, Some(&[6]));
graph.add_vertex(7, Some(&[6]));

// Average pool 2x2 blocks in the graph's adjacency matrix, then apply a threshold of 0.5,
// or 50%. Any blocks with at least 50% of their entries being 1 (rather than 0) will be
// represented with a 1 in the adjacency matrix of the resulting graph.
let approx_graph = graph.approximate(2, 0.5);

println!("{}", graph.matrix_representation_string());
println!();
println!("{}", approx_graph.matrix_representation_string());

/* Ouput:

[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 1, 1, 1, 1, 0, 0, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 0, 1, 1, 1 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]

[ 1, 1, 0, 0 ]
[ 1, 0, 0, 0 ]
[ 0, 0, 0, 0 ]
[ 0, 0, 1, 1 ]

*/

此外，可以在不应用阈值的情况下对图进行平均池化

use graphrox::{Graph, GraphRepresentation};

let mut graph = Graph::new_directed();

graph.add_vertex(0, Some(&[1, 2, 6]));
graph.add_vertex(1, Some(&[1, 2]));
graph.add_vertex(2, Some(&[0, 1]));
graph.add_vertex(3, Some(&[1, 2, 4]));
graph.add_vertex(5, Some(&[6, 7]));
graph.add_vertex(6, Some(&[6]));
graph.add_vertex(7, Some(&[6]));

let avg_pool_matrix = graph.find_avg_pool_matrix(2);

println!("{}", graph.matrix_representation_string());
println!();
println!("{}", avg_pool_matrix.to_string());

/* Ouput:

[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 1, 1, 1, 1, 0, 0, 0, 0 ]
[ 1, 1, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 0 ]
[ 1, 0, 0, 0, 0, 1, 1, 1 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]

[ 0.50, 0.75, 0.00, 0.00 ]
[ 0.50, 0.25, 0.00, 0.00 ]
[ 0.00, 0.25, 0.00, 0.00 ]
[ 0.25, 0.00, 0.50, 0.50 ]

*/

图形压缩

可以将图压缩成一个空间效率高的形式。使用上面提到的相同近似技术，可以将阈值应用于图的邻接矩阵中的8x8块。如果矩阵中的给定块满足阈值，则整个块将以无损失的方式编码在一个无符号64位整数中。如果不满足阈值，则整个块将在结果矩阵中以0表示。因为GraphRox将矩阵存储为邻接表，所以0条目对存储大小没有影响。

0.0 的阈值基本上是一种无损压缩。

use graphrox::{Graph, GraphRepresentation};

let mut graph = Graph::new_directed();
graph.add_vertex(23, None);

for i in 8..16 {
    for j in 8..16 {
        graph.add_edge(i, j);
    }
}

for i in 0..8 {
    for j in 0..4 {
        graph.add_edge(i, j);
    }
}

graph.add_edge(22, 18);
graph.add_edge(15, 18);

let compressed_graph = graph.compress(0.2);

assert_eq!(compressed_graph.vertex_count(), 24);
assert_eq!(compressed_graph.edge_count(), 96); // 64 + 32

// Because half of the 8x8 block was filled, half of the bits in the u64 are ones.
assert_eq!(compressed_graph.get_adjacency_matrix_entry(0, 0),0x00000000ffffffffu64);

// Because the entire 8x8 block was filled, the block is represented with u64::MAX
assert_eq!(compressed_graph.get_adjacency_matrix_entry(1, 1), u64::MAX);

压缩图会产生一个 graphrox::CompressedGraph。可以轻松地将压缩图解压缩回 graphrox::Graph

use graphrox::{Graph, GraphRepresentation};

let mut graph = Graph::new_undirected();

graph.add_vertex(0, Some(&[1, 2, 6]));
graph.add_vertex(3, Some(&[1, 2]));

let compressed_graph = graph.compress(0.1);
let decompressed_graph = compressed_graph.decompress();

assert_eq!(graph.edge_count(), decompressed_graph.edge_count());
assert_eq!(graph.vertex_count(), decompressed_graph.vertex_count());

for (from_vertex, to_vertex) in &decompressed_graph {
    assert!(graph.does_edge_exist(from_vertex, to_vertex));
}

将图保存到磁盘

GraphRox为 graphrox::Graph 和 graphrox::CompressedGraph 提供了 to_bytes() 和 try_from::<&[u8]>() 方法，这些方法将图转换为大端字节阵列的有效表示形式。字节阵列非常适合保存到磁盘或通过websocket发送。

use graphrox::{CompressedGraph, Graph, GraphRepresentation};
use std::fs;

let mut graph = Graph::new_undirected();

graph.add_vertex(0, Some(&[1, 2, 6]));
graph.add_vertex(3, Some(&[1, 2]));

// Convert the graph to bytes
let graph_bytes = graph.to_bytes();

// Save the bytes to a file
fs::write("my-graph.gphrx", graph_bytes).unwrap();

// Read the bytes from a file (then delete the file)
let graph_file = fs::read("my-graph.gphrx").unwrap();
fs::remove_file("my-graph.gphrx").unwrap();

let graph_from_bytes = Graph::try_from(graph_file.as_slice()).unwrap();

assert_eq!(graph.edge_count(), graph_from_bytes.edge_count());

for (from_vertex, to_vertex) in &graph_from_bytes {
    assert!(graph.does_edge_exist(from_vertex, to_vertex));
}

// Compressed graphs can be converted to bytes as well
let compressed_graph = graph.compress(0.05);
fs::write("compressed-graph.cgphrx", compressed_graph.to_bytes()).unwrap();

// Read the compressed_graph from a file (then delete the file)
let compressed_graph_file = fs::read("compressed-graph.cgphrx").unwrap();
fs::remove_file("compressed-graph.cgphrx").unwrap();

let compressed_graph_from_bytes =
    CompressedGraph::try_from(compressed_graph_file.as_slice()).unwrap();

assert_eq!(compressed_graph_from_bytes.edge_count(), compressed_graph.edge_count());