Repository: dominikbraun/graph
Pull request #40 (2022-09-09 06:53:53)

Add `Clone` method


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index d0a56f2..0a87e85 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -10,6 +10,7 @@ adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
 ### 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 `Clone` method for retrieving a deep copy of the graph.
 * 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.
 
diff --git a/directed.go b/directed.go
index dd7969c..8cd3a57 100644
--- a/directed.go
+++ b/directed.go
@@ -162,6 +162,30 @@ func (d *directed[K, T]) PredecessorMap() (map[K]map[K]Edge[K], error) {
 	return predecessors, nil
 }
 
+func (d *directed[K, T]) Clone() (Graph[K, T], error) {
+	traits := &Traits{
+		IsDirected: d.traits.IsDirected,
+		IsAcyclic:  d.traits.IsAcyclic,
+		IsWeighted: d.traits.IsWeighted,
+		IsRooted:   d.traits.IsRooted,
+	}
+
+	vertices := make(map[K]T)
+
+	for hash, vertex := range d.vertices {
+		vertices[hash] = vertex
+	}
+
+	return &directed[K, T]{
+		hash:     d.hash,
+		traits:   traits,
+		vertices: vertices,
+		edges:    cloneEdges(d.edges),
+		outEdges: cloneEdges(d.outEdges),
+		inEdges:  cloneEdges(d.inEdges),
+	}, nil
+}
+
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := d.hash(a.Source)
 	aTargetHash := d.hash(a.Target)
@@ -205,3 +229,30 @@ func (d *directed[K, T]) predecessors(vertexHash K) []K {
 
 	return predecessorHashes
 }
+
+func cloneEdges[K comparable, T any](input map[K]map[K]Edge[T]) map[K]map[K]Edge[T] {
+	edges := make(map[K]map[K]Edge[T])
+
+	for hash, neighbours := range input {
+		edges[hash] = make(map[K]Edge[T])
+
+		for neighbourHash, edge := range neighbours {
+			attributes := make(map[string]string)
+
+			for key, value := range edge.Properties.Attributes {
+				attributes[key] = value
+			}
+
+			edges[hash][neighbourHash] = Edge[T]{
+				Source: edge.Source,
+				Target: edge.Target,
+				Properties: EdgeProperties{
+					Attributes: attributes,
+					Weight:     edge.Properties.Weight,
+				},
+			}
+		}
+	}
+
+	return edges
+}
diff --git a/graph.go b/graph.go
index 86353e7..3b0ae30 100644
--- a/graph.go
+++ b/graph.go
@@ -67,6 +67,9 @@ type Graph[K comparable, T any] interface {
 	// vertices joined by an outgoing edge are considered adjacent to the current vertex, whereas
 	// predecessors are the vertices joined by an ingoing edge.
 	PredecessorMap() (map[K]map[K]Edge[K], error)
+
+	// Clone creates an independent deep copy of the graph and returns that cloned graph.
+	Clone() (Graph[K, T], error)
 }
 
 // Edge represents a graph edge with a source and target vertex as well as a weight, which has the
diff --git a/undirected.go b/undirected.go
index 2845730..a2fc3df 100644
--- a/undirected.go
+++ b/undirected.go
@@ -147,6 +147,29 @@ func (u *undirected[K, T]) PredecessorMap() (map[K]map[K]Edge[K], error) {
 	return u.AdjacencyMap()
 }
 
+func (u *undirected[K, T]) Clone() (Graph[K, T], error) {
+	traits := &Traits{
+		IsDirected: u.traits.IsDirected,
+		IsAcyclic:  u.traits.IsAcyclic,
+		IsWeighted: u.traits.IsWeighted,
+		IsRooted:   u.traits.IsRooted,
+	}
+
+	vertices := make(map[K]T)
+
+	for hash, vertex := range u.vertices {
+		vertices[hash] = vertex
+	}
+
+	return &undirected[K, T]{
+		hash:     u.hash,
+		traits:   traits,
+		vertices: vertices,
+		outEdges: cloneEdges(u.outEdges),
+		inEdges:  cloneEdges(u.inEdges),
+	}, nil
+}
+
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := u.hash(a.Source)
 	aTargetHash := u.hash(a.Target)


Test patch:
diff --git a/directed_test.go b/directed_test.go
index 84224c1..053886b 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -452,6 +452,85 @@ func TestDirected_PredecessorMap(t *testing.T) {
 	}
 }
 
+func TestDirected_Clone(t *testing.T) {
+	tests := map[string]struct {
+		vertices []int
+		edges    []Edge[int]
+	}{
+		"Y-shaped graph": {
+			vertices: []int{1, 2, 3, 4},
+			edges: []Edge[int]{
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+				{Source: 3, Target: 4},
+			},
+		},
+		"diamond-shaped graph": {
+			vertices: []int{1, 2, 3, 4},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 4},
+			},
+		},
+	}
+
+	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())
+			}
+		}
+
+		clonedGraph, err := graph.Clone()
+		if err != nil {
+			t.Fatalf("%s: failed to clone graph: %s", name, err.Error())
+		}
+
+		expected := graph.(*directed[int, int])
+		actual := clonedGraph.(*directed[int, int])
+
+		if actual.hash(5) != expected.hash(5) {
+			t.Errorf("%s: hash expectancy doesn't match: expected %v, got %v", name, expected.hash, actual.hash)
+		}
+
+		if !traitsAreEqual(actual.traits, expected.traits) {
+			t.Errorf("%s: traits expectancy doesn't match: expected %v, got %v", name, expected.traits, actual.traits)
+		}
+
+		if len(actual.vertices) != len(expected.vertices) {
+			t.Fatalf("%s: vertices length expectancy doesn't match: expected %v, got %v", name, len(expected.vertices), len(actual.vertices))
+		}
+
+		for expectedHash, expectedVertex := range expected.vertices {
+			actualVertex, ok := actual.vertices[expectedHash]
+			if !ok {
+				t.Errorf("%s: vertex expectancy doesn't match: expected vertex %v doesn't exist", name, expectedVertex)
+			}
+			if actualVertex != expectedVertex {
+				t.Errorf("%s: vertex expectancy doesn't match: expected %v, got %v", name, expectedVertex, actualVertex)
+			}
+		}
+
+		if len(actual.edges) != len(expected.edges) {
+			t.Errorf("%s: number of edges doesn't match: expected %v, got %v", name, len(expected.edges), len(actual.edges))
+		}
+		if len(actual.inEdges) != len(expected.inEdges) {
+			t.Errorf("%s: number of inEdges doesn't match: expected %v, got %v", name, len(expected.inEdges), len(actual.inEdges))
+		}
+		if len(actual.outEdges) != len(expected.outEdges) {
+			t.Errorf("%s: number of outEdges doesn't match: expected %v, got %v", name, len(expected.outEdges), len(actual.outEdges))
+		}
+	}
+}
+
 func TestDirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
diff --git a/undirected_test.go b/undirected_test.go
index 8e6ccfc..417e12e 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -416,6 +416,82 @@ func TestUndirected_PredecessorMap(t *testing.T) {
 	}
 }
 
+func TestUndirected_Clone(t *testing.T) {
+	tests := map[string]struct {
+		vertices []int
+		edges    []Edge[int]
+	}{
+		"Y-shaped graph": {
+			vertices: []int{1, 2, 3, 4},
+			edges: []Edge[int]{
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 3},
+				{Source: 3, Target: 4},
+			},
+		},
+		"diamond-shaped graph": {
+			vertices: []int{1, 2, 3, 4},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 4},
+			},
+		},
+	}
+
+	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())
+			}
+		}
+
+		clonedGraph, err := graph.Clone()
+		if err != nil {
+			t.Fatalf("%s: failed to clone graph: %s", name, err.Error())
+		}
+
+		expected := graph.(*undirected[int, int])
+		actual := clonedGraph.(*undirected[int, int])
+
+		if actual.hash(5) != expected.hash(5) {
+			t.Errorf("%s: hash expectancy doesn't match: expected %v, got %v", name, expected.hash, actual.hash)
+		}
+
+		if !traitsAreEqual(actual.traits, expected.traits) {
+			t.Errorf("%s: traits expectancy doesn't match: expected %v, got %v", name, expected.traits, actual.traits)
+		}
+
+		if len(actual.vertices) != len(expected.vertices) {
+			t.Fatalf("%s: vertices length expectancy doesn't match: expected %v, got %v", name, len(expected.vertices), len(actual.vertices))
+		}
+
+		for expectedHash, expectedVertex := range expected.vertices {
+			actualVertex, ok := actual.vertices[expectedHash]
+			if !ok {
+				t.Errorf("%s: vertex expectancy doesn't match: expected vertex %v doesn't exist", name, expectedVertex)
+			}
+			if actualVertex != expectedVertex {
+				t.Errorf("%s: vertex expectancy doesn't match: expected %v, got %v", name, expectedVertex, actualVertex)
+			}
+		}
+
+		if len(actual.inEdges) != len(expected.inEdges) {
+			t.Errorf("%s: number of inEdges doesn't match: expected %v, got %v", name, len(expected.inEdges), len(actual.inEdges))
+		}
+		if len(actual.outEdges) != len(expected.outEdges) {
+			t.Errorf("%s: number of outEdges doesn't match: expected %v, got %v", name, len(expected.outEdges), len(actual.outEdges))
+		}
+	}
+}
+
 func TestUndirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]