Liking cljdoc? Tell your friends :D

blossom.max-weight-matching


initialize-contextclj/s

(initialize-context edges options)
source

max-weight-matchingclj/s

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

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.

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

max-weight-matching-implclj/s

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

PMaxWeightMatchingImplclj/sprotocol

blossom-loop-directionclj/s

(blossom-loop-direction ctx b entry-child)

act-on-minimum-deltaclj/s

(act-on-minimum-delta ctx delta-type delta-edge delta-blossom)

consider-tight-edgeclj/s

(consider-tight-edge ctx p v)

promote-sub-blossoms-to-top-blossomsclj/s

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

recycle-blossomclj/s

(recycle-blossom ctx b)

scan-blossomclj/s

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

find-parent-blossomsclj/s

(find-parent-blossoms ctx b)

first-labeled-blossom-leafclj/s

(first-labeled-blossom-leaf ctx bv)

trace-to-baseclj/s

(trace-to-base ctx v bb)

expand-tight-sblossomsclj/s

(expand-tight-sblossoms ctx)

augment-blossomclj/s

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

find-augmenting-pathclj/s

(find-augmenting-path ctx)

mate-endps-to-verticesclj/s

(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

immediate-subblossom-ofclj/s

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

expand-blossomclj/s

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

consider-loose-edge-to-s-blossomclj/s

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

augment-matchingclj/s

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

calc-slackclj/s

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

move-to-base-relabelingclj/s

(move-to-base-relabeling ctx b)

initialize-stageclj/s

(initialize-stage ctx)

valid-matching?clj/s

(valid-matching? ctx matching)

Check if the matching is symmetric

Check if the matching is symmetric

augment-blossom-stepclj/s

(augment-blossom-step ctx b j x)

match-endpointclj/s

(match-endpoint ctx p)

Add endpoint p's edge to the matching.

Add endpoint p's edge to the matching.

assign-labelclj/s

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

verify-optimumclj/s

(verify-optimum ctx)

Verify that the optimum solution has been reached.

Verify that the optimum solution has been reached.

entry-childclj/s

(entry-child ctx b)

relabel-base-t-subblossomclj/s

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

add-blossomclj/s

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

move-back-to-entry-child-relabelingclj/s

(move-back-to-entry-child-relabeling ctx b)

scan-neighborsclj/s

(scan-neighbors ctx v)

consider-loose-edge-to-free-vertexclj/s

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

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

× close