1// Copyright 2022 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package dag
6
7import (
8	"reflect"
9	"strings"
10	"testing"
11)
12
13func TestTranspose(t *testing.T) {
14	g := mustParse(t, diamond)
15	g.Transpose()
16	wantEdges(t, g, "a->b a->c a->d b->d c->d")
17}
18
19func TestTopo(t *testing.T) {
20	g := mustParse(t, diamond)
21	got := g.Topo()
22	// "d" is the root, so it's first.
23	//
24	// "c" and "b" could be in either order, but Topo is
25	// deterministic in reverse node definition order.
26	//
27	// "a" is a leaf.
28	wantNodes := strings.Fields("d c b a")
29	if !reflect.DeepEqual(wantNodes, got) {
30		t.Fatalf("want topo sort %v, got %v", wantNodes, got)
31	}
32}
33
34func TestTransitiveReduction(t *testing.T) {
35	t.Run("diamond", func(t *testing.T) {
36		g := mustParse(t, diamond)
37		g.TransitiveReduction()
38		wantEdges(t, g, "b->a c->a d->b d->c")
39	})
40	t.Run("chain", func(t *testing.T) {
41		const chain = `NONE < a < b < c < d; a, d < e;`
42		g := mustParse(t, chain)
43		g.TransitiveReduction()
44		wantEdges(t, g, "e->d d->c c->b b->a")
45	})
46}
47