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