.. _f-blossom: module ``challenge.blossom`` ============================ .. inheritance-diagram:: 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. :githublink:`%|py|8` Classes +++++++ +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | class | truncated documentation | +=======================================================================================+==========================================================================================================================+ | :class:`Blossom ` | | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`Edge ` | | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`EdgeNotIncident ` | Indicates that a traversal was requested through an edge from a set that doesn't contain any of its endpoints. | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`EdgeNotOutgoing ` | Indicates that a traversal was requested through an edge from a set of vertices containing both its endpoints. | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`EdgeTraversalError ` | | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`MaximumDualReached ` | Indicates that we have reached the maximum dual solution and cannot improve it further. | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`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 ... | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`TreeStructureChanged ` | Used whenever the structure of an alternating tree is changed to abort current traversal and initiate a new one. | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ | :class:`Vertex ` | | +---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------+ Functions +++++++++ +------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ | function | truncated documentation | +==========================================================================================+================================================================================================================+ | :func:`cached_property ` | A memoize decorator for class properties. | +------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ | :func:`get_max_delta ` | Returns the maximal value by which we can improve the dual solution by adjusting charges on alternating trees. | +------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ | :func:`read_input ` | | +------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ | :func:`update_tree_structures ` | | +------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ Properties ++++++++++ +----------------------------------------------------------------------------------+------------------------------------------------+ | property | truncated documentation | +==================================================================================+================================================+ | :meth:`extremities ` | | +----------------------------------------------------------------------------------+------------------------------------------------+ | :meth:`members ` | | +----------------------------------------------------------------------------------+------------------------------------------------+ | :meth:`members ` | | +----------------------------------------------------------------------------------+------------------------------------------------+ | :meth:`outgoing_edges ` | Returns a list of pairs (edge, target vertex). | +----------------------------------------------------------------------------------+------------------------------------------------+ | :meth:`outgoing_edges ` | | +----------------------------------------------------------------------------------+------------------------------------------------+ Methods +++++++ +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | method | truncated documentation | +====================================================================================================+=======================================================================================================================+ | :py:meth:`__eq__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__eq__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__eq__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__hash__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__hash__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__hash__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__init__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__init__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__init__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__repr__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__repr__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__repr__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__str__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__str__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :py:meth:`__str__ ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`add_edge_to ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`adjust_charge ` | Decides what is supposed to happen on charge adjusts and recurses. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`adjust_charge ` | Decides what is supposed to happen on charge adjusts and recurses. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`alter_tree ` | Detects and handles the four cases where trees need to be altered. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`alter_tree ` | Detects and handles the four cases where trees need to be altered. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`attach_out_of_tree_pair ` | Handles case (P2). | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`attach_out_of_tree_pair ` | Handles case (P2). | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`augment_matching ` | Augments the matching along the alternating path containing given edge. (P4) | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`augment_matching ` | Augments the matching along the alternating path containing given edge. (P4) | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`calculate_charge ` | Calculates the total charge on this edge. The charge is calculated as the sum of all blossoms containing ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`detach_children ` | Detaches all children and turns them into out-of-tree pairs. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`detach_children ` | Detaches all children and turns them into out-of-tree pairs. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`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 ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`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 ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`expand ` | Expands this blossom back into its constituents. (P1) | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`expand ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`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 ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`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 ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`flip_root_path ` | Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`flip_root_path ` | Flips edge selection on the alternating path from self to root. Argument edge is the edge from a child from which ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_base_vertex ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_base_vertex ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_max_delta ` | Finds the maximum allowed charge adjust for this blossom and its children. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_max_delta ` | Finds the maximum allowed charge adjust for this blossom and its children. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_outermost_blossom ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_outermost_blossom ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_remaining_charge ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_root ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`get_root ` | | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`handle_tight_edges ` | Finds any fresh tight edges. If a tight edge leads to an out-of-tree blossom, attach the pair (P2). ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`handle_tight_edges ` | Finds any fresh tight edges. If a tight edge leads to an out-of-tree blossom, attach the pair (P2). ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`shrink_with_peer ` | Shrinks the cycle along given edge into a new blossom. (P3) | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`shrink_with_peer ` | Shrinks the cycle along given edge into a new blossom. (P3) | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`toggle_selection ` | Toggles the membership of self in the current matching. | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ | :meth:`traverse_from ` | Returns the other endpoint of an edge. The argument can be either a vertex, a Blossom or a set of vertices. ... | +----------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ Documentation +++++++++++++ .. automodule:: ensae_projects.challenge.blossom :members: :special-members: __init__ :show-inheritance: