graphtage.matching¶

A module for solving variants of the assignment problem.

Much of the code in this module is a nearly complete (but partial) implementation of Karp’s solution to the minimum weight bipartite matching problem [Karp78]. This is the problem of finding an edge between all pairs of nodes such that the sum of their weights is minimized. It is only a partial implementation because, part way through developing it, it was discovered that scipy’s implementation—while asymptotically inferior—is, in practice, almost always superior because it is compiled and not implemented in pure Python.

The two components of this module in which you will most likely be interested are min_weight_bipartite_matching() and a class that wraps it, WeightedBipartiteMatcher.

Example

>>> from graphtage.matching import min_weight_bipartite_matching
>>> from_nodes = ['a', 'b', 'c', 'd', 'e']
>>> to_nodes = range(10)
>>> edge_weights = lambda c, n: ord(c) + n
>>> min_weight_bipartite_matching(from_nodes, to_nodes, edge_weights)
{0: (0, 97), 1: (1, 99), 2: (2, 101), 3: (3, 103), 4: (4, 105)}
# The output format here is: "from_nodes_index: (matched_to_nodes_index, matched_edge_weight)"
>>> min_weight_bipartite_matching(range(5), range(10, 20), lambda a, b: a + b)
{0: (0, 10), 1: (1, 12), 2: (2, 14), 3: (3, 16), 4: (4, 18)}

Karp78(1,2,3,4,5,6,7): Richard M. Karp. An Algorithm to Solve the \(m \times n\) Assignment Problem in Expected Time \(O(mn \log n)\). 1978. It is partially implemented in WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION.

matching classes¶

Edge¶

class graphtage.matching.Edge(from_node: graphtage.matching.MatchingFromNode[T], to_node: graphtage.matching.MatchingToNode[T], weight: graphtage.bounds.Bounded)¶

Bases: graphtage.bounds.Bounded, typing.Generic

Edge data structure used in the implementation of [Karp78].

__init__(from_node: graphtage.matching.MatchingFromNode[T], to_node: graphtage.matching.MatchingToNode[T], weight: graphtage.bounds.Bounded)¶: Initialize self. See help(type(self)) for accurate signature.

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

property cost_bar¶

property cost_star¶

tighten_bounds() → bool ¶

Attempts to shrink the bounds of this object.

Returns: True if the bounds were tightened.
Return type: bool

Matching¶

class graphtage.matching.Matching¶

Bases: collections.abc.Set, graphtage.bounds.Bounded, set, typing.Generic

An abstract base class used by the partial implementation of [Karp78].

__init__()¶: Initialize self. See help(type(self)) for accurate signature.

classmethod _from_iterable(it)¶

Construct an instance of the class from any iterable input.

Must override this method if the class constructor signature does not accept an iterable for an input.

_hash()¶

Compute the hash value of a set.

Note that we don’t define __hash__: not all sets are hashable. But if you define a hashable set type, its __hash__ should call this function.

This must be compatible __eq__.

All sets ought to compare equal if they contain the same elements, regardless of how they are implemented, and regardless of the order of the elements; so there’s not much freedom for __eq__ or __hash__. We match the algorithm used by the built-in frozenset type.

add(edge: graphtage.matching.Edge[T])¶

Add an element to a set.

This has no effect if the element is already present.

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

clear()¶: Remove all elements from this set.

copy()¶: Return a shallow copy of a set.

difference()¶

Return the difference of two or more sets as a new set.

(i.e. all elements that are in this set but not the others.)

difference_update()¶: Remove all elements of another set from this set.

discard()¶

Remove an element from a set if it is a member.

If the element is not a member, do nothing.

intersection()¶

Return the intersection of two sets as a new set.

(i.e. all elements that are in both sets.)

intersection_update()¶: Update a set with the intersection of itself and another.

isdisjoint(other)¶: Return True if two sets have a null intersection.

issubset()¶: Report whether another set contains this set.

issuperset()¶: Report whether this set contains another set.

pop()¶: Remove and return an arbitrary set element. Raises KeyError if the set is empty.

remove()¶

Remove an element from a set; it must be a member.

If the element is not a member, raise a KeyError.

symmetric_difference(matching: Set[graphtage.matching.Edge[T]]) → graphtage.matching.Matching[T]¶

Return the symmetric difference of two sets as a new set.

(i.e. all elements that are in exactly one of the sets.)

symmetric_difference_update()¶: Update a set with the symmetric difference of itself and another.

tighten_bounds() → bool ¶

Attempts to shrink the bounds of this object.

Returns: True if the bounds were tightened.
Return type: bool

union()¶

Return the union of sets as a new set.

(i.e. all elements that are in either set.)

update()¶: Update a set with the union of itself and others.

MatchingFromNode¶

class graphtage.matching.MatchingFromNode(*args, **kwargs)¶

Bases: graphtage.matching.MatchingNode

__init__(*args, **kwargs)¶: Initialize self. See help(type(self)) for accurate signature.

construct_edges() → Dict[graphtage.matching.MatchingNode[T], graphtage.matching.Edge[T]]¶

edges() → Iterable[graphtage.matching.Edge[T]]¶

property sorted_neighbors¶

MatchingNode¶

class graphtage.matching.MatchingNode(matcher: graphtage.matching.WeightedBipartiteMatcher[T], node: T)¶

Bases: typing.Generic

Node data structure used in the implementation of [Karp78].

__init__(matcher: graphtage.matching.WeightedBipartiteMatcher[T], node: T)¶: Initialize self. See help(type(self)) for accurate signature.

abstract construct_edges() → Dict[graphtage.matching.MatchingNode[T], graphtage.matching.Edge[T]]¶

edges() → Iterable[graphtage.matching.Edge[T]]¶

MatchingToNode¶

class graphtage.matching.MatchingToNode(matcher: graphtage.matching.WeightedBipartiteMatcher[T], node: T)¶

Bases: graphtage.matching.MatchingNode

A node type used in the implementation of [Karp78].

__init__(matcher: graphtage.matching.WeightedBipartiteMatcher[T], node: T)¶: Initialize self. See help(type(self)) for accurate signature.

construct_edges() → Dict[graphtage.matching.MatchingNode[T], graphtage.matching.Edge[T]]¶

edges() → Iterable[graphtage.matching.Edge[T]]¶

PathSet¶

class graphtage.matching.PathSet¶

Bases: graphtage.matching.Matching, typing.Generic

A version of a Matching with edge directions overridden, used for [Karp78]

__init__()¶: Initialize self. See help(type(self)) for accurate signature.

classmethod _from_iterable(it)¶

Construct an instance of the class from any iterable input.

Must override this method if the class constructor signature does not accept an iterable for an input.

_hash()¶

Compute the hash value of a set.

Note that we don’t define __hash__: not all sets are hashable. But if you define a hashable set type, its __hash__ should call this function.

This must be compatible __eq__.

All sets ought to compare equal if they contain the same elements, regardless of how they are implemented, and regardless of the order of the elements; so there’s not much freedom for __eq__ or __hash__. We match the algorithm used by the built-in frozenset type.

add(edge: graphtage.matching.Edge[T], flip_direction: bool)¶

Add an element to a set.

This has no effect if the element is already present.

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

clear()¶: Remove all elements from this set.

copy()¶: Return a shallow copy of a set.

difference()¶

Return the difference of two or more sets as a new set.

(i.e. all elements that are in this set but not the others.)

difference_update()¶: Remove all elements of another set from this set.

discard()¶

Remove an element from a set if it is a member.

If the element is not a member, do nothing.

intersection()¶

Return the intersection of two sets as a new set.

(i.e. all elements that are in both sets.)

intersection_update()¶: Update a set with the intersection of itself and another.

isdisjoint(other)¶: Return True if two sets have a null intersection.

issubset()¶: Report whether another set contains this set.

issuperset()¶: Report whether this set contains another set.

path_to(from_any_of: Set[graphtage.matching.MatchingFromNode[T]], node: graphtage.matching.MatchingToNode[T]) → Set[graphtage.matching.Edge[T]]¶

pop()¶: Remove and return an arbitrary set element. Raises KeyError if the set is empty.

remove()¶

Remove an element from a set; it must be a member.

If the element is not a member, raise a KeyError.

symmetric_difference(matching: Set[graphtage.matching.Edge[T]]) → graphtage.matching.Matching[T]¶

Return the symmetric difference of two sets as a new set.

(i.e. all elements that are in exactly one of the sets.)

symmetric_difference_update()¶: Update a set with the symmetric difference of itself and another.

tighten_bounds() → bool ¶

Attempts to shrink the bounds of this object.

Returns: True if the bounds were tightened.
Return type: bool

union()¶

Return the union of sets as a new set.

(i.e. all elements that are in either set.)

update()¶: Update a set with the union of itself and others.

QueueElement¶

class graphtage.matching.QueueElement(edge: graphtage.matching.Edge[T], cost: int, is_special: bool)¶

Bases: object

A helper datastructure used by WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION

__init__(edge: graphtage.matching.Edge[T], cost: int, is_special: bool)¶: Initialize self. See help(type(self)) for accurate signature.

SortedEdges¶

class graphtage.matching.SortedEdges(edges: Iterable[graphtage.matching.Edge[T]])¶

Bases: typing.Generic

A sorted collection of edges.

__init__(edges: Iterable[graphtage.matching.Edge[T]])¶: Initialize self. See help(type(self)) for accurate signature.

head() → graphtage.matching.Edge[T]¶

tail() → graphtage.matching.Edge[T]¶

WeightedBipartiteMatcher¶

class graphtage.matching.WeightedBipartiteMatcher(from_nodes: Iterable[T], to_nodes: Iterable[T], get_edge: Callable[[T, T], Optional[graphtage.bounds.Bounded]])¶

Bases: graphtage.bounds.Bounded, typing.Generic

A graphtage.TreeNode matcher built atop min_weight_bipartite_matching().

It works by iteratively and selectively tightening the bipartite graph’s edges’ bounds until they are all “distinct” (i.e., their bounded ranges are all either graphtage.bounds.Range.definitive() or non-overlapping). It does this using graphtage.bounds.make_distinct(). Then min_weight_bipartite_matching() is used to solve the minimum weight matching problem.

This is used by graphtage.multiset.MultiSetEdit to match graphtage.MultiSetNode.

__init__(from_nodes: Iterable[T], to_nodes: Iterable[T], get_edge: Callable[[T, T], Optional[graphtage.bounds.Bounded]])¶

Initializes the weighted bipartite matcher.

Parameters

from_nodes – The nodes from which to match.
to_nodes – The nodes to which to match.
get_edge – A function returning a bounded edge between two nodes (or None if there is no edge). For example, this could be a graphtage.Edge.

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

property edges¶

Returns a dense matrix of the edges in the graph.

This property lazily constructs the edge matrix and memoizes the result.

is_complete() → bool ¶: Whether the matching has been completed, regardless of whether the bounds have been fully tightened.

property matching¶

Returns the minimum weight matching.

Returns

A mapping from self.from_nodes: to a tuples with the matched node in self.to_nodes and the edge between them.

Return type

Mapping[T, Tuple[T, Bounded]]

Note

This function will perform any necessary computation to determine the mapping in the event that it has not already been completed through prior calls to WeightedBipartiteMatcher.tighten_bounds().

tighten_bounds() → bool ¶

Tightens the bounds on the minimum weight matching.

Returns: True if the bounds were able to be tightened.

WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION¶

class graphtage.matching.WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION(from_nodes: Iterable[T], to_nodes: Iterable[T], get_edge: Callable[[T, T], Optional[graphtage.bounds.Bounded]])¶

Bases: graphtage.bounds.Bounded, typing.Generic

Partial implementation of An Algorithm to Solve the \(m \times n\) Assignment Problem in Expected Time \(O(mn \log n)\) [Karp78].

The implementation is partial because I realized partway through that, even though this implementation has better asymptotic bounds, scipy.optimize.linear_sum_assignment() will almost always be much faster since it is implemented in C++ and not pure Python.

It is retained here in the event that it is ever needed in the future.

__init__(from_nodes: Iterable[T], to_nodes: Iterable[T], get_edge: Callable[[T, T], Optional[graphtage.bounds.Bounded]])¶: Initialize self. See help(type(self)) for accurate signature.

bounds() → graphtage.bounds.Range ¶: Returns the bounds of this object.

free_destinations() → Iterator[graphtage.matching.MatchingToNode[T]]¶

free_sources() → Iterator[graphtage.matching.MatchingFromNode[T]]¶

tighten_bounds() → bool ¶

Attempts to shrink the bounds of this object.

Returns: True if the bounds were tightened.
Return type: bool

matching functions¶

get_dtype¶

graphtage.matching.get_dtype(min_value: int, max_value: int) → numpy.dtype¶: Returns the smallest numpy dtype capable of storing integers in the range [min_value, max_value]

min_weight_bipartite_matching¶

graphtage.matching.min_weight_bipartite_matching(from_nodes: Sequence[T], to_nodes: Sequence[T], get_edges: Callable[[T, T], Optional[W]]) → Mapping[int, Tuple[int, Union[bool, int, float]]]¶

Calculates the minimum weight bipartite matching between two sequences.

Parameters

from_nodes – The nodes in the first bipartite set.
to_nodes – The nodes in the second bipartite set.
get_edges – A function mapping pairs of edges to the weight of the edge between them, or None if there is no edge between them.

Warning

get_edges is expected to return all edge weights using the same type, either int, float, or bool.

Warning

get_edges can only return None for an edge weight if the rest of the edge weights are of type either int or float. Graphs with bool edge weights must be complete.

Warning

This function uses native types for computational efficiency. Edge weights larger than 2**64 or less than -2**63 will result in undefined behavior.

Returns

A mapping from from_node indices to pairs (matched_to_node_index, edge_weight).

Raises

ValueError – If not all of the edges are the same type.
ValueError – If a boolean edge weighted graph is not complete.