-
Notifications
You must be signed in to change notification settings - Fork 0
/
MatchingGraph.ts
148 lines (104 loc) · 3.94 KB
/
MatchingGraph.ts
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
146
147
148
import Graph, { NotFoundGraphError, UndirectedGraph, UsageGraphError } from 'graphology'
import { AugmentingPath } from '../AugmentingPath'
import { Blossom } from '../blossoms/Blossom'
import { Matching } from '../Matching'
import { Node } from '../../graphs/Node'
type MatchingNodeAttributes = {
isSuperNode?: boolean
}
type MatchingEdgeAttributes = {
arePaired?: boolean
}
export class MatchingGraph extends UndirectedGraph<MatchingNodeAttributes, MatchingEdgeAttributes> {
static createFrom(graph: Graph) {
const blossomGraph = new MatchingGraph()
graph.forEachNode((node) => blossomGraph.addNode(node))
graph.forEachEdge((edge) => blossomGraph.addEdge(...graph.extremities(edge)))
return blossomGraph
}
static createCompressing(graph: MatchingGraph, blossom: Blossom) {
const copy = MatchingGraph.createFrom(graph)
graph.pairedEdges().forEach((e) => copy.pair(...graph.extremities(e)))
copy.compress(blossom)
return copy
}
pair(node1: Node, node2: Node) {
const edge = this.edgeOrFail(node1, node2)
this.setEdgeAttribute(edge, 'arePaired', true)
}
unpair(node1: Node, node2: Node) {
const edge = this.edgeOrFail(node1, node2)
this.setEdgeAttribute(edge, 'arePaired', false)
}
augmentWith(augmentingPath: AugmentingPath) {
let hasToPair = true
for (let i = 0; i + 1 < augmentingPath.length; i++) {
const [currentNode, nextNode] = [augmentingPath[i], augmentingPath[i + 1]]
if (hasToPair) this.pair(currentNode, nextNode)
else this.unpair(currentNode, nextNode)
hasToPair = !hasToPair
}
}
matching(): Matching {
return this.pairedEdges().map((edge) => this.extremities(edge))
}
pairedNodes(): Node[] {
return this.matching().flat()
}
isPaired(node: Node) {
return this.pairedNodes().includes(node)
}
unpairedNodes(): Node[] {
const pairedNodes = this.pairedNodes()
return this.nodes().filter((node) => !pairedNodes.includes(node))
}
neighborsThroughUnpairedEdges(node: Node): Node[] {
const nodeUnpairedEdges = this.filterEdges(node, (_, { arePaired }) => !arePaired)
return nodeUnpairedEdges.map((edge) => this.opposite(node, edge))
}
getMate(node: Node) {
const pairedEdge = this.findEdge(node, (_, { arePaired }) => arePaired)
if (!pairedEdge) return undefined
return this.opposite(node, pairedEdge)
}
getMateOrFail(node: Node) {
const mate = this.getMate(node)
if (!mate) throw new UsageGraphError(`mate for ${node} was not found`)
return mate
}
findNeighborOrFail(params: { for: Node; in: Node[] }) {
const { for: node, in: candidates } = params
const neighbor = candidates.find((candidate) => this.areNeighbors(candidate, node))
if (!neighbor) throw new UsageGraphError(`no neighbor found in [${candidates}] for ${node}`)
return neighbor
}
compress(blossom: Blossom) {
const { root, cycle } = blossom
const superNode = cycle.join('-')
this.addNode(superNode, { isSuperNode: true })
this.findBlossomNeighbors(blossom).forEach((superNodeNeighbor) =>
this.addEdge(superNode, superNodeNeighbor)
)
const rootMate = this.getMate(root)
if (rootMate) this.pair(rootMate, superNode)
cycle.forEach((node) => this.dropNode(node))
}
isSuperNode(node: Node) {
return Boolean(this.getNodeAttribute(node, 'isSuperNode'))
}
private findBlossomNeighbors(blossom: Blossom) {
const { cycle } = blossom
return cycle
.flatMap((nodeInsideBlossom) => this.neighbors(nodeInsideBlossom))
.filter((blossomNeighbor) => !blossom.has(blossomNeighbor))
.filter((node, i, nodes) => nodes.indexOf(node) === i) // remove duplicates
}
private pairedEdges() {
return this.filterEdges((_, { arePaired }) => arePaired)
}
private edgeOrFail(node1: Node, node2: Node) {
const edge = this.edge(node1, node2)
if (!edge) throw new NotFoundGraphError(`nodes ${node1}, ${node2} are not neighbors`)
return edge
}
}