forked from PlatONnetwork/PlatON-Go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dag.go
126 lines (111 loc) · 2.46 KB
/
dag.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package dag
import (
"bytes"
"encoding/gob"
"fmt"
)
type Vertex struct {
InDegree int
OutEdges []int
InEdges []int
}
func NewVertex() *Vertex {
vertex := &Vertex{
InDegree: 0,
OutEdges: make([]int, 0),
InEdges: make([]int, 0),
}
return vertex
}
type Dag struct {
V int
Consumed int
VertexList []*Vertex
NextList []int
}
func NewDag(v int) *Dag {
dag := &Dag{
V: v,
}
for i := 0; i < v; i++ {
dag.VertexList = append(dag.VertexList, NewVertex())
}
return dag
}
func (dag *Dag) AddEdge(from, to int) {
dag.VertexList[from].OutEdges = append(dag.VertexList[from].OutEdges, to)
dag.VertexList[to].InDegree++
dag.VertexList[to].InEdges = append(dag.VertexList[to].InEdges, from)
}
func (dag *Dag) GetOutEdges(from int) []int {
return dag.VertexList[from].OutEdges
}
func (dag *Dag) GetInEdges(to int) []int {
return dag.VertexList[to].InEdges
}
func (dag *Dag) HasNext() bool {
return dag.Consumed < dag.V
}
func (dag *Dag) Next() []int {
if len(dag.NextList) == 0 {
for i := 0; i < dag.V; i++ {
if dag.VertexList[i].InDegree == 0 {
dag.NextList = append(dag.NextList, i)
}
}
} else {
//need copy?
preList := dag.NextList
dag.NextList = []int{}
for _, vtxIdx := range preList {
for _, outVtxIdx := range dag.VertexList[vtxIdx].OutEdges {
dag.VertexList[outVtxIdx].InDegree--
if dag.VertexList[outVtxIdx].InDegree == 0 {
dag.NextList = append(dag.NextList, outVtxIdx)
}
}
}
}
dag.Consumed = dag.Consumed + len(dag.NextList)
return dag.NextList
}
func (dag *Dag) InDegree(i int) int {
return dag.VertexList[i].InDegree
}
func (dag *Dag) OutDegree(i int) int {
return len(dag.VertexList[i].OutEdges)
}
func (dag *Dag) Print() (bytes.Buffer, error) {
var buffer bytes.Buffer
var dagCpy = &Dag{}
if err := clone(dag, dagCpy); err != nil {
return buffer, err
}
var level = 0
for dagCpy.HasNext() {
buffer.WriteString(fmt.Sprintf("level:%d \n ", level))
idxs := dagCpy.Next()
for _, idx := range idxs {
if level == 0 {
buffer.WriteString(fmt.Sprintf("idx:%d ", idx))
} else {
buffer.WriteString(fmt.Sprintf("idx:%d%+v ", idx, dagCpy.VertexList[idx].InEdges))
}
}
buffer.WriteString("\n")
level++
}
return buffer, nil
}
func clone(src, dest interface{}) error {
buff := new(bytes.Buffer)
enc := gob.NewEncoder(buff)
dec := gob.NewDecoder(buff)
if err := enc.Encode(src); err != nil {
return err
}
if err := dec.Decode(dest); err != nil {
return err
}
return nil
}