.. _objective: Objective --------- The proposal submitted and accepted for the Google Summer of Code 2024 at SageMath can be found here: :download:`Link <_static/proposal.pdf>`. In the initial proposal, all methods were presented as independent, standalone functions. However, after discussions with my mentor, Prof. David Coudert, we concluded that a more structured approach would be beneficial. Specifically, we decided to create a dedicated class, :class:`MatchingCoveredGraph`, which would inherit from :class:`Graph` (itself inheriting from :class:`GenericGraph`). This class would encapsulate the methods as member functions. This shift to a class-based approach requires overwriting some methods from both :class:`Graph` and :class:`GenericGraph` (that are new to the proposal). The purpose of these overrides is twofold: * to simplify certain operations in the context of time complexity, and * to ensure that the resulting graph is always matching covered, that is, an instance of the class :class:`MatchingCoveredGraph`. This ensures that any transformations or operations performed on a matching covered graph retain its defining properties. The primary objective of this project is to implement and formalize the handling of matching covered graphs within SageMath by developing the :class:`MatchingCoveredGraph` class and refining relevant methods to support these structures. In addition to the core objectives outlined above, there are several supplementary targets associated with this project. A comprehensive and detailed overview of the objectives is as follows: 1. Implementing methods for generating following families of matching covered graphs: - Möbius ladder graph - Staircase graph - Biwheel graph - Truncated biwheel graph 2. Implementing methods for generating some small graphs/ digraphs: - Bicorn graph - Tricorn graph - Murty graph - Cubeplex graph - Twinplex graph - KohTindell digraph 3. Implementing methods pertaining to matching: .. raw:: html
is_matching_covered() Check if the graph is matching covered.
is_bicritical() Check if the graph is bicritical.
4. Introducing the class :class:`MatchingCoveredGraph` and implementing methods concerning matching covered graph: * Class related methods: .. raw:: html
__init__() Check if the graph is matching covered.
__hash__() Compute a hash for the immutable matching covered graph.
__repr__() Return a string representation of the matching covered graph.
_subgraph_by_adding() Return the matching covered subgraph containing the given vertices and edges.
_subgraph_by_deleting() Return the matching covered subgraph containing the provided vertices and edges.
_upgrade_from_graph() Upgrade the given graph to a matching covered graph.
* Methods concerning barriers and canonical partition: .. raw:: html
canonical_partition() Return the canonical partition.
maximal_barrier() Return the (unique) maximal barrier containing the vertex.
* Methods concerning bricks, braces and tight cut decomposition: .. raw:: html
bricks_and_braces() Return the list of (the underlying simple) bricks and braces.
is_brace() Check if the matching covered graph is a brace.
is_brick() Check if the matching covered graph is a brick.
number_of_braces() Return the number of braces.
number_of_bricks() Return the number of bricks.
number_of_petersen_bricks() Return the number of Petersen bricks.
tight_cut_decomposition() Return a tight cut decomposition.
* Methods concerning removability and ear decomposition: .. raw:: html
add_ear() Add an ear to the matching covered graph.
bisubdivide_edge() bisubdivide an edge k times.
bisubdivide_edge() bisubdivide k times edges from an iterable container.
ear_decomposition() Return a matching covered ear decomposition computed efficiently.
is_removable_double_ear() Check whether the pair of ears form a removable double ear.
is_removable_doubleton() Check whether the pair of edges constitute a removable doubleton.
is_removable_ear() Check whether the ear is removable.
is_removable_edge() Check whether the edge is removable.
optimal_ear_decomposition() Return an optimal ear decomposition.
removable_double_ears() Return a list of removable double ears.
removable_doubletons() Return a list of removable doubletons.
removable_ears() Return a list of removable ears.
removable_edegs() Return an EdgesView of removable edges.
retract() Compute the retract of the matching covered graph.
* Methods for generating bricks and braces: .. raw:: html
brace_generation_sequence() Return a McCuaig brace generation sequence of the (provided) brace.
brick_generation_sequence() Return a Norine-Thomas brick generation sequence of the (provided) brick.
is_mccuaig_brace() Check if the brace is a McCuaig brace.
is_norine_thomas_brick() Check if the brick is a Norine-Thomas brick.
* Overwritten methods: .. raw:: html
add_clique() Add a clique to the graph with the provided vertices.
add_cycle() Add a cycle to the graph with the provided vertices.
add_edge() Add an edge from vertex u to vertex v.
add_edges() Add edges from an iterable container.
add_vertex() Add a vertex to the (matching covered) graph.
add_vertices() Add vertices from an iterable container of vertices.
allow_loops() Change whether loops are allowed in (matching covered) graphs.
allows_loops() Return whether loops are permitted in (matching covered) graphs.
cartesian_product() Return the cartesian product of self and other.
clear() Make the graph empty removing all associated informations.
complement() Return the complement of the graph.
contract_edge() Contract an edge from u to v.
contract_edges() Contract edges from an iterable container.
degree_constrained_subgraph() Return a degree-constrained matching covered subgraph.
delete_edge() Delete the edge from u to v.
delete_edges() Delete edges from an iterable container.
delete_multiedge() Delete all edges from u to v.
delete_multiedge() Delete all edges from u to v.
delete_vertices() Delete specified vertices form self.
disjoint_union() Return the disjoint union of self and other.
disjunctive_product() Return the disjunctive product of self and other.
has_loops() Return whether there are loops in the matching covered graph.
has_perfect_matching() Check whether the graph has a perfect matching.
is_biconnected() Check if the matching covered graph is biconnected.
is_block_graph() Check whether the matching covered graph is a block graph.
is_cograph() Check whether the matching covered graph is cograph.
is_forest() Check if the matching covered graph is a forest.
is_matching_covered() Check if the graph is matching covered.
is_path() Check whether the graph is a path.
is_subgraph() Check whether the matching covered graph is a subgraph of other.
is_tree() Check whether the matching covered graph is a tree.
join() Return the join of self and other.
lexicographic_product() Return the lexicographic product of self and other.
load_afile() Load the matching covered graph specified in the given file into the current object.
loop_edges() Return a list of all loops in the matching covered graph.
loop_vertices() Return a list of vertices with loops.
merge_vertices() Merge vertices.
number_of_loops() Return the number of edges that are loops.
random_subgraph() Return a random matching covered subgraph containing each vertex with probability p.
remove_loops() Remove loops on vertices in vertices.
save_afile() Save the graph to file in alist format.
strong_product() Return the strong product of self and other.
subdivide_edge() Subdivide an edge k times.
subdivide_edges() Subdivide k times edges from an iterable container.
subgraph() Return the matching covered subgraph containing the given vertices and edges.
subgraph_search() Return a copy of (matching covered) G in self.
subgraph_search_count() Return the number of labelled occurrences of matching covered G in self.
subgraph_search_iterator() Return an iterator over the labelled copies of (matching covered) G in self.
tensor_product() Return the tensor product of self and other.
to_undirected() Return an undirected Graph instance of the matching covered graph.
transitive_closure() Return the transitive closure of the matching covered graph.
transitive_reduction() Return a transitive reduction of the matching covered graph.
union() Return the union of self and other.
5. Implementing the Micali-Vazirani algorithm for finding a perfect matching in an undirected unweighted graph in :math:`\mathcal{O}(|E| \cdot \sqrt{|V|})`