graph-canon

使用 nauty C 库和基于 petgraph 构建的超级快速且基本的图标准化。

用法

可哈希标签

如果您只想创建一个可哈希的对象以确定同构性，则可以使用 CanonLabeling 结构体。

这可以直接从一个 Graph 对象创建。

有向图

use petgraph::{Directed, Graph};
use graph_canon::CanonLabeling;

let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
let e3 = vec![(1, 0), (1, 2), (2, 1)]; // Non-Isomorphic

let g1 = Graph::<(), (), Directed>::from_edges(&e1);
let g2 = Graph::<(), (), Directed>::from_edges(&e2);
let g3 = Graph::<(), (), Directed>::from_edges(&e3);

let l1 = CanonLabeling::new(&g1);
let l2 = CanonLabeling::new(&g2);
let l3 = CanonLabeling::new(&g3);

assert_eq!(l1, l2);
assert_ne!(l1, l3);

无向图

use petgraph::{Undirected, Graph};
use graph_canon::CanonLabeling;

let e1 = vec![(0, 1), (0, 2), (1, 2)]; // Isomorphic
let e2 = vec![(1, 0), (1, 2), (0, 2)]; // Isomorphic
let e3 = vec![(1, 0), (1, 2)];         // Non-Isomorphic

let g1 = Graph::<(), (), Undirected>::from_edges(&e1);
let g2 = Graph::<(), (), Undirected>::from_edges(&e2);
let g3 = Graph::<(), (), Undirected>::from_edges(&e3);

let l1 = CanonLabeling::new(&g1);
let l2 = CanonLabeling::new(&g2);
let l3 = CanonLabeling::new(&g3);

assert_eq!(l1, l2);
assert_ne!(l1, l3);

恢复标准化的 Graph

如果您对处理图本身感兴趣，可以使用 canonize 函数返回一个新的 Graph 对象

use petgraph::{Directed, Graph};
use graph_canon::canonize;

let edges = vec![(0, 1), (0, 2), (1, 2)];
let graph = Graph::<(), (), Directed>::from_edges(&edges);
let canon = canonize(&graph);
assert_eq!(canon.edge_count(), 3);

性能比较

该软件包受 nauty-pet 启发，但速度更快，因为它更简单。（使用 criterion 进行测试）

此测试使用随机生成的具有 10 个节点和 0.5 边连接概率的图，使用 random_gpn_graph

graph-canon             time:   [1.3272 µs 1.3276 µs 1.3285 µs]
Found 14 outliers among 100 measurements (14.00%)
  3 (3.00%) high mild
  11 (11.00%) high severe

nauty-pet               time:   [6.2591 µs 6.2738 µs 6.2956 µs]
Found 10 outliers among 100 measurements (10.00%)
  2 (2.00%) low mild
  4 (4.00%) high mild
  4 (4.00%) high severe