README.md

grandiso-rust

Ultra-fast implementation of the queue-based GrandIso subgraph isomorphism algorithm, implemented in Rust.

For the original Python implementation, see here.

This implementation relies upon the Rust petgraph library for core graph operations.

Example Usage

use crate::grandiso;
use petgraph::graphmap::DiGraphMap;

// Create a directed triangle motif:
let mut graphmap: DiGraphMap<i8, &str> = DiGraphMap::new();
graphmap.add_edge(0, 1, "3");
graphmap.add_edge(1, 2, "3");
graphmap.add_edge(2, 0, "3");

// Create a directed triangle host graph:
let mut graphmap_host: DiGraphMap<&str, &str> = DiGraphMap::new();
graphmap_host.add_edge("A", "B", "3");
graphmap_host.add_edge("B", "C", "3");
graphmap_host.add_edge("C", "A", "3");

// Perform the search:
let results = grandiso::find_motifs(graphmap.clone(), graphmap_host.clone());

Benchmarks

Legit benchmarks forthcoming, but as a rough ballpark, counting triangles in a complete 200-graph takes ~40s in Python, and 10s in Rust.

All times in mm:ss.

Size (K{n})	Python	Rust
50	<0:00	<0:00.1
100	0:04	<0:01
200	0:40	0:10
400	4:51	1:33