# module challenge.blossom¶

## Short summary¶

module ensae_projects.challenge.blossom

An implementation of Edmonds’ blossom algorithm for finding minimum-weight maximum matchings.

source on GitHub

## Classes¶

class truncated documentation
Blossom
Edge
EdgeNotIncident Indicates that a traversal was requested through an edge from a set that doesn’t contain any of its endpoints.
EdgeNotOutgoing Indicates that a traversal was requested through an edge from a set of vertices containing both its endpoints.
EdgeTraversalError
MaximumDualReached Indicates that we have reached the maximum dual solution and cannot improve it further.
StructureUpToDate This gets raised as soon as the structure of all trees is up-to-date, i.e. there are no more instances of any of the …
TreeStructureChanged Used whenever the structure of an alternating tree is changed to abort current traversal and initiate a new one.
Vertex

## Functions¶

function truncated documentation
cached_property A memoize decorator for class properties.
get_max_delta Returns the maximal value by which we can improve the dual solution by adjusting charges on alternating trees.
read_input
update_tree_structures

## Properties¶

property truncated documentation
extremities
members
members
outgoing_edges Returns a list of pairs (edge, target vertex).
outgoing_edges

## Methods¶

method truncated documentation
__eq__
__eq__
__eq__
__hash__
__hash__
__hash__
__init__
__init__
__init__
__repr__
__repr__
__repr__
__str__
__str__
__str__
add_edge_to
adjust_charge Decides what is supposed to happen on charge adjusts and recurses.
adjust_charge Decides what is supposed to happen on charge adjusts and recurses.
alter_tree Detects and handles the four cases where trees need to be altered.
alter_tree Detects and handles the four cases where trees need to be altered.
attach_out_of_tree_pair Handles case (P2).
attach_out_of_tree_pair Handles case (P2).
augment_matching Augments the matching along the alternating path containing given edge. (P4)
augment_matching Augments the matching along the alternating path containing given edge. (P4)
calculate_charge Calculates the total charge on this edge. The charge is calculated as the sum of all blossoms containing …
detach_children Detaches all children and turns them into out-of-tree pairs.
detach_children Detaches all children and turns them into out-of-tree pairs.
detach_from_parent Detaches itself from the parent and forms an out-of-tree pair. If called on an odd blossom, edge needs to be None …
detach_from_parent Detaches itself from the parent and forms an out-of-tree pair. If called on an odd blossom, edge needs to be None …
expand Expands this blossom back into its constituents. (P1)
expand
flip_alternating_path Flips edge selection on the alternating path from v1 to v2. v1 and v2 are the two vertices at the boundaries of …
flip_alternating_path Flips edge selection on the alternating path from v1 to v2. v1 and v2 are the two vertices at the boundaries of …
flip_root_path Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which …
flip_root_path Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which …
get_base_vertex
get_base_vertex
get_max_delta Finds the maximum allowed charge adjust for this blossom and its children.
get_max_delta Finds the maximum allowed charge adjust for this blossom and its children.
get_outermost_blossom
get_outermost_blossom
get_remaining_charge
get_root
get_root
handle_tight_edges Finds any fresh tight edges. If a tight edge leads to an out-of-tree blossom, attach the pair (P2). …
handle_tight_edges Finds any fresh tight edges. If a tight edge leads to an out-of-tree blossom, attach the pair (P2). …
shrink_with_peer Shrinks the cycle along given edge into a new blossom. (P3)
shrink_with_peer Shrinks the cycle along given edge into a new blossom. (P3)
toggle_selection Toggles the membership of self in the current matching.
traverse_from Returns the other endpoint of an edge. The argument can be either a vertex, a Blossom or a set of vertices. …

## Documentation¶

An implementation of Edmonds’ blossom algorithm for finding minimum-weight maximum matchings.

source on GitHub

exception ensae_projects.challenge.blossom.EdgeNotIncident[source]

Indicates that a traversal was requested through an edge from a set that doesn’t contain any of its endpoints.

source on GitHub

exception ensae_projects.challenge.blossom.EdgeNotOutgoing[source]

Indicates that a traversal was requested through an edge from a set of vertices containing both its endpoints.

source on GitHub

exception ensae_projects.challenge.blossom.EdgeTraversalError[source]

Bases: Exception

exception ensae_projects.challenge.blossom.MaximumDualReached[source]

Bases: Exception

Indicates that we have reached the maximum dual solution and cannot improve it further.

source on GitHub

exception ensae_projects.challenge.blossom.StructureUpToDate[source]

Bases: Exception

This gets raised as soon as the structure of all trees is up-to-date, i.e. there are no more instances of any of the four cases.

source on GitHub

exception ensae_projects.challenge.blossom.TreeStructureChanged[source]

Bases: Exception

Used whenever the structure of an alternating tree is changed to abort current traversal and initiate a new one.

source on GitHub

ensae_projects.challenge.blossom.cached_property(fun)[source]

A memoize decorator for class properties.

source on GitHub

ensae_projects.challenge.blossom.get_max_delta(roots)[source]

Returns the maximal value by which we can improve the dual solution by adjusting charges on alternating trees.

source on GitHub