-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.js
90 lines (80 loc) · 2.64 KB
/
graph.js
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
import Vertex from './vertex.js'
export default class Graph {
vertices = {}
constructor(words) {
for (let i = 0; i < words.length - 1; i++) {
const firstWord = words[i]
const secondWord = words[i + 1]
for (let j = 0; j < Math.min(firstWord.length, secondWord.length); j++) {
const firstChar = firstWord[j]
const secondChar = secondWord[j]
if (firstChar !== secondChar) {
const firstVert = this.vertices[firstChar] || new Vertex(firstChar)
const secondVert = this.vertices[secondChar] || new Vertex(secondChar)
firstVert.addOut(secondChar)
if (firstVert.outEdges.length > 1) {
firstVert.outEdges.sort(
(a, b) => {
const aVert = this.vertices[a]
const bVert = this.vertices[b]
return aVert.inEdges.length > bVert.inEdges.length ?
1 :
bVert.inEdges.length > aVert.inEdges.length ?
-1 : 0
}
)
}
secondVert.addIn(firstChar)
if (secondVert.inEdges.length > 1) {
secondVert.inEdges.sort(
(a, b) => {
const aVert = this.vertices[a]
const bVert = this.vertices[b]
if (!aVert || !bVert) {
return 0
}
return aVert.outEdges.length > bVert.outEdges.length ?
1 :
bVert.outEdges.length > aVert.outEdges.length ?
-1 : 0
}
)
}
this.vertices[firstChar] = firstVert
this.vertices[secondChar] = secondVert
break
}
}
}
}
get firstVertex () {
return this.vertices[
Object.keys(this.vertices).find(k => !this.vertices[k].inEdges.length)
]
}
get length() {
return Object.keys(this.vertices).length
}
reset() {
Object.keys(this.vertices).forEach(v => this.vertices[v].visited = false)
}
topologicalSort (current = this.firstVertex, result = []) {
current.visited = true
if (current.inEdges.length) {
for (let i = 0; i < current.inEdges.length; i++) {
if (!this.vertices[current.inEdges[i]].visited) {
this.topologicalSort(this.vertices[current.inEdges[i]], result)
}
}
}
result.push(current.value)
if (current.outEdges.length) {
for (let i = 0; i < current.outEdges.length; i++) {
if (!this.vertices[current.outEdges[i]].visited) {
this.topologicalSort(this.vertices[current.outEdges[i]], result)
}
}
}
return result
}
}