pkg/bufman/pkg/dag/dag_test.go

// Licensed to the Apache Software Foundation (ASF) under one or more
// contributor license agreements.  See the NOTICE file distributed with
// this work for additional information regarding copyright ownership.
// The ASF licenses this file to You under the Apache License, Version 2.0
// (the "License"); you may not use this file except in compliance with
// the License.  You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package dag

// Largely adopted from https://github.com/stevenle/topsort, with modifications.
//
// Copyright 2013 Steven Le. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// See https://github.com/stevenle/topsort/blob/master/LICENSE.

import (
	"testing"
)

import (
	"github.com/stretchr/testify/require"
)

func TestTopoSort(t *testing.T) {
	t.Parallel()
	testTopoSortSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "c")
		},
		"a",
		[]string{"c", "b", "a"},
	)
}

func TestTopoSort2(t *testing.T) {
	t.Parallel()
	testTopoSortSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "c")
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "c")
		},
		"a",
		[]string{"c", "b", "a"},
	)
}

func TestTopoSort3(t *testing.T) {
	t.Parallel()
	testTopoSortSuccess(
		t,
		func(graph *Graph[string]) {
			// e -> b not part of traversal to a on purpose
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("d", "c")
			graph.AddEdge("c", "b")
			graph.AddEdge("e", "b")
		},
		"a",
		[]string{"b", "c", "d", "a"},
	)
}

func TestTopoSortCycleError(t *testing.T) {
	t.Parallel()
	testTopoSortCycleError(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "a")
		},
		"a",
		[]string{"a", "b", "a"},
	)
}

func TestTopoSortCycleError2(t *testing.T) {
	t.Parallel()
	testTopoSortCycleError(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "a")
		},
		"a",
		[]string{"a", "b", "c", "a"},
	)
}

func TestTopoSortCycleError3(t *testing.T) {
	t.Parallel()
	testTopoSortCycleError(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "b")
		},
		"a",
		[]string{"b", "c", "b"},
	)
}

func TestWalkEdges(t *testing.T) {
	t.Parallel()
	testWalkEdgesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("b", "c")
			graph.AddEdge("a", "c")
			graph.AddEdge("a", "b")
		},
		[]stringEdge{
			{
				From: "a",
				To:   "c",
			},
			{
				From: "a",
				To:   "b",
			},
			{
				From: "b",
				To:   "c",
			},
		},
	)
}

func TestWalkEdges2(t *testing.T) {
	t.Parallel()
	testWalkEdgesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
		},
		[]stringEdge{
			{
				From: "a",
				To:   "b",
			},
			{
				From: "b",
				To:   "c",
			},
			{
				From: "c",
				To:   "d",
			},
			{
				From: "a",
				To:   "d",
			},
		},
	)
}

func TestWalkEdges3(t *testing.T) {
	t.Parallel()
	testWalkEdgesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
		},
		[]stringEdge{
			{
				From: "a",
				To:   "b",
			},
			{
				From: "b",
				To:   "c",
			},
			{
				From: "c",
				To:   "d",
			},
			{
				From: "a",
				To:   "d",
			},
			{
				From: "e",
				To:   "b",
			},
		},
	)
}

func TestWalkEdgesCycleError(t *testing.T) {
	t.Parallel()
	testWalkEdgesCycleError(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddEdge("d", "b")
		},
		[]string{"b", "c", "d", "b"},
	)
}

func TestWalkEdgesCycleError2(t *testing.T) {
	t.Parallel()
	testWalkEdgesCycleError(
		t,
		func(graph *Graph[string]) {
			// there are no sources
			graph.AddEdge("a", "b")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddEdge("d", "e")
			graph.AddEdge("d", "a")
		},
		[]string{"b", "c", "d", "e", "b"},
	)
}

func TestWalkNodes(t *testing.T) {
	t.Parallel()
	testWalkNodesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddNode("f")
		},
		[]stringNode{
			{
				Key:      "a",
				Inbound:  []string{},
				Outbound: []string{"b", "d"},
			},
			{
				Key:      "b",
				Inbound:  []string{"a", "e"},
				Outbound: []string{"c"},
			},
			{
				Key:      "d",
				Inbound:  []string{"a", "c"},
				Outbound: []string{},
			},
			{
				Key:      "c",
				Inbound:  []string{"b"},
				Outbound: []string{"d"},
			},
			{
				Key:      "e",
				Inbound:  []string{},
				Outbound: []string{"b"},
			},
			{
				Key:      "f",
				Inbound:  []string{},
				Outbound: []string{},
			},
		},
	)
}

func TestNumNodes(t *testing.T) {
	t.Parallel()
	testNumNodesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddNode("f")
		},
		6,
	)
}

func TestNumEdges(t *testing.T) {
	t.Parallel()
	testNumEdgesSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddNode("f")
		},
		5,
	)
}

func TestDOTString(t *testing.T) {
	t.Parallel()
	testDOTStringSuccess(
		t,
		func(graph *Graph[string]) {
			graph.AddEdge("a", "b")
			graph.AddEdge("a", "d")
			graph.AddEdge("b", "c")
			graph.AddEdge("c", "d")
			graph.AddEdge("e", "b")
			graph.AddNode("f")
		},
		`digraph {

  1 [label="a"]
  2 [label="b"]
  3 [label="c"]
  4 [label="d"]
  5 [label="e"]
  6 [label="f"]

  1 -> 2
  2 -> 3
  3 -> 4
  1 -> 4
  5 -> 2
  6

}`,
	)
}

func testTopoSortSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	start string,
	expected []string,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	results, err := graph.TopoSort(start)
	require.NoError(t, err)
	require.Equal(t, expected, results)
}

func testTopoSortCycleError(
	t *testing.T,
	setupGraph func(*Graph[string]),
	start string,
	expectedCycle []string,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	_, err := graph.TopoSort(start)
	require.Equal(
		t,
		&CycleError[string]{
			Keys: expectedCycle,
		},
		err,
	)
}

func testWalkEdgesSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expected []stringEdge,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	var results []stringEdge
	err := graph.WalkEdges(
		func(from string, to string) error {
			results = append(
				results,
				stringEdge{
					From: from,
					To:   to,
				},
			)
			return nil
		},
	)
	require.NoError(t, err)
	require.Equal(t, expected, results)
}

func testWalkEdgesCycleError(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expectedCycle []string,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	err := graph.WalkEdges(func(string, string) error { return nil })
	require.Equal(
		t,
		&CycleError[string]{
			Keys: expectedCycle,
		},
		err,
	)
}

func testWalkNodesSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expected []stringNode,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	var results []stringNode
	err := graph.WalkNodes(
		func(key string, inbound []string, outbound []string) error {
			results = append(
				results,
				stringNode{
					Key:      key,
					Inbound:  inbound,
					Outbound: outbound,
				},
			)
			return nil
		},
	)
	require.NoError(t, err)
	require.Equal(t, expected, results)
}

func testNumNodesSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expected int,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	require.Equal(t, expected, graph.NumNodes())
}

func testNumEdgesSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expected int,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	require.Equal(t, expected, graph.NumEdges())
}

func testDOTStringSuccess(
	t *testing.T,
	setupGraph func(*Graph[string]),
	expected string,
) {
	graph := &Graph[string]{}
	setupGraph(graph)
	s, err := graph.DOTString(func(key string) string { return key })
	require.NoError(t, err)
	require.Equal(t, expected, s)
}

type stringEdge struct {
	From string
	To   string
}

type stringNode struct {
	Key      string
	Inbound  []string
	Outbound []string
}