Many-to-many bidirectional map in Rust.
This crate provides
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 two constituent
multimaps. HashMap<&str, HashSet<&str>>, BTreeMap<i64, Vec<&str>>,
indexmap::IndexMap<&str, Box<(i64, i64)> are all valid options. Naturally, in
case you have keys that are clostly to clone (e.g. large owned String), you can
also just wrap them in Rc or
Arc.
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, or just one-to-one bimaps.
All 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. See Supported
containers section
in its readme for a list of all types that can be used.
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 has no unsafe code and is compatible
with serde and
undoredo libraries. It is also
no_std-compatible, though alloc is
still required. There is no mandatory third-party dependencies, but there is a
first-party dependency on maplike, a
crate also developed by this library's authors. MSRV is 1.92.
First, add multi_bimap as a dependency to your Cargo.toml:
[dependencies]
multi_bimap = "0.9.0"Following are examples of multi_bimap usage. You can also find them in the
examples/
directory.
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 (here under alias
HashMultiBimap
for brevity) can fully represent that:
use multi_bimap::HashMultiBimap;
use std::collections::HashSet;
fn main() {
let mut authorship: HashMultiBimap<&str, &str> = HashMultiBimap::new();
// `HashMultiBimap` is an alias for a multi-bimap made of two antiparallel hash
// maps with hash sets as values. Without alias the above line would be this:
/*let mut authorship: MultiBimap<
HashMap<&str, HashSet<&str>>,
HashMap<&str, HashSet<&str>>,
> = MultiBimap::new();*/
authorship.insert("Stefan Banach", "Sur les opérations dans les ensembles abstraits");
authorship.insert("Stefan Banach", "Théorie des opérations linéaires");
authorship.insert("Stefan Banach", "Sur le principe de la condensation des singularités");
authorship.insert("Hugo Steinhaus", "Sur le principe de la condensation des singularités");
// Papers where Stefan Banach is an author.
assert_eq!(
authorship.get_by_left("Stefan Banach"),
Some(&HashSet::from([
"Sur les opérations dans les ensembles abstraits",
"Théorie des opérations linéaires",
"Sur le principe de la condensation des singularités",
])),
);
// "Sur le principe de la condensation des singularités" has two authors; it was
// co-authored by Stefan Banach and Hugo Steinhaus.
assert_eq!(
authorship.get_by_right("Sur le principe de la condensation des singularités"),
Some(&HashSet::from(["Stefan Banach", "Hugo Steinhaus"])),
);
// As an example, remove one author-paper association, of Hugo Steinhaus with
// this paper. Empty keys will disappear from both sides.
assert_eq!(
authorship.remove(
&"Hugo Steinhaus",
&"Sur le principe de la condensation des singularités",
),
Some((
"Hugo Steinhaus",
"Sur le principe de la condensation des singularités",
)),
);
assert_eq!(
authorship.get_by_right("Sur le principe de la condensation des singularités"),
Some(&HashSet::from(["Stefan Banach"])),
);
assert_eq!(authorship.get_by_left("Hugo Steinhaus"), None);
// Restore Hugo Steinhaus as co-author.
authorship.insert(
"Hugo Steinhaus",
"Sur le principe de la condensation des singularités",
);
assert_eq!(
authorship.get_by_right("Sur le principe de la condensation des singularités"),
Some(&HashSet::from(["Stefan Banach", "Hugo Steinhaus"])),
);
assert_eq!(
authorship.get_by_left("Hugo Steinhaus"),
Some(&HashSet::from([
"Sur le principe de la condensation des singularités",
])),
);
}multi_bimap can also represent type-enforced one-to-one relations, as an
alternative to the venerable bimap
crate, which sadly appears unmaintained (though it has a maintained fork,
bidimap).
An example of a one-to-one-relation is a country and its capital: each country
has one capital, and each capital belongs to one country. MultiBimap (here
under alias HashBimap) can represent that just as well without any additional
logic:
use maplike::one::One;
use multi_bimap::HashBimap;
fn main() {
let mut capitals: HashBimap<&str, &str> = HashBimap::new();
// `HashBimap` is an alias for a one-to-one bimap made of two antiparallel hash
// maps with `One` as value type. `One` is a special container that can hold
// only one element that gets displaced upon insert. Without alias the above
// line would be this:
/*let mut capitals: MultiBimap<
HashMap<&str, One<&str>>,
HashMap<&str, One<&str>>,
> = MultiBimap::new();*/
capitals.insert("Poland", "Warsaw");
capitals.insert("France", "Paris");
capitals.insert("Lithuania", "Vilnius");
// Unfortunately, in 1920, Vilnius was annexed by Poland and held until 1939,
// a regrettable episode in Polish history. During that period Lithuania's capital
// was Kaunas.
assert_eq!(
capitals.insert("Lithuania", "Kaunas"),
(Some("Vilnius"), None),
);
assert_eq!(capitals.get_by_left("Lithuania"), Some(&One::new("Kaunas")));
// After Lithuania regained Vilnius in 1939, as a side effect of Nazi
// Germany's and Soviet Union's joint invasion and annexation of Poland, it
// was restored as Lithuania's capital. (Though soon thereafter, in 1940,
// Lithuania was annexed whole by Soviet Union anyway)
assert_eq!(
capitals.insert("Lithuania", "Vilnius"),
(Some("Kaunas"), None),
);
assert_eq!(capitals.get_by_left("Lithuania"), Some(&One::new("Vilnius")));
}MultiBimap::insert() performs a clone on both inserted keys to make it
possible for both sides of the relation to own them. This is fine for cheap
keys, such as Rust primitive number types like i64, or references like &str,
but for owned strings or large values this can get expensive. If the latter is
the case, to avoid costly cloning, you can just wrap keys in Rc (or Arc if
you need thread safety).
This is also what the bimap/bidimap crate does internally.
use multi_bimap::HashMultiBimap;
use std::collections::HashSet;
use std::rc::Rc;
fn main() {
// Polish medieval and Renaissance scientists and the fields they worked in.
// This is a many-to-many relation: some scientists worked in multiple
// fields, and some fields were worked on by multiple scientists.
let mut fields: HashMultiBimap<Rc<str>, Rc<str>> = HashMultiBimap::new();
let vitello = Rc::from("Vitello");
let krol = Rc::from("Marcin Król of Żurawica");
let brudzewski = Rc::from("Albert Brudzewski");
let copernicus = Rc::from("Nicolaus Copernicus");
let sedziwoj = Rc::from("Michał Sędziwój");
let optics = Rc::from("optics");
let astronomy = Rc::from("astronomy");
let mathematics = Rc::from("mathematics");
let alchemy = Rc::from("alchemy");
// Vitello was both an optician and mathematician.
fields.insert(Rc::clone(&vitello), Rc::clone(&optics));
fields.insert(Rc::clone(&vitello), Rc::clone(&mathematics));
// Król, Brudzewski, and Copernicus were both astronomers and
// mathematicians.
fields.insert(Rc::clone(&krol), Rc::clone(&astronomy));
fields.insert(Rc::clone(&krol), Rc::clone(&mathematics));
fields.insert(Rc::clone(&brudzewski), Rc::clone(&astronomy));
fields.insert(Rc::clone(&brudzewski), Rc::clone(&mathematics));
fields.insert(Rc::clone(&copernicus), Rc::clone(&astronomy));
fields.insert(Rc::clone(&copernicus), Rc::clone(&mathematics));
// Sędziwój was an alchemist.
fields.insert(Rc::clone(&sedziwoj), Rc::clone(&alchemy));
assert_eq!(
fields.get_by_left("Albert Brudzewski"),
Some(&HashSet::from([
Rc::clone(&astronomy),
Rc::clone(&mathematics),
])),
);
assert_eq!(
fields.get_by_right("astronomy"),
Some(&HashSet::from([
Rc::clone(&krol),
Rc::clone(&brudzewski),
Rc::clone(&copernicus),
])),
);
}See the documentation for more information
on multi_bimap's usage.
multi_bimap is published as a crate on the
Crates.io registry.
We welcome issues, pull requests and any other contributions from anyone to our repository on GitHub.
multi_bimap is dual-licensed as under
at your option.
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.