graph/flow/control_flow_test.go

// Copyright ©2017 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package flow

import (
	"reflect"
	"sort"
	"testing"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/internal/ordered"
	"gonum.org/v1/gonum/graph/simple"
)

var dominatorsTests = []struct {
	n     graph.Node
	edges []simple.Edge

	want DominatorTree
}{
	{ // Example from Lengauer and Tarjan http://www.dtic.mil/dtic/tr/fulltext/u2/a054144.pdf fig 1.
		n: char('R'),
		edges: []simple.Edge{
			{F: char('A'), T: char('D')},
			{F: char('B'), T: char('A')},
			{F: char('B'), T: char('D')},
			{F: char('B'), T: char('E')},
			{F: char('C'), T: char('F')},
			{F: char('C'), T: char('G')},
			{F: char('D'), T: char('L')},
			{F: char('E'), T: char('H')},
			{F: char('F'), T: char('I')},
			{F: char('G'), T: char('I')},
			{F: char('G'), T: char('J')},
			{F: char('H'), T: char('E')},
			{F: char('H'), T: char('K')},
			{F: char('I'), T: char('K')},
			{F: char('J'), T: char('I')},
			{F: char('K'), T: char('I')},
			{F: char('K'), T: char('R')},
			{F: char('L'), T: char('H')},
			{F: char('R'), T: char('A')},
			{F: char('R'), T: char('B')},
			{F: char('R'), T: char('C')},
		},

		want: DominatorTree{
			root: char('R'),
			dominatorOf: map[int64]graph.Node{
				'A': char('R'),
				'B': char('R'),
				'C': char('R'),
				'D': char('R'),
				'E': char('R'),
				'F': char('C'),
				'G': char('C'),
				'H': char('R'),
				'I': char('R'),
				'J': char('G'),
				'K': char('R'),
				'L': char('D'),
			},
			dominatedBy: map[int64][]graph.Node{
				'C': {char('F'), char('G')},
				'D': {char('L')},
				'G': {char('J')},
				'R': {char('A'), char('B'), char('C'), char('D'), char('E'), char('H'), char('I'), char('K')},
			},
		},
	},
	{ // WP example: https://en.wikipedia.org/w/index.php?title=Dominator_(graph_theory)&oldid=758099236.
		n: simple.Node(1),
		edges: []simple.Edge{
			{F: simple.Node(1), T: simple.Node(2)},
			{F: simple.Node(2), T: simple.Node(3)},
			{F: simple.Node(2), T: simple.Node(4)},
			{F: simple.Node(2), T: simple.Node(6)},
			{F: simple.Node(3), T: simple.Node(5)},
			{F: simple.Node(4), T: simple.Node(5)},
			{F: simple.Node(5), T: simple.Node(2)},
		},

		want: DominatorTree{
			root: simple.Node(1),
			dominatorOf: map[int64]graph.Node{
				2: simple.Node(1),
				3: simple.Node(2),
				4: simple.Node(2),
				5: simple.Node(2),
				6: simple.Node(2),
			},
			dominatedBy: map[int64][]graph.Node{
				1: {simple.Node(2)},
				2: {simple.Node(3), simple.Node(4), simple.Node(5), simple.Node(6)},
			},
		},
	},
	{ // WP example with node IDs decremented by 1.
		n: simple.Node(0),
		edges: []simple.Edge{
			{F: simple.Node(0), T: simple.Node(1)},
			{F: simple.Node(1), T: simple.Node(2)},
			{F: simple.Node(1), T: simple.Node(3)},
			{F: simple.Node(1), T: simple.Node(5)},
			{F: simple.Node(2), T: simple.Node(4)},
			{F: simple.Node(3), T: simple.Node(4)},
			{F: simple.Node(4), T: simple.Node(1)},
		},

		want: DominatorTree{
			root: simple.Node(0),
			dominatorOf: map[int64]graph.Node{
				1: simple.Node(0),
				2: simple.Node(1),
				3: simple.Node(1),
				4: simple.Node(1),
				5: simple.Node(1),
			},
			dominatedBy: map[int64][]graph.Node{
				0: {simple.Node(1)},
				1: {simple.Node(2), simple.Node(3), simple.Node(4), simple.Node(5)},
			},
		},
	},
}

type char rune

func (n char) ID() int64      { return int64(n) }
func (n char) String() string { return string(n) }

func TestDominators(t *testing.T) {
	// The dominator functions are non-deterministic due
	// to map iteration ordering, so repeat the tests to
	// ensure consistent coverage. The value of 100 was
	// chosen empirically to have no observed reduction
	// in coverage in several hundred runs of go test -cover.
	for i := 0; i < 100; i++ {
		for _, test := range dominatorsTests {
			g := simple.NewDirectedGraph()
			for _, e := range test.edges {
				g.SetEdge(e)
			}

			for _, alg := range []struct {
				name string
				fn   func(graph.Node, graph.Directed) DominatorTree
			}{
				{"Dominators", Dominators},
				{"DominatorsSLT", DominatorsSLT},
			} {
				got := alg.fn(test.n, g)

				if !reflect.DeepEqual(got.Root(), test.want.root) {
					t.Errorf("unexpected dominator tree root from %s: got:%v want:%v",
						alg.name, got.root, test.want.root)
				}

				if !reflect.DeepEqual(got.dominatorOf, test.want.dominatorOf) {
					t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
						alg.name, got.dominatorOf, test.want.dominatorOf)
				}

				for q, want := range test.want.dominatorOf {
					node := got.DominatorOf(q)
					if node != want {
						t.Errorf("unexpected dominator tree result from %s dominated of %v: got:%v want:%v",
							alg.name, q, node, want)
					}
				}

				for _, nodes := range got.dominatedBy {
					sort.Sort(ordered.ByID(nodes))
				}

				if !reflect.DeepEqual(got.dominatedBy, test.want.dominatedBy) {
					t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
						alg.name, got.dominatedBy, test.want.dominatedBy)
				}

				for q, want := range test.want.dominatedBy {
					nodes := got.DominatedBy(q)
					if !reflect.DeepEqual(nodes, want) {
						t.Errorf("unexpected dominator tree result from %s dominated by %v: got:%v want:%v",
							alg.name, q, nodes, want)
					}
				}
			}
		}
	}
}