3 releases (breaking)

0.3.0 May 6, 2020
0.2.0 Jan 6, 2017
0.1.0 Oct 9, 2015

#380 in Compression

MIT/Apache

81KB
1.5K SLoC

zdd

Build Status Latest Version

zdd is a Zero-suppressed binary Decision Diagram library in Rust. It is based on Zero-suppressed BDDs and their applications by Shin-Ichi Minato.

For details see [the documentation][doc].

Warning

I wrote this crate a very long time ago, when I was a Rust newbie. There seems to be little interest in this library, so I only barely maintain it. If you are serious about using it, consider letting me know to see if I or someone else can improve or rewrite it.

(Zero-suppressed BDDs and their applications) [doc]: https://docs.rs/zdd (zdd documentation)


lib.rs:

A ZDD library, based on this paper by Shin-Ichi Minato.

ZDDs are hash consed so equality is constant time. All operations on ZDDs provided by Factory are cached: count, offset, onset, change, union, inter, minus and subset.

Warning

I wrote this crate a very long time ago, when I was a Rust newbie. There seems to be little interest in this library, so I only barely maintain it. If you are serious about using it, consider letting me know to see if I or someone else can improve or rewrite it.

Factory

A Factory maintains the hash cons table for the ZDDs, as well as the caches for basic operations. A factory is thread-safe. Usage is Caml-module-like

use zdd::* ;
let f = Factory::<&'static str>::mk(7) ;

let ref zero = f.zero() ;
let ref one = f.one() ;

let ref x = f.mk_node("x", zero, one) ;
let ref _x = f.change(one, "x") ;
println!(" x: {}",  x) ;
println!("_x: {}", _x) ;
assert!(x == _x) ;

let ref y = f.change(one, "y") ;
let ref x_u_y = f.union(x, y) ;
let ref z = f.change(one, "z") ;
let ref x_u_y_m_z = f.minus(x_u_y, z) ;
assert!(x_u_y_m_z == x_u_y) ;

Wrapped

The easiest way to manipulate ZDDs is to use wrapped::Zdd which is wrapper around a ZDD and its associated factory.

use zdd::wrapped::* ;
let f = mk_factory::<&'static str>(7) ;

let ref one = Zdd::one(&f) ;

let ref x = one ^ "x"         ; // Change "x" in one.
let ref y = one ^ "y"         ; // change "y" in one.
let ref z = one ^ "z"         ; // Change "z" in one.
let ref x_u_y = x + y         ; // Union.
let ref x_u_y_m_z = x_u_y - z ; // Difference.
assert!(x_u_y_m_z == x_u_y) ;

Dependencies

~605KB
~11K SLoC