Liking cljdoc? Tell your friends :D

## blossom.max-weight-matching

#### initialize-context

``(initialize-context edges options)``
source

#### max-weight-matching

``(max-weight-matching edges)``
``(max-weight-matching edges opts)``

Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once. The weight of a matching is the sum of the weights of its edges. A maximal matching cannot add more edges and still be a matching. The cardinality of a matching is the number of matched edges.

## Parameters

`edges` : Edges of an undirected graph. A sequence of tuples [i j wt] describing an undirected edge between vertex i and vertex j with weight wt. There is at most one edge between any two vertices; no vertex has an edge to itself. Vertices are identified by consecutive, non-negative integers. `opts` : option map

## Options

max-cardinality: boolean, optional (default=false) If max-cardinality is true, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings. check-optimum: boolean, optional (default=false) Check optimality of solution before returning; only works on integer weights.

## Returns

matching : collection A maximal matching of the graph in the form of a collection of unique vertices pairs.

```Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once.
The weight of a matching is the sum of the weights of its edges.
A maximal matching cannot add more edges and still be a matching.
The cardinality of a matching is the number of matched edges.

Parameters
----------
`edges` : Edges of an undirected graph. A sequence of tuples [i j wt]
describing an undirected edge between vertex i and vertex j with weight wt.
There is at most one edge between any two vertices; no vertex has an edge to itself.
Vertices are identified by consecutive, non-negative integers.
`opts` : option map

Options
----------
max-cardinality: boolean, optional (default=false)
If max-cardinality is true, compute the maximum-cardinality matching
with maximum weight among all maximum-cardinality matchings.
check-optimum: boolean, optional (default=false)
Check optimality of solution before returning; only works on integer weights.

Returns
-------
matching : collection
A maximal matching of the graph in the form of a collection of unique vertices
pairs.

Notes
-----
This function takes time O(number_of_nodes ** 3).

If all edge weights are integers, the algorithm uses only integer
computations.  If floating point weights are used, the algorithm
could return a slightly suboptimal matching due to numeric
precision errors.

This method is based on the "blossom" method for finding augmenting
paths and the "primal-dual"  method for finding a matching of maximum
weight, both methods invented by Jack Edmonds _.

References
----------
..  "Efficient Algorithms for Finding Maximum Matching in Graphs",
Zvi Galil, ACM Computing Surveys, 1986.```
sourceraw docstring

#### max-weight-matching-impl

``````(max-weight-matching-impl edges
{:keys [max-cardinality check-optimum],
:or {max-cardinality false,
check-optimum false},
:as opts})``````
source

#### PMaxWeightMatchingImplprotocol

##### act-on-minimum-delta
``(act-on-minimum-delta ctx delta-type delta-edge delta-blossom)``
``(add-blossom ctx base k)``

Construct a new blossom with given `base`, containing edge k which connects a pair of S vertices. Label the new blossom as S; set its dual variable to zero; relabel its T-vertices to S and add them to the queue. Returns an updated `context`.

```Construct a new blossom with given `base`, containing edge k which
connects a pair of S vertices. Label the new blossom as S; set its dual
variable to zero; relabel its T-vertices to S and add them to the queue.
Returns an updated `context`.```

##### assign-label
``(assign-label ctx w t p)``

Assign label `t` to the top-level blossom containing vertex `w`, and record the fact that w was reached through the edge with remote enpoint `p`. Returns an updated `context`.

```Assign label `t` to the top-level blossom containing vertex `w`,
and record the fact that w was reached through the edge with
remote enpoint `p`.
Returns an updated `context`.```

##### augment-blossom
``(augment-blossom ctx b v)``

Swap matched/unmatched edges over an alternating path through blossom `b` between vertex `v` and the base vertex. Keep blossom bookkeeping consistent.

```Swap matched/unmatched edges over an alternating path through blossom `b`
between vertex `v` and the base vertex. Keep blossom bookkeeping
consistent.```

##### augment-blossom-step
``(augment-blossom-step ctx b j x)``
##### augment-matching
``(augment-matching ctx k)``

Swap matched/unmatched edges over an alternating path between two single vertices. The augmenting path runs through S-vertices `v` and `w`. Returns an updated `context`.

```Swap matched/unmatched edges over an alternating path between two
single vertices. The augmenting path runs through S-vertices `v` and `w`.
Returns an updated `context`.```

##### blossom-loop-direction
``(blossom-loop-direction ctx b entry-child)``
##### calc-slack
``(calc-slack ctx k)``

Returns a map with keys kslack and context. kslack is the slack for edge k context is and context is an updated context with a modified allow-edge cache.

```Returns a map with keys kslack and context.
kslack is the slack for edge k context is and context is an updated context
with a modified allow-edge cache.```

##### consider-loose-edge-to-free-vertex
``(consider-loose-edge-to-free-vertex ctx w k kslack)``

w is a free vertex (or an unreached vertex inside a T-blossom) but we can not reach it yet; keep track of the least-slack edge that reaches w.

```w is a free vertex (or an unreached vertex inside
a T-blossom) but we can not reach it yet;
keep track of the least-slack edge that reaches w.```

##### consider-loose-edge-to-s-blossom
``(consider-loose-edge-to-s-blossom ctx bv k kslack)``

keep track of the least-slack non-allowable edge to a different S-blossom.

```keep track of the least-slack non-allowable edge to
a different S-blossom.```

##### consider-tight-edge
``(consider-tight-edge ctx p v)``
##### entry-child
``(entry-child ctx b)``
##### expand-blossom
``(expand-blossom ctx b endstage)``

Expand the given top-level blossom. Returns an updated `context`.

```Expand the given top-level blossom.
Returns an updated `context`.```

##### expand-tight-sblossoms
``(expand-tight-sblossoms ctx)``
##### find-augmenting-path
``(find-augmenting-path ctx)``
##### find-parent-blossoms
``(find-parent-blossoms ctx b)``
##### first-labeled-blossom-leaf
``(first-labeled-blossom-leaf ctx bv)``
##### immediate-subblossom-of
``(immediate-subblossom-of ctx v b)``

Starting from a vertex `v`, ascend the blossom tree, and return the sub-blossom immediately below `b`.

```Starting from a vertex `v`, ascend the blossom tree, and
return the sub-blossom immediately below `b`.```

##### initialize-stage
``(initialize-stage ctx)``
##### match-endpoint
``(match-endpoint ctx p)``

Add endpoint p's edge to the matching.

```Add endpoint p's edge to the matching.
```

##### mate-endps-to-vertices
``(mate-endps-to-vertices ctx)``

Transform mate[] such that mate[v] is the vertex to which v is paired. Return the updated mate[] sequence

```Transform mate[] such that mate[v] is the vertex to which v is paired. Return the updated mate[] sequence
```

##### move-back-to-entry-child-relabeling
``(move-back-to-entry-child-relabeling ctx b)``
##### move-to-base-relabeling
``(move-to-base-relabeling ctx b)``
##### promote-sub-blossoms-to-top-blossoms
``(promote-sub-blossoms-to-top-blossoms ctx b endstage)``
##### recycle-blossom
``(recycle-blossom ctx b)``
##### relabel-base-t-subblossom
``(relabel-base-t-subblossom ctx b p)``
##### scan-blossom
``(scan-blossom ctx v w)``

Trace back from vertices `v` and `w` to discover either a new blossom or an augmenting path. Return the base vertex of the new blossom, or NO-NODE if an augmenting path was found.

```Trace back from vertices `v` and `w` to discover either a new blossom
or an augmenting path. Return the base vertex of the new blossom,
or NO-NODE if an augmenting path was found.```

##### scan-neighbors
``(scan-neighbors ctx v)``
##### trace-to-base
``(trace-to-base ctx v bb)``
##### valid-matching?
``(valid-matching? ctx matching)``

Check if the matching is symmetric

```Check if the matching is symmetric
```

##### verify-optimum
``(verify-optimum ctx)``

Verify that the optimum solution has been reached.

```Verify that the optimum solution has been reached.
```

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

× close