order_sort_subgraph_test.go

package dagro

import (
	"reflect"
	"testing"
)

func newSortSubgraphTestGraph(t *testing.T) (*Graph, *Graph) {
	t.Helper()
	g := newOrderTestGraph(true)
	for i, v := range []string{"0", "1", "2", "3", "4"} {
		g.SetNode(v, Attrs{"order": float64(i)})
	}
	return g, NewGraph()
}

func setOrderTestParents(t *testing.T, g *Graph, children []string, parent string) {
	t.Helper()
	for _, child := range children {
		if err := g.SetParent(child, parent); err != nil {
			t.Fatal(err)
		}
	}
}

func TestSortSubgraph(t *testing.T) {
	t.Run("flat barycenter sort", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetEdge("3", "x")
		g.SetEdge("1", "y", Attrs{"weight": float64(2)})
		g.SetEdge("4", "y")
		setOrderTestParents(t, g, []string{"x", "y"}, "movable")
		if got, want := sortSubgraph(g, "movable", cg, false).VS, []string{"y", "x"}; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("preserves node without neighbors", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetEdge("3", "x")
		g.SetNode("y")
		g.SetEdge("1", "z", Attrs{"weight": float64(2)})
		g.SetEdge("4", "z")
		setOrderTestParents(t, g, []string{"x", "y", "z"}, "movable")
		if got, want := sortSubgraph(g, "movable", cg, false).VS, []string{"z", "y", "x"}; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("tie bias", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetEdge("1", "x")
		g.SetEdge("1", "y")
		setOrderTestParents(t, g, []string{"x", "y"}, "movable")
		left := sortSubgraph(g, "movable", cg, false)
		if got, want := left.VS, []string{"x", "y"}; !reflect.DeepEqual(got, want) {
			t.Fatalf("left-biased sort = %v, want %v", got, want)
		}
		if !left.UsedBias {
			t.Fatal("equal non-edge barycenters did not report bias use")
		}
		right := sortSubgraph(g, "movable", cg, true)
		if got, want := right.VS, []string{"y", "x"}; !reflect.DeepEqual(got, want) {
			t.Fatalf("right-biased sort = %v, want %v", got, want)
		}
		if !right.UsedBias {
			t.Fatal("equal non-edge barycenters did not report bias use")
		}
	})

	t.Run("keeps reversed parallel edge dummies together", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		edge := Edge{V: "a", W: "b", Name: "parallel", HasName: true}
		g.SetNode("x", Attrs{
			"dummy": "edge", "edgeObj": edge, "edgeLabel": Attrs{},
		})
		g.SetNode("y", Attrs{
			"dummy": "edge", "edgeObj": edge, "edgeLabel": Attrs{"reversed": true},
		})
		g.SetEdge("1", "x")
		g.SetEdge("1", "y")
		setOrderTestParents(t, g, []string{"x", "y"}, "movable")

		got := sortSubgraph(g, "movable", cg, true)
		if want := []string{"x", "y"}; !reflect.DeepEqual(got.VS, want) {
			t.Fatalf("reversed-pair sort = %v, want %v", got.VS, want)
		}
		if got.UsedBias {
			t.Fatal("reversed edge pair incorrectly reported bias use")
		}
	})

	t.Run("preserves three same-direction parallel dummies", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		edge := Edge{V: "a", W: "b", Name: "parallel", HasName: true}
		for _, v := range []string{"x", "y", "z"} {
			g.SetNode(v, Attrs{
				"dummy": "edge", "edgeObj": edge, "edgeLabel": Attrs{},
			})
			g.SetEdge("1", v)
		}
		setOrderTestParents(t, g, []string{"x", "y", "z"}, "movable")

		got := sortSubgraph(g, "movable", cg, true)
		if want := []string{"z", "y", "x"}; !reflect.DeepEqual(got.VS, want) {
			t.Fatalf("three-parallel sort = %v, want %v", got.VS, want)
		}
		if !got.UsedBias {
			t.Fatal("same-direction parallel tie did not report bias use")
		}
	})

	t.Run("preserves multiple reversed partners for one forward dummy", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		edge := Edge{V: "a", W: "b", Name: "parallel", HasName: true}
		g.SetNode("forward", Attrs{
			"dummy": "edge", "edgeObj": edge, "edgeLabel": Attrs{},
		})
		for _, v := range []string{"reverse-1", "reverse-2"} {
			g.SetNode(v, Attrs{
				"dummy": "edge", "edgeObj": edge, "edgeLabel": Attrs{"reversed": true},
			})
		}
		for _, v := range []string{"forward", "reverse-1", "reverse-2"} {
			g.SetEdge("1", v)
		}
		setOrderTestParents(t, g, []string{"forward", "reverse-1", "reverse-2"}, "movable")

		got := sortSubgraph(g, "movable", cg, false)
		want := []string{"forward", "reverse-2", "reverse-1"}
		if !reflect.DeepEqual(got.VS, want) {
			t.Fatalf("multi-reversed-pair sort = %v, want %v", got.VS, want)
		}
		if !got.UsedBias {
			t.Fatal("same-direction reversed partners did not report bias use")
		}
	})

	t.Run("aggregates subgraph statistics", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetEdge("3", "x")
		g.SetEdge("1", "y", Attrs{"weight": float64(2)})
		g.SetEdge("4", "y")
		setOrderTestParents(t, g, []string{"x", "y"}, "movable")
		got := sortSubgraph(g, "movable", cg, false)
		if !got.HasBarycenter || got.Barycenter != 2.25 || got.Weight != 4 {
			t.Fatalf("sortSubgraph stats = %#v, want barycenter=2.25 weight=4", got)
		}
	})

	t.Run("nested subgraph without barycenter", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetNodes([]string{"a", "b", "c"})
		setOrderTestParents(t, g, []string{"a", "b", "c"}, "y")
		g.SetEdge("0", "x")
		g.SetEdge("1", "z")
		g.SetEdge("2", "y")
		setOrderTestParents(t, g, []string{"x", "y", "z"}, "movable")
		want := []string{"x", "z", "a", "b", "c"}
		if got := sortSubgraph(g, "movable", cg, false).VS; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("nested subgraph with barycenter", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetNodes([]string{"a", "b", "c"})
		setOrderTestParents(t, g, []string{"a", "b", "c"}, "y")
		g.SetEdge("0", "a", Attrs{"weight": float64(3)})
		g.SetEdge("0", "x")
		g.SetEdge("1", "z")
		g.SetEdge("2", "y")
		setOrderTestParents(t, g, []string{"x", "y", "z"}, "movable")
		want := []string{"x", "a", "b", "c", "z"}
		if got := sortSubgraph(g, "movable", cg, false).VS; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("nested subgraph with leaf in-edges", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetNodes([]string{"a", "b", "c"})
		setOrderTestParents(t, g, []string{"a", "b", "c"}, "y")
		g.SetEdge("0", "a")
		g.SetEdge("1", "b")
		g.SetEdge("0", "x")
		g.SetEdge("1", "z")
		setOrderTestParents(t, g, []string{"x", "y", "z"}, "movable")
		want := []string{"x", "a", "b", "c", "z"}
		if got := sortSubgraph(g, "movable", cg, false).VS; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("border nodes stay at extremes", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetEdge("0", "x")
		g.SetEdge("1", "y")
		g.SetEdge("2", "z")
		g.SetNode("sg1", Attrs{"borderLeft": "bl", "borderRight": "br"})
		setOrderTestParents(t, g, []string{"x", "y", "z", "bl", "br"}, "sg1")
		want := []string{"bl", "x", "y", "z", "br"}
		if got := sortSubgraph(g, "sg1", cg, false).VS; !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %v, want %v", got, want)
		}
	})

	t.Run("border predecessors determine barycenter", func(t *testing.T) {
		g, cg := newSortSubgraphTestGraph(t)
		g.SetNode("bl1", Attrs{"order": float64(0)})
		g.SetNode("br1", Attrs{"order": float64(1)})
		g.SetEdge("bl1", "bl2")
		g.SetEdge("br1", "br2")
		setOrderTestParents(t, g, []string{"bl2", "br2"}, "sg")
		g.SetNode("sg", Attrs{"borderLeft": "bl2", "borderRight": "br2"})
		got := sortSubgraph(g, "sg", cg, false)
		want := orderResult{VS: []string{"bl2", "br2"}, Barycenter: 0.5, Weight: 2, HasBarycenter: true}
		if !reflect.DeepEqual(got, want) {
			t.Fatalf("sortSubgraph = %#v, want %#v", got, want)
		}
	})
}