graph/path: replace map and slice index chasing with pointer chasing
MODIFY
graph/path/control_flow.go
graph/path/control_flow.go
package path
-import (
- "gonum.org/v1/gonum/graph"
- "gonum.org/v1/gonum/graph/internal/set"
-)
+import "gonum.org/v1/gonum/graph"
// Dominators returns a dominator tree for all nodes in the flow graph
// g starting from the given root node.
func Dominators(root graph.Node, g graph.Directed) DominatorTree {
- // The algorithm used here is the Lengauer and Tarjan
+ // The algorithm used here is essentially the Lengauer and Tarjan
// algorithm described in https://doi.org/10.1145%2F357062.357071
lt := lengauerTarjan{
- parent: make(map[int64]graph.Node),
- pred: make(map[int64][]graph.Node),
- semi: make(map[int64]int),
- vertex: make([]graph.Node, 1), // FIXME(kortschak): The current implementation requires non-zero node numbers.
- bucket: make(map[int64]set.Nodes),
- dom: make(map[int64]graph.Node),
-
- ancestor: make(map[int64]graph.Node),
- label: make(map[int64]graph.Node),
+ indexOf: make(map[int64]int),
}
// step 1.
lt.dfs(g, root)
- for i := lt.n; i >= 2; i-- {
- w := lt.vertex[i]
- wid := w.ID()
+ for i := len(lt.nodes) - 1; i > 0; i-- {
+ w := lt.nodes[i]
+
// step 2.
- for _, v := range lt.pred[wid] {
- uid := lt.eval(v).ID()
- if lt.semi[uid] < lt.semi[wid] {
- lt.semi[wid] = lt.semi[uid]
+ for _, v := range w.pred {
+ u := lt.eval(v)
+
+ if u.semi < w.semi {
+ w.semi = u.semi
}
}
- b, ok := lt.bucket[lt.vertex[lt.semi[wid]].ID()]
- if !ok {
- b = make(set.Nodes)
- lt.bucket[lt.vertex[lt.semi[wid]].ID()] = b
- }
- b.Add(w)
- lt.link(lt.parent[wid], w)
+ lt.nodes[w.semi].bucket[w] = struct{}{}
+ lt.link(w.parent, w)
// step 3.
- for _, v := range lt.bucket[lt.parent[wid].ID()] {
- vid := v.ID()
- lt.bucket[lt.parent[wid].ID()].Remove(v)
+ for v := range w.parent.bucket {
+ delete(w.parent.bucket, v)
+
u := lt.eval(v)
- if lt.semi[u.ID()] < lt.semi[vid] {
- lt.dom[vid] = u
+ if u.semi < v.semi {
+ v.dom = u
} else {
- lt.dom[vid] = lt.parent[wid]
+ v.dom = w.parent
}
}
-
}
// step 4.
- for i := 2; i <= lt.n; i++ {
- w := lt.vertex[i]
- wid := w.ID()
- if lt.dom[wid].ID() != lt.vertex[lt.semi[wid]].ID() {
- lt.dom[wid] = lt.dom[lt.dom[wid].ID()]
+ for _, w := range lt.nodes[1:] {
+ if w.dom.node.ID() != lt.nodes[w.semi].node.ID() {
+ w.dom = w.dom.dom
}
}
- delete(lt.dom, root.ID())
- nodes := make(set.Nodes)
- for _, n := range g.Nodes() {
- nodes.Add(n)
- }
+ // Construct the public-facing dominator tree structure.
+ dominatorOf := make(map[int64]graph.Node)
dominatedBy := make(map[int64][]graph.Node)
- for nid, d := range lt.dom {
- did := d.ID()
- dominatedBy[did] = append(dominatedBy[did], nodes[nid])
+ for _, w := range lt.nodes[1:] {
+ dominatorOf[w.node.ID()] = w.dom.node
+ did := w.dom.node.ID()
+ dominatedBy[did] = append(dominatedBy[did], w.node)
}
- return DominatorTree{root: root, dominatorOf: lt.dom, dominatedBy: dominatedBy}
+ return DominatorTree{root: root, dominatorOf: dominatorOf, dominatedBy: dominatedBy}
}
+// lengauerTarjan holds global state of the Lengauer-Tarjan algorithm.
+// This is a mapping between nodes and the postordering of the nodes.
type lengauerTarjan struct {
- // The vertex which is the parent of vertex w
+ // nodes is the nodes traversed during the
+ // Lengauer-Tarjan depth-first-search.
+ nodes []*ltNode
+ // indexOf contains a mapping between
+ // the id-dense representation of the
+ // graph and the potentially id-sparse
+ // nodes held in nodes.
+ //
+ // This corresponds to the vertex
+ // number of the node in the Lengauer-
+ // Tarjan algorithm.
+ indexOf map[int64]int
+}
+
+// ltNode is a graph node with accounting for the Lengauer-Tarjan
+// algorithm.
+//
+// For the purposes of documentation the ltNode is given the name w.
+type ltNode struct {
+ node graph.Node
+
+ // parent is vertex which is the parent of w
// in the spanning tree generated by the search.
- parent map[int64]graph.Node
+ parent *ltNode
- // The set of vertices v such that (v, w) is an edge
- // of the graph.
- pred map[int64][]graph.Node
+ // pred is the set of vertices v such that (v, w)
+ // is an edge of the graph.
+ pred []*ltNode
- // semi[w] is a number defined as follows:
- // (i) Before vertex w is numbered, semi[w] = 0, false.
- // (ii) After w is numbered but before its semidominator
- // is computed, semi[w] is the number of w.
- // (iii) After the semidominator of w is computed, semi[w]
+ // semi is a number defined as follows:
+ // (i) After w is numbered but before its semidominator
+ // is computed, semi is the number of w.
+ // (ii) After the semidominator of w is computed, semi
// is the number of the semidominator of w.
- semi map[int64]int
-
- // vertex[i] is the vertex whose number is i.
- vertex []graph.Node
+ semi int
- // bucket[w] is the set of vertices whose
+ // bucket is the set of vertices whose
// semidominator is w.
- bucket map[int64]set.Nodes
+ bucket map[*ltNode]struct{}
- // dom[w] is vertex defined as follows:
+ // dom is vertex defined as follows:
// (i) After step 3, if the semidominator of w is its
- // immediate dominator, then dom[w] is the immediate
- // dominator of w. Otherwise dom[w] is a vertex v
+ // immediate dominator, then dom is the immediate
+ // dominator of w. Otherwise dom is a vertex v
// whose number is smaller than w and whose immediate
// dominator is also w's immediate dominator.
- // (ii) After step 4, dom[w] is the immediate dominator of w.
- dom map[int64]graph.Node
-
- // In general ancestor[v] = 0 only if v is a tree root
- // in the forest; otherwise ancestor[v] is an ancestor
- // of v in the forest.
- ancestor map[int64]graph.Node
+ // (ii) After step 4, dom is the immediate dominator of w.
+ dom *ltNode
- // Initially label[v] is v.
- label map[int64]graph.Node
+ // In general ancestor is nil only if w is a tree root
+ // in the forest; otherwise ancestor is an ancestor
+ // of w in the forest.
+ ancestor *ltNode
- n int
+ // Initially label is w. It is adjusted during
+ // the algorithm to maintain invariant (3) in the
+ // Lengauer and Tarjan paper.
+ label *ltNode
}
+// dfs is the Lengauer-Tarjan DFS procedure.
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)
+ i := len(lt.nodes)
+ lt.indexOf[v.ID()] = i
+ ltv := &ltNode{
+ node: v,
+ semi: i,
+ bucket: make(map[*ltNode]struct{}),
+ }
+ ltv.label = ltv
+ lt.nodes = append(lt.nodes, ltv)
+
for _, w := range g.From(v) {
wid := w.ID()
- if _, ok := lt.semi[wid]; !ok {
- lt.parent[wid] = v
+
+ idx, ok := lt.indexOf[wid]
+ if !ok {
lt.dfs(g, w)
+
+ // We place this below the recursive call
+ // in contrast to the original algorithm
+ // since w needs to be initialised, and
+ // this happens in the child call to dfs.
+ idx, ok = lt.indexOf[wid]
+ if !ok {
+ panic("path: unintialized node")
+ }
+ lt.nodes[idx].parent = ltv
}
- lt.pred[wid] = append(lt.pred[wid], v)
+ ltw := lt.nodes[idx]
+ ltw.pred = append(ltw.pred, ltv)
}
}
-func (lt *lengauerTarjan) compress(v graph.Node) {
- vid := v.ID()
- if _, ok := lt.ancestor[lt.ancestor[vid].ID()]; ok {
- lt.compress(lt.ancestor[vid])
- if lt.semi[lt.label[lt.ancestor[vid].ID()].ID()] < lt.semi[lt.label[vid].ID()] {
- lt.label[vid] = lt.label[lt.ancestor[vid].ID()]
+// compress is the Lengauer-Tarjan COMPRESS procedure.
+func (lt *lengauerTarjan) compress(v *ltNode) {
+ if v.ancestor.ancestor != nil {
+ lt.compress(v.ancestor)
+ if v.ancestor.label.semi < v.label.semi {
+ v.label = v.ancestor.label
}
- lt.ancestor[vid] = lt.ancestor[lt.ancestor[vid].ID()]
+ v.ancestor = v.ancestor.ancestor
}
}
-func (lt *lengauerTarjan) eval(v graph.Node) graph.Node {
- vid := v.ID()
- if _, ok := lt.ancestor[vid]; !ok {
+// eval is the Lengauer-Tarjan EVAL function.
+func (lt *lengauerTarjan) eval(v *ltNode) *ltNode {
+ if v.ancestor == nil {
return v
}
lt.compress(v)
- return lt.label[vid]
+ return v.label
}
-func (lt *lengauerTarjan) link(v, w graph.Node) {
- lt.ancestor[w.ID()] = v
+// link is the Lengauer-Tarjan LINK procedure.
+func (*lengauerTarjan) link(v, w *ltNode) {
+ w.ancestor = v
}
// DominatorTree is a flow graph dominator tree.

graph/path: replace map and slice index chasing with pointer chasing