Struct graphrox::CompressedGraph
source · pub struct CompressedGraph { /* private fields */ }
Expand description
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§
source§impl CompressedGraph
impl CompressedGraph
sourcepub fn decompress(&self) -> StandardGraph
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));
}
sourcepub fn compression_level(&self) -> u8
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);
sourcepub fn get_compressed_matrix_entry(&self, col: u64, row: u64) -> u64
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 u64
s 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§
source§impl Clone for CompressedGraph
impl Clone for CompressedGraph
source§fn clone(&self) -> CompressedGraph
fn clone(&self) -> CompressedGraph
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more