11 releases (7 breaking)
0.8.0 | Aug 26, 2024 |
---|---|
0.7.0 | Nov 21, 2023 |
0.6.1 | Jul 21, 2023 |
0.5.0 | Mar 25, 2023 |
0.1.1 | May 27, 2020 |
#202 in Math
606 downloads per month
Used in 5 crates
(4 directly)
1MB
26K
SLoC
Low-level bindings for nauty and Traces
This crate provides ffi bindings for nauty and Traces. Nauty and Traces are implementations of algorithms for computing graph automorphisms.
Usage
Add the following lines to your Cargo.toml:
[dependencies]
nauty-Traces-sys = "0.8"
By default, you need a C compiler installed on your system. See the Features section for alternatives.
Caveats
-
You can use either the version of nauty and Traces that is bundled with this crate or a local installation. Both options have advantages and disadvantages. See the Features section below. Note that version 0.8 of this crate assumes nauty & Traces version 2.8.9 and may not work with other versions.
-
Some C macros have no direct equivalent.
-
Instead of using
DYNALLSTAT
andDYNALLOC
you can createVec
s or arrays. -
Most
DEFAULT
-type macros have been replaced with implementations of the rustDefault
trait. -
The following macros are implemented as functions:
Original macro Replacement EMPTY_GRAPH
empty_graph
DEFAULTOPTIONS_SPARSEGRAPH
optionsblk::default_sparse()
DEFAULTOPTIONS_DIGRAPH
optionsblk::default_digraph()
DEFAULTOPTIONS_SPARSEDIGRAPH
optionsblk::default_sparse_digraph()
-
The
SparseGraph
struct helps with creating sparse graphs. A&mut SparseGraph
can be converted to thesparsegraph
used by nauty and Traces.
-
Examples
The following program prints the generators for the automorphism
groups of n-vertex polygons. It is a pretty literal translation of the
nautyex2
C program that is part of the nauty and Traces bundle.
use nauty_Traces_sys::*;
use std::io::{self, Write};
use std::os::raw::c_int;
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut options = optionblk::default();
options.writeautoms = TRUE;
let mut stats = statsblk::default();
loop {
print!("\nenter n : ");
io::stdout().flush().unwrap();
let mut input = String::new();
io::stdin().read_line(&mut input)?;
let n = input.trim().parse()?;
if n > 0 {
let m = SETWORDSNEEDED(n);
unsafe {
nauty_check(WORDSIZE as c_int, m as c_int, n as c_int, NAUTYVERSIONID as c_int);
}
let mut lab = vec![0; n];
let mut ptn = vec![0; n];
let mut orbits = vec![0; n];
let mut g = empty_graph(m, n);
for v in 0..n {
ADDONEEDGE(&mut g, v, (v + 1) % n, m);
}
println!("Generators for Aut(C[{}]):", n);
unsafe {
densenauty(
g.as_mut_ptr(),
lab.as_mut_ptr(),
ptn.as_mut_ptr(),
orbits.as_mut_ptr(),
&mut options,
&mut stats,
m as c_int,
n as c_int,
std::ptr::null_mut()
);
}
print!("[");
for orbit in orbits {
print!("{} ", orbit)
}
println!("]");
print!("order = ");
io::stdout().flush().unwrap();
unsafe {
writegroupsize(stderr, stats.grpsize1, stats.grpsize2);
}
println!();
} else {
break;
}
}
Ok(())
}
Features
See The Cargo Book for guidance on features.
Default features
-
bundled
: Use the version of nauty and Traces that comes bundled with this crate. This requires a C compiler on your system.Deactivate this feature to use a custom installation. In that case, you can only free memory allocated by nauty and Traces if this crate is linked to the same libc. Use the
libc
feature to generate the required bindings. -
tls
: Ensure thread-safety in the bundled library. Corresponds to compiling nauty and Traces withUSE_TLS
defined. -
libc
: nauty and Traces sometimes allocate memory internally, for example in thenauty_to_sg
function. This feature enable bindings toDYNFREE
andSG_FREE
, which are needed to deallocate this memory again. Note that this can only be done safely if nauty and Traces are linked to the same libc as this crate.
Non-default features
Activating the following features may make the generated binaries faster but less portable.
-
lzc
: Allow using thelzcnt
processor instruction, if available. -
popcnt
: Allow using thepopcnt
processor instruction, if available. -
native
: Allow processor instructions that are specific to the current hardware. Implieslzc
andpopcnt
.
License: Apache-2.0
Dependencies
~0.1–2.1MB
~41K SLoC