Repository: dominikbraun/graph (go)

Issue:
stable topological sort
Sometimes it is desirable to have a stable output for operations such as topological sort.

There are two ways of doing this (depending on if the goal is stability, or merely determinism):
- remember the order in which edges were declared, and use that order when walking;
- or, sort the edges of each node in a deterministic way before walking.

I tend to favor the former approach, because it provides both properties at once (and also because it feels more general: edge order is a nice tiebreaker to have in a lot of scenarios, not just this one).  But either works for producing deterministic outputs.

The current implementation can produce random reordering among nodes that aren't constrained.  (I assume this is because a golang map is used somewhere.)  Sometimes this is fine!  But in some scenarios, less fune: unstable output ordering is a big bummer if you have application level predictability desires... Or even just are doing text fixtures which depend on consistency :)

Pull request:
Implement `StableTopologicalSort`
Closes #61.

CC @deitch, @williamfzc, @geoah

Patch:
diff --git a/dag.go b/dag.go
index dafd0db..e55181a 100644
--- a/dag.go
+++ b/dag.go
@@ -3,6 +3,7 @@ package graph
 import (
 	"errors"
 	"fmt"
+	"sort"
 )
 
 // TopologicalSort runs a topological sort on a given directed graph and returns
@@ -13,6 +14,15 @@ import (
 // TopologicalSort only works for directed acyclic graphs. This implementation
 // works non-recursively and utilizes Kahn's algorithm.
 func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
+	return StableTopologicalSort(g, func(_, _ K) bool {
+		return false
+	})
+}
+
+// StableTopologicalSort does the same as [TopologicalSort], but takes a function
+// for comparing (and then ordering) two given vertices. This allows for a stable
+// and deterministic output even for graphs with multiple topological orderings.
+func StableTopologicalSort[K comparable, T any](g Graph[K, T], less func(K, K) bool) ([]K, error) {
 	if !g.Traits().IsDirected {
 		return nil, fmt.Errorf("topological sort cannot be computed on undirected graph")
 	}
@@ -33,6 +43,10 @@ func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
 	order := make([]K, 0, len(predecessorMap))
 	visited := make(map[K]struct{})
 
+	sort.Slice(queue, func(i, j int) bool {
+		return less(queue[i], queue[j])
+	})
+
 	for len(queue) > 0 {
 		currentVertex := queue[0]
 		queue = queue[1:]
@@ -49,6 +63,10 @@ func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
 
 			if len(predecessors) == 0 {
 				queue = append(queue, vertex)
+
+				sort.Slice(queue, func(i, j int) bool {
+					return less(queue[i], queue[j])
+				})
 			}
 		}
 	}
diff --git a/graph.go b/graph.go
index 08ca454..9376eb5 100644
--- a/graph.go
+++ b/graph.go
@@ -377,3 +377,11 @@ func VertexAttribute(key, value string) func(*VertexProperties) {
 		e.Attributes[key] = value
 	}
 }
+
+// VertexAttributes returns a function that sets the given map as the attributes
+// of a vertex. This is a functional option for the [graph.Graph.AddVertex] methods.
+func VertexAttributes(attributes map[string]string) func(*VertexProperties) {
+	return func(e *VertexProperties) {
+		e.Attributes = attributes
+	}
+}


Test patch:
diff --git a/dag_test.go b/dag_test.go
index 5ecd28b..cc21483 100644
--- a/dag_test.go
+++ b/dag_test.go
@@ -1,6 +1,9 @@
 package graph
 
-import "testing"
+import (
+	"fmt"
+	"testing"
+)
 
 func TestDirectedTopologicalSort(t *testing.T) {
 	tests := map[string]struct {
@@ -94,6 +97,89 @@ func TestUndirectedTopologicalSort(t *testing.T) {
 	}
 }
 
+func TestDirectedStableTopologicalSort(t *testing.T) {
+	tests := map[string]struct {
+		vertices      []int
+		edges         []Edge[int]
+		expectedOrder []int
+		shouldFail    bool
+	}{
+		"graph with 5 vertices": {
+			vertices: []int{1, 2, 3, 4, 5},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 4},
+				{Source: 4, Target: 5},
+			},
+			expectedOrder: []int{1, 2, 3, 4, 5},
+		},
+		"graph with many possible topological orders": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 60},
+			edges: []Edge[int]{
+				{Source: 1, Target: 10},
+				{Source: 2, Target: 20},
+				{Source: 3, Target: 30},
+				{Source: 4, Target: 40},
+				{Source: 5, Target: 50},
+				{Source: 6, Target: 60},
+			},
+			expectedOrder: []int{1, 2, 3, 4, 5, 6, 10, 20, 30, 40, 50, 60},
+		},
+		"graph with cycle": {
+			vertices: []int{1, 2, 3},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 2, Target: 3},
+				{Source: 3, Target: 1},
+			},
+			shouldFail: true,
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(IntHash, Directed())
+
+		for _, vertex := range test.vertices {
+			_ = graph.AddVertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight)); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		order, err := StableTopologicalSort(graph, func(a, b int) bool {
+			return a < b
+		})
+
+		if test.shouldFail != (err != nil) {
+			t.Errorf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, err != nil, err)
+		}
+
+		if test.shouldFail {
+			continue
+		}
+
+		if len(order) != len(test.expectedOrder) {
+			t.Errorf("%s: order length expectancy doesn't match: expected %v, got %v", name, len(test.expectedOrder), len(order))
+		}
+
+		fmt.Println("expected", test.expectedOrder)
+		fmt.Println("actual", order)
+
+		for i, expectedVertex := range test.expectedOrder {
+			if expectedVertex != order[i] {
+				t.Errorf("%s: order expectancy doesn't match: expected %v at %d, got %v", name, expectedVertex, i, order[i])
+			}
+		}
+	}
+}
+
 func TestDirectedTransitiveReduction(t *testing.T) {
 	tests := map[string]struct {
 		vertices      []string