graph/cyclic.go at main · ailidani/graph · GitHub

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

//---------------------------
// Cyclic
//---------------------------

type color int

const (
	white color = iota // unvisited nodes
	gray               // visiting nodes
	black              // visited nodes
)

func visit[K comparable](g Graph[K], v K, colors map[K]color) bool {
	colors[v] = gray
	for _, u := range g.From(v) {
		if colors[u.ID()] == gray {
			return true
		}
		if colors[u.ID()] == white && visit(g, u.ID(), colors) {
			return true
		}
	}
	colors[v] = black
	return false
}

// Cyclic returns true if the graph contains a cycle
func Cyclic[K comparable](g Graph[K]) bool {
	colors := make(map[K]color)
	// set all nodes color to white
	nodes := g.Nodes()
	for nodes.Next() {
		v := nodes.Node()
		colors[v.ID()] = white
	}

	nodes.Reset()
	for nodes.Next() {
		v := nodes.Node()
		if colors[v.ID()] == white {
			if visit(g, v.ID(), colors) {
				return true
			}
		}
	}
	return false
}

func CyclicNode[K comparable](g Graph[K], v K) bool {
	colors := make(map[K]color)
	// set all nodes color to white
	nodes := g.Nodes()
	for nodes.Next() {
		u := nodes.Node()
		colors[u.ID()] = white
	}
	return visit(g, v, colors)
}

// CyclePath returns the first cycle with vertices
func CyclePath[K comparable](g Graph[K]) []Node[K] {
	colors := make(map[K]color)
	// set all nodes color to white
	nodes := g.Nodes()
	for nodes.Next() {
		v := nodes.Node()
		colors[v.ID()] = white
	}

	nodes.Reset()
	for nodes.Next() {
		v := nodes.Node()
		if colors[v.ID()] == white {
			if visit(g, v.ID(), colors) {
				cycle := make([]Node[K], 0)
				for u, color := range colors {
					if color == gray {
						cycle = append(cycle, g.Node(u))
					}
				}
				return cycle
			}
		}
	}
	return nil
}