Repository: dominikbraun/graph
Pull request #41 (2022-09-09 13:42:10)

Add Order and Size

pangeran-bottor: Hi @dominikbraun,
This PR is for issue #21 with a minor fix on a comment. I would love to get any feedback on this. Also, let me know if some changes are needed to the PR so it can be merged. Thank you!

Patch:
diff --git a/directed.go b/directed.go
index 8cd3a57..fb867f3 100644
--- a/directed.go
+++ b/directed.go
@@ -186,6 +186,18 @@ func (d *directed[K, T]) Clone() (Graph[K, T], error) {
 	}, nil
 }
 
+func (d *directed[K, T]) Order() int {
+	return len(d.vertices)
+}
+
+func (d *directed[K, T]) Size() int {
+	size := 0
+	for _, outEdges := range d.outEdges {
+		size += len(outEdges)
+	}
+	return size
+}
+
 func (d *directed[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := d.hash(a.Source)
 	aTargetHash := d.hash(a.Target)
diff --git a/graph.go b/graph.go
index 3b0ae30..a871901 100644
--- a/graph.go
+++ b/graph.go
@@ -51,7 +51,7 @@ type Graph[K comparable, T any] interface {
 	//	map[string]map[string]Edge[string]{
 	//		"A": map[string]Edge[string]{
 	//			"B": {Source: "A", Target: "B"}
-	//			"C": {Source: "A", Target: "B"}
+	//			"C": {Source: "A", Target: "C"}
 	//		}
 	//	}
 	//
@@ -70,6 +70,12 @@ type Graph[K comparable, T any] interface {
 
 	// Clone creates an independent deep copy of the graph and returns that cloned graph.
 	Clone() (Graph[K, T], error)
+
+	// Order computes and returns the number of vertices in the graph.
+	Order() int
+
+	// Size computes and returns the number of edges in the graph.
+	Size() int
 }
 
 // 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 a2fc3df..4b47203 100644
--- a/undirected.go
+++ b/undirected.go
@@ -170,6 +170,20 @@ func (u *undirected[K, T]) Clone() (Graph[K, T], error) {
 	}, nil
 }
 
+func (u *undirected[K, T]) Order() int {
+	return len(u.vertices)
+}
+
+func (u *undirected[K, T]) Size() int {
+	size := 0
+	for _, outEdges := range u.outEdges {
+		size += len(outEdges)
+	}
+
+	// Divide by 2 since every add edge operation on undirected graph is counted twice.
+	return size / 2
+}
+
 func (u *undirected[K, T]) edgesAreEqual(a, b Edge[T]) bool {
 	aSourceHash := u.hash(a.Source)
 	aTargetHash := u.hash(a.Target)


Test patch:
diff --git a/directed_test.go b/directed_test.go
index 053886b..338b50b 100644
--- a/directed_test.go
+++ b/directed_test.go
@@ -531,6 +531,78 @@ func TestDirected_Clone(t *testing.T) {
 	}
 }
 
+func TestDirected_OrderAndSize(t *testing.T) {
+	tests := map[string]struct {
+		vertices      []int
+		edges         []Edge[int]
+		expectedOrder int
+		expectedSize  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},
+			},
+			expectedOrder: 4,
+			expectedSize:  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},
+			},
+			expectedOrder: 4,
+			expectedSize:  4,
+		},
+		"two-vertices two-edges graph": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+				{Source: 2, Target: 1},
+			},
+			expectedOrder: 2,
+			expectedSize:  2,
+		},
+		"edgeless graph": {
+			vertices:      []int{1, 2},
+			edges:         []Edge[int]{},
+			expectedOrder: 2,
+			expectedSize:  0,
+		},
+	}
+
+	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())
+			}
+		}
+
+		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)
+		}
+
+		if size != test.expectedSize {
+			t.Errorf("%s: size expectancy doesn't match: expected %d, got %d", name, test.expectedSize, size)
+		}
+
+	}
+}
+
 func TestDirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]
diff --git a/undirected_test.go b/undirected_test.go
index 417e12e..b15326c 100644
--- a/undirected_test.go
+++ b/undirected_test.go
@@ -492,6 +492,77 @@ func TestUndirected_Clone(t *testing.T) {
 	}
 }
 
+func TestUndirected_OrderAndSize(t *testing.T) {
+	tests := map[string]struct {
+		vertices      []int
+		edges         []Edge[int]
+		expectedOrder int
+		expectedSize  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},
+			},
+			expectedOrder: 4,
+			expectedSize:  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},
+			},
+			expectedOrder: 4,
+			expectedSize:  4,
+		},
+		"two-vertices graph": {
+			vertices: []int{1, 2},
+			edges: []Edge[int]{
+				{Source: 1, Target: 2},
+			},
+			expectedOrder: 2,
+			expectedSize:  1,
+		},
+		"edgeless graph": {
+			vertices:      []int{1, 2},
+			edges:         []Edge[int]{},
+			expectedOrder: 2,
+			expectedSize:  0,
+		},
+	}
+
+	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())
+			}
+		}
+
+		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)
+		}
+
+		if size != test.expectedSize {
+			t.Errorf("%s: size expectancy doesn't match: expected %d, got %d", name, test.expectedSize, size)
+		}
+
+	}
+}
+
 func TestUndirected_edgesAreEqual(t *testing.T) {
 	tests := map[string]struct {
 		a             Edge[int]