tusc.graph.matching.BipartiteMatching¶
- class graph.matching.BipartiteMatching(n, m, preferences=None)¶
Methods
is_stable_matching([matching])Checks if the provided matching is stable.
Uses NetworkX to return a matching that maximizes edge weight.
score_preference_rank([preferences])Re-weights edges according to a preference rank dictionary.
- is_stable_matching(matching=None)¶
Checks if the provided matching is stable.
- Parameters
matching (dict) – keys and vals are both endpoints. if your graph is undirected,
- max_weight_matching()¶
Uses NetworkX to return a matching that maximizes edge weight.
- score_preference_rank(preferences=None)¶
Re-weights edges according to a preference rank dictionary. We assume each vertex/node “assigns” n-i points to the ith vertex in its preference list. The weight of an edge/pair is the sum of the points assigned by the endpoints.
- Parameters
preferences (dict) –
overwrites preferences attribute if not None dictionary of preference ranks
keys are ints vals are lists of ints
- example, for K_{2,2}:
- {
0 : [2, 3], 1 : [3, 2], 2 : [0, 1], 3 : [1, 0]
} indicating 1 prefers 3 over 2, etc.
Notes
Inspired by Problem 3.2.10 in [1]
References
[1] West, Douglas Brent. “Matchings and Factors.” In Introduction to Graph Theory, 135-135. United States: Pearson, 2018.