Expand description
Bipartite (two-mode) graphs and matchings (igraph_bipartite.h, igraph_matching.h).
A graph is bipartite if its vertices can be split into two classes so
that every edge connects vertices of different classes: actors and
movies, authors and papers, workers and jobs. igraph has no dedicated
bipartite graph type: an ordinary Graph is paired with a types
vector, one bool per vertex, telling which class each vertex belongs
to. In this crate the types are plain &[bool] inputs and Vec<bool>
outputs; by igraph’s convention vertices of type false form the first
(or “bottom”) class and vertices of type true the second (“top”) one.
Functions that create bipartite graphs return a BipartiteGraph,
which bundles the graph with its types and offers shortcuts to the
analysis methods below.
§Example
use igraph::{bipartite::BipartiteGraph, prelude::*};
// Three workers (vertices 0..3, type false) and three jobs (3..6, type true).
let types = vec![false, false, false, true, true, true];
let edges = [(0, 3), (0, 4), (1, 3), (2, 4), (2, 5)];
let staff = BipartiteGraph::new(types, &edges, false).unwrap();
// Everyone can get a job: the maximum matching is perfect.
let m = staff.maximum_matching(None).unwrap();
assert_eq!(m.size, 3);
assert_eq!(m.mate(1), Some(3)); // worker 1 can only take job 3
assert!(staff.graph.is_matching(Some(&staff.types), &m.matching).unwrap());
// Workers sharing a job skill are connected in the projection.
let p = staff.projection().unwrap();
assert_eq!(p.proj1.edge_list(), vec![(0, 1), (0, 2)]);§Provided functionality
| Rust | C function | What it does |
|---|---|---|
Graph::is_bipartite, Graph::bipartite_types, BipartiteGraph::from_graph | igraph_is_bipartite | test bipartiteness, find a 2-coloring |
Graph::create_bipartite, BipartiteGraph::new | igraph_create_bipartite | build from types + edges, checking bipartiteness |
Graph::full_bipartite | igraph_full_bipartite | complete bipartite graph K(n1, n2) |
Graph::biadjacency | igraph_biadjacency | graph from a bipartite adjacency matrix |
Graph::weighted_biadjacency | igraph_weighted_biadjacency | weighted graph from a bipartite adjacency matrix |
Graph::get_biadjacency, BipartiteGraph::biadjacency | igraph_get_biadjacency | bipartite adjacency matrix of a graph |
Graph::bipartite_projection_size | igraph_bipartite_projection_size | sizes of the two projections |
Graph::bipartite_projection, Graph::bipartite_projection_of, BipartiteGraph::projection | igraph_bipartite_projection | the one-mode projections |
Graph::bipartite_game_gnp | igraph_bipartite_game_gnp | random G(n1, n2, p) graph |
Graph::bipartite_game_gnm | igraph_bipartite_game_gnm | random G(n1, n2, m) graph |
Graph::bipartite_iea_game | igraph_bipartite_iea_game (implemented with igraph_bipartite_game_gnm, working around an igraph 1.0.0 and 1.0.1 bug) | random multigraph by independent edge assignment |
Graph::is_matching | igraph_is_matching | validity of a matching |
Graph::is_maximal_matching | igraph_is_maximal_matching | maximality of a matching |
Graph::maximum_bipartite_matching, Graph::maximum_bipartite_matching_eps, BipartiteGraph::maximum_matching | igraph_maximum_bipartite_matching | maximum (weighted) bipartite matching |
§Related functionality in other modules
| Rust | What it does |
|---|---|
Graph::layout_bipartite (layout) | two-row drawing of a bipartite graph, from its types |
Graph::realize_bipartite_degree_sequence (constructors) | deterministic bipartite graph with given degrees |
is_bigraphical (mixing) | whether two degree sequences can be realized by a bipartite graph |
Graph::full_multipartite, Graph::turan (constructors) | complete k-partite graphs, generalizing Graph::full_bipartite |
Graph::erdos_renyi_game_gnp, Graph::erdos_renyi_game_gnm (games) | one-mode versions of the random bipartite games |
Graph::maxflow_value (flow) | maximum flow: a bipartite matching is a unit-capacity flow from one class to the other |
Graph::girth (structural) | shortest cycle; a graph is bipartite iff it has no odd cycle |
Graph::is_bipartite_coloring (cliques) | whether a given types vector is a proper 2-coloring, and how the edges are oriented |
Graph::read_graph_pajek (foreign) | reads two-mode Pajek networks, storing the types in the type vertex attribute when attributes are enabled |
§Matchings
A matching is represented, as in igraph, by a vector with one entry per
vertex: entry i is the vertex matched to i, or UNMATCHED (-1)
if i is unmatched. BipartiteMatching offers mate
and pairs to read it in a friendlier way.
See the igraph C documentation chapter on bipartite graphs and the section on matchings.
Structs§
- Biadjacency
- A bipartite adjacency matrix, the output of
Graph::get_biadjacency. - Bipartite
Game Options - Parameters shared by the random bipartite generators
Graph::bipartite_game_gnpandGraph::bipartite_game_gnm. - Bipartite
Graph - A graph together with its vertex types: the output of the bipartite constructors and generators of this module.
- Bipartite
Matching - A maximum matching of a bipartite graph, the output of
Graph::maximum_bipartite_matching. - Bipartite
Projection - The two one-mode projections of a bipartite graph, the output of
Graph::bipartite_projection. - Projection
Size - Vertex and edge counts of the two projections of a bipartite graph,
the output of
Graph::bipartite_projection_size. - Weighted
Bipartite Graph - A bipartite graph with edge weights, the output of
Graph::weighted_biadjacency.
Constants§
- UNMATCHED
- Marker used in matching vectors for unmatched vertices (
-1).