graphs.edmonds_blossom_algorithm¶
Classes¶
Class to hold auxiliary data during the blossom algorithm's execution. |
|
Class to encapsulate data related to a blossom in the graph. |
|
Module Contents¶
- class graphs.edmonds_blossom_algorithm.BlossomAuxData(queue: collections.deque, parent: list[int], base: list[int], in_blossom: list[bool], match: list[int], in_queue: list[bool])¶
Class to hold auxiliary data during the blossom algorithm’s execution.
- base¶
- in_blossom¶
- in_queue¶
- match¶
- parent¶
- queue¶
- class graphs.edmonds_blossom_algorithm.BlossomData(aux_data: BlossomAuxData, vertex_u: int, vertex_v: int, lowest_common_ancestor: int)¶
Class to encapsulate data related to a blossom in the graph.
- aux_data¶
- lowest_common_ancestor¶
- vertex_u¶
- vertex_v¶
- class graphs.edmonds_blossom_algorithm.EdmondsBlossomAlgorithm¶
- static contract_blossom(blossom_data: BlossomData) None¶
Contracts a blossom found during the matching process.
- Args:
blossom_data: The data related to the blossom to be contracted.
- static find_base(base: list[int], parent: list[int], vertex_u: int, vertex_v: int) int¶
Finds the base of the blossom.
- Args:
base: The base array for each vertex. parent: The parent array from BFS. vertex_u: One endpoint of the blossom. vertex_v: The other endpoint of the blossom.
- Returns:
The lowest common ancestor of vertex_u and vertex_v in the blossom.
- static maximum_matching(edges: list[list[int]], vertex_count: int) list[list[int]]¶
Finds the maximum matching in a graph using the Edmonds Blossom Algorithm.
- Args:
edges: A list of edges represented as pairs of vertices. vertex_count: The total number of vertices in the graph.
- Returns:
A list of matched pairs in the form of a list of lists.
- static update_matching(match: list[int], parent: list[int], matched_vertex: int) None¶
Updates the matching based on the augmenting path found.
- Args:
match: The current match list. parent: The parent list from BFS traversal. matched_vertex: The vertex where the augmenting path ends.
- UNMATCHED = -1¶