-
Notifications
You must be signed in to change notification settings - Fork 0
/
path.go
88 lines (79 loc) · 1.77 KB
/
path.go
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
package graph
import (
"slices"
"github.com/ailidani/graph/queue"
)
//---------------------------
// Path between
//---------------------------
// PathsBetween finding all paths from source to destination
func PathsBetween[K comparable](g Graph[K], s, d Node[K]) [][]Node[K] {
all := make([][]Node[K], 0)
queue := queue.New[[]Node[K]]()
// current path
path := make([]Node[K], 0)
path = append(path, s)
queue.Push(path)
for queue.Size() != 0 {
path := queue.Pop()
last := path[len(path)-1]
if last.ID() == d.ID() {
all = append(all, path)
continue
}
for _, v := range g.From(last.ID()) {
if slices.Contains(path, v) {
continue
}
newPath := make([]Node[K], len(path))
copy(newPath, path)
newPath = append(newPath, v)
queue.Push(newPath)
}
}
return all
}
//---------------------------
// Path all
//---------------------------
func Paths[K comparable](g Graph[K], root Node[K]) [][]Node[K] {
all := make([][]Node[K], 0)
queue := queue.New[[]Node[K]]()
// current path
path := make([]Node[K], 0)
path = append(path, root)
queue.Push(path)
for queue.Size() != 0 {
path := queue.Pop()
last := path[len(path)-1]
// leaf node
if len(g.From(last.ID())) == 0 {
all = append(all, path)
continue
}
for _, v := range g.From(last.ID()) {
// cycle path
if slices.Contains(path, v) {
if !containsPath(all, path) {
all = append(all, path)
}
continue
}
newPath := make([]Node[K], len(path))
copy(newPath, path)
newPath = append(newPath, v)
queue.Push(newPath)
}
}
return all
}
func containsPath[K comparable](paths [][]Node[K], path []Node[K]) bool {
for _, i := range paths {
if slices.EqualFunc(i, path, func(a, b Node[K]) bool {
return a.ID() == b.ID()
}) {
return true
}
}
return false
}