matchpy.matching.bipartite module

Contains classes and functions related to bipartite graphs.

The BipartiteGraph class is used to represent a bipartite graph as a dictionary. In particular, BipartiteGraph.find_matching() can be used to find a maximum matching in such a graph.

The function enum_maximum_matchings_iter can be used to enumerate all maximum matchings of a BipartiteGraph.

class BipartiteGraph(*args, **kwargs)

Bases: typing.MutableMapping

A bipartite graph representation.

This class is a specialized dictionary, where each edge is represented by a 2-tuple that is used as a key in the dictionary. The value can either be True or any value that you want to associate with the edge.

For example, the edge from 1 to 2 with a label 42 would be set like this:

>>> graph = BipartiteGraph()
>>> graph[1, 2] = 42

__init__(*args, **kwargs)

Initialize self. See help(type(self)) for accurate signature.

as_graph() → None

Returns a graphviz.Graph representation of this bipartite graph.

clear()

Removes all cached data.

edges()

edges_with_labels()

Returns a view on the edges with labels.

find_matching() → Dict[TLeft, TRight]

Finds a matching in the bipartite graph.

This is done using the Hopcroft-Karp algorithm.

Returns:A dictionary where each edge of the matching is represented by a key-value pair with the key being from the left part of the graph and the value from te right part.

limited_to(left: Set[TLeft], right: Set[TRight]) → matchpy.matching.bipartite.BipartiteGraph[[TLeft, TRight], TEdgeValue]

Returns the induced subgraph where only the nodes from the given sets are included.

without_edge(edge: Tuple[TLeft, TRight]) → matchpy.matching.bipartite.BipartiteGraph[[TLeft, TRight], TEdgeValue]

Returns a copy of this bipartite graph with the given edge removed.

without_nodes(edge: Tuple[TLeft, TRight]) → matchpy.matching.bipartite.BipartiteGraph[[TLeft, TRight], TEdgeValue]

Returns a copy of this bipartite graph with the given edge and its adjacent nodes removed.

enum_maximum_matchings_iter(graph: matchpy.matching.bipartite.BipartiteGraph[[TLeft, TRight], TEdgeValue]) → Iterator[Dict[TLeft, TRight]]