Repository: dominikbraun/graph
Pull request #3 (2022-06-18 21:19:12)

Implement cycle detection (prediction for new edges)


Patch:
diff --git a/directed.go b/directed.go
index ac00400..e4e954f 100644
--- a/directed.go
+++ b/directed.go
@@ -166,6 +166,54 @@ func (d *directed[K, T]) BFSByHash(startHash K, visit func(value T) bool) error
 	return nil
 }
 
+func (d *directed[K, T]) CreatesCycle(source, target T) (bool, error) {
+	sourceHash := d.hash(source)
+	targetHash := d.hash(target)
+
+	return d.CreatesCycleByHashes(sourceHash, targetHash)
+}
+
+func (d *directed[K, T]) CreatesCycleByHashes(sourceHash, targetHash K) (bool, error) {
+	source, ok := d.vertices[sourceHash]
+	if !ok {
+		return false, fmt.Errorf("could not find source vertex with hash %v", source)
+	}
+
+	_, ok = d.vertices[targetHash]
+	if !ok {
+		return false, fmt.Errorf("could not find target vertex with hash %v", source)
+	}
+
+	if sourceHash == targetHash {
+		return true, nil
+	}
+
+	stack := make([]K, 0)
+	visited := make(map[K]bool)
+
+	stack = append(stack, sourceHash)
+
+	for len(stack) > 0 {
+		currentHash := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		if _, ok := visited[currentHash]; !ok {
+			// If the current vertex, e.g. a predecessor of the source vertex, is also the target
+			// vertex, an edge between these two would create a cycle.
+			if currentHash == targetHash {
+				return true, nil
+			}
+			visited[currentHash] = true
+
+			for _, predecessor := range d.predecessors(currentHash) {
+				stack = append(stack, predecessor)
+			}
+		}
+	}
+
+	return false, nil
+}
+
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := d.hash(a.Source)
 	aTargetHash := d.hash(a.Target)
@@ -194,3 +242,18 @@ func (d *directed[K, T]) addEdge(sourceHash, targetHash K, edge 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
+}
diff --git a/graph.go b/graph.go
index 7ed00f6..57bbbb5 100644
--- a/graph.go
+++ b/graph.go
@@ -105,6 +105,27 @@ type Graph[K comparable, T any] interface {
 
 	// BFSByHash does the same as BFS, but uses a hash value to identify the starting vertex.
 	BFSByHash(startHash K, visit func(value T) bool) error
+
+	// 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.
+	//
+	// A potential edge would create a cycle if the target vertex is also a parent of the source
+	// vertex. Given a graoh A-B-C-D, adding an edge DA would introduce a cycle:
+	//
+	//	A -
+	//	|  |
+	//	B  |
+	//	|  |
+	//	C  |
+	//	|  |
+	//	D -
+	//
+	// CreatesCycle backtracks the ingoing edges of D, resulting in a reverse walk C-B-A.
+	CreatesCycle(source, target T) (bool, error)
+
+	// CreatesCycleByHashes does the same as CreatesCycle, but uses a hash value to identify the
+	// starting vertex.
+	CreatesCycleByHashes(sourceHash, targetHash K) (bool, 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 1196780..1a99077 100644
--- a/undirected.go
+++ b/undirected.go
@@ -173,6 +173,54 @@ func (u *undirected[K, T]) BFSByHash(startHash K, visit func(value T) bool) erro
 	return nil
 }
 
+func (u *undirected[K, T]) CreatesCycle(source, target T) (bool, error) {
+	sourceHash := u.hash(source)
+	targetHash := u.hash(target)
+
+	return u.CreatesCycleByHashes(sourceHash, targetHash)
+}
+
+func (u *undirected[K, T]) CreatesCycleByHashes(sourceHash, targetHash K) (bool, error) {
+	source, ok := u.vertices[sourceHash]
+	if !ok {
+		return false, fmt.Errorf("could not find source vertex with hash %v", source)
+	}
+
+	_, ok = u.vertices[targetHash]
+	if !ok {
+		return false, fmt.Errorf("could not find target vertex with hash %v", source)
+	}
+
+	if sourceHash == targetHash {
+		return true, nil
+	}
+
+	stack := make([]K, 0)
+	visited := make(map[K]bool)
+
+	stack = append(stack, sourceHash)
+
+	for len(stack) > 0 {
+		currentHash := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		if _, ok := visited[currentHash]; !ok {
+			// If the current vertex, e.g. a predecessor of the source vertex, is also the target
+			// vertex, an edge between these two would create a cycle.
+			if currentHash == targetHash {
+				return true, nil
+			}
+			visited[currentHash] = true
+
+			for _, adjacency := range u.adjacencies(currentHash) {
+				stack = append(stack, adjacency)
+			}
+		}
+	}
+
+	return false, nil
+}
+
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := u.hash(a.Source)
 	aTargetHash := u.hash(a.Target)
@@ -221,3 +269,20 @@ func (u *undirected[K, T]) addEdge(sourceHash, targetHash K, edge Edge[T]) {
 	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
+	}
+
+	for hash := range inEdges {
+		adjacencyHashes = append(adjacencyHashes, hash)
+	}
+
+	return adjacencyHashes
+}


Test patch:
diff --git a/directed_test.go b/directed_test.go
index 9e74a50..fb69b95 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -305,6 +305,87 @@ func TestDirected_BFSByHash(t *testing.T) {
 	}
 }
 
+func TestDirected_CreatesCycle(t *testing.T) {
+	TestDirected_CreatesCycleByHashes(t)
+}
+
+func TestDirected_CreatesCycleByHashes(t *testing.T) {
+	tests := map[string]struct {
+		vertices     []int
+		edges        []Edge[int]
+		sourceHash   int
+		targetHash   int
+		createsCycle bool
+	}{
+		"directed 2-4-7-5 cycle": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 2},
+			},
+			sourceHash:   7,
+			targetHash:   5,
+			createsCycle: true,
+		},
+		"undirected 2-4-7-5 'cycle'": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 2},
+			},
+			sourceHash: 5,
+			targetHash: 7,
+			// The direction of the edge (57 instead of 75) doesn't create a directed cycle.
+			createsCycle: false,
+		},
+		"no cycle": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 2},
+			},
+			sourceHash:   5,
+			targetHash:   6,
+			createsCycle: false,
+		},
+	}
+
+	for name, test := range tests {
+		graph := newDirected(IntHash, &properties{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.Edge(edge.Source, edge.Target); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		createsCycle, err := graph.CreatesCycle(test.sourceHash, test.targetHash)
+		if err != nil {
+			t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+		}
+
+		if createsCycle != test.createsCycle {
+			t.Errorf("%s: cycle expectancy doesn't match: expected %v, got %v", name, test.createsCycle, createsCycle)
+		}
+	}
+}
+
 func TestDirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
@@ -366,7 +447,68 @@ func TestDirected_addEdge(t *testing.T) {
 	}
 }
 
-func slicesAreEqual[T any](a []T, b []T, equals func(a, b T) bool) bool {
+func TestDirected_predecessors(t *testing.T) {
+	tests := map[string]struct {
+		vertices             []int
+		edges                []Edge[int]
+		vertex               int
+		expectedPredecessors []int
+	}{
+		"graph with 3 vertices": {
+			vertices: []int{1, 2, 3},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+			},
+			vertex:               2,
+			expectedPredecessors: []int{1},
+		},
+		"graph with 6 vertices": {
+			vertices: []int{1, 2, 3, 4, 5, 6},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 6},
+			},
+			vertex:               5,
+			expectedPredecessors: []int{2},
+		},
+		"graph with 4 vertices and 3 predecessors": {
+			vertices: []int{1, 2, 3, 4},
+			edges: []Edge[int]{
+				{Source: 1, Target: 4},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 4},
+			},
+			vertex:               4,
+			expectedPredecessors: []int{1, 2, 3},
+		},
+	}
+
+	for name, test := range tests {
+		graph := newDirected(IntHash, &properties{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.Edge(edge.Source, edge.Target); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		predecessors := graph.predecessors(graph.hash(test.vertex))
+
+		if !slicesAreEqual(predecessors, test.expectedPredecessors) {
+			t.Errorf("%s: predecessors don't match: expected %v, got %v", name, test.expectedPredecessors, predecessors)
+		}
+	}
+}
+
+func slicesAreEqual[T comparable](a []T, b []T) bool {
 	if len(a) != len(b) {
 		return false
 	}
@@ -374,7 +516,7 @@ func slicesAreEqual[T any](a []T, b []T, equals func(a, b T) bool) bool {
 	for _, aValue := range a {
 		found := false
 		for _, bValue := range b {
-			if equals(aValue, bValue) {
+			if aValue == bValue {
 				found = true
 			}
 		}
diff --git a/undirected_test.go b/undirected_test.go
index 6137853..938f2e0 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -358,6 +358,85 @@ func TestUndirected_BFSByHash(t *testing.T) {
 	}
 }
 
+func TestUndirected_CreatesCycle(t *testing.T) {
+	TestUndirected_CreatesCycleByHashes(t)
+}
+
+func TestUndirected_CreatesCycleByHashes(t *testing.T) {
+	tests := map[string]struct {
+		vertices     []int
+		edges        []Edge[int]
+		sourceHash   int
+		targetHash   int
+		createsCycle bool
+	}{
+		"undirected 2-4-7-5 cycle": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 7},
+			},
+			sourceHash:   2,
+			targetHash:   5,
+			createsCycle: true,
+		},
+		"undirected 5-6-3-1-2-7 cycle": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 7},
+			},
+			sourceHash:   5,
+			targetHash:   6,
+			createsCycle: true,
+		},
+		"no cycle": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+			},
+			sourceHash:   5,
+			targetHash:   7,
+			createsCycle: false,
+		},
+	}
+
+	for name, test := range tests {
+		graph := newUndirected(IntHash, &properties{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.Edge(edge.Source, edge.Target); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		createsCycle, err := graph.CreatesCycle(test.sourceHash, test.targetHash)
+		if err != nil {
+			t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+		}
+
+		if createsCycle != test.createsCycle {
+			t.Errorf("%s: cycle expectancy doesn't match: expected %v, got %v", name, test.createsCycle, createsCycle)
+		}
+	}
+}
+
 func TestUndirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
@@ -423,3 +502,96 @@ func TestUndirected_addEdge(t *testing.T) {
 		}
 	}
 }
+
+func TestUndirected_adjacencies(t *testing.T) {
+	tests := map[string]struct {
+		vertices             []int
+		edges                []Edge[int]
+		vertex               int
+		expectedAdjancencies []int
+	}{
+		"graph with 3 vertices": {
+			vertices: []int{1, 2, 3},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+			},
+			vertex:               2,
+			expectedAdjancencies: []int{1},
+		},
+		"graph with 6 vertices": {
+			vertices: []int{1, 2, 3, 4, 5, 6},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 6},
+			},
+			vertex:               2,
+			expectedAdjancencies: []int{1, 4, 5},
+		},
+		"graph with 7 vertices and a diamond cycle (#1)": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 7},
+			},
+			vertex:               5,
+			expectedAdjancencies: []int{2, 7},
+		},
+		"graph with 7 vertices and a diamond cycle (#2)": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 7},
+			},
+			vertex:               7,
+			expectedAdjancencies: []int{4, 5},
+		},
+		"graph with 7 vertices and a diamond cycle (#3)": {
+			vertices: []int{1, 2, 3, 4, 5, 6, 7},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 1, Target: 3},
+				{Source: 2, Target: 4},
+				{Source: 2, Target: 5},
+				{Source: 3, Target: 6},
+				{Source: 4, Target: 7},
+				{Source: 5, Target: 7},
+			},
+			vertex:               2,
+			expectedAdjancencies: []int{1, 4, 5},
+		},
+	}
+
+	for name, test := range tests {
+		graph := newUndirected(IntHash, &properties{})
+
+		for _, vertex := range test.vertices {
+			graph.Vertex(vertex)
+		}
+
+		for _, edge := range test.edges {
+			if err := graph.Edge(edge.Source, edge.Target); err != nil {
+				t.Fatalf("%s: failed to add edge: %s", name, err.Error())
+			}
+		}
+
+		adjacencies := graph.adjacencies(graph.hash(test.vertex))
+
+		if !slicesAreEqual(adjacencies, test.expectedAdjancencies) {
+			t.Errorf("%s: adjacencies don't match: expected %v, got %v", name, test.expectedAdjancencies, adjacencies)
+		}
+	}
+}