module challenge.blossom

Short summary

module ensae_projects.challenge.blossom

Source: https://github.com/koniiiik/edmonds-blossom/blob/master/blossom.py

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

Source: https://github.com/koniiiik/edmonds-blossom/blob/master/blossom.py

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

source on GitHub

exception ensae_projects.challenge.blossom.EdgeNotIncident

Bases: EdgeTraversalError

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

Bases: EdgeTraversalError

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

Bases: Exception

exception ensae_projects.challenge.blossom.MaximumDualReached

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

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

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)

A memoize decorator for class properties.

source on GitHub

ensae_projects.challenge.blossom.get_max_delta(roots)

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

source on GitHub