Function generateTree

graph/lowestcommonancestor_test.go:149–201

()

}

func generateTree() *Tree {
	rnd := rand.New(rand.NewSource(time.Now().UnixNano()))

	const MAXVERTEX int = 2000
	var numbersVertex int = rnd.Intn(MAXVERTEX) + 1
	var root int = rnd.Intn(numbersVertex)
	var edges []TreeEdge

	var fullGraph []TreeEdge
	for u := 0; u < numbersVertex; u++ {
		for v := 0; v < numbersVertex; v++ {
			fullGraph = append(fullGraph, TreeEdge{
				from: u,
				to:   v,
			})
		}
	}
	rnd.Shuffle(len(fullGraph), func(i, j int) {
		fullGraph[i], fullGraph[j] = fullGraph[j], fullGraph[i]
	})

	par := make([]int, numbersVertex)
	for u := 0; u < numbersVertex; u++ {
		par[u] = u
	}

	var findp func(int) int
	findp = func(u int) int {
		if u == par[u] {
			return u
		} else {
			par[u] = findp(par[u])
			return par[u]
		}
	}

	join := func(u, v int) bool {
		u, v = findp(u), findp(v)
		if u == v {
			return false
		}
		par[v] = u
		return true
	}

	for _, e := range fullGraph {
		if join(e.from, e.to) == true {
			edges = append(edges, e)
		}
	}

	return NewTree(numbersVertex, root, edges)
}

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