blossom.matching
is-matching?clj/s
(is-matching? g matching)Decides whether the given set represents a valid matching in G.
A matching in a graph is a set of edges in which no two distinct edges share a common endpoint.
Parameters
g : graph
matching : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
boolean Whether the given set represents a valid matching in the graph.
Decides whether the given set represents a valid matching in G.
A *matching* in a graph is a set of edges in which no two distinct
edges share a common endpoint.
Parameters
----------
`g` : graph
`matching` : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
-------
boolean
Whether the given set represents a valid matching
in the graph.is-maximal-matching?clj/s
(is-maximal-matching? g matching)Decides whether the given set represents a valid maximal matching in G.
A maximal matching in a graph is a matching in which adding any edge would cause the set to no longer be a valid matching.
Parameters
g : graph
matching : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
boolean Whether the given set represents a valid maximal matching in the graph.
Decides whether the given set represents a valid
maximal matching in G.
A *maximal matching* in a graph is a matching in which adding any
edge would cause the set to no longer be a valid matching.
Parameters
----------
`g` : graph
`matching` : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
-------
boolean
Whether the given set represents a valid maximal
matching in the graph.is-perfect-matching?clj/s
(is-perfect-matching? g matching)Decides whether the given set represents a valid perfect matching in g
A perfect matching in a graph is a matching in which exactly one edge is incident upon each vertex.
Parameters
g : graph
matching : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
boolean Whether the given set or dictionary represents a valid perfect matching in the graph.
Decides whether the given set represents a valid perfect matching in `g`
A *perfect matching* in a graph is a matching in which exactly one edge
is incident upon each vertex.
Parameters
----------
`g` : graph
`matching` : set
A set representing a matching. It must have elements
of the form #{u v}, where [u v] is an edge in the
matching.
Returns
-------
boolean
Whether the given set or dictionary represents a valid perfect
matching in the graph.maximal-matchingclj/s
(maximal-matching g)Find a maximal matching in the graph.
A matching is a subset of edges in which no node occurs more than once. A maximal matching cannot add more edges and still be a matching.
Parameters
g : Undirected graph
Returns
matching : set A maximal matching of the graph.
Notes
The algorithm greedily selects a maximal matching M of the graph G (i.e. no superset of M exists). It runs in $O(|E|)$ time.
Find a maximal matching in the graph.
A matching is a subset of edges in which no node occurs more than once.
A maximal matching cannot add more edges and still be a matching.
Parameters
----------
`g` : Undirected graph
Returns
-------
matching : set
A maximal matching of the graph.
Notes
-----
The algorithm greedily selects a maximal matching M of the graph G
(i.e. no superset of M exists). It runs in $O(|E|)$ time.cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close