alg_test.go

     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  
     5  package dag
     6  
     7  import (
     8  	"reflect"
     9  	"strings"
    10  	"testing"
    11  )
    12  
    13  func 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  
    19  func 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  
    34  func 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
View as plain text