Liking cljdoc? Tell your friends :D

blossom.matching


is-matching?

(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.
sourceraw docstring

is-maximal-matching?

(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.
sourceraw docstring

is-perfect-matching?

(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.
sourceraw docstring

matching-to-set

(matching-to-set matching)
source

maximal-matching

(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.
sourceraw docstring

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close