Repository: dragonflyoss/Dragonfly2
Pull request #1479 (2022-07-24 09:16:34)

feat: add dag interface
<!--- Provide a general summary of your changes in the Title above -->

## Description

<!--- Describe your changes in detail -->
add dag interface, for find all start of vertex and all end of vertex
## Related Issue

<!--- This project only accepts pull requests related to open issues -->
<!--- If suggesting a new feature or change, please discuss it in an issue first -->
<!--- If fixing a bug, there should be an issue describing it with steps to reproduce -->
<!--- Please link to the issue here: -->

## Motivation and Context

<!--- Why is this change required? What problem does it solve? -->

## Screenshots (if appropriate)

## Types of changes

<!--- What types of changes does your code introduce? Put an `x` in all the boxes that apply: -->

- [ ] Bug fix (non-breaking change which fixes an issue)
- [x] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing functionality to change)
- [ ] Documentation Update (if none of the other choices apply)

## Checklist

<!--- Go over all the following points, and put an `x` in all the boxes that apply. -->
<!--- If you're unsure about any of these, don't hesitate to ask. We're here to help! -->

- [ ] My change requires a change to the documentation.
- [ ] I have updated the documentation accordingly.
- [ ] I have read the **CONTRIBUTING** document.
- [ ] I have added tests to cover my changes.


codecov-commenter: # [Codecov](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) Report
> Merging [#1479](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (7414e62) into [main](https://codecov.io/gh/dragonflyoss/Dragonfly2/commit/79f71afa0642f03ea71ce1f48316244da31cabb9?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) (79f71af) will **increase** coverage by `0.20%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479/graphs/tree.svg?width=650&height=150&src=pr&token=PUICJYSAT7&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss)

```diff
@@            Coverage Diff             @@
##             main    #1479      +/-   ##
==========================================
+ Coverage   43.29%   43.49%   +0.20%     
==========================================
  Files         120      120              
  Lines       10863    10875      +12     
==========================================
+ Hits         4703     4730      +27     
+ Misses       5662     5640      -22     
- Partials      498      505       +7     
```

| Flag | Coverage Δ | |
|---|---|---|
| Object-compatibility-e2etests | `?` | |
| e2etests | `?` | |
| unittests | `43.49% <100.00%> (+0.20%)` | :arrow_up: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss) | Coverage Δ | |
|---|---|---|
| [pkg/dag/dag.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-cGtnL2RhZy9kYWcuZ28=) | `71.29% <100.00%> (+3.58%)` | :arrow_up: |
| [...ent/daemon/peer/peertask\_piecetask\_synchronizer.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX3BpZWNldGFza19zeW5jaHJvbml6ZXIuZ28=) | `47.61% <0.00%> (-1.30%)` | :arrow_down: |
| [client/daemon/peer/peertask\_conductor.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX2NvbmR1Y3Rvci5nbw==) | `56.62% <0.00%> (-0.50%)` | :arrow_down: |
| [client/daemon/peer/peertask\_piecetask\_poller.go](https://codecov.io/gh/dragonflyoss/Dragonfly2/pull/1479/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=dragonflyoss#diff-Y2xpZW50L2RhZW1vbi9wZWVyL3BlZXJ0YXNrX3BpZWNldGFza19wb2xsZXIuZ28=) | `47.10% <0.00%> (+16.66%)` | :arrow_up: |


Patch:
diff --git a/pkg/dag/dag.go b/pkg/dag/dag.go
index 1464c187..6969545b 100644
--- a/pkg/dag/dag.go
+++ b/pkg/dag/dag.go
@@ -54,6 +54,12 @@ type DAG interface {
 	// GetVertices returns map of vertices.
 	GetVertices() map[string]*Vertex
 
+	// GetSourceVertices returns source vertices.
+	GetSourceVertices() map[string]*Vertex
+
+	// GetSinkVertices returns sink vertices.
+	GetSinkVertices() map[string]*Vertex
+
 	// VertexCount returns count of vertices.
 	VertexCount() int
 
@@ -252,6 +258,36 @@ func (d *dag) DeleteEdge(fromVertexID, toVertexID string) error {
 	return nil
 }
 
+// GetSourceVertices returns source vertices.
+func (d *dag) GetSourceVertices() map[string]*Vertex {
+	d.mu.RLock()
+	defer d.mu.RUnlock()
+
+	sourceVertices := make(map[string]*Vertex)
+	for k, v := range d.vertices {
+		if v.InDegree() == 0 {
+			sourceVertices[k] = v
+		}
+	}
+
+	return sourceVertices
+}
+
+// GetSinkVertices returns sink vertices.
+func (d *dag) GetSinkVertices() map[string]*Vertex {
+	d.mu.RLock()
+	defer d.mu.RUnlock()
+
+	sinkVertices := make(map[string]*Vertex)
+	for k, v := range d.vertices {
+		if v.OutDegree() == 0 {
+			sinkVertices[k] = v
+		}
+	}
+
+	return sinkVertices
+}
+
 // depthFirstSearch is a depth-first search of the directed acyclic graph.
 func (d *dag) depthFirstSearch(fromVertexID, toVertexID string) bool {
 	successors := make(map[string]struct{})
diff --git a/pkg/dag/mocks/dag_mock.go b/pkg/dag/mocks/dag_mock.go
index 43db04ca..8e63e929 100644
--- a/pkg/dag/mocks/dag_mock.go
+++ b/pkg/dag/mocks/dag_mock.go
@@ -102,6 +102,34 @@ func (mr *MockDAGMockRecorder) DeleteVertex(id interface{}) *gomock.Call {
 	return mr.mock.ctrl.RecordCallWithMethodType(mr.mock, "DeleteVertex", reflect.TypeOf((*MockDAG)(nil).DeleteVertex), id)
 }
 
+// GetSinkVertices mocks base method.
+func (m *MockDAG) GetSinkVertices() map[string]*dag.Vertex {
+	m.ctrl.T.Helper()
+	ret := m.ctrl.Call(m, "GetSinkVertices")
+	ret0, _ := ret[0].(map[string]*dag.Vertex)
+	return ret0
+}
+
+// GetSinkVertices indicates an expected call of GetSinkVertices.
+func (mr *MockDAGMockRecorder) GetSinkVertices() *gomock.Call {
+	mr.mock.ctrl.T.Helper()
+	return mr.mock.ctrl.RecordCallWithMethodType(mr.mock, "GetSinkVertices", reflect.TypeOf((*MockDAG)(nil).GetSinkVertices))
+}
+
+// GetSourceVertices mocks base method.
+func (m *MockDAG) GetSourceVertices() map[string]*dag.Vertex {
+	m.ctrl.T.Helper()
+	ret := m.ctrl.Call(m, "GetSourceVertices")
+	ret0, _ := ret[0].(map[string]*dag.Vertex)
+	return ret0
+}
+
+// GetSourceVertices indicates an expected call of GetSourceVertices.
+func (mr *MockDAGMockRecorder) GetSourceVertices() *gomock.Call {
+	mr.mock.ctrl.T.Helper()
+	return mr.mock.ctrl.RecordCallWithMethodType(mr.mock, "GetSourceVertices", reflect.TypeOf((*MockDAG)(nil).GetSourceVertices))
+}
+
 // GetVertex mocks base method.
 func (m *MockDAG) GetVertex(id string) (*dag.Vertex, error) {
 	m.ctrl.T.Helper()


Test patch:
diff --git a/pkg/dag/dag_test.go b/pkg/dag/dag_test.go
index 4e89a3df..3097fa7a 100644
--- a/pkg/dag/dag_test.go
+++ b/pkg/dag/dag_test.go
@@ -619,6 +619,100 @@ func TestDAGDeleteEdge(t *testing.T) {
 	}
 }
 
+func TestDAGSourceVertices(t *testing.T) {
+	tests := []struct {
+		name   string
+		expect func(t *testing.T, d DAG)
+	}{
+		{
+			name: "get source vertices",
+			expect: func(t *testing.T, d DAG) {
+				assert := assert.New(t)
+				var (
+					mockVertexEID = "bae"
+					mockVertexFID = "baf"
+				)
+				if err := d.AddVertex(mockVertexEID, mockVertexValue); err != nil {
+					assert.NoError(err)
+				}
+
+				if err := d.AddVertex(mockVertexFID, mockVertexValue); err != nil {
+					assert.NoError(err)
+				}
+
+				if err := d.AddEdge(mockVertexEID, mockVertexFID); err != nil {
+					assert.NoError(err)
+				}
+
+				sourceVertices := d.GetSourceVertices()
+				assert.Equal(len(sourceVertices), 1)
+				assert.Equal(sourceVertices[mockVertexEID].Value, mockVertexValue)
+			},
+		},
+		{
+			name: "source vertices not found",
+			expect: func(t *testing.T, d DAG) {
+				assert := assert.New(t)
+				sourceVertices := d.GetSourceVertices()
+				assert.Equal(len(sourceVertices), 0)
+			},
+		},
+	}
+	for _, tc := range tests {
+		t.Run(tc.name, func(t *testing.T) {
+			d := NewDAG()
+			tc.expect(t, d)
+		})
+	}
+}
+
+func TestDAGSinkVertices(t *testing.T) {
+	tests := []struct {
+		name   string
+		expect func(t *testing.T, d DAG)
+	}{
+		{
+			name: "get sink vertices",
+			expect: func(t *testing.T, d DAG) {
+				assert := assert.New(t)
+				var (
+					mockVertexEID = "bae"
+					mockVertexFID = "baf"
+				)
+				if err := d.AddVertex(mockVertexEID, mockVertexValue); err != nil {
+					assert.NoError(err)
+				}
+
+				if err := d.AddVertex(mockVertexFID, mockVertexValue); err != nil {
+					assert.NoError(err)
+				}
+
+				if err := d.AddEdge(mockVertexEID, mockVertexFID); err != nil {
+					assert.NoError(err)
+				}
+
+				sinkVertices := d.GetSinkVertices()
+				assert.Equal(len(sinkVertices), 1)
+				assert.Equal(sinkVertices[mockVertexFID].Value, mockVertexValue)
+			},
+		},
+		{
+			name: "sink vertices not found",
+			expect: func(t *testing.T, d DAG) {
+				assert := assert.New(t)
+				sinkVertices := d.GetSinkVertices()
+				assert.Equal(len(sinkVertices), 0)
+			},
+		},
+	}
+	for _, tc := range tests {
+		t.Run(tc.name, func(t *testing.T) {
+			d := NewDAG()
+			tc.expect(t, d)
+		})
+	}
+}
+
 func BenchmarkDAGAddVertex(b *testing.B) {
 	var ids []string
 	d := NewDAG()
diff --git a/pkg/dag/vertex_test.go b/pkg/dag/vertex_test.go
index bf72b5f3..5c063b85 100644
--- a/pkg/dag/vertex_test.go
+++ b/pkg/dag/vertex_test.go
@@ -24,7 +24,7 @@ import (
 
 const (
 	mockVertexID    = "foo"
-	mockVertexValue = "var"
+	mockVertexValue = "bar"
 )
 
 func TestNewVertex(t *testing.T) {