-
Notifications
You must be signed in to change notification settings - Fork 1
/
matching.cljc
145 lines (121 loc) · 4.1 KB
/
matching.cljc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
(ns blossom.matching
(:require [clojure.spec.alpha :as s]
[blossom.endpoint :as endp]
[loom.graph :as lg]))
(defn maximal-matching
"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."
[g]
(as-> {:matching #{}
:nodes #{}} result
(reduce (fn [{:keys [nodes] :as result} [u v]]
(cond-> result
(and (not= u v)
(not (contains? nodes u))
(not (contains? nodes v)))
(-> (update :matching conj #{u v})
(update :nodes conj u v))))
result
(lg/edges g))
(get result :matching)))
(defn is-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."
[g matching]
(and (s/valid? :blossom/matching matching)
(let [{:keys [all-distinct all-edges]}
(reduce (fn [result [u v]]
(cond-> result
(some #{u v} (:nodes result))
(assoc :all-distinct false)
(not (lg/has-edge? g u v))
(assoc :all-edges false)
:true
(update :nodes conj u v)))
{:nodes #{}
:all-distinct true
:all-edges true}
(map vec matching))]
(and all-distinct all-edges))))
(defn is-perfect-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."
[g matching]
(let [incident-edges-freqs (->> matching
(mapcat identity)
frequencies
vals)]
(and (is-matching? g matching)
(every? #{1} incident-edges-freqs)
(= (count (lg/nodes g))
(count incident-edges-freqs)))))
(defn is-maximal-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."
[g matching]
(and (is-matching? g matching)
(not-any? true?
(map (fn [edge]
(and (not (contains? matching (set edge)))
(is-matching? g (conj matching (set edge)))))
(lg/edges g)))))
(defn matching-to-set [matching]
(reduce (fn [result [a b]]
(cond-> result
(and (endp/some-endp? a)
(endp/some-endp? b))
(conj #{a b})))
#{}
(map-indexed vector matching)))