Repository: dominikbraun/graph
Pull request #34 (2022-09-02 21:17:06)

Change `Predecessors` method signature and behavior


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 658b76e..6970149 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -9,6 +9,9 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 
 ### Added
 
+### Changed
+* Changed the `Predecessors` method signature and behavior towards returning a predecessor map containing all vertices.
+
 ## [0.9.0] - 2022-08-17
 
 ### Added
diff --git a/directed.go b/directed.go
index 9b76a6f..adae072 100644
--- a/directed.go
+++ b/directed.go
@@ -127,18 +127,23 @@ func (d *directed[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 	return adjacencyMap, nil
 }
 
-func (d *directed[K, T]) Predecessors(vertex K) (map[K]Edge[K], error) {
-	if _, ok := d.vertices[vertex]; !ok {
-		return nil, fmt.Errorf("vertex with hash %v doesn't exist", vertex)
-	}
+func (d *directed[K, T]) Predecessors() (map[K]map[K]Edge[K], error) {
+	predecessors := make(map[K]map[K]Edge[K])
 
-	predecessors := make(map[K]Edge[K])
+	for vertexHash := range d.vertices {
+		predecessors[vertexHash] = make(map[K]Edge[K])
+	}
 
-	for predecessor, edge := range d.inEdges[vertex] {
-		predecessors[predecessor] = Edge[K]{
-			Source:     vertex,
-			Target:     predecessor,
-			Properties: edge.Properties,
+	for vertexHash, inEdges := range d.inEdges {
+		for predecessorHash, edge := range inEdges {
+			predecessors[vertexHash][predecessorHash] = Edge[K]{
+				Source: predecessorHash,
+				Target: vertexHash,
+				Properties: EdgeProperties{
+					Attributes: edge.Properties.Attributes,
+					Weight:     edge.Properties.Weight,
+				},
+			}
 		}
 	}
 
diff --git a/graph.go b/graph.go
index dff109b..ddf71f0 100644
--- a/graph.go
+++ b/graph.go
@@ -54,13 +54,15 @@ type Graph[K comparable, T any] interface {
 	// This design makes AdjacencyMap suitable for a wide variety of scenarios and demands.
 	AdjacencyMap() (map[K]map[K]Edge[K], error)
 
-	// Predecessors determines and returns the predecessors of the vertex with the given hash.
+	// Predecessors computes and returns a predecessors map containing all vertices in the graph.
 	//
-	// In a directed graph, these are the directed predecessors with an outgoing edge to the given
-	// edge whereas in an undirected graph, all adjacent vertices are considered as predecessors.
+	// The map layout is the same as for Adjacencies.
 	//
-	// Consequently, Predecessors returns a subset of AdjacencyMap for the given vertex.
-	Predecessors(vertex K) (map[K]Edge[K], error)
+	// For an undirected graph, Predecessors is the same as Adjacencies. For a directed graph,
+	// Predecessors is the complement of Adjacencies. This is because in a directed graph, only
+	// vertices joined by an outgoing edge are considered adjacent to the current vertex, whereas
+	// predecessors are the vertices joined by an ingoing edge.
+	Predecessors() (map[K]map[K]Edge[K], error)
 }
 
 // Edge represents a graph edge with a source and target vertex as well as a weight, which has the
diff --git a/paths.go b/paths.go
index 653b8aa..dbce8aa 100644
--- a/paths.go
+++ b/paths.go
@@ -34,6 +34,11 @@ func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, e
 		return true, nil
 	}
 
+	predecessors, err := g.Predecessors()
+	if err != nil {
+		return false, fmt.Errorf("failed to get predecessors: %w", err)
+	}
+
 	stack := make([]K, 0)
 	visited := make(map[K]bool)
 
@@ -51,9 +56,7 @@ func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, e
 			}
 			visited[currentHash] = true
 
-			predecessors, _ := g.Predecessors(currentHash)
-
-			for adjacency := range predecessors {
+			for adjacency := range predecessors[currentHash] {
 				stack = append(stack, adjacency)
 			}
 		}
@@ -72,7 +75,7 @@ func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, e
 func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, error) {
 	weights := make(map[K]float64)
 	visited := make(map[K]bool)
-	predecessors := make(map[K]K)
+	bestPredecessors := make(map[K]K)
 
 	weights[source] = 0
 	visited[target] = true
@@ -83,6 +86,11 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 		return nil, fmt.Errorf("could not get adjacency map: %w", err)
 	}
 
+	predecessors, err := g.Predecessors()
+	if err != nil {
+		return nil, fmt.Errorf("failed to get predecessors: %w", err)
+	}
+
 	for hash := range adjacencyMap {
 		if hash != source {
 			weights[hash] = math.Inf(1)
@@ -97,10 +105,8 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 		hasInfiniteWeight := math.IsInf(weights[vertex], 1)
 
 		if vertex == target {
-			targetPredecessors, err := g.Predecessors(target)
-			if err != nil {
-				return nil, fmt.Errorf("failed to get predecessors of %v: %w", target, err)
-			}
+			targetPredecessors := predecessors[target]
+
 			if len(targetPredecessors) == 0 {
 				return nil, fmt.Errorf("vertex %v is not reachable from vertex %v", target, source)
 			}
@@ -111,7 +117,7 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 
 			if weight < weights[adjacency] && !hasInfiniteWeight {
 				weights[adjacency] = weight
-				predecessors[adjacency] = vertex
+				bestPredecessors[adjacency] = vertex
 				queue.DecreasePriority(adjacency, weight)
 			}
 		}
@@ -122,7 +128,7 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 	hashCursor := target
 
 	for hashCursor != source {
-		hashCursor = predecessors[hashCursor]
+		hashCursor = bestPredecessors[hashCursor]
 		path = append([]K{hashCursor}, path...)
 	}
 
diff --git a/undirected.go b/undirected.go
index 3c7a9e6..749abd7 100644
--- a/undirected.go
+++ b/undirected.go
@@ -130,22 +130,8 @@ func (u *undirected[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 	return adjacencyMap, nil
 }
 
-func (u *undirected[K, T]) Predecessors(vertex K) (map[K]Edge[K], error) {
-	if _, ok := u.vertices[vertex]; !ok {
-		return nil, fmt.Errorf("vertex with hash %v doesn't exist", vertex)
-	}
-
-	predecessors := make(map[K]Edge[K])
-
-	for predecessor, edge := range u.inEdges[vertex] {
-		predecessors[predecessor] = Edge[K]{
-			Source:     vertex,
-			Target:     predecessor,
-			Properties: edge.Properties,
-		}
-	}
-
-	return predecessors, nil
+func (u *undirected[K, T]) Predecessors() (map[K]map[K]Edge[K], error) {
+	return u.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 ac2c8cc..214d419 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -315,6 +315,89 @@ func TestDirected_AdjacencyList(t *testing.T) {
 	}
 }
 
+func TestDirected_Predecessors(t *testing.T) {
+	tests := map[string]struct {
+		vertices []int
+		edges    []Edge[int]
+		expected map[int]map[int]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},
+			},
+			expected: map[int]map[int]Edge[int]{
+				1: {},
+				2: {},
+				3: {
+					1: {Source: 1, Target: 3},
+					2: {Source: 2, Target: 3},
+				},
+				4: {
+					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},
+			},
+			expected: map[int]map[int]Edge[int]{
+				1: {},
+				2: {
+					1: {Source: 1, Target: 2},
+				},
+				3: {
+					1: {Source: 1, Target: 3},
+				},
+				4: {
+					2: {Source: 2, Target: 4},
+					3: {Source: 3, Target: 4},
+				},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		graph := newDirected(IntHash, &Traits{})
+
+		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())
+			}
+		}
+
+		predecessors, _ := graph.Predecessors()
+
+		for expectedVertex, expectedPredecessors := range test.expected {
+			predecessors, ok := predecessors[expectedVertex]
+			if !ok {
+				t.Errorf("%s: expected vertex %v does not exist in adjacency map", name, expectedVertex)
+			}
+
+			for expectedPredecessor, expectedEdge := range expectedPredecessors {
+				edge, ok := predecessors[expectedPredecessor]
+				if !ok {
+					t.Errorf("%s: expected adjacency %v does not exist in map of %v", name, expectedPredecessor, 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)
+				}
+			}
+		}
+	}
+}
+
 func TestDirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
diff --git a/undirected_test.go b/undirected_test.go
index 69d89fb..1717c31 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -176,7 +176,7 @@ func TestUndirected_Edge(t *testing.T) {
 	}
 }
 
-func TestUndirected_AdjacencyList(t *testing.T) {
+func TestUndirected_Adjacencies(t *testing.T) {
 	tests := map[string]struct {
 		vertices []int
 		edges    []Edge[int]
@@ -269,6 +269,99 @@ func TestUndirected_AdjacencyList(t *testing.T) {
 	}
 }
 
+func TestUndirected_Predecessors(t *testing.T) {
+	tests := map[string]struct {
+		vertices []int
+		edges    []Edge[int]
+		expected map[int]map[int]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},
+			},
+			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": {
+			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},
+			},
+			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},
+				},
+			},
+		},
+	}
+
+	for name, test := range tests {
+		graph := newUndirected(IntHash, &Traits{})
+
+		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())
+			}
+		}
+
+		predecessors, _ := graph.Predecessors()
+
+		for expectedVertex, expectedPredecessors := range test.expected {
+			predecessors, ok := predecessors[expectedVertex]
+			if !ok {
+				t.Errorf("%s: expected vertex %v does not exist in adjacency map", name, expectedVertex)
+			}
+
+			for expectedPredecessor, expectedEdge := range expectedPredecessors {
+				edge, ok := predecessors[expectedPredecessor]
+				if !ok {
+					t.Errorf("%s: expected adjacency %v does not exist in map of %v", name, expectedPredecessor, 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)
+				}
+			}
+		}
+	}
+}
+
 func TestUndirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]