Repository: dominikbraun/graph
Pull request #18 (2022-07-22 09:37:02)

Change `AdjacencyList` to `AdjacencyMap`


Patch:
diff --git a/directed.go b/directed.go
index dee1f33..0b6c92e 100644
--- a/directed.go
+++ b/directed.go
@@ -400,22 +400,26 @@ func (d *directed[K, T]) ShortestPathByHashes(sourceHash, targetHash K) ([]K, er
 	return path, nil
 }
 
-func (d *directed[K, T]) AdjacencyList() map[K][]K {
-	adjacencyList := make(map[K][]K)
+func (d *directed[K, T]) AdjacencyMap() map[K]map[K]Edge[K] {
+	adjacencyMap := make(map[K]map[K]Edge[K])
 
 	// Create an entry for each vertex to guarantee that all vertices are contained and its
 	// adjacencies can be safely accessed without a preceding check.
 	for vertexHash := range d.vertices {
-		adjacencyList[vertexHash] = make([]K, 0)
+		adjacencyMap[vertexHash] = make(map[K]Edge[K])
 	}
 
-	for vertex, outEdges := range d.outEdges {
-		for adjacencyHash := range outEdges {
-			adjacencyList[vertex] = append(adjacencyList[vertex], adjacencyHash)
+	for vertexHash, outEdges := range d.outEdges {
+		for adjacencyHash, edge := range outEdges {
+			adjacencyMap[vertexHash][adjacencyHash] = Edge[K]{
+				Source: vertexHash,
+				Target: adjacencyHash,
+				Weight: edge.Weight,
+			}
 		}
 	}
 
-	return adjacencyList
+	return adjacencyMap
 }
 
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
diff --git a/graph.go b/graph.go
index e6dc8f5..c53d371 100644
--- a/graph.go
+++ b/graph.go
@@ -155,12 +155,23 @@ type Graph[K comparable, T any] interface {
 	// vertices.
 	ShortestPathByHashes(sourceHash, targetHash K) ([]K, error)
 
-	// AdjacencyList computes an adjacency list for all vertices in the graph and returns a map
-	// with all vertex hashes mapped against a list of their adjacency hashes.
+	// AdjacencyMap computes and returns an adjacency map containing all vertices in the graph.
 	//
-	// Since the AdjacencyList map contains all vertices, it is safe to check for the adjacencies
-	// of every vertex even if some vertices don't have any adjacencies.
-	AdjacencyList() map[K][]K
+	// There is an entry for each vertex, and each of those entries is another map whose keys are
+	// the hash values of the adjacent vertices. The value is an Edge instance that stores the
+	// source and target hash values (these are the same as the map keys) as well as edge metadata.
+	//
+	// For a graph with edges AB and AC, the adjacency map would look as follows:
+	//
+	//	map[string]map[string]Edge[string]{
+	//		"A": map[string]Edge[string]{
+	//			"B": {Source: "A", Target: "B"}
+	//			"C": {Source: "A", Target: "B"}
+	//		}
+	//	}
+	//
+	// This design makes AdjacencyMap suitable for a wide variety of scenarios and demands.
+	AdjacencyMap() map[K]map[K]Edge[K]
 }
 
 // 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 d2972ed..994f874 100644
--- a/undirected.go
+++ b/undirected.go
@@ -329,22 +329,26 @@ func (u *undirected[K, T]) ShortestPathByHashes(sourceHash, targetHash K) ([]K,
 	return path, nil
 }
 
-func (u *undirected[K, T]) AdjacencyList() map[K][]K {
-	adjacencyList := make(map[K][]K)
+func (u *undirected[K, T]) AdjacencyMap() map[K]map[K]Edge[K] {
+	adjacencyMap := make(map[K]map[K]Edge[K])
 
 	// Create an entry for each vertex to guarantee that all vertices are contained and its
 	// adjacencies can be safely accessed without a preceding check.
 	for vertexHash := range u.vertices {
-		adjacencyList[vertexHash] = make([]K, 0)
+		adjacencyMap[vertexHash] = make(map[K]Edge[K])
 	}
 
-	for vertex, outEdges := range u.outEdges {
-		for adjacencyHash := range outEdges {
-			adjacencyList[vertex] = append(adjacencyList[vertex], adjacencyHash)
+	for vertexHash, outEdges := range u.outEdges {
+		for adjacencyHash, edge := range outEdges {
+			adjacencyMap[vertexHash][adjacencyHash] = Edge[K]{
+				Source: vertexHash,
+				Target: adjacencyHash,
+				Weight: edge.Weight,
+			}
 		}
 	}
 
-	return adjacencyList
+	return adjacencyMap
 }
 
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {


Test patch:
diff --git a/directed_test.go b/directed_test.go
index d06b17e..f4d9c1d 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -624,7 +624,7 @@ func TestDirected_AdjacencyList(t *testing.T) {
 	tests := map[string]struct {
 		vertices []int
 		edges    []Edge[int]
-		expected map[int][]int
+		expected map[int]map[int]Edge[int]
 	}{
 		"Y-shaped graph": {
 			vertices: []int{1, 2, 3, 4},
@@ -633,10 +633,16 @@ func TestDirected_AdjacencyList(t *testing.T) {
 				{Source: 2, Target: 3},
 				{Source: 3, Target: 4},
 			},
-			expected: map[int][]int{
-				1: {3},
-				2: {3},
-				3: {4},
+			expected: map[int]map[int]Edge[int]{
+				1: {
+					3: {Source: 1, Target: 3},
+				},
+				2: {
+					3: {Source: 2, Target: 3},
+				},
+				3: {
+					4: {Source: 3, Target: 4},
+				},
 				4: {},
 			},
 		},
@@ -648,10 +654,17 @@ func TestDirected_AdjacencyList(t *testing.T) {
 				{Source: 2, Target: 4},
 				{Source: 3, Target: 4},
 			},
-			expected: map[int][]int{
-				1: {2, 3},
-				2: {4},
-				3: {4},
+			expected: map[int]map[int]Edge[int]{
+				1: {
+					2: {Source: 1, Target: 2},
+					3: {Source: 1, Target: 3},
+				},
+				2: {
+					4: {Source: 2, Target: 4},
+				},
+				3: {
+					4: {Source: 3, Target: 4},
+				},
 				4: {},
 			},
 		},
@@ -670,16 +683,22 @@ func TestDirected_AdjacencyList(t *testing.T) {
 			}
 		}
 
-		adjacencyList := graph.AdjacencyList()
+		adjacencyMap := graph.AdjacencyMap()
 
 		for expectedVertex, expectedAdjacencies := range test.expected {
-			adjacencies, ok := adjacencyList[expectedVertex]
+			adjacencies, ok := adjacencyMap[expectedVertex]
 			if !ok {
-				t.Errorf("%s: expected vertex %v does not exist in adjacency list", name, expectedVertex)
+				t.Errorf("%s: expected vertex %v does not exist in adjacency map", name, expectedVertex)
 			}
 
-			if !slicesAreEqual(expectedAdjacencies, adjacencies) {
-				t.Errorf("%s: adjacency expectancy for vertex %v doesn't match: expected %v, got %v", name, expectedVertex, test.expected, adjacencies)
+			for expectedAdjacency, expectedEdge := range expectedAdjacencies {
+				edge, ok := adjacencies[expectedAdjacency]
+				if !ok {
+					t.Errorf("%s: expected adjacency %v does not exist in map of %v", name, expectedAdjacency, expectedVertex)
+				}
+				if edge.Source != expectedEdge.Source || edge.Target != expectedEdge.Target {
+					t.Errorf("%s: edge expectancy doesn't match: expected %v, got %v", name, expectedEdge, edge)
+				}
 			}
 		}
 	}
diff --git a/undirected_test.go b/undirected_test.go
index 37cb7c5..eece8e3 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -643,7 +643,7 @@ func TestUndirected_AdjacencyList(t *testing.T) {
 	tests := map[string]struct {
 		vertices []int
 		edges    []Edge[int]
-		expected map[int][]int
+		expected map[int]map[int]Edge[int]
 	}{
 		"Y-shaped graph": {
 			vertices: []int{1, 2, 3, 4},
@@ -652,11 +652,21 @@ func TestUndirected_AdjacencyList(t *testing.T) {
 				{Source: 2, Target: 3},
 				{Source: 3, Target: 4},
 			},
-			expected: map[int][]int{
-				1: {3},
-				2: {3},
-				3: {1, 2, 4},
-				4: {3},
+			expected: map[int]map[int]Edge[int]{
+				1: {
+					3: {Source: 1, Target: 3},
+				},
+				2: {
+					3: {Source: 2, Target: 3},
+				},
+				3: {
+					1: {Source: 3, Target: 1},
+					2: {Source: 3, Target: 2},
+					4: {Source: 3, Target: 4},
+				},
+				4: {
+					3: {Source: 4, Target: 3},
+				},
 			},
 		},
 		"diamond-shaped graph": {
@@ -667,11 +677,23 @@ func TestUndirected_AdjacencyList(t *testing.T) {
 				{Source: 2, Target: 4},
 				{Source: 3, Target: 4},
 			},
-			expected: map[int][]int{
-				1: {2, 3},
-				2: {1, 4},
-				3: {1, 4},
-				4: {2, 3},
+			expected: map[int]map[int]Edge[int]{
+				1: {
+					2: {Source: 1, Target: 2},
+					3: {Source: 1, Target: 3},
+				},
+				2: {
+					1: {Source: 2, Target: 1},
+					4: {Source: 2, Target: 4},
+				},
+				3: {
+					1: {Source: 3, Target: 1},
+					4: {Source: 3, Target: 4},
+				},
+				4: {
+					2: {Source: 4, Target: 2},
+					3: {Source: 4, Target: 3},
+				},
 			},
 		},
 	}
@@ -689,16 +711,22 @@ func TestUndirected_AdjacencyList(t *testing.T) {
 			}
 		}
 
-		adjacencyList := graph.AdjacencyList()
+		adjacencyMap := graph.AdjacencyMap()
 
 		for expectedVertex, expectedAdjacencies := range test.expected {
-			adjacencies, ok := adjacencyList[expectedVertex]
+			adjacencies, ok := adjacencyMap[expectedVertex]
 			if !ok {
-				t.Errorf("%s: expected vertex %v does not exist in adjacency list", name, expectedVertex)
+				t.Errorf("%s: expected vertex %v does not exist in adjacency map", name, expectedVertex)
 			}
 
-			if !slicesAreEqual(expectedAdjacencies, adjacencies) {
-				t.Errorf("%s: adjacency expectancy for vertex %v doesn't match: expected %v, got %v", name, expectedVertex, test.expected, adjacencies)
+			for expectedAdjacency, expectedEdge := range expectedAdjacencies {
+				edge, ok := adjacencies[expectedAdjacency]
+				if !ok {
+					t.Errorf("%s: expected adjacency %v does not exist in map of %v", name, expectedAdjacency, expectedVertex)
+				}
+				if edge.Source != expectedEdge.Source || edge.Target != expectedEdge.Target {
+					t.Errorf("%s: edge expectancy doesn't match: expected %v, got %v", name, expectedEdge, edge)
+				}
 			}
 		}
 	}