challenge.blossom
¶module ensae_projects.challenge.blossom
Source: https://github.com/koniiiik/edmondsblossom/blob/master/blossom.py
An implementation of Edmonds’ blossom algorithm for finding minimumweight maximum matchings.
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 uptodate, 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 
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 
property  truncated documentation 

extremities 

members 

members 

outgoing_edges 
Returns a list of pairs (edge, target vertex). 
outgoing_edges 
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 outoftree pairs. 
detach_children 
Detaches all children and turns them into outoftree pairs. 
detach_from_parent 
Detaches itself from the parent and forms an outoftree pair. If called on an odd blossom, edge needs to be None … 
detach_from_parent 
Detaches itself from the parent and forms an outoftree 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 outoftree blossom, attach the pair (P2). … 
handle_tight_edges 
Finds any fresh tight edges. If a tight edge leads to an outoftree 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. … 
Source: https://github.com/koniiiik/edmondsblossom/blob/master/blossom.py
An implementation of Edmonds’ blossom algorithm for finding minimumweight maximum matchings.
ensae_projects.challenge.blossom.
EdgeNotIncident
[source]¶Bases: ensae_projects.challenge.blossom.EdgeTraversalError
Indicates that a traversal was requested through an edge from a set that doesn’t contain any of its endpoints.
ensae_projects.challenge.blossom.
EdgeNotOutgoing
[source]¶Bases: ensae_projects.challenge.blossom.EdgeTraversalError
Indicates that a traversal was requested through an edge from a set of vertices containing both its endpoints.
ensae_projects.challenge.blossom.
MaximumDualReached
[source]¶Bases: Exception
Indicates that we have reached the maximum dual solution and cannot improve it further.
ensae_projects.challenge.blossom.
StructureUpToDate
[source]¶Bases: Exception
This gets raised as soon as the structure of all trees is uptodate, i.e. there are no more instances of any of the four cases.
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.
ensae_projects.challenge.blossom.
cached_property
(fun)[source]¶A memoize decorator for class properties.