graph/path: replace recursive dfs with iterative implementation
@@ -7,6 +7,7 @@ package path
import (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/traverse"
)
// Dominators returns immediate dominators for all nodes in the flow graph
@@ -30,7 +31,7 @@ func Dominators(root graph.Node, g graph.Directed) map[int64]graph.Node {
// step 1.
lt.dfs(g, root)
- for i := lt.n; i >= 2; i-- {
+ for i := len(lt.vertex) - 1; i >= 2; i-- {
w := lt.vertex[i]
wid := w.ID()
// step 2.
@@ -64,8 +65,7 @@ func Dominators(root graph.Node, g graph.Directed) map[int64]graph.Node {
}
// step 4.
- for i := 2; i <= lt.n; i++ {
- w := lt.vertex[i]
+ for _, w := range lt.vertex[2:] {
wid := w.ID()
if lt.dom[wid].ID() != lt.vertex[lt.semi[wid]].ID() {
lt.dom[wid] = lt.dom[lt.dom[wid].ID()]
@@ -116,24 +116,26 @@ type lengauerTarjan struct {
// Initially label[v] is v.
label map[int64]graph.Node
-
- n int
}
-func (lt *lengauerTarjan) dfs(g graph.Directed, v graph.Node) {
- vid := v.ID()
- lt.n++
- lt.semi[vid] = lt.n
- lt.label[vid] = v
- lt.vertex = append(lt.vertex, v)
- for _, w := range g.From(v) {
- wid := w.ID()
- if _, ok := lt.semi[wid]; !ok {
- lt.parent[wid] = v
- lt.dfs(g, w)
- }
- lt.pred[wid] = append(lt.pred[wid], v)
- }
+func (lt *lengauerTarjan) dfs(g graph.Directed, root graph.Node) {
+ df := traverse.DepthFirst{EdgeFilter: func(e graph.Edge) bool {
+ u := e.From()
+ vid := e.To().ID()
+ lt.pred[vid] = append(lt.pred[vid], u)
+ if _, ok := lt.semi[vid]; ok {
+ return false
+ }
+ lt.parent[vid] = u
+ return true
+ }}
+ df.Walk(g, root, func(u graph.Node) bool {
+ uid := u.ID()
+ lt.label[uid] = u
+ lt.semi[uid] = len(lt.vertex)
+ lt.vertex = append(lt.vertex, u)
+ return false
+ })
}
func (lt *lengauerTarjan) compress(v graph.Node) {
