Liking cljdoc? Tell your friends :D

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

`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

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.

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

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 [1]_.

.. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs", Zvi Galil, ACM Computing Surveys, 1986.

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 [1]_. References ---------- .. [1] "Efficient Algorithms for Finding Maximum Matching in Graphs", Zvi Galil, ACM Computing Surveys, 1986.

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

`(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 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 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 ctx b j x)`

`(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 ctx b entry-child)`

`(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 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 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 ctx p v)`

`(entry-child ctx b)`

`(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 ctx)`

`(find-augmenting-path ctx)`

`(find-parent-blossoms ctx b)`

`(first-labeled-blossom-leaf ctx bv)`

`(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 ctx)`

`(match-endpoint ctx p)`

Add endpoint p's edge to the matching.

Add endpoint p's edge to the matching.

`(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 ctx b)`

`(move-to-base-relabeling ctx b)`

`(promote-sub-blossoms-to-top-blossoms ctx b endstage)`

`(recycle-blossom ctx b)`

`(relabel-base-t-subblossom ctx b p)`

`(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 ctx v)`

`(trace-to-base ctx v bb)`

`(valid-matching? ctx matching)`

Check if the matching is symmetric

Check if the matching is symmetric

`(verify-optimum ctx)`

Verify that the optimum solution has been reached.

Verify that the optimum solution has been reached.

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