module challenge.blossom
¶
Short summary¶
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.
Classes¶
class 
truncated documentation 





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

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

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

This gets raised as soon as the structure of all trees is uptodate, i.e. there are no more instances of any of the … 

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


Functions¶
function 
truncated documentation 

A memoize decorator for class properties. 

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




Properties¶
property 
truncated documentation 








Returns a list of pairs (edge, target vertex). 

Methods¶
method 
truncated documentation 


































Decides what is supposed to happen on charge adjusts and recurses. 

Decides what is supposed to happen on charge adjusts and recurses. 

Detects and handles the four cases where trees need to be altered. 

Detects and handles the four cases where trees need to be altered. 

Handles case (P2). 

Handles case (P2). 

Augments the matching along the alternating path containing given edge. (P4) 

Augments the matching along the alternating path containing given edge. (P4) 

Calculates the total charge on this edge. The charge is calculated as the sum of all blossoms containing … 

Detaches all children and turns them into outoftree pairs. 

Detaches all children and turns them into outoftree pairs. 

Detaches itself from the parent and forms an outoftree pair. If called on an odd blossom, edge needs to be None … 

Detaches itself from the parent and forms an outoftree pair. If called on an odd blossom, edge needs to be None … 

Expands this blossom back into its constituents. (P1) 



Flips edge selection on the alternating path from v1 to v2. v1 and v2 are the two vertices at the boundaries of … 

Flips edge selection on the alternating path from v1 to v2. v1 and v2 are the two vertices at the boundaries of … 

Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which … 

Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which … 





Finds the maximum allowed charge adjust for this blossom and its children. 

Finds the maximum allowed charge adjust for this blossom and its children. 











Finds any fresh tight edges. If a tight edge leads to an outoftree blossom, attach the pair (P2). … 

Finds any fresh tight edges. If a tight edge leads to an outoftree blossom, attach the pair (P2). … 

Shrinks the cycle along given edge into a new blossom. (P3) 

Shrinks the cycle along given edge into a new blossom. (P3) 

Toggles the membership of self in the current matching. 

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/edmondsblossom/blob/master/blossom.py
An implementation of Edmonds’ blossom algorithm for finding minimumweight maximum matchings.

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.

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.

exception
ensae_projects.challenge.blossom.
MaximumDualReached
[source]¶ Bases:
Exception
Indicates that we have reached the maximum dual solution and cannot improve it further.

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

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.

ensae_projects.challenge.blossom.
cached_property
(fun)[source]¶ A memoize decorator for class properties.