graph-builder

1
package graph
2

3
import (
4
	"sort"
5
)
6

7
// DFS Поиск в глубину для невзвешенного графа
8
func (g *AbstractGraph[T]) DFS(start T, compare func(want T) bool) ([]*Node[T], bool) {
9
	var searchStack []*Node[T]
10
	for vert := range g.Graph {
11
		if vert.Name == start {
12
			searchStack = append(searchStack, vert)
13
			break
14
		}
15
	}
16
	for len(searchStack) != 0 {
17
		var vertex = searchStack[len(searchStack)-1]
18
		searchStack = searchStack[:len(searchStack)-1]
19
		if vertex.Mark != 1 {
20
			if compare(vertex.Name) {
21
				g.Unmark()
22
				g.Vertexes = append(g.Vertexes, vertex)
23
				return g.Vertexes, true
24
			}
25
			vertex.Mark = 1
26
			g.Vertexes = append(g.Vertexes, vertex)
27
			searchStack = append(searchStack, g.GetAdjacentVertices(vertex)...)
28
		}
29
	}
30
	g.Unmark()
31
	return nil, false
32
}
33

34
// BFS Поиск в ширину
35
func (g *AbstractGraph[T]) BFS(start T, compare func(want T) bool) ([]*Node[T], bool) {
36
	var searchQueue []*Node[T]
37
	for vert := range g.Graph {
38
		if vert.Name == start {
39
			searchQueue = append(searchQueue, vert)
40
			break
41
		}
42
	}
43
	for len(searchQueue) != 0 {
44
		var vertex = searchQueue[0]
45
		searchQueue = searchQueue[1:]
46
		if vertex.Mark != 1 {
47
			if compare(vertex.Name) {
48
				g.Unmark()
49
				g.Vertexes = append(g.Vertexes, vertex)
50
				return g.Vertexes, true
51
			}
52
			vertex.Mark = 1
53
			g.Vertexes = append(g.Vertexes, vertex)
54
			searchQueue = append(searchQueue, g.GetAdjacentVertices(vertex)...)
55
		}
56

57
	}
58
	g.Unmark()
59
	return nil, false
60
}
61

62
// Painting Раскраска графа
63
func (g *AbstractGraph[T]) Painting() map[T][]int {
64
	colors := randomColorsInRGB(len(g.Graph))
65
	i := 0
66
	var vList = make([]*Node[T], len(g.Graph))
67
	for vert := range g.Graph {
68
		vList[i] = vert
69
		i++
70
	}
71
	// сортируем список вершин по убыванию степени
72
	sort.Slice(vList, func(i, j int) bool {
73
		return vList[i].Power > vList[j].Power
74
	})
75
	i = 0
76
	var output = make(map[T][]int, len(g.Graph))
77
	// проходим по списку вершин
78
	for _, vert := range vList {
79
		if vert.Mark == 1 {
80
			continue
81
		}
82
		output[vert.Name] = colors[i]
83
		vert.Mark = 1
84
		subVerts := g.Graph[vert]
85
		// и еще раз, чтобы покрасить все несмежные
86
		for _, vertex := range vList {
87
			if !checkIfIn(subVerts, vertex) && vertex.Mark != 1 {
88
				output[vertex.Name] = colors[i]
89
				vertex.Mark = 1
90
			}
91
		}
92
		i++
93
	}
94
	g.Unmark()
95
	return output
96
}
97

98
// Cycle - поиск цикла в графе на основе поиска в глубину (TODO НЕ ДОДЕЛАНО, нужна помощь)
99
func (g *AbstractGraph[T]) Cycle(start T) []*Node[T] {
100
	var searchStack, output []*Node[T]
101
	var startNode *Node[T]
102
	for vert := range g.Graph {
103
		if vert.Name == start {
104
			searchStack = append(searchStack, vert)
105
			startNode = vert
106
			break
107
		}
108
	}
109
	for len(searchStack) != 0 {
110
		var vertex = searchStack[len(searchStack)-1]
111
		searchStack = searchStack[:len(searchStack)-1]
112
		if vertex.Mark != 1 {
113
			vertex.Mark = 1
114
			output = append(output, vertex)
115
			searchStack = append(searchStack, g.GetAdjacentVertices(vertex)...)
116
			if checkIfIn(g.Graph[vertex], startNode) && len(output) > 2 {
117
				output = append(output, startNode)
118
				return output
119
			}
120
		}
121
	}
122
	return nil
123
}
124

125
// Dijkstra Алгоритм Дейкстры поиска кратчайших путей из вершины в графе.
126
func (g *AbstractGraph[T]) Dijkstra(start, end T) map[*Node[T]]int {
127
	var processed []*Node[T]
128
	var endNode, _temp *Node[T]
129
	var nodeParents, vertCosts = make(map[*Node[T]]*Node[T], len(g.Graph)), make(map[*Node[T]]int, len(g.Graph))
130
	for vert := range g.Graph {
131
		if vert.Name == start {
132
			for kid := range g.Graph[vert] {
133
				nodeParents[kid] = vert
134
				vertCosts[kid] = g.Graph[vert][kid]
135
			}
136
		}
137
		if vert.Name == end {
138
			endNode = vert
139
		}
140
	}
141
	nodeParents[endNode] = nil
142
	_temp = findMinimalCostNode(vertCosts, processed)
143
	for _temp != nil {
144
		cost := vertCosts[_temp]
145
		neighbours := g.Graph[_temp]
146
		for node := range neighbours {
147
			newCost := cost + neighbours[node]
148
			if vertCosts[node] > newCost {
149
				vertCosts[node] = newCost
150
				nodeParents[node] = node
151
			}
152
		}
153
		processed = append(processed, _temp)
154
		_temp = findMinimalCostNode(vertCosts, processed)
155
	}
156
	return vertCosts
157
}
158