Repository: dominikbraun/graph
Pull request #37 (2022-09-07 15:05:25)

Add `RemoveEdge` method


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index bf9e404..5565384 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 `RemoveEdge` method for removing the edge between two vertices.
 * Added the `TopologicalSort` function for obtaining the topological order of the vertices in the graph.
 
 ### Removed
diff --git a/directed.go b/directed.go
index c650c5e..081c0a6 100644
--- a/directed.go
+++ b/directed.go
@@ -102,6 +102,16 @@ func (d *directed[K, T]) Edge(sourceHash, targetHash K) (Edge[T], error) {
 	return edge, nil
 }
 
+func (d *directed[K, T]) RemoveEdge(source, target K) error {
+	if _, err := d.Edge(source, target); err != nil {
+		return fmt.Errorf("failed to find edge from %v to %v: %w", source, target, err)
+	}
+
+	delete(d.edges[source], target)
+
+	return nil
+}
+
 func (d *directed[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 	adjacencyMap := make(map[K]map[K]Edge[K])
 
diff --git a/graph.go b/graph.go
index 2bb7a5b..86353e7 100644
--- a/graph.go
+++ b/graph.go
@@ -36,6 +36,10 @@ type Graph[K comparable, T any] interface {
 	// undirected graph, an edge with swapped source and target vertices does match.
 	Edge(sourceHash, targetHash K) (Edge[T], error)
 
+	// RemoveEdge removes the edge between the given source and target vertices. If the edge doesn't
+	// exist, ErrEdgeNotFound will be returned.
+	RemoveEdge(source, target K) error
+
 	// AdjacencyMap computes and returns an adjacency map containing all vertices in the graph.
 	//
 	// There is an entry for each vertex, and each of those entries is another map whose keys are
diff --git a/undirected.go b/undirected.go
index 381cfcf..2845730 100644
--- a/undirected.go
+++ b/undirected.go
@@ -105,6 +105,19 @@ func (u *undirected[K, T]) Edge(sourceHash, targetHash K) (Edge[T], error) {
 	return Edge[T]{}, ErrEdgeNotFound
 }
 
+func (u *undirected[K, T]) RemoveEdge(source, target K) error {
+	if _, err := u.Edge(source, target); err != nil {
+		return fmt.Errorf("failed to find edge from %v to %v: %w", source, target, err)
+	}
+
+	delete(u.inEdges[source], target)
+	delete(u.inEdges[target], source)
+	delete(u.outEdges[source], target)
+	delete(u.outEdges[target], source)
+
+	return nil
+}
+
 func (u *undirected[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 	adjacencyMap := make(map[K]map[K]Edge[K])
 


Test patch:
diff --git a/directed_test.go b/directed_test.go
index 4d345f2..84224c1 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -231,6 +231,60 @@ func TestDirected_Edge(t *testing.T) {
 	}
 }
 
+func TestDirected_RemoveEdge(t *testing.T) {
+	tests := map[string]struct {
+		vertices    []int
+		edges       []Edge[int]
+		removeEdges []Edge[int]
+	}{
+		"two-vertices graph": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+			},
+			removeEdges: []Edge[int]{
+				{Source: 1, Target: 2},
+			},
+		},
+		"remove 2 edges from triangle": {
+			vertices: []int{1, 2, 3},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+			},
+			removeEdges: []Edge[int]{
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+			},
+		},
+	}
+
+	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())
+			}
+		}
+
+		for _, removeEdge := range test.removeEdges {
+			if err := graph.RemoveEdge(removeEdge.Source, removeEdge.Target); err != nil {
+				t.Fatalf("%s: failed to remove edge: %s", name, err.Error())
+			}
+			// After removing the edge, verify that it can't be retrieved using Edge anymore.
+			if _, err := graph.Edge(removeEdge.Source, removeEdge.Target); err != ErrEdgeNotFound {
+				t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v", name, ErrEdgeNotFound, err)
+			}
+		}
+	}
+}
+
 func TestDirected_AdjacencyList(t *testing.T) {
 	tests := map[string]struct {
 		vertices []int
diff --git a/undirected_test.go b/undirected_test.go
index aab6378..8e6ccfc 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -176,6 +176,60 @@ func TestUndirected_Edge(t *testing.T) {
 	}
 }
 
+func TestUndirected_RemoveEdge(t *testing.T) {
+	tests := map[string]struct {
+		vertices    []int
+		edges       []Edge[int]
+		removeEdges []Edge[int]
+	}{
+		"two-vertices graph": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+			},
+			removeEdges: []Edge[int]{
+				{Source: 1, Target: 2},
+			},
+		},
+		"remove 2 edges from triangle": {
+			vertices: []int{1, 2, 3},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+			},
+			removeEdges: []Edge[int]{
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		graph := New(IntHash)
+
+		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())
+			}
+		}
+
+		for _, removeEdge := range test.removeEdges {
+			if err := graph.RemoveEdge(removeEdge.Source, removeEdge.Target); err != nil {
+				t.Fatalf("%s: failed to remove edge: %s", name, err.Error())
+			}
+			// After removing the edge, verify that it can't be retrieved using Edge anymore.
+			if _, err := graph.Edge(removeEdge.Source, removeEdge.Target); err != ErrEdgeNotFound {
+				t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v", name, ErrEdgeNotFound, err)
+			}
+		}
+	}
+}
+
 func TestUndirected_Adjacencies(t *testing.T) {
 	tests := map[string]struct {
 		vertices []int