Repository: dominikbraun/graph
Pull request #108 (2023-04-24 20:08:38)

Implement `AddVerticesFrom` method


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 3c5a836..792bafb 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -8,6 +8,7 @@ adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
 ## [0.20.0] - 2023-05-01
 
 ### Added
+* Added the `AddVerticesFrom` method for adding all vertices from another graph.
 
 ## [0.19.0] - 2023-04-23
 
diff --git a/directed.go b/directed.go
index 87f7544..414948c 100644
--- a/directed.go
+++ b/directed.go
@@ -37,6 +37,26 @@ func (d *directed[K, T]) AddVertex(value T, options ...func(*VertexProperties))
 	return d.store.AddVertex(hash, value, properties)
 }
 
+func (d *directed[K, T]) AddVerticesFrom(g Graph[K, T]) error {
+	adjacencyMap, err := g.AdjacencyMap()
+	if err != nil {
+		return fmt.Errorf("failed to get adjacency map: %w", err)
+	}
+
+	for hash := range adjacencyMap {
+		vertex, properties, err := g.VertexWithProperties(hash)
+		if err != nil {
+			return fmt.Errorf("failed to get vertex %v: %w", hash, err)
+		}
+
+		if err = d.AddVertex(vertex, copyVertexProperties(properties)); err != nil {
+			return fmt.Errorf("failed to add vertex %v: %w", hash, err)
+		}
+	}
+
+	return nil
+}
+
 func (d *directed[K, T]) Vertex(hash K) (T, error) {
 	vertex, _, err := d.store.Vertex(hash)
 	return vertex, err
diff --git a/graph.go b/graph.go
index 36f13aa..e3c8450 100644
--- a/graph.go
+++ b/graph.go
@@ -77,6 +77,13 @@ type Graph[K comparable, T any] interface {
 	//
 	AddVertex(value T, options ...func(*VertexProperties)) error
 
+	// AddVerticesFrom adds all vertices along with their properties from the
+	// given graph to the receiving graph.
+	//
+	// All vertices will be added until an error occurs. If one of the vertices
+	// already exists, ErrVertexAlreadyExists will be returned.
+	AddVerticesFrom(g Graph[K, T]) error
+
 	// Vertex returns the vertex with the given hash or ErrVertexNotFound if it
 	// doesn't exist.
 	Vertex(hash K) (T, error)
diff --git a/undirected.go b/undirected.go
index 5bf83bc..3e2f784 100644
--- a/undirected.go
+++ b/undirected.go
@@ -100,6 +100,26 @@ func (u *undirected[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Ed
 	return nil
 }
 
+func (u *undirected[K, T]) AddVerticesFrom(g Graph[K, T]) error {
+	adjacencyMap, err := g.AdjacencyMap()
+	if err != nil {
+		return fmt.Errorf("failed to get adjacency map: %w", err)
+	}
+
+	for hash := range adjacencyMap {
+		vertex, properties, err := g.VertexWithProperties(hash)
+		if err != nil {
+			return fmt.Errorf("failed to get vertex %v: %w", hash, err)
+		}
+
+		if err = u.AddVertex(vertex, copyVertexProperties(properties)); err != nil {
+			return fmt.Errorf("failed to add vertex %v: %w", hash, err)
+		}
+	}
+
+	return nil
+}
+
 func (u *undirected[K, T]) Edge(sourceHash, targetHash K) (Edge[T], error) {
 	// In an undirected graph, since multigraphs aren't supported, the edge AB
 	// is the same as BA. Therefore, if source[target] cannot be found, this


Test patch:
diff --git a/directed_test.go b/directed_test.go
index ae1fa23..27e9d98 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -118,6 +118,99 @@ func TestDirected_AddVertex(t *testing.T) {
 	}
 }
 
+func TestDirected_AddVerticesFrom(t *testing.T) {
+	tests := map[string]struct {
+		vertices           []int
+		properties         map[int]VertexProperties
+		existingVertices   []int
+		expectedVertices   []int
+		expectedProperties map[int]VertexProperties
+		expectedError      error
+	}{
+		"graph with 3 vertices": {
+			vertices: []int{1, 2, 3},
+			properties: map[int]VertexProperties{
+				1: {
+					Attributes: map[string]string{"color": "red"},
+					Weight:     10,
+				},
+				2: {
+					Attributes: map[string]string{"color": "green"},
+					Weight:     20,
+				},
+				3: {
+					Attributes: map[string]string{"color": "blue"},
+					Weight:     30,
+				},
+			},
+			existingVertices: []int{},
+			expectedVertices: []int{1, 2, 3},
+			expectedProperties: map[int]VertexProperties{
+				1: {
+					Attributes: map[string]string{"color": "red"},
+					Weight:     10,
+				},
+				2: {
+					Attributes: map[string]string{"color": "green"},
+					Weight:     20,
+				},
+				3: {
+					Attributes: map[string]string{"color": "blue"},
+					Weight:     30,
+				},
+			},
+		},
+		"graph with duplicated vertex": {
+			vertices:           []int{1, 2, 3},
+			properties:         map[int]VertexProperties{},
+			existingVertices:   []int{2},
+			expectedVertices:   []int{1},
+			expectedProperties: map[int]VertexProperties{},
+			expectedError:      ErrVertexAlreadyExists,
+		},
+	}
+
+	for name, test := range tests {
+		t.Run(name, func(t *testing.T) {
+			source := New(IntHash, Directed())
+
+			for _, vertex := range test.vertices {
+				_ = source.AddVertex(vertex, copyVertexProperties(test.properties[vertex]))
+			}
+
+			g := New(IntHash, Directed())
+
+			for _, vertex := range test.existingVertices {
+				_ = g.AddVertex(vertex)
+			}
+
+			err := g.AddVerticesFrom(source)
+
+			if !errors.Is(err, test.expectedError) {
+				t.Errorf("expected error %v, got %v", test.expectedError, err)
+			}
+
+			if err != nil {
+				return
+			}
+
+			for _, vertex := range test.expectedVertices {
+				_, actualProperties, err := g.VertexWithProperties(vertex)
+				if err != nil {
+					t.Errorf("failed to get vertex %v with properties: %v", vertex, err.Error())
+					return
+				}
+
+				if expectedProperties, ok := test.expectedProperties[vertex]; ok {
+					if !vertexPropertiesAreEqual(expectedProperties, actualProperties) {
+						t.Errorf("expected properties %v for %v, got %v", expectedProperties, vertex, actualProperties)
+					}
+				}
+			}
+		})
+	}
+}
+
 func TestDirected_Vertex(t *testing.T) {
 	tests := map[string]struct {
 		vertices      []int
@@ -973,6 +1066,27 @@ func slicesAreEqual[T comparable](a, b []T) bool {
 	return true
 }
 
+func vertexPropertiesAreEqual(a, b VertexProperties) bool {
+	if a.Weight != b.Weight {
+		return false
+	}
+
+	// A length check is required because in the iteration below, a.Attributes
+	// could be empty and thus circumvent the comparison.
+	if len(a.Attributes) != len(b.Attributes) {
+		return false
+	}
+
+	for key, aValue := range a.Attributes {
+		bValue, ok := b.Attributes[key]
+		if !ok || aValue != bValue {
+			return false
+		}
+	}
+
+	return true
+}
+
 func edgePropertiesAreEqual(a, b EdgeProperties) bool {
 	if a.Weight != b.Weight {
 		return false
diff --git a/undirected_test.go b/undirected_test.go
index 56ddeb0..8597ad2 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -119,6 +119,99 @@ func TestUndirected_AddVertex(t *testing.T) {
 	}
 }
 
+func TestUndirected_AddVerticesFrom(t *testing.T) {
+	tests := map[string]struct {
+		vertices           []int
+		properties         map[int]VertexProperties
+		existingVertices   []int
+		expectedVertices   []int
+		expectedProperties map[int]VertexProperties
+		expectedError      error
+	}{
+		"graph with 3 vertices": {
+			vertices: []int{1, 2, 3},
+			properties: map[int]VertexProperties{
+				1: {
+					Attributes: map[string]string{"color": "red"},
+					Weight:     10,
+				},
+				2: {
+					Attributes: map[string]string{"color": "green"},
+					Weight:     20,
+				},
+				3: {
+					Attributes: map[string]string{"color": "blue"},
+					Weight:     30,
+				},
+			},
+			existingVertices: []int{},
+			expectedVertices: []int{1, 2, 3},
+			expectedProperties: map[int]VertexProperties{
+				1: {
+					Attributes: map[string]string{"color": "red"},
+					Weight:     10,
+				},
+				2: {
+					Attributes: map[string]string{"color": "green"},
+					Weight:     20,
+				},
+				3: {
+					Attributes: map[string]string{"color": "blue"},
+					Weight:     30,
+				},
+			},
+		},
+		"graph with duplicated vertex": {
+			vertices:           []int{1, 2, 3},
+			properties:         map[int]VertexProperties{},
+			existingVertices:   []int{2},
+			expectedVertices:   []int{1},
+			expectedProperties: map[int]VertexProperties{},
+			expectedError:      ErrVertexAlreadyExists,
+		},
+	}
+
+	for name, test := range tests {
+		t.Run(name, func(t *testing.T) {
+			source := New(IntHash)
+
+			for _, vertex := range test.vertices {
+				_ = source.AddVertex(vertex, copyVertexProperties(test.properties[vertex]))
+			}
+
+			g := New(IntHash)
+
+			for _, vertex := range test.existingVertices {
+				_ = g.AddVertex(vertex)
+			}
+
+			err := g.AddVerticesFrom(source)
+
+			if !errors.Is(err, test.expectedError) {
+				t.Errorf("expected error %v, got %v", test.expectedError, err)
+			}
+
+			if err != nil {
+				return
+			}
+
+			for _, vertex := range test.expectedVertices {
+				_, actualProperties, err := g.VertexWithProperties(vertex)
+				if err != nil {
+					t.Errorf("failed to get vertex %v with properties: %v", vertex, err.Error())
+					return
+				}
+
+				if expectedProperties, ok := test.expectedProperties[vertex]; ok {
+					if !vertexPropertiesAreEqual(expectedProperties, actualProperties) {
+						t.Errorf("expected properties %v for %v, got %v", expectedProperties, vertex, actualProperties)
+					}
+				}
+			}
+		})
+	}
+}
+
 func TestUndirected_Vertex(t *testing.T) {
 	tests := map[string]struct {
 		vertices      []int