-
Notifications
You must be signed in to change notification settings - Fork 1
/
graph.go
176 lines (147 loc) · 4.63 KB
/
graph.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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
package parse
import (
"go/types"
"sort"
"github.com/emilien-puget/go-dependency-graph/pkg/parse/struct_decl"
"golang.org/x/tools/go/packages"
)
// Node represents a node of the dependency graph.
type Node struct {
Name string // The fully qualified name of the struct, PackageName.StructName
PackageName string
StructName string
Methods []struct_decl.Method
Doc string
External bool
InboundEdges []*Node
ActualNamedType *types.Named
P *packages.Package
FilePath string
}
func (n *Node) MergeAdditionalFields(other *Node) {
if len(other.Methods) > 0 {
n.Methods = other.Methods
}
if n.ActualNamedType == nil && other.ActualNamedType != nil {
n.ActualNamedType = other.ActualNamedType
}
if n.P == nil && other.P != nil {
n.P = other.P
}
if n.FilePath == "" && other.FilePath != "" {
n.FilePath = other.FilePath
}
}
// Graph represents the dependency graph.
type Graph struct {
Nodes []*Node // A slice of pointers to all the nodes in the graph
Adj map[*Node][]*Adj // An adjacency list mapping each node to its adjacent nodes
NodeByName map[string]*Node // A hash map to store nodes by their names
NodesByPackage map[string][]*Node // A hash map to store nodes by their packages
}
type Adj struct {
Node *Node
Func []string
}
func NewGraph() *Graph {
return &Graph{
Nodes: make([]*Node, 0),
Adj: make(map[*Node][]*Adj),
NodeByName: make(map[string]*Node),
NodesByPackage: make(map[string][]*Node),
}
}
// AddNode adds a new Node to the graph.
func (g *Graph) AddNode(node *Node) {
existingNode, exists := g.NodeByName[node.Name]
if exists {
existingNode.MergeAdditionalFields(node)
return
}
g.Nodes = append(g.Nodes, node)
g.Adj[node] = make([]*Adj, 0) // Initialize the adjacency list for the new node
g.NodeByName[node.Name] = node // Add the node to the hash map using its name as the key
// Update the NodesByPackage hash map
g.NodesByPackage[node.PackageName] = append(g.NodesByPackage[node.PackageName], node)
// Initialize the inbound edges slice for the new node
node.InboundEdges = make([]*Node, 0)
}
func (g *Graph) GetAdjacency(node *Node) []*Adj {
return g.Adj[node]
}
// GetNodeByName finds a node by its name in the graph.
func (g *Graph) GetNodeByName(name string) *Node {
return g.NodeByName[name]
}
// AddEdge adds a directed edge between two nodes in the graph.
func (g *Graph) AddEdge(from *Node, to *Adj) {
existingFromNode, exists := g.NodeByName[from.Name]
if exists {
from = existingFromNode
}
existingToNode, exists := g.NodeByName[to.Node.Name]
if exists {
existingToNode.MergeAdditionalFields(to.Node)
to.Node = existingToNode
}
// Update the adjacency list
g.Adj[from] = append(g.Adj[from], to)
// Update the inbound edges for the 'to' node
to.Node.InboundEdges = append(to.Node.InboundEdges, from)
}
// TopologicalSort performs a topological sort on the graph.
func (g *Graph) TopologicalSort() []*Node {
visited := make(map[*Node]bool)
stack := make([]*Node, 0)
var dfs func(node *Node)
dfs = func(node *Node) {
visited[node] = true
for _, neighbor := range g.Adj[node] {
if !visited[neighbor.Node] {
dfs(neighbor.Node)
}
}
stack = append(stack, node) // Push the node onto the stack
}
for _, node := range g.Nodes {
if !visited[node] {
dfs(node)
}
}
// Pop nodes from the stack to get the topological order
sortedNodes := make([]*Node, 0, len(stack))
for i := len(stack) - 1; i >= 0; i-- {
sortedNodes = append(sortedNodes, stack[i])
}
return sortedNodes
}
// GetLeafNodes returns all the leaf nodes.
// A leaf node is a node without any inbound nodes.
func (g *Graph) GetLeafNodes() []*Node {
leafNodes := make([]*Node, 0)
for _, node := range g.Nodes {
if len(node.InboundEdges) == 0 && len(g.Adj[node]) > 0 {
leafNodes = append(leafNodes, node)
}
}
return leafNodes
}
// GetNodesSortedByName returns all nodes sorted by node name.
func (g *Graph) GetNodesSortedByName() []*Node {
sortedNodes := make([]*Node, len(g.Nodes))
copy(sortedNodes, g.Nodes)
sort.SliceStable(sortedNodes, func(i, j int) bool {
return sortedNodes[i].Name < sortedNodes[j].Name
})
return sortedNodes
}
// GetAdjacenciesSortedByName returns the adjacencies sorted by the adjacent node names.
func (g *Graph) GetAdjacenciesSortedByName(node *Node) []*Adj {
adjacencies := g.Adj[node]
sortedAdjacencies := make([]*Adj, len(adjacencies))
copy(sortedAdjacencies, adjacencies)
sort.SliceStable(sortedAdjacencies, func(i, j int) bool {
return sortedAdjacencies[i].Node.Name < sortedAdjacencies[j].Node.Name
})
return sortedAdjacencies
}