Function generateQuery

graph/lowestcommonancestor_test.go:203–230

(tree *Tree)

}

func generateQuery(tree *Tree) []Query {
	rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
	const MAXQUERY = 50
	var queries []Query

	bruteforceLCA := func(u, v int) int {
		for u != v {
			if tree.GetDepth(u) > tree.GetDepth(v) {
				u = tree.GetDad(u)
			} else {
				v = tree.GetDad(v)
			}
		}
		return u
	}

	for q := 1; q <= MAXQUERY; q++ {
		u := rnd.Intn(tree.numbersVertex)
		v := rnd.Intn(tree.numbersVertex)
		queries = append(queries, Query{
			u:        u,
			v:        v,
			expected: bruteforceLCA(u, v),
		})
	}

	return queries
}

// Test with the tree with up to 2000 vertices.
func TestLCAWithLargeTree(t *testing.T) {