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[graphtage.matching.T], to_node: graphtage.matching.MatchingToNode[graphtage.matching.T], weight: graphtage.bounds.Bounded)¶
Bases:
graphtage.bounds.Bounded
,Generic
[graphtage.matching.T
]Edge data structure used in the implementation of [Karp78].
- __init__(from_node: graphtage.matching.MatchingFromNode[graphtage.matching.T], to_node: graphtage.matching.MatchingToNode[graphtage.matching.T], weight: graphtage.bounds.Bounded)¶
- bounds() graphtage.bounds.Range ¶
Returns the bounds of this object.
Matching¶
- class graphtage.matching.Matching¶
Bases:
Generic
[graphtage.matching.T
],collections.abc.Set
,graphtage.bounds.Bounded
,Set
[graphtage.matching.Edge
[graphtage.matching.T
]]An abstract base class used by the partial implementation of [Karp78].
- __init__()¶
- 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[graphtage.matching.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[graphtage.matching.T]]) graphtage.matching.Matching[graphtage.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
- 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:
Generic
[graphtage.matching.T
],graphtage.matching.MatchingNode
[graphtage.matching.T
]- __init__(*args, **kwargs)¶
- construct_edges() Dict[graphtage.matching.MatchingNode[graphtage.matching.T], graphtage.matching.Edge[graphtage.matching.T]] ¶
- edges() Iterable[graphtage.matching.Edge[graphtage.matching.T]] ¶
- property sorted_neighbors: graphtage.matching.SortedEdges[graphtage.matching.T]¶
MatchingNode¶
- class graphtage.matching.MatchingNode(matcher: graphtage.matching.WeightedBipartiteMatcher[graphtage.matching.T], node: graphtage.matching.T)¶
Bases:
Generic
[graphtage.matching.T
]Node data structure used in the implementation of [Karp78].
- __init__(matcher: graphtage.matching.WeightedBipartiteMatcher[graphtage.matching.T], node: graphtage.matching.T)¶
- abstract construct_edges() Dict[graphtage.matching.MatchingNode[graphtage.matching.T], graphtage.matching.Edge[graphtage.matching.T]] ¶
- edges() Iterable[graphtage.matching.Edge[graphtage.matching.T]] ¶
MatchingToNode¶
- class graphtage.matching.MatchingToNode(matcher: graphtage.matching.WeightedBipartiteMatcher[graphtage.matching.T], node: graphtage.matching.T)¶
Bases:
Generic
[graphtage.matching.T
],graphtage.matching.MatchingNode
[graphtage.matching.T
]A node type used in the implementation of [Karp78].
- __init__(matcher: graphtage.matching.WeightedBipartiteMatcher[graphtage.matching.T], node: graphtage.matching.T)¶
- construct_edges() Dict[graphtage.matching.MatchingNode[graphtage.matching.T], graphtage.matching.Edge[graphtage.matching.T]] ¶
- edges() Iterable[graphtage.matching.Edge[graphtage.matching.T]] ¶
PathSet¶
- class graphtage.matching.PathSet¶
Bases:
graphtage.matching.Matching
[graphtage.matching.T
],Generic
[graphtage.matching.T
]A version of a Matching with edge directions overridden, used for [Karp78]
- __init__()¶
- 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[graphtage.matching.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[graphtage.matching.T]], node: graphtage.matching.MatchingToNode[graphtage.matching.T]) Set[graphtage.matching.Edge[graphtage.matching.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[graphtage.matching.T]]) graphtage.matching.Matching[graphtage.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
- 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[graphtage.matching.T], cost: int, is_special: bool)¶
Bases:
object
A helper datastructure used by
WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION
- __init__(edge: graphtage.matching.Edge[graphtage.matching.T], cost: int, is_special: bool)¶
SortedEdges¶
- class graphtage.matching.SortedEdges(edges: Iterable[graphtage.matching.Edge[graphtage.matching.T]])¶
Bases:
Generic
[graphtage.matching.T
]A sorted collection of edges.
- __init__(edges: Iterable[graphtage.matching.Edge[graphtage.matching.T]])¶
- head() graphtage.matching.Edge[graphtage.matching.T] ¶
- tail() graphtage.matching.Edge[graphtage.matching.T] ¶
WeightedBipartiteMatcher¶
- class graphtage.matching.WeightedBipartiteMatcher(from_nodes: Iterable[graphtage.matching.T], to_nodes: Iterable[graphtage.matching.T], get_edge: Callable[[graphtage.matching.T, graphtage.matching.T], Optional[graphtage.bounds.Bounded]])¶
Bases:
graphtage.bounds.Bounded
,Generic
[graphtage.matching.T
]A
graphtage.TreeNode
matcher built atopmin_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 usinggraphtage.bounds.make_distinct()
. Thenmin_weight_bipartite_matching()
is used to solve the minimum weight matching problem.This is used by
graphtage.multiset.MultiSetEdit
to matchgraphtage.MultiSetNode
.- __init__(from_nodes: Iterable[graphtage.matching.T], to_nodes: Iterable[graphtage.matching.T], get_edge: Callable[[graphtage.matching.T, graphtage.matching.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 agraphtage.Edge
.
- bounds() graphtage.bounds.Range ¶
Returns the bounds of this object.
- property edges: List[List[Optional[graphtage.bounds.Bounded]]]¶
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: Mapping[graphtage.matching.T, Tuple[graphtage.matching.T, graphtage.bounds.Bounded]]¶
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.
- A mapping from
- 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()
.
WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION¶
- class graphtage.matching.WeightedBipartiteMatcherPARTIAL_IMPLEMENTATION(from_nodes: Iterable[graphtage.matching.T], to_nodes: Iterable[graphtage.matching.T], get_edge: Callable[[graphtage.matching.T, graphtage.matching.T], Optional[graphtage.bounds.Bounded]])¶
Bases:
graphtage.bounds.Bounded
,Generic
[graphtage.matching.T
]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[graphtage.matching.T], to_nodes: Iterable[graphtage.matching.T], get_edge: Callable[[graphtage.matching.T, graphtage.matching.T], Optional[graphtage.bounds.Bounded]])¶
- bounds() graphtage.bounds.Range ¶
Returns the bounds of this object.
- free_destinations() Iterator[graphtage.matching.MatchingToNode[graphtage.matching.T]] ¶
- free_sources() Iterator[graphtage.matching.MatchingFromNode[graphtage.matching.T]] ¶
matching functions¶
get_dtype¶
min_weight_bipartite_matching¶
- graphtage.matching.min_weight_bipartite_matching(from_nodes: Sequence[graphtage.matching.T], to_nodes: Sequence[graphtage.matching.T], get_edges: Callable[[graphtage.matching.T, graphtage.matching.T], Optional[graphtage.matching.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, eitherint
,float
, orbool
.Warning
get_edges
can only returnNone
for an edge weight if the rest of the edge weights are of type eitherint
orfloat
. Graphs withbool
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.