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.

```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