Repository: dominikbraun/graph
Pull request #4 (2022-06-19 19:29:38)

Cycle checks for `Edge` functions


Patch:
diff --git a/README.md b/README.md
index abb8c6e..6796ba0 100644
--- a/README.md
+++ b/README.md
@@ -85,6 +85,31 @@ _ = g.DFS(1, func(value int) bool {
 })
 ```
 
+## Cycle checks for acyclic graphs
+
+```go
+g := graph.New(graph.IntHash, graph.Acyclic())
+
+g.Vertex(1)
+g.Vertex(2)
+g.Vertex(3)
+
+
+if err := g.Edge(1, 2); err != nil {
+    panic(err)
+}
+if err := g.Edge(2, 3); err != nil {
+    panic(err)
+}
+if err := g.Edge(3, 1); err != nil {
+    panic(err)
+}
+```
+
+```
+panic: an edge between 3 and 1 would introduce a cycle
+```
+
 # Concepts
 
 ## Hashes
diff --git a/directed.go b/directed.go
index e4e954f..1d98a76 100644
--- a/directed.go
+++ b/directed.go
@@ -57,6 +57,17 @@ func (d *directed[K, T]) WeightedEdgeByHashes(sourceHash, targetHash K, weight i
 		return fmt.Errorf("an edge between vertices %v and %v already exists", sourceHash, targetHash)
 	}
 
+	// If the graph was declared to be acyclic, permit the creation of a cycle.
+	if d.properties.isAcyclic {
+		createsCycle, err := d.CreatesCycleByHashes(sourceHash, targetHash)
+		if err != nil {
+			return fmt.Errorf("failed to check for cycles: %w", err)
+		}
+		if createsCycle {
+			return fmt.Errorf("an edge between %v and %v would introduce a cycle", sourceHash, targetHash)
+		}
+	}
+
 	edge := Edge[T]{
 		Source: source,
 		Target: target,
diff --git a/undirected.go b/undirected.go
index 1a99077..7993eca 100644
--- a/undirected.go
+++ b/undirected.go
@@ -57,6 +57,17 @@ func (u *undirected[K, T]) WeightedEdgeByHashes(sourceHash, targetHash K, weight
 		return fmt.Errorf("an edge between vertices %v and %v already exists", sourceHash, targetHash)
 	}
 
+	// If the graph was declared to be acyclic, permit the creation of a cycle.
+	if u.properties.isAcyclic {
+		createsCycle, err := u.CreatesCycleByHashes(sourceHash, targetHash)
+		if err != nil {
+			return fmt.Errorf("failed to check for cycles: %w", err)
+		}
+		if createsCycle {
+			return fmt.Errorf("an edge between %v and %v would introduce a cycle", sourceHash, targetHash)
+		}
+	}
+
 	edge := Edge[T]{
 		Source: source,
 		Target: target,


Test patch:
diff --git a/directed_test.go b/directed_test.go
index fb69b95..49a6f5c 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -51,37 +51,56 @@ func TestDirected_WeightedEdgeByHashes(t *testing.T) {
 	tests := map[string]struct {
 		vertices      []int
 		edgeHashes    [][3]int
+		properties    *properties
 		expectedEdges []Edge[int]
-		shouldFail    bool
+		// Even though some of the WeightedEdgeByHashes calls might work, at least one of them
+		// could fail - for example if the last call would introduce a cycle.
+		shouldFinallyFail bool
 	}{
 		"graph with 2 edges": {
 			vertices:   []int{1, 2, 3},
 			edgeHashes: [][3]int{{1, 2, 10}, {1, 3, 20}},
+			properties: &properties{},
 			expectedEdges: []Edge[int]{
 				{Source: 1, Target: 2, Weight: 10},
 				{Source: 1, Target: 3, Weight: 20},
 			},
 		},
 		"hashes for non-existent vertices": {
-			vertices:   []int{1, 2},
-			edgeHashes: [][3]int{{1, 3, 20}},
-			shouldFail: true,
+			vertices:          []int{1, 2},
+			edgeHashes:        [][3]int{{1, 3, 20}},
+			properties:        &properties{},
+			shouldFinallyFail: true,
+		},
+		"edge introducing a cycle in an acyclic graph": {
+			vertices:   []int{1, 2, 3},
+			edgeHashes: [][3]int{{1, 2, 0}, {2, 3, 0}, {3, 1, 0}},
+			properties: &properties{
+				isAcyclic: true,
+			},
+			shouldFinallyFail: true,
 		},
 	}
 
 	for name, test := range tests {
-		graph := newDirected(IntHash, &properties{})
+		graph := newDirected(IntHash, test.properties)
 
 		for _, vertex := range test.vertices {
 			graph.Vertex(vertex)
 		}
-		for _, edge := range test.edgeHashes {
-			err := graph.WeightedEdgeByHashes(edge[0], edge[1], edge[2])
 
-			if test.shouldFail != (err != nil) {
-				t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, (err != nil), err)
+		var err error
+
+		for _, edge := range test.edgeHashes {
+			if err = graph.WeightedEdgeByHashes(edge[0], edge[1], edge[2]); err != nil {
+				break
 			}
 		}
+
+		if test.shouldFinallyFail != (err != nil) {
+			t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFinallyFail, (err != nil), err)
+		}
+
 		for _, expectedEdge := range test.expectedEdges {
 			sourceHash := graph.hash(expectedEdge.Source)
 			targetHash := graph.hash(expectedEdge.Target)
diff --git a/undirected_test.go b/undirected_test.go
index 938f2e0..46a364e 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -51,37 +51,56 @@ func TestUndirected_WeightedEdgeByHashes(t *testing.T) {
 	tests := map[string]struct {
 		vertices      []int
 		edgeHashes    [][3]int
+		properties    *properties
 		expectedEdges []Edge[int]
-		shouldFail    bool
+		// Even though some of the WeightedEdgeByHashes calls might work, at least one of them
+		// could fail - for example if the last call would introduce a cycle.
+		shouldFinallyFail bool
 	}{
 		"graph with 2 edges": {
 			vertices:   []int{1, 2, 3},
 			edgeHashes: [][3]int{{1, 2, 10}, {1, 3, 20}},
+			properties: &properties{},
 			expectedEdges: []Edge[int]{
 				{Source: 1, Target: 2, Weight: 10},
 				{Source: 1, Target: 3, Weight: 20},
 			},
 		},
 		"hashes for non-existent vertices": {
-			vertices:   []int{1, 2},
-			edgeHashes: [][3]int{{1, 3, 20}},
-			shouldFail: true,
+			vertices:          []int{1, 2},
+			edgeHashes:        [][3]int{{1, 3, 20}},
+			properties:        &properties{},
+			shouldFinallyFail: true,
+		},
+		"edge introducing a cycle in an acyclic graph": {
+			vertices:   []int{1, 2, 3},
+			edgeHashes: [][3]int{{1, 2, 0}, {2, 3, 0}, {3, 1, 0}},
+			properties: &properties{
+				isAcyclic: true,
+			},
+			shouldFinallyFail: true,
 		},
 	}
 
 	for name, test := range tests {
-		graph := newUndirected(IntHash, &properties{})
+		graph := newUndirected(IntHash, test.properties)
 
 		for _, vertex := range test.vertices {
 			graph.Vertex(vertex)
 		}
-		for _, edge := range test.edgeHashes {
-			err := graph.WeightedEdgeByHashes(edge[0], edge[1], edge[2])
 
-			if test.shouldFail != (err != nil) {
-				t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFail, (err != nil), err)
+		var err error
+
+		for _, edge := range test.edgeHashes {
+			if err = graph.WeightedEdgeByHashes(edge[0], edge[1], edge[2]); err != nil {
+				break
 			}
 		}
+
+		if test.shouldFinallyFail != (err != nil) {
+			t.Fatalf("%s: error expectancy doesn't match: expected %v, got %v (error: %v)", name, test.shouldFinallyFail, (err != nil), err)
+		}
+
 		for _, expectedEdge := range test.expectedEdges {
 			sourceHash := graph.hash(expectedEdge.Source)
 			targetHash := graph.hash(expectedEdge.Target)