-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs.go
154 lines (126 loc) · 4.51 KB
/
dfs.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
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
149
150
151
152
153
154
package algo
import (
"github.com/vc-souza/gga/ds"
)
/*
A DFNode node represents a node in a Depth-First tree in a Depth-First forest, holding
the attributes produced by a DFS, for a particular vertex. At the end of the DFS, every
vertex is part of one of the DF trees in the DF forest produced by the algorithm.
*/
type DFNode struct {
// Discovery records when the vertex was marked as discovered.
Discovery int
// Finish records when the vertex was marked as fully explored.
Finish int
/*
Parent holds the vertex that discovered this vertex, with the edge (v.Parent, v) being called a tree edge.
This is how the DF tree that this vertex is a part of is encoded: by following the parent pointers from
this vertex, one can get to the root of the DF tree.
After a DFS, every root of a DF tree in the DF forest will have a nil Parent.
*/
Parent int
visited bool
}
/*
A DFForest is one of the results of a DFS, representing a forest of DF trees (connected acyclic subgraphs),
with each DF tree being composed of all (at the time) unvisited vertices that were reachable from the root
of the DF tree, during the execution of the DFS.
Slightly different trees can be generated for the same graph, if the visiting order for either vertices
or edges is changed.
The gga graph implementation guarantees both vertex and edge traversal in insertion order,
so repeated DFS calls always produce the same DF forest.
*/
type DFForest []DFNode
func classifyDirectedEdge(fst DFForest, tps *EdgeTypes, e ds.GE) {
// the vertex being reached (Dst) was discovered before
// the vertex being explored (Src), so Dst is either
// an ancestor of Src, or they do not have a direct
// ancestor/descendant relationship
if fst[e.Src].Discovery >= fst[e.Dst].Discovery {
// ancestor/descendant relationship,
// self-loops included here
if fst[e.Dst].Finish == 0 {
tps.Back = append(tps.Back, e)
} else {
tps.Cross = append(tps.Cross, e)
}
} else {
// Src is an ancestor of Dst, and since Dst has
// been discovered before, this is a Forward edge
tps.Forward = append(tps.Forward, e)
}
}
func classifyUndirectedEdge(fst DFForest, tps *EdgeTypes, e ds.GE) {
// due to how adjacency lists work, undirected
// graphs represent the same edge twice, so
// if we're dealing with the reverse of a tree
// edge, then do not flag the reverse edge as
// being a back edge
if fst[e.Src].Parent == e.Dst {
return
}
// undirected graphs only have tree and back edges
// even if this looks like a forward edge from one
// side, it will be classified as a back edge
// when the reverse edge gets classified
tps.Back = append(tps.Back, e)
}
/*
DFS implements the Depth-First Search (DFS) algorithm.
Given a graph, DFS eventually explores every vertex, building a DF forest that holds DF trees.
The search is conducted using a depth-first approach: given a vertex, one adjacent vertex
and all of its descendants need to be fully explored before the next adjacent vertex
(and all of its descendants) can be explored. After all of its adjacent vertices are
explored, then a vertex can be marked as fully explored.
During its execution, DFS will record and assign both discovery and finish times to each vertex,
which can later be used to infer ancestor/descendant relationships between vertices in the forest.
Certain implementations of DFS (like this one) can also classify edges (in addition to tree edges)
according to the DF forest generated by the algorithm:
- Forward Edges: Connect an ancestor to a descendant in the same tree.
- Back Edges: Connect a descendant to an ancestor in the same tree.
- Cross Edges: Either connect vertices in different trees,
or non ancestor/descendant vertices in the same tree.
Expectations:
- The graph is correctly built.
Complexity:
- Time: Θ(V + E)
- Space (without edge classification): Θ(V)
- Space (wit edge classification): Θ(V) + O(E)
*/
func DFS(g *ds.G, classify bool) (DFForest, EdgeTypes, error) {
var visit func(int)
fst := make(DFForest, g.VertexCount())
tps := EdgeTypes{}
t := 0
for v := range g.V {
fst[v].Parent = -1
}
visit = func(v int) {
t++
fst[v].Discovery = t
fst[v].visited = true
for _, e := range g.V[v].E {
if fst[e.Dst].visited {
if !classify {
continue
}
if g.Directed() {
classifyDirectedEdge(fst, &tps, e)
} else {
classifyUndirectedEdge(fst, &tps, e)
}
} else {
fst[e.Dst].Parent = v
visit(e.Dst)
}
}
t++
fst[v].Finish = t
}
for v := range g.V {
if !fst[v].visited {
visit(v)
}
}
return fst, tps, nil
}