GraphRox is a network graph library for efficiently generating approximations of graphs. GraphRox additionally provides a high-fidelity, lossy graph compression algorithm.
To use the library in Rust, add it to [dependencies] in Cargo.toml.
toml
[dependencies]
graphrox = "1.0"
GraphRox is available on PyPi, so you can install the package with:
sh
pip3 install graphrox
And then you can import it:
python
import graphrox as gx
After downloading and building GraphRox from source (with cargo build --release), a static library and a dynamic link library will each be produced in the target/release directory. C code can link to the GraphRox library statically using the compile library and the gphrx.h header from the graphrox-c directory, or dynamically using the DLL.
The approximation algorithm applies average pooling to a graph's adjacency matrix to construct an approximation of the graph. The approximation will have a lower dimensionality than the original graph. The adjacency matrix will be partitioned into blocks of a specified of dimension and then the matrix entries within each partition will be average pooled. A given threshold will be applied to the average pooled entries such that each entry that is greater than or equal to the threshold will become a 1 in the adjacency matrix of the resulting approximate graph. Average pooled entries that are lower than the threshold will become zeros in the resulting approximate graph. The graph's adjacency matrix will be padded with zeros if a block to be average pooled does not fit withing the adjacency matrix.
Using the same approximation technique mentioned above, a threshold is applied to 8x8 blocks in a graph's adjacency matrix. If a given block in the matrix meets the threshold, the entire block will be losslessly encoded in an unsigned 64-bit integer. If the block does not meet the threshold, the entire block will be represented by a 0 in the resulting matrix. Because GraphRox stores matrices as adjacency lists, 0 entries have no effect on storage size.
A threshold of 0.0 is essentially a lossless compression.
The graphrox::Graph struct is a basic, unweighted graph structure and the
graphrox::GraphRepresentation trait defines some methods for some basic graph operations.
Edges and vertices can be added to or removed from a graph. Each vertex in a graph has an
ID, indexed from zero. If an edge is created from the vertex with ID 3 to the vertex with
ID 5, vertices with IDs 0, 1, 2, and 4 are created implicitly.
```rust use graphrox::{Graph, GraphRepresentation};
let mut graph = Graph::newdirected(); graph.addedge(3, 5);
// Vertices 0 through 5 have been defined asserteq!(graph.vertexcount(), 6); assert!(graph.doesedgeexist(3, 5));
let edgesto2 = [4, 0, 5, 1]; graph.addvertex(2, Some(&edgesto_2));
asserteq!(graph.edgecount(), 5);
// Add a vertex with ID 8 and no edges. This implicitly defines all vertices IDs less // than 8 graph.add_vertex(8, None);
asserteq!(graph.vertexcount(), 9); asserteq!(graph.edgecount(), 5);
// Edges can be removed graph.delete_edge(2, 5);
asserteq!(graph.edgecount(), 4); assert!(!graph.doesedgeexist(2, 5)); ```
A graph can be approximated into a graphrox::Graph with a lower dimensionality. This is
done by average pooling blocks of a given dimension in the adjacency matrix representation
of the graph, then applying a threshold to the average pooled matrix to determine which
entries in the adjacency matrix of the resulting graph will be 1 rather than 0.
```rust use graphrox::{Graph, GraphRepresentation};
let mut graph = Graph::new_directed();
graph.addvertex(0, Some(&[1, 2, 6])); graph.addvertex(1, Some(&[1, 2])); graph.addvertex(2, Some(&[0, 1])); graph.addvertex(3, Some(&[1, 2, 4])); graph.addvertex(5, Some(&[6, 7])); graph.addvertex(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.matrixrepresentationstring()); println!(); println!("{}", approxgraph.matrixrepresentation_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 ]
*/ ```
Additionally, a graph can be average pooled without applying a threshold:
```rust use graphrox::{Graph, GraphRepresentation};
let mut graph = Graph::new_directed();
graph.addvertex(0, Some(&[1, 2, 6])); graph.addvertex(1, Some(&[1, 2])); graph.addvertex(2, Some(&[0, 1])); graph.addvertex(3, Some(&[1, 2, 4])); graph.addvertex(5, Some(&[6, 7])); graph.addvertex(6, Some(&[6])); graph.add_vertex(7, Some(&[6]));
let avgpoolmatrix = graph.findavgpool_matrix(2);
println!("{}", graph.matrixrepresentationstring()); println!(); println!("{}", avgpoolmatrix.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 ]
*/ ```
Graphs can be compressed into a space-efficient form. Using the same approximation technique mentioned above, a threshold can be applied to 8x8 blocks in a graph's adjacency matrix. If a given block in the matrix meets the threshold, the entire block will be losslessly encoded in an unsigned 64-bit integer. If the block does not meet the threshold, the entire block will be represented by a 0 in the resulting matrix. Because GraphRox stores matrices as adjacency lists, 0 entries have no effect on storage size.
A threshold of 0.0 is essentially a lossless compression.
```rust use graphrox::{Graph, GraphRepresentation};
let mut graph = Graph::newdirected(); graph.addvertex(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.addedge(22, 18); graph.addedge(15, 18);
let compressed_graph = graph.compress(0.2);
asserteq!(compressedgraph.vertexcount(), 24); asserteq!(compressedgraph.edgecount(), 96); // 64 + 32
// Because half of the 8x8 block was filled, half of the bits in the u64 are ones. asserteq!(compressedgraph.getadjacencymatrix_entry(0, 0),0x00000000ffffffffu64);
// Because the entire 8x8 block was filled, the block is represented with u64::MAX asserteq!(compressedgraph.getadjacencymatrix_entry(1, 1), u64::MAX); ```
Compressing a graph yields a graphrox::CompressedGraph. CompressedGraphs can be easily
decompressed back into a graphrox::Graph:
```rust use graphrox::{Graph, GraphRepresentation};
let mut graph = Graph::new_undirected();
graph.addvertex(0, Some(&[1, 2, 6])); graph.addvertex(3, Some(&[1, 2]));
let compressedgraph = graph.compress(0.1); let decompressedgraph = compressed_graph.decompress();
asserteq!(graph.edgecount(), decompressedgraph.edgecount()); asserteq!(graph.vertexcount(), decompressedgraph.vertexcount());
for (fromvertex, tovertex) in &decompressedgraph { assert!(graph.doesedgeexist(fromvertex, to_vertex)); } ```
GraphRox provides to_bytes() and try_from::<&[u8]>() methods on graphrox::Graph and
graphrox::CompressedGraph which convert to and from efficient big-endian byte-array
representations of graphs. The byte arrays are perfect for saving to disk or sending over
a websocket.
```rust use graphrox::{CompressedGraph, Graph, GraphRepresentation}; use std::fs;
let mut graph = Graph::new_undirected();
graph.addvertex(0, Some(&[1, 2, 6])); graph.addvertex(3, Some(&[1, 2]));
// Convert the graph to bytes let graphbytes = graph.tobytes();
// 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 graphfile = fs::read("my-graph.gphrx").unwrap(); fs::removefile("my-graph.gphrx").unwrap();
let graphfrombytes = Graph::tryfrom(graphfile.as_slice()).unwrap();
asserteq!(graph.edgecount(), graphfrombytes.edge_count());
for (fromvertex, tovertex) in &graphfrombytes { assert!(graph.doesedgeexist(fromvertex, tovertex)); }
// Compressed graphs can be converted to bytes as well let compressedgraph = graph.compress(0.05); fs::write("compressed-graph.cgphrx", compressedgraph.to_bytes()).unwrap();
// Read the compressedgraph from a file (then delete the file) let compressedgraphfile = fs::read("compressed-graph.cgphrx").unwrap(); fs::removefile("compressed-graph.cgphrx").unwrap();
let compressedgraphfrombytes = CompressedGraph::tryfrom(compressedgraphfile.as_slice()).unwrap();
asserteq!(compressedgraphfrombytes.edgecount(), compressedgraph.edge_count()); ```