Repository: dominikbraun/graph
Pull request #71 (2023-01-09 19:15:47)

Add custom data to graph edges
This PR adds a custom data property to `EdgeProperties`. This allows the user to write custom edge data and store it in the graph using the new functional option `EdgeData(data any)`.

My use case for this is creating a DAG for a set of configuration files. These files can import one another in any way (so long as its not circular) and I need a nice way to store information about how to merge these files together on the graph edges.

I tried to find a nice way of adding an edge type to the type constraints in `graph.New()`, but the API didn't seem right and most users probably won't need edge data anyway. Instead, I opted for a simpler (non-API breaking) design that uses a simple `any` interface. Unfortunately, this means the user has to type assert the edge data when pulling it out of the graph. However, I believe this is better than adding a third type constraint and overhauling the API for a feature that most people don't need.

dominikbraun: Thanks for your PR! I get the use case and I agree with all you said - it's not ideal to need these type assertions, but introducing a third generic parameter is even less ideal. I'll review this one.

@geoah Does this change collide with your PR?
geoah: @dominikbraun nothing that we can't resolve. There will be a slight issue with unmarshalling stuff into an `interface{}` but that will be an issue only for non in-memory storage implementations. I'll rebase my PR on this and will start looking for a solution for this issue. I'll bug you and @pd93 with some options once the rebase is done.
dominikbraun: > There will be a slight issue with unmarshalling stuff into an `interface{}` but that will be an issue only for non in-memory storage implementations.

@geoah Yes... Storing the custom metadata as a `[]byte` came to my mind quickly, but I'm not sure if that would be nice to work with as a user.

geoah: Yeah doesn't sound really fun from a developer experience perspective.

My current thinking is defering this to the storage implementation/implementer, something in these lines maybe?
```go
type ValueScanner interface {
	Value() ([]byte, error)
	Scan([]byte) error
}

func NewSQLStore[K comparable, T any](
	edgePropertiesValueScanner ValueScanner,
) Store[K, T] {
	return &SQLStore{
		edgePropertiesValueScannerType: reflect.TypeOf(edgePropertiesValueScanner),
		// ...
	}
}

func (s *SQLStore) ListEdges() ([]Edge[K], error) {
	// fetch edges from database
	// ...

	// loop over edges
	// ...
	edgePropertiesPtr := reflect.New(reflect.TypeOf(s.edgePropertiesValueScannerType))
	edgeProperties := edgePropertiesPtr.Elem().Interface().(ValueScanner)
	edgeProperties.Scan(row.EdgePropertiesBytes)

	// ...
}
```


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 3ac9b06..53c98d3 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -5,6 +5,14 @@ All notable changes to this project will be documented in this file.
 The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/),  and this project
 adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
 
+## [0.15.1] - 2023-01-18
+
+### Changed
+* Changed `ShortestPath` to return `ErrTargetNotReachable` if the target vertex is not reachable.
+
+### Fixed
+* Fixed `ShortestPath` to return correct results for large unweighted graphs.
+
 ## [0.15.0] - 2022-11-25
 
 ### Added
diff --git a/directed.go b/directed.go
index 8d67680..694756d 100644
--- a/directed.go
+++ b/directed.go
@@ -160,6 +160,7 @@ func (d *directed[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 				Properties: EdgeProperties{
 					Weight:     edge.Properties.Weight,
 					Attributes: edge.Properties.Attributes,
+					Data:       edge.Properties.Data,
 				},
 			}
 		}
@@ -183,6 +184,7 @@ func (d *directed[K, T]) PredecessorMap() (map[K]map[K]Edge[K], error) {
 				Properties: EdgeProperties{
 					Attributes: edge.Properties.Attributes,
 					Weight:     edge.Properties.Weight,
+					Data:       edge.Properties.Data,
 				},
 			}
 		}
@@ -296,6 +298,7 @@ func cloneEdges[K comparable, T any](input map[K]map[K]Edge[T]) map[K]map[K]Edge
 				Properties: EdgeProperties{
 					Attributes: attributes,
 					Weight:     edge.Properties.Weight,
+					Data:       edge.Properties.Data,
 				},
 			}
 		}
diff --git a/graph.go b/graph.go
index deb31bd..411edac 100644
--- a/graph.go
+++ b/graph.go
@@ -113,6 +113,7 @@ type Edge[T any] struct {
 type EdgeProperties struct {
 	Attributes map[string]string
 	Weight     int
+	Data       any
 }
 
 // Hash is a hashing function that takes a vertex of type T and returns a hash value of type K.
@@ -205,6 +206,14 @@ func EdgeAttribute(key, value string) func(*EdgeProperties) {
 	}
 }
 
+// EdgeData returns a function that sets the data of an edge to the given value. This is a functional
+// option for the Edge and AddEdge methods.
+func EdgeData(data any) func(*EdgeProperties) {
+	return func(e *EdgeProperties) {
+		e.Data = data
+	}
+}
+
 // VertexProperties represents a set of properties that each vertex has. They can be set when adding
 // a new vertex using the functional options provided by this library:
 //
diff --git a/paths.go b/paths.go
index 13e614e..63547e5 100644
--- a/paths.go
+++ b/paths.go
@@ -6,6 +6,8 @@ import (
 	"math"
 )
 
+var ErrTargetNotReachable = errors.New("target vertex not reachable from source")
+
 // CreatesCycle determines whether an edge between the given source and target vertices would
 // introduce a cycle. It won't create that edge in any case.
 //
@@ -66,21 +68,16 @@ func CreatesCycle[K comparable, T any](g Graph[K, T], source, target K) (bool, e
 }
 
 // ShortestPath computes the shortest path between a source and a target vertex using the edge
-// weights and returns the hash values of the vertices forming that path. This search runs in
-// O(|V|+|E|log(|V|)) time.
+// weights and returns the hash values of the vertices forming that path using Dijkstra's algorithm.
+// This search runs in O(|V|+|E|log(|V|)) time.
 //
 // The returned path includes the source and target vertices. If the target cannot be reached
-// from the source vertex, ShortestPath returns an error. If there are multiple shortest paths,
-// an arbitrary one will be returned.
+// from the source vertex, ErrTargetNotReachable will be returned. If there are multiple shortest
+// paths, an arbitrary one will be returned.
 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)
 
-	// bestPredecessors stores the best (i.e. cheapest or least-weighted) predecessor for each
-	// vertex. If there is an edge AC with weight 4 and an edge BC with weight 2, the best
-	// predecessor for C is B.
-	bestPredecessors := make(map[K]K)
-
 	weights[source] = 0
 	visited[target] = true
 
@@ -90,11 +87,6 @@ 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)
 	}
 
-	predecessorMap, err := g.PredecessorMap()
-	if err != nil {
-		return nil, fmt.Errorf("failed to get predecessor map: %w", err)
-	}
-
 	for hash := range adjacencyMap {
 		if hash != source {
 			weights[hash] = math.Inf(1)
@@ -104,20 +96,19 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 		queue.Push(hash, weights[hash])
 	}
 
+	// bestPredecessors stores the best (i.e. cheapest or least-weighted) predecessor for each
+	// vertex. If there is an edge AC with weight 4 and an edge BC with weight 2, the best
+	// predecessor for C is B.
+	bestPredecessors := make(map[K]K)
+
 	for queue.Len() > 0 {
 		vertex, _ := queue.Pop()
 		hasInfiniteWeight := math.IsInf(weights[vertex], 1)
 
-		if vertex == target {
-			targetPredecessors := predecessorMap[target]
-
-			if len(targetPredecessors) == 0 {
-				return nil, fmt.Errorf("vertex %v is not reachable from vertex %v", target, source)
-			}
-		}
-
 		for adjacency, edge := range adjacencyMap[vertex] {
-			weight := weights[vertex] + float64(edge.Properties.Weight)
+			// Adding 1 to the actual weight is necessary for unweighted graphs with weights of 0.
+			// Otherwise, all paths would have a sum of 0 and a random path would be returned.
+			weight := weights[vertex] + float64(edge.Properties.Weight) + 1
 
 			if weight < weights[adjacency] && !hasInfiniteWeight {
 				weights[adjacency] = weight
@@ -135,7 +126,7 @@ func ShortestPath[K comparable, T any](g Graph[K, T], source, target K) ([]K, er
 		// If hashCursor is not a present key in bestPredecessors, hashCursor is set to the zero
 		// value. Without this check, this leads to endless prepending of zeros to the path.
 		if _, ok := bestPredecessors[hashCursor]; !ok {
-			return nil, fmt.Errorf("vertex %v is not reachable from vertex %v", target, source)
+			return nil, ErrTargetNotReachable
 		}
 		hashCursor = bestPredecessors[hashCursor]
 		path = append([]K{hashCursor}, path...)
diff --git a/undirected.go b/undirected.go
index 1affc5b..e71e266 100644
--- a/undirected.go
+++ b/undirected.go
@@ -164,6 +164,7 @@ func (u *undirected[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
 				Properties: EdgeProperties{
 					Weight:     edge.Properties.Weight,
 					Attributes: edge.Properties.Attributes,
+					Data:       edge.Properties.Data,
 				},
 			}
 		}


Test patch:
diff --git a/directed_test.go b/directed_test.go
index dff535e..c9154e8 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -234,6 +234,28 @@ func TestDirected_AddEdge(t *testing.T) {
 			},
 			traits: &Traits{},
 		},
+		"edge with data": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{
+					Source: 1,
+					Target: 2,
+					Properties: EdgeProperties{
+						Data: "foo",
+					},
+				},
+			},
+			expectedEdges: []Edge[int]{
+				{
+					Source: 1,
+					Target: 2,
+					Properties: EdgeProperties{
+						Data: "foo",
+					},
+				},
+			},
+			traits: &Traits{},
+		},
 	}
 
 	for name, test := range tests {
@@ -247,12 +269,12 @@ func TestDirected_AddEdge(t *testing.T) {
 
 		for _, edge := range test.edges {
 			if len(edge.Properties.Attributes) == 0 {
-				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight))
+				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeData(edge.Properties.Data))
 			}
 			// If there are edge attributes, iterate over them and call EdgeAttribute for each
 			// entry. An edge should only have one attribute so that AddEdge is invoked once.
 			for key, value := range edge.Properties.Attributes {
-				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeAttribute(key, value))
+				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeData(edge.Properties.Data), EdgeAttribute(key, value))
 			}
 			if err != nil {
 				break
@@ -297,6 +319,10 @@ func TestDirected_AddEdge(t *testing.T) {
 					t.Errorf("%s: attribute values don't match: expected value %v for key %v, got %v", name, expectedValue, expectedKey, value)
 				}
 			}
+
+			if edge.Properties.Data != expectedEdge.Properties.Data {
+				t.Errorf("%s: edge data doesn't match: expected data %v, got %v", name, expectedEdge.Properties.Data, edge.Properties.Data)
+			}
 		}
 	}
 }
diff --git a/paths_test.go b/paths_test.go
index c356213..85279e8 100644
--- a/paths_test.go
+++ b/paths_test.go
@@ -1,6 +1,8 @@
 package graph
 
-import "testing"
+import (
+	"testing"
+)
 
 func TestDirectedCreatesCycle(t *testing.T) {
 	tests := map[string]struct {
@@ -193,6 +195,21 @@ func TestDirectedShortestPath(t *testing.T) {
 			targetHash:           "D",
 			expectedShortestPath: []string{"A", "B", "D"},
 		},
+		"unweighted graph": {
+			vertices: []string{"A", "B", "C", "D", "E", "F", "G"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Properties: EdgeProperties{}},
+				{Source: "A", Target: "C", Properties: EdgeProperties{}},
+				{Source: "B", Target: "D", Properties: EdgeProperties{}},
+				{Source: "C", Target: "F", Properties: EdgeProperties{}},
+				{Source: "D", Target: "G", Properties: EdgeProperties{}},
+				{Source: "E", Target: "G", Properties: EdgeProperties{}},
+				{Source: "F", Target: "E", Properties: EdgeProperties{}},
+			},
+			sourceHash:           "A",
+			targetHash:           "G",
+			expectedShortestPath: []string{"A", "B", "D", "G"},
+		},
 		"source equal to target": {
 			vertices: []string{"A", "B", "C", "D"},
 			edges: []Edge[string]{
@@ -205,7 +222,7 @@ func TestDirectedShortestPath(t *testing.T) {
 			targetHash:           "B",
 			expectedShortestPath: []string{"B"},
 		},
-		"target not reachable": {
+		"target not reachable in a disconnected graph": {
 			vertices: []string{"A", "B", "C", "D"},
 			edges: []Edge[string]{
 				{Source: "A", Target: "B", Properties: EdgeProperties{Weight: 2}},
@@ -216,7 +233,7 @@ func TestDirectedShortestPath(t *testing.T) {
 			expectedShortestPath: []string{},
 			shouldFail:           true,
 		},
-		"target not reachable connected directed graph": {
+		"target not reachable in a connected graph": {
 			vertices: []string{"A", "B", "C"},
 			edges: []Edge[string]{
 				{Source: "A", Target: "B", Properties: EdgeProperties{Weight: 0}},
@@ -299,6 +316,21 @@ func TestUndirectedShortestPath(t *testing.T) {
 			targetHash:           "D",
 			expectedShortestPath: []string{"A", "B", "D"},
 		},
+		"unweighted graph": {
+			vertices: []string{"A", "B", "C", "D", "E", "F", "G"},
+			edges: []Edge[string]{
+				{Source: "A", Target: "B", Properties: EdgeProperties{}},
+				{Source: "A", Target: "C", Properties: EdgeProperties{}},
+				{Source: "B", Target: "D", Properties: EdgeProperties{}},
+				{Source: "C", Target: "F", Properties: EdgeProperties{}},
+				{Source: "D", Target: "G", Properties: EdgeProperties{}},
+				{Source: "E", Target: "G", Properties: EdgeProperties{}},
+				{Source: "F", Target: "E", Properties: EdgeProperties{}},
+			},
+			sourceHash:           "A",
+			targetHash:           "G",
+			expectedShortestPath: []string{"A", "B", "D", "G"},
+		},
 		"source equal to target": {
 			vertices: []string{"A", "B", "C", "D"},
 			edges: []Edge[string]{
@@ -311,7 +343,7 @@ func TestUndirectedShortestPath(t *testing.T) {
 			targetHash:           "B",
 			expectedShortestPath: []string{"B"},
 		},
-		"target not reachable": {
+		"target not reachable in a disconnected graph": {
 			vertices: []string{"A", "B", "C", "D"},
 			edges: []Edge[string]{
 				{Source: "A", Target: "B", Properties: EdgeProperties{Weight: 2}},
diff --git a/undirected_test.go b/undirected_test.go
index 7161652..6acaf74 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -234,6 +234,28 @@ func TestUndirected_AddEdge(t *testing.T) {
 			},
 			traits: &Traits{},
 		},
+		"edge with data": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{
+					Source: 1,
+					Target: 2,
+					Properties: EdgeProperties{
+						Data: "foo",
+					},
+				},
+			},
+			expectedEdges: []Edge[int]{
+				{
+					Source: 1,
+					Target: 2,
+					Properties: EdgeProperties{
+						Data: "foo",
+					},
+				},
+			},
+			traits: &Traits{},
+		},
 	}
 
 	for name, test := range tests {
@@ -247,12 +269,12 @@ func TestUndirected_AddEdge(t *testing.T) {
 
 		for _, edge := range test.edges {
 			if len(edge.Properties.Attributes) == 0 {
-				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight))
+				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeData(edge.Properties.Data))
 			}
 			// If there are edge attributes, iterate over them and call EdgeAttribute for each
 			// entry. An edge should only have one attribute so that AddEdge is invoked once.
 			for key, value := range edge.Properties.Attributes {
-				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeAttribute(key, value))
+				err = graph.AddEdge(edge.Source, edge.Target, EdgeWeight(edge.Properties.Weight), EdgeData(edge.Properties.Data), EdgeAttribute(key, value))
 			}
 			if err != nil {
 				break
@@ -297,6 +319,10 @@ func TestUndirected_AddEdge(t *testing.T) {
 					t.Errorf("%s: attribute values don't match: expected value %v for key %v, got %v", name, expectedValue, expectedKey, value)
 				}
 			}
+
+			if edge.Properties.Data != expectedEdge.Properties.Data {
+				t.Errorf("%s: edge data doesn't match: expected data %v, got %v", name, expectedEdge.Properties.Data, edge.Properties.Data)
+			}
 		}
 	}
 }