Repository: dominikbraun/graph
Pull request #50 (2022-09-19 18:24:24)

Proposal: Decouple vertice/edge store from graphs
Hey @dominikbraun, sorry for the delay, managed to get some time to give this another shot.

The pull requests lifts-and-shifts the storage part of the verticies and edges into its own store interface so that we can then start implementing additional non in-memory stores.

```golang
type Store[K comparable, T any] interface {
	AddVertex(hash K, value T) error
	Vertex(hash K) (T, error)
	ListVertices() ([]K, error) // not currently used
	CountVertices() (int, error)
	AddEdge(sourceHash, targetHash K, edge Edge[K]) error
	RemoveEdge(sourceHash, targetHash K) error
	Edge(sourceHash, targetHash K) (Edge[K], error)
	GetEdgesBySource(sourceHash K) ([]Edge[K], error)
	GetEdgesByTarget(targetHash K) ([]Edge[K], error) // not currently used
	AdjacencyMap() (map[K]map[K]Edge[K], error)
	PredecessorMap() (map[K]map[K]Edge[K], error)
}
```

I see that you're consistantly making changes to the api of the graph, and I'm kind of worried that this change might be a bit restrictive for iterating quickly.

Please do take a look and let me know what you think and if there is a different direction you think might make more sense.

Regards, George

dominikbraun: Wow, thanks again! This time, there isn't as much "time pressure" as last time regarding merge conflicts and the evolution of the codebase, because all the algorithms have their own isolated functions and the internal vertex and edge CRUD operations are unlikely to change. The `Graph` interface on the other hand has been stabilized with the latest releases - the `AdjacencyMap` and `PredecessorMap` methods meet the needs of a lot of algorithms. 
geoah: Hey @dominikbraun, just pushed a commit to make the linters happy. 😂 

When you get a change please check out the state of this PR and see if there is anything else you think would be needed before possibly merging.
geoah: @dominikbraun rebased on current main, a review and a list of things you'd like to see fixed before we can merge this would be appreciated, and I tackle them asap. :D
dominikbraun: @geoah Thanks, I'm gonna take a look!
geoah: @dominikbraun happy new year! :D Hope you're having a great 2023 so far. 🎉 🎊 

Just wanted to check if you are still interested in merging this, and if so if there is any chance you have some time to review this at some point. I'm more than happy to refactor things you don't like either before or after getting this merged.

No worries if you don't want to go ahead with merging this, happy to maintain this as a fork for my own use cases. In which case please feel free to close this PR. :)

Thank you very much in advance.
dominikbraun: @geoah Happy new year! 🎊 The last couple of weeks have been very stressful because I've interviewed with a new company, but I'll review the PR within the next couple of days. I want this change to be contained in one of the next few releases.
geoah: @dominikbraun good luck and I hope it all works out with your interview! :D 🤞 
Please do not stress about this at all, we can revisit this at a later date when you have some spare time! :)

Patch:
diff --git a/.golangci.yml b/.golangci.yml
index 6542aed..3e01292 100644
--- a/.golangci.yml
+++ b/.golangci.yml
@@ -6,14 +6,12 @@ linters:
   enable:
     - govet
     - gofumpt
-    - deadcode
     - errcheck
     - gosimple
     - ineffassign
     - staticcheck
     - typecheck
     - unused
-    - varcheck
 
 linters-settings:
   govet:
diff --git a/dag.go b/dag.go
index 4766683..22c3970 100644
--- a/dag.go
+++ b/dag.go
@@ -52,7 +52,12 @@ func TopologicalSort[K comparable, T any](g Graph[K, T]) ([]K, error) {
 		}
 	}
 
-	if len(order) != g.Order() {
+	gOrder, err := g.Order()
+	if err != nil {
+		return nil, fmt.Errorf("failed to get graph order: %w", err)
+	}
+
+	if len(order) != gOrder {
 		return nil, errors.New("topological sort cannot be computed on graph with cycles")
 	}
 
@@ -85,10 +90,14 @@ func TransitiveReduction[K comparable, T any](g Graph[K, T]) (Graph[K, T], error
 		//
 		// These edges are redundant because their targets obviously are reachable through the DFS,
 		// hence they can be removed from the top-level vertex.
+		tOrder, err := transitiveReduction.Order()
+		if err != nil {
+			return nil, fmt.Errorf("failed to get graph order: %w", err)
+		}
 		for successor := range successors {
-			stack := make([]K, 0, transitiveReduction.Order())
-			visited := make(map[K]struct{}, transitiveReduction.Order())
-			onStack := make(map[K]bool, transitiveReduction.Order())
+			stack := make([]K, 0, tOrder)
+			visited := make(map[K]struct{}, tOrder)
+			onStack := make(map[K]bool, tOrder)
 
 			stack = append(stack, successor)
 
diff --git a/directed.go b/directed.go
index 694756d..ce7ad33 100644
--- a/directed.go
+++ b/directed.go
@@ -6,24 +6,16 @@ import (
 )
 
 type directed[K comparable, T any] struct {
-	hash             Hash[K, T]
-	traits           *Traits
-	vertices         map[K]T
-	vertexProperties map[K]*VertexProperties
-	edges            map[K]map[K]Edge[T]
-	outEdges         map[K]map[K]Edge[T]
-	inEdges          map[K]map[K]Edge[T]
+	hash   Hash[K, T]
+	traits *Traits
+	store  Store[K, T]
 }
 
-func newDirected[K comparable, T any](hash Hash[K, T], traits *Traits) *directed[K, T] {
+func newDirected[K comparable, T any](hash Hash[K, T], traits *Traits, store Store[K, T]) *directed[K, T] {
 	return &directed[K, T]{
-		hash:             hash,
-		traits:           traits,
-		vertices:         make(map[K]T),
-		vertexProperties: make(map[K]*VertexProperties),
-		edges:            make(map[K]map[K]Edge[T]),
-		outEdges:         make(map[K]map[K]Edge[T]),
-		inEdges:          make(map[K]map[K]Edge[T]),
+		hash:   hash,
+		traits: traits,
+		store:  store,
 	}
 }
 
@@ -33,56 +25,41 @@ func (d *directed[K, T]) Traits() *Traits {
 
 func (d *directed[K, T]) AddVertex(value T, options ...func(*VertexProperties)) error {
 	hash := d.hash(value)
-
-	if _, ok := d.vertices[hash]; ok {
-		return ErrVertexAlreadyExists
-	}
-
-	d.vertices[hash] = value
-	d.vertexProperties[hash] = &VertexProperties{
+	properties := VertexProperties{
 		Weight:     0,
 		Attributes: make(map[string]string),
 	}
 
 	for _, option := range options {
-		option(d.vertexProperties[hash])
+		option(&properties)
 	}
 
-	return nil
+	return d.store.AddVertex(hash, value, properties)
 }
 
 func (d *directed[K, T]) Vertex(hash K) (T, error) {
-	vertex, ok := d.vertices[hash]
-	if !ok {
-		return vertex, ErrVertexNotFound
-	}
-
-	return vertex, nil
+	vertex, _, err := d.store.Vertex(hash)
+	return vertex, err
 }
 
 func (d *directed[K, T]) VertexWithProperties(hash K) (T, VertexProperties, error) {
-	vertex, err := d.Vertex(hash)
+	vertex, properties, err := d.store.Vertex(hash)
 	if err != nil {
 		return vertex, VertexProperties{}, err
 	}
 
-	properties, ok := d.vertexProperties[hash]
-	if !ok {
-		return vertex, *properties, ErrVertexNotFound
-	}
-
-	return vertex, *properties, nil
+	return vertex, properties, nil
 }
 
 func (d *directed[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*EdgeProperties)) error {
-	source, ok := d.vertices[sourceHash]
-	if !ok {
-		return fmt.Errorf("source vertex %v: %w", sourceHash, ErrVertexNotFound)
+	_, _, err := d.store.Vertex(sourceHash)
+	if err != nil {
+		return fmt.Errorf("source vertex %v: %w", sourceHash, err)
 	}
 
-	target, ok := d.vertices[targetHash]
-	if !ok {
-		return fmt.Errorf("target vertex %v: %w", targetHash, ErrVertexNotFound)
+	_, _, err = d.store.Vertex(targetHash)
+	if err != nil {
+		return fmt.Errorf("target vertex %v: %w", targetHash, err)
 	}
 
 	if _, err := d.Edge(sourceHash, targetHash); !errors.Is(err, ErrEdgeNotFound) {
@@ -100,9 +77,9 @@ func (d *directed[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Edge
 		}
 	}
 
-	edge := Edge[T]{
-		Source: source,
-		Target: target,
+	edge := Edge[K]{
+		Source: sourceHash,
+		Target: targetHash,
 		Properties: EdgeProperties{
 			Attributes: make(map[string]string),
 		},
@@ -112,23 +89,34 @@ func (d *directed[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Edge
 		option(&edge.Properties)
 	}
 
-	d.addEdge(sourceHash, targetHash, edge)
-
-	return nil
+	return d.addEdge(sourceHash, targetHash, edge)
 }
 
 func (d *directed[K, T]) Edge(sourceHash, targetHash K) (Edge[T], error) {
-	sourceEdges, ok := d.edges[sourceHash]
-	if !ok {
-		return Edge[T]{}, ErrEdgeNotFound
+	edge, err := d.store.Edge(sourceHash, targetHash)
+	if err != nil {
+		return Edge[T]{}, err
 	}
 
-	edge, ok := sourceEdges[targetHash]
-	if !ok {
-		return Edge[T]{}, ErrEdgeNotFound
+	sourceVertex, _, err := d.store.Vertex(sourceHash)
+	if err != nil {
+		return Edge[T]{}, err
 	}
 
-	return edge, nil
+	targetVertex, _, err := d.store.Vertex(targetHash)
+	if err != nil {
+		return Edge[T]{}, err
+	}
+
+	return Edge[T]{
+		Source: sourceVertex,
+		Target: targetVertex,
+		Properties: EdgeProperties{
+			Weight:     edge.Properties.Weight,
+			Attributes: edge.Properties.Attributes,
+			Data:       edge.Properties.Data,
+		},
+	}, nil
 }
 
 func (d *directed[K, T]) RemoveEdge(source, target K) error {
@@ -136,61 +124,66 @@ func (d *directed[K, T]) RemoveEdge(source, target K) error {
 		return err
 	}
 
-	delete(d.edges[source], target)
-	delete(d.inEdges[target], source)
-	delete(d.outEdges[source], target)
+	if err := d.store.RemoveEdge(source, target); err != nil {
+		return fmt.Errorf("failed to remove edge from %v to %v: %w", source, target, err)
+	}
 
 	return nil
 }
 
 func (d *directed[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
-	adjacencyMap := make(map[K]map[K]Edge[K])
+	vertices, err := d.store.ListVertices()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list vertices: %w", err)
+	}
 
-	// Create an entry for each vertex to guarantee that all vertices are contained and its
-	// adjacent vertices can be safely accessed without a preceding check.
-	for vertexHash := range d.vertices {
-		adjacencyMap[vertexHash] = make(map[K]Edge[K])
+	edges, err := d.store.ListEdges()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list edges: %w", err)
 	}
 
-	for vertexHash, outEdges := range d.outEdges {
-		for adjacencyHash, edge := range outEdges {
-			adjacencyMap[vertexHash][adjacencyHash] = Edge[K]{
-				Source: vertexHash,
-				Target: adjacencyHash,
-				Properties: EdgeProperties{
-					Weight:     edge.Properties.Weight,
-					Attributes: edge.Properties.Attributes,
-					Data:       edge.Properties.Data,
-				},
-			}
-		}
+	m := make(map[K]map[K]Edge[K])
+
+	for _, vertex := range vertices {
+		m[vertex] = make(map[K]Edge[K])
 	}
 
-	return adjacencyMap, nil
+	for _, edge := range edges {
+		m[edge.Source][edge.Target] = edge
+	}
+
+	return m, nil
 }
 
 func (d *directed[K, T]) PredecessorMap() (map[K]map[K]Edge[K], error) {
-	predecessors := make(map[K]map[K]Edge[K])
+	m := make(map[K]map[K]Edge[K])
+
+	vertices, err := d.store.ListVertices()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list vertices: %w", err)
+	}
 
-	for vertexHash := range d.vertices {
-		predecessors[vertexHash] = make(map[K]Edge[K])
+	edges, err := d.store.ListEdges()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list edges: %w", err)
+	}
+
+	for _, vertex := range vertices {
+		m[vertex] = make(map[K]Edge[K])
 	}
 
-	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,
-					Data:       edge.Properties.Data,
-				},
-			}
+	for _, edge := range edges {
+		if _, ok := m[edge.Target]; !ok {
+			m[edge.Target] = make(map[K]Edge[K])
 		}
+		m[edge.Target][edge.Source] = edge
 	}
 
-	return predecessors, nil
+	return m, nil
+}
+
+func (d *directed[K, T]) addEdge(sourceHash, targetHash K, edge Edge[K]) error {
+	return d.store.AddEdge(sourceHash, targetHash, edge)
 }
 
 func (d *directed[K, T]) Clone() (Graph[K, T], error) {
@@ -201,38 +194,29 @@ func (d *directed[K, T]) Clone() (Graph[K, T], error) {
 		IsRooted:   d.traits.IsRooted,
 	}
 
-	vertices := make(map[K]T)
-	vertexProperties := make(map[K]*VertexProperties)
-
-	for hash, vertex := range d.vertices {
-		vertices[hash] = vertex
-		vertexProperties[hash] = &VertexProperties{
-			Weight:     d.vertexProperties[hash].Weight,
-			Attributes: d.vertexProperties[hash].Attributes,
-		}
-	}
-
 	return &directed[K, T]{
-		hash:             d.hash,
-		traits:           traits,
-		vertices:         vertices,
-		vertexProperties: vertexProperties,
-		edges:            cloneEdges(d.edges),
-		outEdges:         cloneEdges(d.outEdges),
-		inEdges:          cloneEdges(d.inEdges),
+		hash:   d.hash,
+		traits: traits,
+		store:  d.store,
 	}, nil
 }
 
-func (d *directed[K, T]) Order() int {
-	return len(d.vertices)
+func (d *directed[K, T]) Order() (int, error) {
+	return d.store.VertexCount()
 }
 
-func (d *directed[K, T]) Size() int {
+func (d *directed[K, T]) Size() (int, error) {
 	size := 0
-	for _, outEdges := range d.outEdges {
+	outEdges, err := d.AdjacencyMap()
+	if err != nil {
+		return 0, fmt.Errorf("failed to get adjacency map: %w", err)
+	}
+
+	for _, outEdges := range outEdges {
 		size += len(outEdges)
 	}
-	return size
+
+	return size, nil
 }
 
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
@@ -243,66 +227,3 @@ func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 
 	return aSourceHash == bSourceHash && aTargetHash == bTargetHash
 }
-
-func (d *directed[K, T]) addEdge(sourceHash, targetHash K, edge Edge[T]) {
-	if _, ok := d.edges[sourceHash]; !ok {
-		d.edges[sourceHash] = make(map[K]Edge[T])
-	}
-
-	d.edges[sourceHash][targetHash] = edge
-
-	if _, ok := d.outEdges[sourceHash]; !ok {
-		d.outEdges[sourceHash] = make(map[K]Edge[T])
-	}
-
-	d.outEdges[sourceHash][targetHash] = edge
-
-	if _, ok := d.inEdges[targetHash]; !ok {
-		d.inEdges[targetHash] = make(map[K]Edge[T])
-	}
-
-	d.inEdges[targetHash][sourceHash] = edge
-}
-
-func (d *directed[K, T]) predecessors(vertexHash K) []K {
-	var predecessorHashes []K
-
-	inEdges, ok := d.inEdges[vertexHash]
-	if !ok {
-		return predecessorHashes
-	}
-
-	for hash := range inEdges {
-		predecessorHashes = append(predecessorHashes, hash)
-	}
-
-	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,
-					Data:       edge.Properties.Data,
-				},
-			}
-		}
-	}
-
-	return edges
-}
diff --git a/graph.go b/graph.go
index 411edac..5fa097a 100644
--- a/graph.go
+++ b/graph.go
@@ -89,10 +89,10 @@ type Graph[K comparable, T any] interface {
 	Clone() (Graph[K, T], error)
 
 	// Order computes and returns the number of vertices in the graph.
-	Order() int
+	Order() (int, error)
 
 	// Size computes and returns the number of edges in the graph.
-	Size() int
+	Size() (int, error)
 }
 
 // Edge represents a graph edge with a source and target vertex as well as a weight, which has the
@@ -165,6 +165,12 @@ type Hash[K comparable, T any] func(T) K
 //
 // Which Graph implementation will be returned depends on these traits.
 func New[K comparable, T any](hash Hash[K, T], options ...func(*Traits)) Graph[K, T] {
+	return NewWithStore(hash, newMemoryStore[K, T](), options...)
+}
+
+// NewWithStore creates a new graph same as New, but uses the provided store instead of the default
+// memory store.
+func NewWithStore[K comparable, T any](hash Hash[K, T], store Store[K, T], options ...func(*Traits)) Graph[K, T] {
 	var p Traits
 
 	for _, option := range options {
@@ -172,10 +178,10 @@ func New[K comparable, T any](hash Hash[K, T], options ...func(*Traits)) Graph[K
 	}
 
 	if p.IsDirected {
-		return newDirected(hash, &p)
+		return newDirected(hash, &p, store)
 	}
 
-	return newUndirected(hash, &p)
+	return newUndirected(hash, &p, store)
 }
 
 // StringHash is a hashing function that accepts a string and uses that exact string as a hash
diff --git a/store.go b/store.go
new file mode 100644
index 0000000..a4c41fd
--- /dev/null
+++ b/store.go
@@ -0,0 +1,12 @@
+package graph
+
+type Store[K comparable, T any] interface {
+	AddVertex(hash K, value T, properties VertexProperties) error
+	Vertex(hash K) (T, VertexProperties, error)
+	ListVertices() ([]K, error)
+	VertexCount() (int, error)
+	AddEdge(sourceHash, targetHash K, edge Edge[K]) error
+	RemoveEdge(sourceHash, targetHash K) error
+	Edge(sourceHash, targetHash K) (Edge[K], error)
+	ListEdges() ([]Edge[K], error)
+}
diff --git a/store_memory.go b/store_memory.go
new file mode 100644
index 0000000..4b345fa
--- /dev/null
+++ b/store_memory.go
@@ -0,0 +1,128 @@
+package graph
+
+import (
+	"sync"
+)
+
+type memoryStore[K comparable, T any] struct {
+	lock             sync.RWMutex
+	vertices         map[K]T
+	vertexProperties map[K]VertexProperties
+	outEdges         map[K]map[K]Edge[K] // source -> target
+	inEdges          map[K]map[K]Edge[K] // target -> source
+}
+
+func newMemoryStore[K comparable, T any]() Store[K, T] {
+	return &memoryStore[K, T]{
+		vertices:         make(map[K]T),
+		vertexProperties: make(map[K]VertexProperties),
+		outEdges:         make(map[K]map[K]Edge[K]),
+		inEdges:          make(map[K]map[K]Edge[K]),
+	}
+}
+
+func (s *memoryStore[K, T]) AddVertex(k K, t T, p VertexProperties) error {
+	s.lock.Lock()
+	defer s.lock.Unlock()
+
+	if _, ok := s.vertices[k]; ok {
+		return ErrVertexAlreadyExists
+	}
+
+	s.vertices[k] = t
+	s.vertexProperties[k] = p
+
+	return nil
+}
+
+func (s *memoryStore[K, T]) ListVertices() ([]K, error) {
+	s.lock.RLock()
+	defer s.lock.RUnlock()
+
+	var hashes []K
+	for k := range s.vertices {
+		hashes = append(hashes, k)
+	}
+
+	return hashes, nil
+}
+
+func (s *memoryStore[K, T]) VertexCount() (int, error) {
+	s.lock.RLock()
+	defer s.lock.RUnlock()
+
+	return len(s.vertices), nil
+}
+
+func (s *memoryStore[K, T]) Vertex(k K) (T, VertexProperties, error) {
+	s.lock.RLock()
+	defer s.lock.RUnlock()
+
+	var v T
+	var ok bool
+	v, ok = s.vertices[k]
+	if !ok {
+		return v, VertexProperties{}, ErrVertexNotFound
+	}
+
+	p := s.vertexProperties[k]
+	return v, p, nil
+}
+
+func (s *memoryStore[K, T]) AddEdge(sourceHash, targetHash K, edge Edge[K]) error {
+	s.lock.Lock()
+	defer s.lock.Unlock()
+
+	if _, ok := s.outEdges[sourceHash]; !ok {
+		s.outEdges[sourceHash] = make(map[K]Edge[K])
+	}
+
+	s.outEdges[sourceHash][targetHash] = edge
+
+	if _, ok := s.inEdges[targetHash]; !ok {
+		s.inEdges[targetHash] = make(map[K]Edge[K])
+	}
+
+	s.inEdges[targetHash][sourceHash] = edge
+
+	return nil
+}
+
+func (s *memoryStore[K, T]) RemoveEdge(sourceHash, targetHash K) error {
+	s.lock.Lock()
+	defer s.lock.Unlock()
+
+	delete(s.inEdges[sourceHash], targetHash)
+	delete(s.outEdges[sourceHash], targetHash)
+	return nil
+}
+
+func (s *memoryStore[K, T]) Edge(sourceHash, targetHash K) (Edge[K], error) {
+	s.lock.RLock()
+	defer s.lock.RUnlock()
+
+	sourceEdges, ok := s.outEdges[sourceHash]
+	if !ok {
+		return Edge[K]{}, ErrEdgeNotFound
+	}
+
+	edge, ok := sourceEdges[targetHash]
+	if !ok {
+		return Edge[K]{}, ErrEdgeNotFound
+	}
+
+	return edge, nil
+}
+
+func (s *memoryStore[K, T]) ListEdges() ([]Edge[K], error) {
+	s.lock.RLock()
+	defer s.lock.RUnlock()
+
+	res := make([]Edge[K], 0)
+	for _, edges := range s.outEdges {
+		for _, edge := range edges {
+			res = append(res, edge)
+		}
+	}
+	return res, nil
+}
diff --git a/undirected.go b/undirected.go
index e71e266..54e1a19 100644
--- a/undirected.go
+++ b/undirected.go
@@ -6,22 +6,16 @@ import (
 )
 
 type undirected[K comparable, T any] struct {
-	hash             Hash[K, T]
-	traits           *Traits
-	vertices         map[K]T
-	vertexProperties map[K]*VertexProperties
-	outEdges         map[K]map[K]Edge[T]
-	inEdges          map[K]map[K]Edge[T]
+	hash   Hash[K, T]
+	traits *Traits
+	store  Store[K, T]
 }
 
-func newUndirected[K comparable, T any](hash Hash[K, T], traits *Traits) *undirected[K, T] {
+func newUndirected[K comparable, T any](hash Hash[K, T], traits *Traits, store Store[K, T]) *undirected[K, T] {
 	return &undirected[K, T]{
-		hash:             hash,
-		traits:           traits,
-		vertices:         make(map[K]T),
-		vertexProperties: make(map[K]*VertexProperties),
-		outEdges:         make(map[K]map[K]Edge[T]),
-		inEdges:          make(map[K]map[K]Edge[T]),
+		hash:   hash,
+		traits: traits,
+		store:  store,
 	}
 }
 
@@ -32,57 +26,42 @@ func (u *undirected[K, T]) Traits() *Traits {
 func (u *undirected[K, T]) AddVertex(value T, options ...func(*VertexProperties)) error {
 	hash := u.hash(value)
 
-	if _, ok := u.vertices[hash]; ok {
-		return ErrVertexAlreadyExists
-	}
-
-	u.vertices[hash] = value
-	u.vertexProperties[hash] = &VertexProperties{
+	prop := VertexProperties{
 		Weight:     0,
 		Attributes: make(map[string]string),
 	}
 
 	for _, option := range options {
-		option(u.vertexProperties[hash])
+		option(&prop)
 	}
 
-	return nil
+	return u.store.AddVertex(hash, value, prop)
 }
 
 func (u *undirected[K, T]) Vertex(hash K) (T, error) {
-	vertex, ok := u.vertices[hash]
-	if !ok {
-		return vertex, ErrVertexNotFound
-	}
-
-	return vertex, nil
+	vertex, _, err := u.store.Vertex(hash)
+	return vertex, err
 }
 
 func (u *undirected[K, T]) VertexWithProperties(hash K) (T, VertexProperties, error) {
-	vertex, err := u.Vertex(hash)
+	vertex, prop, err := u.store.Vertex(hash)
 	if err != nil {
 		return vertex, VertexProperties{}, err
 	}
 
-	properties, ok := u.vertexProperties[hash]
-	if !ok {
-		return vertex, *properties, ErrVertexNotFound
-	}
-
-	return vertex, *properties, nil
+	return vertex, prop, nil
 }
 
 func (u *undirected[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*EdgeProperties)) error {
-	source, ok := u.vertices[sourceHash]
-	if !ok {
-		return fmt.Errorf("source vertex %v: %w", sourceHash, ErrVertexNotFound)
+	if _, _, err := u.store.Vertex(sourceHash); err != nil {
+		return fmt.Errorf("could not find source vertex with hash %v: %w", sourceHash, err)
 	}
 
-	target, ok := u.vertices[targetHash]
-	if !ok {
-		return fmt.Errorf("target vertex %v: %w", targetHash, ErrVertexNotFound)
+	if _, _, err := u.store.Vertex(targetHash); err != nil {
+		return fmt.Errorf("could not find target vertex with hash %v: %w", targetHash, err)
 	}
 
+	// nolint: govet // false positive err shawdowing
 	if _, err := u.Edge(sourceHash, targetHash); !errors.Is(err, ErrEdgeNotFound) {
 		return ErrEdgeAlreadyExists
 	}
@@ -98,9 +77,9 @@ func (u *undirected[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Ed
 		}
 	}
 
-	edge := Edge[T]{
-		Source: source,
-		Target: target,
+	edge := Edge[K]{
+		Source: sourceHash,
+		Target: targetHash,
 		Properties: EdgeProperties{
 			Attributes: make(map[string]string),
 		},
@@ -110,7 +89,9 @@ func (u *undirected[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Ed
 		option(&edge.Properties)
 	}
 
-	u.addEdge(sourceHash, targetHash, edge)
+	if err := u.addEdge(sourceHash, targetHash, edge); err != nil {
+		return fmt.Errorf("failed to add edge: %w", err)
+	}
 
 	return nil
 }
@@ -118,20 +99,34 @@ func (u *undirected[K, T]) AddEdge(sourceHash, targetHash K, options ...func(*Ed
 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 function also looks for target[source].
-	if sourceEdges, ok := u.outEdges[sourceHash]; ok {
-		if edge, ok := sourceEdges[targetHash]; ok {
-			return edge, nil
-		}
+
+	edge, err := u.store.Edge(sourceHash, targetHash)
+	if errors.Is(err, ErrEdgeNotFound) {
+		edge, err = u.store.Edge(targetHash, sourceHash)
 	}
 
-	targetEdges, ok := u.outEdges[targetHash]
-	if ok {
-		if edge, ok := targetEdges[sourceHash]; ok {
-			return edge, nil
-		}
+	if err != nil {
+		return Edge[T]{}, err
+	}
+
+	sourceVertex, _, err := u.store.Vertex(sourceHash)
+	if err != nil {
+		return Edge[T]{}, err
 	}
 
-	return Edge[T]{}, ErrEdgeNotFound
+	targetVertex, _, err := u.store.Vertex(targetHash)
+	if err != nil {
+		return Edge[T]{}, err
+	}
+
+	return Edge[T]{
+		Source: sourceVertex,
+		Target: targetVertex,
+		Properties: EdgeProperties{
+			Weight:     edge.Properties.Weight,
+			Attributes: edge.Properties.Attributes,
+		},
+	}, nil
 }
 
 func (u *undirected[K, T]) RemoveEdge(source, target K) error {
@@ -139,38 +134,39 @@ func (u *undirected[K, T]) RemoveEdge(source, target K) error {
 		return err
 	}
 
-	delete(u.inEdges[source], target)
-	delete(u.inEdges[target], source)
-	delete(u.outEdges[source], target)
-	delete(u.outEdges[target], source)
+	if err := u.store.RemoveEdge(source, target); err != nil {
+		return fmt.Errorf("failed to remove edge from %v to %v: %w", source, target, err)
+	}
+
+	if err := u.store.RemoveEdge(target, source); err != nil {
+		return fmt.Errorf("failed to remove edge from %v to %v: %w", target, source, err)
+	}
 
 	return nil
 }
 
 func (u *undirected[K, T]) AdjacencyMap() (map[K]map[K]Edge[K], error) {
-	adjacencyMap := make(map[K]map[K]Edge[K])
+	vertices, err := u.store.ListVertices()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list vertices: %w", err)
+	}
 
-	// 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 {
-		adjacencyMap[vertexHash] = make(map[K]Edge[K])
+	edges, err := u.store.ListEdges()
+	if err != nil {
+		return nil, fmt.Errorf("failed to list edges: %w", err)
 	}
 
-	for vertexHash, outEdges := range u.outEdges {
-		for adjacencyHash, edge := range outEdges {
-			adjacencyMap[vertexHash][adjacencyHash] = Edge[K]{
-				Source: vertexHash,
-				Target: adjacencyHash,
-				Properties: EdgeProperties{
-					Weight:     edge.Properties.Weight,
-					Attributes: edge.Properties.Attributes,
-					Data:       edge.Properties.Data,
-				},
-			}
-		}
+	m := make(map[K]map[K]Edge[K])
+
+	for _, vertex := range vertices {
+		m[vertex] = make(map[K]Edge[K])
 	}
 
-	return adjacencyMap, nil
+	for _, edge := range edges {
+		m[edge.Source][edge.Target] = edge
+	}
+
+	return m, nil
 }
 
 func (u *undirected[K, T]) PredecessorMap() (map[K]map[K]Edge[K], error) {
@@ -185,39 +181,29 @@ func (u *undirected[K, T]) Clone() (Graph[K, T], error) {
 		IsRooted:   u.traits.IsRooted,
 	}
 
-	vertices := make(map[K]T)
-	vertexProperties := make(map[K]*VertexProperties)
-
-	for hash, vertex := range u.vertices {
-		vertices[hash] = vertex
-		vertexProperties[hash] = &VertexProperties{
-			Weight:     u.vertexProperties[hash].Weight,
-			Attributes: u.vertexProperties[hash].Attributes,
-		}
-	}
-
 	return &undirected[K, T]{
-		hash:             u.hash,
-		traits:           traits,
-		vertices:         vertices,
-		vertexProperties: vertexProperties,
-		outEdges:         cloneEdges(u.outEdges),
-		inEdges:          cloneEdges(u.inEdges),
+		hash:   u.hash,
+		traits: traits,
+		store:  u.store,
 	}, nil
 }
 
-func (u *undirected[K, T]) Order() int {
-	return len(u.vertices)
+func (u *undirected[K, T]) Order() (int, error) {
+	return u.store.VertexCount()
 }
 
-func (u *undirected[K, T]) Size() int {
+func (u *undirected[K, T]) Size() (int, error) {
 	size := 0
-	for _, outEdges := range u.outEdges {
+	outEdges, err := u.AdjacencyMap()
+	if err != nil {
+		return 0, fmt.Errorf("failed to get adjacency map: %w", err)
+	}
+	for _, outEdges := range outEdges {
 		size += len(outEdges)
 	}
 
-	// Divide by 2 since every AddEdge call on undirected graphs is counted twice.
-	return size / 2
+	// Divide by 2 since every add edge operation on undirected graph is counted twice.
+	return size / 2, nil
 }
 
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
@@ -237,41 +223,26 @@ func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	return false
 }
 
-func (u *undirected[K, T]) addEdge(sourceHash, targetHash K, edge Edge[T]) {
-	if _, ok := u.outEdges[sourceHash]; !ok {
-		u.outEdges[sourceHash] = make(map[K]Edge[T])
-	}
-	if _, ok := u.outEdges[targetHash]; !ok {
-		u.outEdges[targetHash] = make(map[K]Edge[T])
-	}
-
-	u.outEdges[sourceHash][targetHash] = edge
-	u.outEdges[targetHash][sourceHash] = edge
-
-	if _, ok := u.inEdges[targetHash]; !ok {
-		u.inEdges[targetHash] = make(map[K]Edge[T])
-	}
-	if _, ok := u.inEdges[sourceHash]; !ok {
-		u.inEdges[sourceHash] = make(map[K]Edge[T])
+func (u *undirected[K, T]) addEdge(sourceHash, targetHash K, edge Edge[K]) error {
+	err := u.store.AddEdge(sourceHash, targetHash, edge)
+	if err != nil {
+		return err
 	}
 
-	u.inEdges[targetHash][sourceHash] = edge
-	u.inEdges[sourceHash][targetHash] = edge
-}
-
-func (u *undirected[K, T]) adjacencies(vertexHash K) []K {
-	var adjacencyHashes []K
-
-	// An undirected graph creates an undirected edge as two directed edges in the opposite
-	// direction, so both the in-edges and the out-edges work here.
-	inEdges, ok := u.inEdges[vertexHash]
-	if !ok {
-		return adjacencyHashes
+	rEdge := Edge[K]{
+		Source: edge.Target,
+		Target: edge.Source,
+		Properties: EdgeProperties{
+			Weight:     edge.Properties.Weight,
+			Attributes: edge.Properties.Attributes,
+			Data:       edge.Properties.Data,
+		},
 	}
 
-	for hash := range inEdges {
-		adjacencyHashes = append(adjacencyHashes, hash)
+	err = u.store.AddEdge(targetHash, sourceHash, rEdge)
+	if err != nil {
+		return err
 	}
 
-	return adjacencyHashes
+	return nil
 }


Test patch:
diff --git a/directed_test.go b/directed_test.go
index c9154e8..9794f27 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -21,7 +21,7 @@ func TestDirected_Traits(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		g := newDirected(IntHash, test.traits)
+		g := newDirected(IntHash, test.traits, newMemoryStore[int, int]())
 		traits := g.Traits()
 
 		if !traitsAreEqual(traits, test.expected) {
@@ -60,7 +60,7 @@ func TestDirected_AddVertex(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		var err error
 
@@ -80,30 +80,32 @@ func TestDirected_AddVertex(t *testing.T) {
 			t.Errorf("%s: error expectancy doesn't match: expected %v, got %v", name, test.finallyExpectedError, err)
 		}
 
+		graphStore := graph.store.(*memoryStore[int, int])
 		for _, vertex := range test.vertices {
-			if len(graph.vertices) != len(test.expectedVertices) {
-				t.Errorf("%s: vertex count doesn't match: expected %v, got %v", name, len(test.expectedVertices), len(graph.vertices))
+			if len(graphStore.vertices) != len(test.expectedVertices) {
+				t.Errorf("%s: vertex count doesn't match: expected %v, got %v", name, len(test.expectedVertices), len(graphStore.vertices))
 			}
 
 			hash := graph.hash(vertex)
-			if _, ok := graph.vertices[hash]; !ok {
-				t.Errorf("%s: vertex %v not found in graph: %v", name, vertex, graph.vertices)
+			if _, _, err := graph.store.Vertex(hash); err != nil {
+				vertices := graphStore.vertices
+				t.Errorf("%s: vertex %v not found in graph: %v", name, vertex, vertices)
 			}
 
 			if test.properties == nil {
 				continue
 			}
 
-			if graph.vertexProperties[hash].Weight != test.expectedProperties.Weight {
-				t.Errorf("%s: edge weights don't match: expected weight %v, got %v", name, test.expectedProperties.Weight, graph.vertexProperties[hash].Weight)
+			if graphStore.vertexProperties[hash].Weight != test.expectedProperties.Weight {
+				t.Errorf("%s: edge weights don't match: expected weight %v, got %v", name, test.expectedProperties.Weight, graphStore.vertexProperties[hash].Weight)
 			}
 
-			if len(graph.vertexProperties[hash].Attributes) != len(test.expectedProperties.Attributes) {
-				t.Fatalf("%s: attributes lengths don't match: expcted %v, got %v", name, len(test.expectedProperties.Attributes), len(graph.vertexProperties[hash].Attributes))
+			if len(graphStore.vertexProperties[hash].Attributes) != len(test.expectedProperties.Attributes) {
+				t.Fatalf("%s: attributes lengths don't match: expcted %v, got %v", name, len(test.expectedProperties.Attributes), len(graphStore.vertexProperties[hash].Attributes))
 			}
 
 			for expectedKey, expectedValue := range test.expectedProperties.Attributes {
-				value, ok := graph.vertexProperties[hash].Attributes[expectedKey]
+				value, ok := graphStore.vertexProperties[hash].Attributes[expectedKey]
 				if !ok {
 					t.Errorf("%s: attribute keys don't match: expected key %v not found", name, expectedKey)
 				}
@@ -133,7 +135,7 @@ func TestDirected_Vertex(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -259,7 +261,7 @@ func TestDirected_AddEdge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, test.traits)
+		graph := newDirected(IntHash, test.traits, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -274,7 +276,13 @@ func TestDirected_AddEdge(t *testing.T) {
 			// 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), EdgeData(edge.Properties.Data), 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
@@ -289,8 +297,8 @@ func TestDirected_AddEdge(t *testing.T) {
 			sourceHash := graph.hash(expectedEdge.Source)
 			targetHash := graph.hash(expectedEdge.Target)
 
-			edge, ok := graph.edges[sourceHash][targetHash]
-			if !ok {
+			edge, err := graph.Edge(sourceHash, targetHash)
+			if err != nil {
 				t.Fatalf("%s: edge with source %v and target %v not found", name, expectedEdge.Source, expectedEdge.Target)
 			}
 
@@ -345,8 +353,7 @@ func TestDirected_Edge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
-
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
 		}
@@ -354,9 +361,12 @@ func TestDirected_Edge(t *testing.T) {
 		sourceHash := graph.hash(test.vertices[0])
 		targetHash := graph.hash(test.vertices[1])
 
-		_ = graph.AddEdge(sourceHash, targetHash)
+		err := graph.AddEdge(sourceHash, targetHash)
+		if err != nil {
+			t.Fatalf("%s: error adding edge: %v", name, err)
+		}
 
-		_, err := graph.Edge(test.getEdgeHashes[0], test.getEdgeHashes[1])
+		_, err = graph.Edge(test.getEdgeHashes[0], test.getEdgeHashes[1])
 
 		if test.exists != (err == nil) {
 			t.Fatalf("%s: result expectancy doesn't match: expected %v, got %v", name, test.exists, err)
@@ -480,7 +490,7 @@ func TestDirected_AdjacencyList(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -563,7 +573,7 @@ func TestDirected_PredecessorMap(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -649,34 +659,8 @@ func TestDirected_Clone(t *testing.T) {
 			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 actual.vertexProperties[expectedHash].Weight != expected.vertexProperties[expectedHash].Weight {
-				t.Errorf("%s: vertex properties expectancy doesn't match: expected %v, got %v", name, expected.vertexProperties[expectedHash], actual.vertexProperties[expectedHash])
-			}
-			if actual.vertexProperties[expectedHash].Attributes["color"] != expected.vertexProperties[expectedHash].Attributes["color"] {
-				t.Errorf("%s: vertex properties expectancy doesn't match: expected %v, got %v", name, expected.vertexProperties[expectedHash], actual.vertexProperties[expectedHash])
-			}
-		}
-
-		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))
+		if actual.store != expected.store {
+			t.Fatalf("%s: stores don't match", name)
 		}
 	}
 }
@@ -727,7 +711,7 @@ func TestDirected_OrderAndSize(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -739,8 +723,8 @@ func TestDirected_OrderAndSize(t *testing.T) {
 			}
 		}
 
-		order := graph.Order()
-		size := graph.Size()
+		order, _ := graph.Order()
+		size, _ := graph.Size()
 
 		if order != test.expectedOrder {
 			t.Errorf("%s: order expectancy doesn't match: expected %d, got %d", name, test.expectedOrder, order)
@@ -771,7 +755,7 @@ func TestDirected_edgesAreEqual(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 		actual := graph.edgesAreEqual(test.a, test.b)
 
 		if actual != test.edgesAreEqual {
@@ -794,22 +778,24 @@ func TestDirected_addEdge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, edge := range test.edges {
 			sourceHash := graph.hash(edge.Source)
 			TargetHash := graph.hash(edge.Target)
-			graph.addEdge(sourceHash, TargetHash, edge)
+			err := graph.addEdge(sourceHash, TargetHash, edge)
+			if err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
 		}
 
-		if len(graph.edges) != len(test.edges) {
-			t.Errorf("%s: number of edges doesn't match: expected %v, got %v", name, len(test.edges), len(graph.edges))
-		}
-		if len(graph.outEdges) != len(test.edges) {
-			t.Errorf("%s: number of outgoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(graph.outEdges))
+		outEdges := graph.store.(*memoryStore[int, int]).outEdges
+		if len(outEdges) != len(test.edges) {
+			t.Errorf("%s: number of outgoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(outEdges))
 		}
-		if len(graph.inEdges) != len(test.edges) {
-			t.Errorf("%s: number of ingoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(graph.inEdges))
+		inEdges := graph.store.(*memoryStore[int, int]).inEdges
+		if len(inEdges) != len(test.edges) {
+			t.Errorf("%s: number of ingoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(inEdges))
 		}
 	}
 }
@@ -855,7 +841,7 @@ func TestDirected_predecessors(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &Traits{})
+		graph := newDirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -867,7 +853,7 @@ func TestDirected_predecessors(t *testing.T) {
 			}
 		}
 
-		predecessors := graph.predecessors(graph.hash(test.vertex))
+		predecessors, _ := predecessors(graph, graph.hash(test.vertex))
 
 		if !slicesAreEqual(predecessors, test.expectedPredecessors) {
 			t.Errorf("%s: predecessors don't match: expected %v, got %v", name, test.expectedPredecessors, predecessors)
@@ -894,3 +880,18 @@ func slicesAreEqual[T comparable](a, b []T) bool {
 
 	return true
 }
+
+func predecessors[K comparable, T any](g *directed[K, T], vertexHash K) ([]K, error) {
+	var predecessorHashes []K
+
+	predecessorMap, err := g.PredecessorMap()
+	if err != nil {
+		return nil, err
+	}
+
+	for _, edge := range predecessorMap[vertexHash] {
+		predecessorHashes = append(predecessorHashes, edge.Source)
+	}
+
+	return predecessorHashes, nil
+}
diff --git a/undirected_test.go b/undirected_test.go
index 6acaf74..5af08d9 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -21,7 +21,7 @@ func TestUndirected_Traits(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		g := newUndirected(IntHash, test.traits)
+		g := newUndirected(IntHash, test.traits, newMemoryStore[int, int]())
 		traits := g.Traits()
 
 		if !traitsAreEqual(traits, test.expected) {
@@ -60,7 +60,7 @@ func TestUndirected_AddVertex(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		var err error
 
@@ -80,30 +80,33 @@ func TestUndirected_AddVertex(t *testing.T) {
 			t.Errorf("%s: error expectancy doesn't match: expected %v, got %v", name, test.finallyExpectedError, err)
 		}
 
+		graphStore := graph.store.(*memoryStore[int, int])
+
 		for _, vertex := range test.vertices {
-			if len(graph.vertices) != len(test.expectedVertices) {
-				t.Errorf("%s: vertex count doesn't match: expected %v, got %v", name, len(test.expectedVertices), len(graph.vertices))
+			if len(graphStore.vertices) != len(test.expectedVertices) {
+				t.Errorf("%s: vertex count doesn't match: expected %v, got %v", name, len(test.expectedVertices), len(graphStore.vertices))
 			}
 
 			hash := graph.hash(vertex)
-			if _, ok := graph.vertices[hash]; !ok {
-				t.Errorf("%s: vertex %v not found in graph: %v", name, vertex, graph.vertices)
+			vertices := graph.store.(*memoryStore[int, int]).vertices
+			if _, ok := vertices[hash]; !ok {
+				t.Errorf("%s: vertex %v not found in graph: %v", name, vertex, vertices)
 			}
 
 			if test.properties == nil {
 				continue
 			}
 
-			if graph.vertexProperties[hash].Weight != test.expectedProperties.Weight {
-				t.Errorf("%s: edge weights don't match: expected weight %v, got %v", name, test.expectedProperties.Weight, graph.vertexProperties[hash].Weight)
+			if graphStore.vertexProperties[hash].Weight != test.expectedProperties.Weight {
+				t.Errorf("%s: edge weights don't match: expected weight %v, got %v", name, test.expectedProperties.Weight, graphStore.vertexProperties[hash].Weight)
 			}
 
-			if len(graph.vertexProperties[hash].Attributes) != len(test.expectedProperties.Attributes) {
-				t.Fatalf("%s: attributes lengths don't match: expcted %v, got %v", name, len(test.expectedProperties.Attributes), len(graph.vertexProperties[hash].Attributes))
+			if len(graphStore.vertexProperties[hash].Attributes) != len(test.expectedProperties.Attributes) {
+				t.Fatalf("%s: attributes lengths don't match: expcted %v, got %v", name, len(test.expectedProperties.Attributes), len(graphStore.vertexProperties[hash].Attributes))
 			}
 
 			for expectedKey, expectedValue := range test.expectedProperties.Attributes {
-				value, ok := graph.vertexProperties[hash].Attributes[expectedKey]
+				value, ok := graphStore.vertexProperties[hash].Attributes[expectedKey]
 				if !ok {
 					t.Errorf("%s: attribute keys don't match: expected key %v not found", name, expectedKey)
 				}
@@ -133,7 +136,7 @@ func TestUndirected_Vertex(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -259,7 +262,7 @@ func TestUndirected_AddEdge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, test.traits)
+		graph := newUndirected(IntHash, test.traits, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -289,7 +292,7 @@ func TestUndirected_AddEdge(t *testing.T) {
 			sourceHash := graph.hash(expectedEdge.Source)
 			targetHash := graph.hash(expectedEdge.Target)
 
-			edge, ok := graph.outEdges[sourceHash][targetHash]
+			edge, ok := graph.store.(*memoryStore[int, int]).outEdges[sourceHash][targetHash]
 			if !ok {
 				t.Fatalf("%s: edge with source %v and target %v not found", name, expectedEdge.Source, expectedEdge.Target)
 			}
@@ -346,7 +349,7 @@ func TestUndirected_Edge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -355,9 +358,12 @@ func TestUndirected_Edge(t *testing.T) {
 		sourceHash := graph.hash(test.vertices[0])
 		targetHash := graph.hash(test.vertices[1])
 
-		_ = graph.AddEdge(sourceHash, targetHash)
+		err := graph.AddEdge(sourceHash, targetHash)
+		if err != nil {
+			t.Fatalf("%s: error adding edge: %v", name, err)
+		}
 
-		_, err := graph.Edge(test.getEdgeHashes[0], test.getEdgeHashes[1])
+		_, err = graph.Edge(test.getEdgeHashes[0], test.getEdgeHashes[1])
 
 		if test.exists != (err == nil) {
 			t.Fatalf("%s: result expectancy doesn't match: expected %v, got %v", name, test.exists, err)
@@ -490,7 +496,7 @@ func TestUndirected_Adjacencies(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -583,7 +589,7 @@ func TestUndirected_PredecessorMap(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -669,31 +675,8 @@ func TestUndirected_Clone(t *testing.T) {
 			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 actual.vertexProperties[expectedHash].Weight != expected.vertexProperties[expectedHash].Weight {
-				t.Errorf("%s: vertex properties expectancy doesn't match: expected %v, got %v", name, expected.vertexProperties[expectedHash], actual.vertexProperties[expectedHash])
-			}
-			if actual.vertexProperties[expectedHash].Attributes["color"] != expected.vertexProperties[expectedHash].Attributes["color"] {
-				t.Errorf("%s: vertex properties expectancy doesn't match: expected %v, got %v", name, expected.vertexProperties[expectedHash], actual.vertexProperties[expectedHash])
-			}
-		}
-
-		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))
+		if actual.store != expected.store {
+			t.Fatalf("%s: stores don't match", name)
 		}
 	}
 }
@@ -743,7 +726,7 @@ func TestUndirected_OrderAndSize(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -755,8 +738,8 @@ func TestUndirected_OrderAndSize(t *testing.T) {
 			}
 		}
 
-		order := graph.Order()
-		size := graph.Size()
+		order, _ := graph.Order()
+		size, _ := graph.Size()
 
 		if order != test.expectedOrder {
 			t.Errorf("%s: order expectancy doesn't match: expected %d, got %d", name, test.expectedOrder, order)
@@ -792,7 +775,7 @@ func TestUndirected_edgesAreEqual(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 		actual := graph.edgesAreEqual(test.a, test.b)
 
 		if actual != test.edgesAreEqual {
@@ -815,19 +798,24 @@ func TestUndirected_addEdge(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, edge := range test.edges {
 			sourceHash := graph.hash(edge.Source)
 			TargetHash := graph.hash(edge.Target)
-			graph.addEdge(sourceHash, TargetHash, edge)
+			err := graph.addEdge(sourceHash, TargetHash, edge)
+			if err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
 		}
 
-		if len(graph.outEdges) != len(test.edges) {
-			t.Errorf("%s: number of outgoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(graph.outEdges))
+		outEdges := graph.store.(*memoryStore[int, int]).outEdges
+		if len(outEdges) != len(test.edges) {
+			t.Errorf("%s: number of outgoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(outEdges))
 		}
-		if len(graph.inEdges) != len(test.edges) {
-			t.Errorf("%s: number of ingoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(graph.inEdges))
+		inEdges := graph.store.(*memoryStore[int, int]).inEdges
+		if len(inEdges) != len(test.edges) {
+			t.Errorf("%s: number of ingoing edges doesn't match: expected %v, got %v", name, len(test.edges), len(inEdges))
 		}
 	}
 }
@@ -905,7 +893,7 @@ func TestUndirected_adjacencies(t *testing.T) {
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &Traits{})
+		graph := newUndirected(IntHash, &Traits{}, newMemoryStore[int, int]())
 
 		for _, vertex := range test.vertices {
 			_ = graph.AddVertex(vertex)
@@ -917,10 +905,27 @@ func TestUndirected_adjacencies(t *testing.T) {
 			}
 		}
 
-		adjacencies := graph.adjacencies(graph.hash(test.vertex))
+		adjacencies := adjacencies(graph.store, graph.hash(test.vertex))
 
 		if !slicesAreEqual(adjacencies, test.expectedAdjancencies) {
 			t.Errorf("%s: adjacencies don't match: expected %v, got %v", name, test.expectedAdjancencies, adjacencies)
 		}
 	}
 }
+
+func adjacencies[K comparable, T any](store Store[K, T], vertexHash K) []K {
+	var adjacencyHashes []K
+
+	// An undirected graph creates an undirected edge as two directed edges in the opposite
+	// direction, so both the in-edges and the out-edges work here.
+	inEdges, ok := store.(*memoryStore[K, T]).inEdges[vertexHash]
+	if !ok {
+		return adjacencyHashes
+	}
+
+	for hash := range inEdges {
+		adjacencyHashes = append(adjacencyHashes, hash)
+	}
+
+	return adjacencyHashes
+}