Struct CompressedGraph

pub struct CompressedGraph { /* private fields */ }

An efficient representation of a network graph. Graphs are stored as a sparse edge list using a HashMap of HashMaps that maps a column to a row and then a row to an entry. Each entry is a u64 that encodes all the edges for an 8x8 block of the graph’s adjacency matrix.

When a CompressedGraph is constructed from a graphrox::Graph, it is normally approximated. Only clusters of edges in the original adjacency matrix are represented in the CompressedGraph, hence a CompressedGraph tracks a compression_level that indicates the threshold applied to the average pooling of the original matrix. The compression_level is divided by 64 to obtain the threshold. Thus, compression_level is equal to the number of entries in an 8x8 block of the adjacency matrix that must be ones in order for the block to be losslessly encoded in the CompressedGraph. A CompressedGraph is not necessarily approximated, though, because the compression_level may be one. compression_level will be clamped to a number between 1 and 64 inclusive.

Normally, a CompressedGraph is constructed by calling compress() on a graphrox::Graph, but they can also be constructed manually using a graphrox::builder::CompressedGraphBuilder. A CompressedGraph is immutable, but can be decompressed into a mutable graphrox::Graph.

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]));
// ... more vertices ...

let compressed_graph = graph.compress(3);

assert_eq!(compressed_graph.compression_level(), 3);
assert!(compressed_graph.does_edge_exist(0, 1));
assert!(compressed_graph.does_edge_exist(0, 2));
// ...

Implementations

impl CompressedGraph

pub fn decompress(&self) -> StandardGraph

Decompresses a CompressedGraph into a graphrox::Graph.

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]));
// ... more vertices ...

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

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

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

pub fn compression_level(&self) -> u8

Returns the compression level that was applied to the average pooling of the original graph’s adjacency matrix to create the CompressedGraph.

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]));
// ... more vertices ...

let compressed_graph = graph.compress(42);

assert_eq!(compressed_graph.compression_level(), 42);

pub fn get_compressed_matrix_entry(&self, col: u64, row: u64) -> u64

Returns an entry in the matrix that is used to store a CompressedGraph. The entries are u64s that represent 8x8 blocks in an uncompressed matrix.

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);
    }
}

let compressed_graph = graph.compress(2);

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

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

Trait Implementations

impl Clone for CompressedGraph

fn clone(&self) -> CompressedGraph

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for CompressedGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl GraphRepresentation for CompressedGraph

fn is_undirected(&self) -> bool

Returns true if the graph is undirected and false if the graph is directed.

fn vertex_count(&self) -> u64

Returns a count of the vertices in the graph. This is also the dimension of the adjacency matrix that represents the graph.

fn edge_count(&self) -> u64

Returns a count of the edges between vertices in the graph.

fn matrix_string(&self) -> String

Returns a string representation of a graph’s adjacency matrix.

fn does_edge_exist(&self, from_vertex_id: u64, to_vertex_id: u64) -> bool

Returns true if the specified edge exists in the graph.

fn to_bytes(&self) -> Vec<u8>

Converts the graph to a vector of big-endian bytes that can be easily saved to and subsequently loaded from a file.

impl Into<Vec<u8>> for CompressedGraph

fn into(self) -> Vec<u8>

Converts this type into the (usually inferred) input type.

impl TryFrom<&[u8]> for CompressedGraph

type Error = GraphRoxError

The type returned in the event of a conversion error.

fn try_from(bytes: &[u8]) -> Result<Self, Self::Error>

Performs the conversion.