module challenge.blossom

Inheritance diagram of ensae_projects.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[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.

source on GitHub

exception 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.

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