Repository: dominikbraun/graph
Pull request #36 (2022-09-03 11:04:02)

Implement topological sort


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index c4cac76..bf9e404 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -9,6 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ### Added
 * Added the `PredecessorMap` method for obtaining a map with all predecessors of each vertex.
+* Added the `TopologicalSort` function for obtaining the topological order of the vertices in the graph.
 
 ### Removed
 * Removed the `Predecessors` function. Use `PredecessorMap` instead and look up the respective vertex.
diff --git a/README.md b/README.md
index f9dfb25..6c33f73 100644
--- a/README.md
+++ b/README.md
@@ -171,6 +171,24 @@ fmt.Println(path)
 [A C E B]
 ```
 
+## Perform a topological sort
+
+![topological sort](img/topological-sort.svg)
+
+```go
+g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())
+
+// Add vertices and weighted edges ...
+
+order, _ := graph.TopologicalSort(g)
+
+fmt.Println(order)
+```
+
+```
+[1 2 3 4 5]
+```
+
 ## Cycle checks for acyclic graphs
 
 ![cycle checks](img/cycles.svg)
diff --git a/dag.go b/dag.go
new file mode 100644
index 0000000..5d0e395
--- /dev/null
+++ b/dag.go
@@ -0,0 +1,57 @@
+package graph
+
+import (
+	"errors"
+	"fmt"
+)
+
+// TopologicalSort performs a topological sort on a given graph and returns the vertex hashes in
+// topological order. A topological order is a non-unique order of the vertices in a directed graph
+// where an edge from vertex A to vertex B implies that vertex A appears before vertex B.
+//
+// TopologicalSort only works for directed acyclic graphs. The current implementation works non-
+// recursively and uses Kahn's algorithm.
+func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
+	if !g.Traits().IsDirected || !g.Traits().IsAcyclic {
+		return nil, errors.New("topological sort can only be performed to DAGs")
+	}
+
+	predecessorMap, err := g.PredecessorMap()
+	if err != nil {
+		return nil, fmt.Errorf("failed to get predecessor map: %w", err)
+	}
+
+	queue := make([]K, 0)
+
+	for vertex, predecessors := range predecessorMap {
+		if len(predecessors) == 0 {
+			queue = append(queue, vertex)
+		}
+	}
+
+	order := make([]K, 0, len(predecessorMap))
+	visited := make(map[K]struct{})
+
+	for len(queue) > 0 {
+		currentVertex := queue[0]
+		queue = queue[1:]
+
+		if _, ok := visited[currentVertex]; !ok {
+			visited[currentVertex] = struct{}{}
+		} else {
+			continue
+		}
+
+		order = append(order, currentVertex)
+
+		for vertex, predecessors := range predecessorMap {
+			delete(predecessors, currentVertex)
+
+			if len(predecessors) == 0 {
+				queue = append(queue, vertex)
+			}
+		}
+	}
+
+	return order, nil
+}
diff --git a/img/topological-sort.svg b/img/topological-sort.svg
new file mode 100644
index 0000000..e8e8824
--- /dev/null
+++ b/img/topological-sort.svg
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!-- Do not edit this file with editors other than diagrams.net -->
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
+<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" width="262px" height="158px" viewBox="-0.5 -0.5 262 158" content="&lt;mxfile host=&quot;app.diagrams.net&quot; modified=&quot;2022-09-03T11:21:13.268Z&quot; agent=&quot;5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/103.0.0.0 Safari/537.36&quot; etag=&quot;VtjHObugR936E70Uc5BJ&quot; version=&quot;20.0.4&quot; type=&quot;device&quot;&gt;&lt;diagram id=&quot;UgWaNB6gBv--an5tvsQc&quot; name=&quot;Page-1&quot;&gt;7Zlbb5swGIZ/TS47AY4JuVyTrDtoWqWqanvp4A+wRnBmnIbs188UOxxMD6tIG6m5ify9Pr9+YhsYodmquBBknfzkFNKR59BihOYjzwtcV/2Wwq4SsOdXQiwYrSS3Fq7YX9Cio9UNo5C3CkrOU8nWbTHkWQahbGlECL5tF4t42u51TWKwhKuQpLZ6w6hMtOo5Tp3xFVicmK59k7MiprQW8oRQvm1IaDFCM8G5rFKrYgZpaZ4xpqr35ZHc/cgEZPIlFW4ug5njkJj+4d8X07tf6Nvk+syrWrkn6aY941zujAeqGWW3Cs63CZNwtSZhmbNVC660RK5SFbkqSfJ1tQYRK0D1eh6xNJ3xlIuHhhAlEESh0nMp+G9o5PhhAMtI5diT0uO5ByGhaEh6khfAVyDFThXRud5UG66Rc5GOt/UCGilpLJ3RiEYm3rdcm6oS2td+j68vL7wA/0iyaAExv4mXkw0/cy2PvcN5HEXgh70e08l0qeA0HluG9tj+qMcoODKPbY7R4TwGl2KY9Hk89SeI+IfxeL+RvJfHyPJ4fECOgxD6OV4GeIwH4njsH5nHY8tjfMD9GENAx30eB94S+QNx3PX43fcKbHlsW5zRz+XtQUVhSvKchW1nBd9ktLR0XoIIBZO3OqdM35X6J6yjedEoNt+ZIFNTuW0GjVplWFd7iEy9aqhArWuLdWLmfCNCeP7sl0TEIJ87v+zlbSwf7lk+owlIiWT37eH2ranu4ZIzNZGaHtz5hwYdLKpp6lrN60+nIex0GuryVflgNfSA2H7ar6fOfwvq3Ncwd3zEeSfiBiBu8rGIe+ru/Sxx6ETcAMQFH+9kfepp5ETdm1A3PVH3X3vd+ETdANSZN5QDYrdHqKZmf8Q+gZDBtUb0rkloL64DYodO2L0ldvbbxIF2uzY+L73XtVE9wpvd+z5LdGhBziuxs/jFQ2GnwvobRFW8/pKDFv8A&lt;/diagram&gt;&lt;/mxfile&gt;" style="background-color: rgb(255, 255, 255);"><defs/><g><ellipse cx="19.5" cy="19.5" rx="19.5" ry="19.5" fill="#dae8fc" stroke="#6c8ebf" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 15px; margin-left: 1px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">1</div></div></div></foreignObject><text x="15" y="19" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">1</text></switch></g><ellipse cx="136.5" cy="19.5" rx="19.5" ry="19.5" fill="#ffe6cc" stroke="#d79b00" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 15px; margin-left: 91px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">2</div></div></div></foreignObject><text x="105" y="19" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">2</text></switch></g><ellipse cx="136.5" cy="136.5" rx="19.5" ry="19.5" fill="#e1d5e7" stroke="#9673a6" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 105px; margin-left: 91px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">3</div></div></div></foreignObject><text x="105" y="109" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">3</text></switch></g><ellipse cx="240.5" cy="136.5" rx="19.5" ry="19.5" fill="#f8cecc" stroke="#b85450" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 105px; margin-left: 171px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">4</div></div></div></foreignObject><text x="185" y="109" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">4</text></switch></g><ellipse cx="240.5" cy="19.5" rx="19.5" ry="19.5" fill="#d5e8d4" stroke="#82b366" stroke-width="1.3" pointer-events="all"/><g transform="translate(-0.5 -0.5)scale(1.3)"><switch><foreignObject pointer-events="none" width="100%" height="100%" requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility" style="overflow: visible; text-align: left;"><div xmlns="http://www.w3.org/1999/xhtml" style="display: flex; align-items: unsafe center; justify-content: unsafe center; width: 28px; height: 1px; padding-top: 15px; margin-left: 171px;"><div data-drawio-colors="color: rgb(0, 0, 0); " style="box-sizing: border-box; font-size: 0px; text-align: center;"><div style="display: inline-block; font-size: 12px; font-family: Helvetica; color: rgb(0, 0, 0); line-height: 1.2; pointer-events: all; white-space: normal; overflow-wrap: normal;">5</div></div></div></foreignObject><text x="185" y="19" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">5</text></switch></g><path d="M 39 19.5 L 108.72 19.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 115.55 19.5 L 106.45 24.05 L 108.72 19.5 L 106.45 14.95 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 33.29 33.29 L 116.86 116.86" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 121.68 121.68 L 112.03 118.47 L 116.86 116.86 L 118.47 112.03 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 150.29 33.29 L 221.33 116.42" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 225.77 121.61 L 216.4 117.64 L 221.33 116.42 L 223.31 111.73 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 156 136.5 L 212.72 136.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 219.55 136.5 L 210.45 141.05 L 212.72 136.5 L 210.45 131.95 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 156 19.5 L 212.72 19.5" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 219.55 19.5 L 210.45 24.05 L 212.72 19.5 L 210.45 14.95 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 240.5 117 L 240.5 47.28" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 240.5 40.45 L 245.05 49.55 L 240.5 47.28 L 235.95 49.55 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 136.5 39 L 136.5 108.72" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 136.5 115.55 L 131.95 106.45 L 136.5 108.72 L 141.05 106.45 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/></g><switch><g requiredFeatures="http://www.w3.org/TR/SVG11/feature#Extensibility"/><a transform="translate(0,-5)" xlink:href="https://www.diagrams.net/doc/faq/svg-export-text-problems" target="_blank"><text text-anchor="middle" font-size="10px" x="50%" y="100%">Text is not SVG - cannot display</text></a></switch></svg>
\ No newline at end of file


Test patch:
diff --git a/dag_test.go b/dag_test.go
new file mode 100644
index 0000000..bb61067
--- /dev/null
+++ b/dag_test.go
@@ -0,0 +1,80 @@
+package graph
+
+import "testing"
+
+func TestDirectedTopologicalSort(t *testing.T) {
+	tests := map[string]struct {
+		vertices      []int
+		edges         []Edge[int]
+		expectedOrder []int
+	}{
+		"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},
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(IntHash, Directed(), Acyclic())
+
+		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 := TopologicalSort(graph)
+		if err != nil {
+			t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+		}
+
+		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))
+		}
+
+		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 TestUndirectedTopologicalSort(t *testing.T) {
+	tests := map[string]struct {
+		expectedOrder []int
+		shouldFail    bool
+	}{
+		"return error": {
+			expectedOrder: nil,
+			shouldFail:    true,
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(IntHash)
+
+		order, err := TopologicalSort(graph)
+
+		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.expectedOrder == nil && order != nil {
+			t.Errorf("%s: order expectancy doesn't match: expcted %v, got %v", name, test.expectedOrder, order)
+		}
+	}
+}