Bipartite Graph

bipartite_graph_matching(graph, edge_weights)

The bipartite graph matching problem is to find a maximum cardinality matching with minimum weight in a bipartite graph.

is_bipartite_graph(graph[, return_coloring])

Test if a graph is bipartite and return a coloring if it is bipartite.
bipartite_graph_matching(graph, edge_weights)[source]

The bipartite graph matching problem is to find a maximum cardinality matching with minimum weight in a bipartite graph.

This function returns the list of edge indices of the matching.

The input graph can either be:

  • an UndirectedGraph or

  • a triplet of two arrays and an integer (sources, targets, num_vertices) defining all the edges of the graph and its number of vertices

The input graph must be a bipartite graph.

Edge weights should be of integral type, otherwise they are casted to int64, a warning is emitted, and a possible loss of precision may occur.

This function is implemented using the CSA library by Andrew V. Goldberg and Robert Kennedy see https://github.com/rick/CSA . It is based on a push-relabel method.

Examples:

Example with an undirected graph:

>>> g = hg.UndirectedGraph(6)
>>> g.add_edges([5, 5, 1, 1, 4, 6], [2, 3, 2, 3, 0, 0])
>>> weights = [1, 2, 2, 5, 8, 5]
>>> hg.bipartite_graph_matching(g, weights)
array([1, 2, 5])

Example with a list of edges:

>>> hg.bipartite_graph_matching(([5, 5, 1, 1, 4, 6], [2, 3, 2, 3, 0, 0], 7), [1, 2, 2, 5, 8, 5])
array([1, 2, 5])
Parameters:

  • graph – an undirected graph or a triplet of two arrays and an integer (sources, targets, num_vertices), must be bipartite

  • edge_weights – edge weights of the graph

Returns:

the list of edge indices of the matching

is_bipartite_graph(graph, return_coloring=True)[source]

Test if a graph is bipartite and return a coloring if it is bipartite.

A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets \(X\) and \(Y\) such that every edge connects a vertex in \(X\) to one in \(Y\).

If the graph is bipartite, the function returns the value True and an array of colors. For any vertex \(v\), \(color[v] == 0\) if \(v\) belongs to \(X\) and \(color[v] == 1\) if \(v\) belongs to \(Y\). Note that the coloring is not unique, the algorithm returns any valid coloring.

If the graph is not bipartite, the function returns the value False and an empty array.

The input graph can either be:

  • an UndirectedGraph or

  • a triplet of two arrays and an integer (sources, targets, num_vertices) defining all the edges of the graph and its number of vertices

Examples:

Example with an undirected graph:

>>> g = hg.UndirectedGraph(6)
>>> g.add_edges([0, 0, 4, 2], [1, 4, 3, 3])
>>> hg.is_bipartite_graph(g)
(True, array([0, 1, 1, 0, 1, 0]))

Example with a list of edges:

>>> hg.is_bipartite_graph(([0, 0, 1, 1, 2, 1, 5], [3, 4, 3, 5, 5, 4, 4], 6))
(False, array([]))
Complexity:

If the graph is provided as an undirected graph, the algorithm is implemented using a depth first search. Its runtime complexity is \(O(|V| + |E|)\) where \(|V|\) is the number of vertices and \(|E|\) the number of edges of the graph.

If the graph is provided as a list of edges (sources, targets, num_vertices), the algorithm is implemented using a union find approach. Its runtime complexity is \(O(|E|\times \alpha(|V|))\) time, where \(\alpha\) is the inverse of the single-valued Ackermann function.

Parameters:

  • graph – an undirected graph or a triplet of two arrays and an integer (sources, targets, num_vertices)

  • return_coloring – if True returns a pair (is_bipartite, coloring), otherwise returns only is_bipartite where is_bipartite is a boolean and coloring is a 1D array indicating the color of each vertex

Returns:

(is_bipartite, coloring) or is_bipartite