multi_bimap

Many-to-many bidirectional map in Rust.

This crate provides a MultiBimap struct, a bidirectional multimap that is implemented as two antiparallel multimaps that are kept in sync.

You can arbitrarily choose what should be the types of the constituent multimaps: for example, HashMap<&str, HashSet<&str>>, BTreeMap<i64, Vec<&str>>, indexmap::IndexMap<&str, Box<(i64, i64)> are all valid options.

Even better, these multimaps can have mixed types (e.g. HashMap of HashSets pointing rightwards, BTreeMap of Boxes pointing leftwards), so you can also have one-to-many or many-to-one bimaps as well (one-to-one bimap is obviously also an option). This is possible because MultiBimap uses traits from maplike, a Rust crate which allows to have a generic interface over a large number of containers.

This bidirectional multimap relation that MultiBimap models is also known under many other names: bi-multimap, multi-bimap, or sometimes even just bimap; in set theory, it's simply called a relation; in graph theory, it's the same as a bipartite graph.

This crate is compatible with no_std, undoredo and serde.

Usage

Adding dependency

First, add multi_bimap as a dependency to your Cargo.toml:

[dependencies]
multi_bimap = "0.3.1"

Examples

Many-to-many bidirectional map

In academic publishing, the relation between authors and academic papers is many-to-many; it is a bipartite graph: each author may have many papers, and each paper may have many authors. A MultiBimap can fully represent that:

use multi_bimap::MultiBimap;
use std::collections::{HashMap, HashSet};

let mut authorship: MultiBimap<
    HashMap<&str, HashSet<&str>>,
> = MultiBimap::new();

authorship.insert("Alan Turing", "On Computable Numbers");
authorship.insert("Alan Turing", "Computing Machinery and Intelligence");
authorship.insert("Ada Lovelace", "Notes on the Analytical Engine");
authorship.insert("Charles Babbage", "Notes on the Analytical Engine");

// Papers by one author.
assert_eq!(
    authorship.get_by_left("Alan Turing"),
    Some(&HashSet::from([
        "On Computable Numbers",
        "Computing Machinery and Intelligence",
    ])),
);

// Authors of one paper.
assert_eq!(
    authorship.get_by_right("Notes on the Analytical Engine"),
    Some(&HashSet::from(["Ada Lovelace", "Charles Babbage"])),
);

// Remove one author-paper association. Empty keys will disappear from both
// sides.
assert_eq!(
    authorship.remove(&"Charles Babbage", &"Notes on the Analytical Engine"),
    Some(("Charles Babbage", "Notes on the Analytical Engine")),
);
assert_eq!(
    authorship.get_by_right("Notes on the Analytical Engine"),
    Some(&HashSet::from(["Ada Lovelace"])),
);
assert_eq!(authorship.get_by_left("Charles Babbage"), None);

Documentation

See the documentation for more information on multi_bimap's usage.

Packaging

multi_bimap is published as a crate on the Crates.io registry.

Contributing

We welcome issues, pull requests and any other contributions from anyone to our repository on GitHub.

Licence

Outbound licence

multi_bimap is dual-licensed as under

MIT license, or
Apache License, Version 2.0,

at your option.

Inbound licence

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this work by you will be dual-licensed as described above, without any additional terms or conditions.

multi_bimap 0.3.1