Repository: dominikbraun/graph
Pull request #38 (2022-09-08 11:15:40)

Add `TransitiveReduction` function


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 5565384..088a142 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -11,6 +11,11 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 * Added the `PredecessorMap` method for obtaining a map with all predecessors of each vertex.
 * Added the `RemoveEdge` method for removing the edge between two vertices.
 * Added the `TopologicalSort` function for obtaining the topological order of the vertices in the graph.
+* Added the `TransitiveReduction` function for transforming the graph into its transitive reduction.
+
+### Changed
+* Changed the `visit` function of `DFS` to accept a vertex hash instead of the vertex value (i.e. `K` instead of `T`).
+* Changed the `visit` function of `BFS` to accept a vertex hash instead of the vertex value (i.e. `K` instead of `T`).
 
 ### Removed
 * Removed the `Predecessors` function. Use `PredecessorMap` instead and look up the respective vertex.
diff --git a/README.md b/README.md
index f855565..1c4ce72 100644
--- a/README.md
+++ b/README.md
@@ -6,14 +6,13 @@ It supports different kinds of graphs such as directed graphs, acyclic graphs, o
 # Features
 
 * Generic vertices of any type, such as `int` or `City`.
-* Edges with optional data, such as weights or custom attributes.
-* Optionally combinable graph types and traits.
-* Validations considering the graph traits, such as cycle detection in acyclic graphs.
-* Determination of graph and vertex properties, such as degree or tree-depth.
-* Various algorithms for finding particular paths, components, circuits, and trees.
-* Non-recursive graph traversal, such as DFS or BFS.
-* Visualization of graphs using Graphviz.
-* Extensive tests with over 90% coverage.
+* Graph traits with corresponding validations, such as cycle checks in acyclic graphs.
+* Algorithms for finding paths or components, such as shortest paths or strongly connected components.
+* Algorithms for transformations and representations, such as transitive reduction or topological order.
+* Algorithms for non-recursive graph traversal, such as DFS or BFS.
+* Edges with optional metadata, such as weights or custom attributes.
+* Visualization of graphs using the DOT language and Graphviz.
+* Extensive unit tests with over 90% code coverage.
 
 > Status: Because `graph` is in version 0, the public API shouldn't be considered stable.
 
@@ -174,7 +173,7 @@ fmt.Println(path)
 ```go
 g := graph.New(graph.IntHash, graph.Directed(), graph.Acyclic())
 
-// Add vertices and weighted edges ...
+// Add vertices and edges ...
 
 order, _ := graph.TopologicalSort(g)
 
@@ -185,6 +184,18 @@ fmt.Println(order)
 [1 2 3 4 5]
 ```
 
+## Perform a transitive reduction
+
+![transitive reduction](img/transitive-reduction.svg)
+
+```go
+g := graph.New(graph.StringHash, graph.Directed(), graph.Acyclic())
+
+// Add vertices and edges ...
+
+_ := graph.TransitiveReduction(g)
+```
+
 ## Cycle checks for acyclic graphs
 
 ![cycle checks](img/cycles.svg)
diff --git a/dag.go b/dag.go
index 5cc2026..9e0ce85 100644
--- a/dag.go
+++ b/dag.go
@@ -12,7 +12,7 @@ import (
 // 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 {
+	if !isDAG(g) {
 		return nil, errors.New("topological sort can only be performed on DAGs")
 	}
 
@@ -54,3 +54,48 @@ func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
 
 	return order, nil
 }
+
+// TransitiveReduction transforms the graph into its own transitive reduction. The transitive
+// reduction of the given graph is another graph with the same vertices and the same reachability,
+// but with as few edges as possible. This greatly reduces the complexity of the graph.
+//
+// With a time complexity of O(V(V+E)), TransitiveReduction is a very costly operation.
+func TransitiveReduction[K comparable, T any](g Graph[K, T]) error {
+	if !isDAG(g) {
+		return errors.New("topological sort can only be performed on DAGs")
+	}
+
+	adjacencyMap, err := g.AdjacencyMap()
+	if err != nil {
+		return fmt.Errorf("failed to get adajcency map: %w", err)
+	}
+
+	for vertex, successors := range adjacencyMap {
+		// For each direct successor of the current vertex, run a DFS starting from that successor.
+		// Then, for each vertex visited in the DFS, inspect all of its edges. Remove the edges that
+		// also appear in the edges of the top-level iteration vertex.
+		//
+		// These edges are redundant because their targets obviously are reachable via DFS, i.e.
+		// they aren't needed in the top-level vertex anymore and can be removed from there.
+		for successor := range successors {
+			err := DFS(g, successor, func(current K) bool {
+				for _, edge := range adjacencyMap[current] {
+					if _, ok := adjacencyMap[vertex][edge.Target]; ok {
+						_ = g.RemoveEdge(vertex, edge.Target)
+					}
+				}
+
+				return false
+			})
+			if err != nil {
+				return err
+			}
+		}
+	}
+
+	return nil
+}
+
+func isDAG[K comparable, T any](g Graph[K, T]) bool {
+	return g.Traits().IsDirected && g.Traits().IsAcyclic
+}
diff --git a/directed.go b/directed.go
index 081c0a6..dd7969c 100644
--- a/directed.go
+++ b/directed.go
@@ -108,6 +108,8 @@ func (d *directed[K, T]) RemoveEdge(source, target K) error {
 	}
 
 	delete(d.edges[source], target)
+	delete(d.inEdges[target], source)
+	delete(d.outEdges[source], target)
 
 	return nil
 }
diff --git a/img/transitive-reduction.svg b/img/transitive-reduction.svg
new file mode 100644
index 0000000..a466030
--- /dev/null
+++ b/img/transitive-reduction.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="392px" height="388px" viewBox="-0.5 -0.5 392 388" content="&lt;mxfile host=&quot;app.diagrams.net&quot; modified=&quot;2022-09-08T11:21:41.918Z&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;Ys1souaCIfJ38X5PVvR8&quot; version=&quot;20.2.8&quot; type=&quot;device&quot;&gt;&lt;diagram id=&quot;UgWaNB6gBv--an5tvsQc&quot; name=&quot;Page-1&quot;&gt;7Ztbb5swFMc/TR47AcYEHtuk66Sp26Q8rNtL5WAT0AiOwGnIPv1MsMPFaXMZARTRh8o+vmD//ZN9fCAjMFmmTzFa+c8Uk3BkaDgdgenIMIAD+P/MsM0NBoS5YREHODfphWEW/CXCqAnrOsAkqVRklIYsWFWNLo0i4rKKDcUx3VSreTSsPnWFFkQxzFwUqtafAWa+sBqaVhR8IcHCl4+2ZMkSydrCkPgI003JBB5HYBJTyvLUMp2QMBNPCpO3+/xO6X5kMYnYKQ0Yevl+twX49Xk2XeCvv5+W39Cd6OUNhWsx43sxWraVGvBuuNw887DxA0ZmK+RmJRu+4Nzms2XIczpPomSVr4EXpIQ/9cELwnBCQxrvOgIYEdtzuT1hMf1DSiWWa5O5x0vEcEjMSPruPPW9ehw7QpeExVteRTYwheACOQBFflMsIBAmv7R00oYEMot9z4WoPCF0PUNjQ9H44Xoaex6x3IMa47Ez53A2ovFeLKmx3rHGQNF4cj2NiY4hGR/S2LHGAFlX0tjpWGNT0fjxihzbLjnM8dyGJmyIY1Pv2V4BFY2nV9yPIbGxeUhj25gDqyGOgdEzjS1FY1XiCN9n3gPPuSFKksCtKhvTdYQzSacZiCQN2IsoydK/SvZpWs5sZSbiE3kpZ3ZtPkGZLZrtcrJdPlCCFaelthh8MnQdu+T4yc9QvCDs2OmlLm5p8eCBxZO2mISIBW/V4R5aUfGEHzTgEynY0arsQK0GRT5N0ars/NQ7gtWOTFjrKNdB6WgH2H7alzM3boM5/VaYAwNzDTCnq07RNTa6HKBzsWsPOuNE6GCX0BnOEVZOhq52+zHr9F4bOtVL7A10envQgQG6NqFT3eb/he7Cw/ISWBvEDp6InTlg1wR26k3i5qJnete3NV11nW8ufNa9yLYi8s3Fzwyza5EdReSbC6B1TrIMNt1yBK17kdXXRqrGXd0sWw1oCA/gqMOVn2J9CWmApkIaRsshDclZD+NofYTOHqBrAro+x9Fa3e3GJ4JX+r6hB/dLhZdL75dGy/dLo51YWr8jafJqMkDXEnRDLK16kzh+zDoDeE2A18o70t6/OTh5v+sWO1D/Ouli787u2LtTozI9OWT7eKXo9pDtHDpOAdqWqq2yCskHm3M9mm5WvtHlibzHRomWIg1ED9to80TX3A0dtEH0eWGfiEZZbBejxN8hrH/Edi2iq+3+zmCxK3LqL+r2C3MuOeaxji4+gHm2+HlDXr34kQh4/Ac=&lt;/diagram&gt;&lt;/mxfile&gt;" style="background-color: rgb(255, 255, 255);"><defs/><g><ellipse cx="19.5" cy="314.6" 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: 242px; 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;">A</div></div></div></foreignObject><text x="15" y="246" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">A</text></switch></g><ellipse cx="136.5" cy="262.6" 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: 202px; 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;">B</div></div></div></foreignObject><text x="105" y="206" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">B</text></switch></g><ellipse cx="136.5" cy="366.6" 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: 282px; 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;">C</div></div></div></foreignObject><text x="105" y="286" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">C</text></switch></g><ellipse cx="370.5" cy="314.6" 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: 242px; margin-left: 271px;"><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;">E</div></div></div></foreignObject><text x="285" y="246" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">E</text></switch></g><ellipse cx="253.5" cy="314.6" 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: 242px; margin-left: 181px;"><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;">D</div></div></div></foreignObject><text x="195" y="246" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">D</text></switch></g><path d="M 33.29 300.81 L 109.47 266.04" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 115.68 263.2 L 109.29 271.12 L 109.47 266.04 L 105.51 262.84 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 328.39 L 109.47 363.16" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 115.68 366 L 105.51 366.36 L 109.47 363.16 L 109.29 358.08 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 262.6 L 232.18 297.37" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 238.39 300.21 L 228.22 300.57 L 232.18 297.37 L 232 292.29 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 366.6 L 232.18 331.83" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 238.39 328.99 L 232 336.91 L 232.18 331.83 L 228.22 328.63 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 273 314.6 L 342.72 314.6" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 349.55 314.6 L 340.45 319.15 L 342.72 314.6 L 340.45 310.05 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><ellipse cx="19.5" cy="54.6" 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: 42px; 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;">A</div></div></div></foreignObject><text x="15" y="46" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">A</text></switch></g><ellipse cx="136.5" cy="54.6" 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: 42px; 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;">B</div></div></div></foreignObject><text x="105" y="46" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">B</text></switch></g><ellipse cx="136.5" cy="171.6" 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: 132px; 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;">C</div></div></div></foreignObject><text x="105" y="136" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">C</text></switch></g><ellipse cx="370.5" cy="54.6" 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: 42px; margin-left: 271px;"><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;">E</div></div></div></foreignObject><text x="285" y="46" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">E</text></switch></g><ellipse cx="253.5" cy="54.6" 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: 42px; margin-left: 181px;"><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;">D</div></div></div></foreignObject><text x="195" y="46" fill="rgb(0, 0, 0)" font-family="Helvetica" font-size="12px" text-anchor="middle">D</text></switch></g><path d="M 39 54.6 L 108.72 54.6" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 115.55 54.6 L 106.45 59.15 L 108.72 54.6 L 106.45 50.05 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 68.39 L 116.86 151.96" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 121.68 156.78 L 112.03 153.57 L 116.86 151.96 L 118.47 147.13 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 54.6 L 225.72 54.6" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 232.55 54.6 L 223.45 59.15 L 225.72 54.6 L 223.45 50.05 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 157.81 L 233.86 74.24" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 238.68 69.42 L 235.47 79.07 L 233.86 74.24 L 229.03 72.63 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 273 54.6 L 342.72 54.6" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 349.55 54.6 L 340.45 59.15 L 342.72 54.6 L 340.45 50.05 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 171.6 L 349.35 72.17" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 355.42 69.05 L 349.41 77.26 L 349.35 72.17 L 345.25 69.17 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 40.81 L 130 22.1 L 231.55 39.42" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 238.28 40.57 L 228.54 43.52 L 231.55 39.42 L 230.07 34.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 33.29 40.81 L 195 9.1 L 348.59 39.22" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="stroke"/><path d="M 355.29 40.53 L 345.48 43.25 L 348.59 39.22 L 347.23 34.32 Z" fill="rgb(0, 0, 0)" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" pointer-events="all"/><path d="M 0 217.1 L 390 217.1" fill="none" stroke="rgb(0, 0, 0)" stroke-width="1.3" stroke-miterlimit="10" stroke-dasharray="3.9000000000000004 3.9000000000000004" pointer-events="stroke"/></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
diff --git a/traversal.go b/traversal.go
index 4a05122..e52f500 100644
--- a/traversal.go
+++ b/traversal.go
@@ -3,9 +3,9 @@ package graph
 import "fmt"
 
 // DFS performs a depth-first search on the graph, starting from the given vertex. The visit
-// function will be invoked for each visited vertex. If it returns false, DFS will continue
-// traversing the path, and if it returns true, the traversal will be stopped. In case the graph is
-// disconnected, only the vertices joined with the starting vertex will be traversed.
+// function will be invoked with the hash of the vertex currently visited. If it returns false, DFS
+// will continue traversing the graph, and if it returns true, the traversal will be stopped. In
+// case the graph is disconnected, only the vertices joined with the starting vertex are visited.
 //
 // This example prints all vertices of the graph in DFS-order:
 //
@@ -32,7 +32,7 @@ import "fmt"
 //	}
 //
 // DFS is non-recursive and maintains a stack instead.
-func DFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error {
+func DFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error {
 	adjacencyMap, err := g.AdjacencyMap()
 	if err != nil {
 		return fmt.Errorf("could not get adjacency map: %w", err)
@@ -49,13 +49,12 @@ func DFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
 
 	for len(stack) > 0 {
 		currentHash := stack[len(stack)-1]
-		currentVertex, _ := g.Vertex(currentHash)
 
 		stack = stack[:len(stack)-1]
 
 		if _, ok := visited[currentHash]; !ok {
 			// Stop traversing the graph if the visit function returns true.
-			if stop := visit(currentVertex); stop {
+			if stop := visit(currentHash); stop {
 				break
 			}
 			visited[currentHash] = true
@@ -69,10 +68,10 @@ func DFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
 	return nil
 }
 
-// BFS performs a Breadth-First Search on the graph, starting from the given vertex. The visit
-// function will be invoked for each visited vertex. If it returns false, BFS will continue
-// traversing the path, and if it returns true, the traversal will be stopped. In case the graph is
-// disconnected, only the vertices joined with the starting vertex will be traversed.
+// BFS performs a depth-first search on the graph, starting from the given vertex. The visit
+// function will be invoked with the hash of the vertex currently visited. If it returns false, BFS
+// will continue traversing the graph, and if it returns true, the traversal will be stopped. In
+// case the graph is disconnected, only the vertices joined with the starting vertex are visited.
 //
 // This example prints all vertices of the graph in BFS-order:
 //
@@ -99,7 +98,7 @@ func DFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
 //	}
 //
 // BFS is non-recursive and maintains a stack instead.
-func BFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error {
+func BFS[K comparable, T any](g Graph[K, T], start K, visit func(K) bool) error {
 	adjacencyMap, err := g.AdjacencyMap()
 	if err != nil {
 		return fmt.Errorf("could not get adjacency map: %w", err)
@@ -117,12 +116,11 @@ func BFS[K comparable, T any](g Graph[K, T], start K, visit func(T) bool) error
 
 	for len(queue) > 0 {
 		currentHash := queue[0]
-		currentVertex, _ := g.Vertex(currentHash)
 
 		queue = queue[1:]
 
 		// Stop traversing the graph if the visit function returns true.
-		if stop := visit(currentVertex); stop {
+		if stop := visit(currentHash); stop {
 			break
 		}
 


Test patch:
diff --git a/dag_test.go b/dag_test.go
index bb61067..63e37b2 100644
--- a/dag_test.go
+++ b/dag_test.go
@@ -78,3 +78,105 @@ func TestUndirectedTopologicalSort(t *testing.T) {
 		}
 	}
 }
+
+func TestDirectedTransitiveReduction(t *testing.T) {
+	tests := map[string]struct {
+		vertices      []string
+		edges         []Edge[string]
+		expectedEdges []Edge[string]
+	}{
+		"graph as on img/transitive-reduction.svg": {
+			vertices: []string{"A", "B", "C", "D", "E"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B"},
+				{Source: "A", Target: "C"},
+				{Source: "A", Target: "D"},
+				{Source: "A", Target: "E"},
+				{Source: "B", Target: "D"},
+				{Source: "C", Target: "D"},
+				{Source: "C", Target: "E"},
+				{Source: "D", Target: "E"},
+			},
+			expectedEdges: []Edge[string]{
+				{Source: "A", Target: "B"},
+				{Source: "A", Target: "C"},
+				{Source: "B", Target: "D"},
+				{Source: "C", Target: "D"},
+				{Source: "D", Target: "E"},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(StringHash, 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())
+			}
+		}
+
+		if err := TransitiveReduction(graph); err != nil {
+			t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+		}
+
+		actualEdges := make([]Edge[string], 0)
+		adjacencyMap, _ := graph.AdjacencyMap()
+
+		for _, adjacencies := range adjacencyMap {
+			for _, edge := range adjacencies {
+				actualEdges = append(actualEdges, edge)
+			}
+		}
+
+		equalsFunc := graph.(*directed[string, string]).edgesAreEqual
+
+		if !slicesAreEqualWithFunc(actualEdges, test.expectedEdges, equalsFunc) {
+			t.Errorf("%s: edge expectancy doesn't match: expected %v, got %v", name, test.expectedEdges, actualEdges)
+		}
+	}
+}
+
+func TestUndirectedTransitiveReduction(t *testing.T) {
+	tests := map[string]struct {
+		shouldFail bool
+	}{
+		"return error": {
+			shouldFail: true,
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(StringHash)
+
+		err := TransitiveReduction(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)
+		}
+	}
+}
+
+func slicesAreEqualWithFunc[T any](a, b []T, equals func(a, b T) bool) bool {
+	if len(a) != len(b) {
+		return false
+	}
+
+	for _, aValue := range a {
+		found := false
+		for _, bValue := range b {
+			if equals(aValue, bValue) {
+				found = true
+			}
+		}
+		if !found {
+			return false
+		}
+	}
+
+	return true
+}