Analysis and Implementation of Graph Data Structure in Go
A kindGraphicsIs a representation of the network structure. There are a large number of real-world examples of graphs, and the Internet and social graphs are classic examples.
Basically a groupNodeConnect byedge.
I will skip the mathematical concepts because you can find them anywhere, and then jump directly to the Go implementation of the diagram.
carried out
The graphics data structure will expose these methods:
AddNode()
Insert nodeAddEdge()
Add an edge between two nodes
withString()
Used for inspection purposes.
The graph is defined as
type ItemGraph struct {
nodes []*Node
edges map[Node][]*Node
lock sync.RWMutex
}
And node is
type Node struct {
value Item
}
I will implement an undirected graph, which means that adding an edge from A to B will also add an edge from B to A.
carried out
// Package graph creates a ItemGraph data structure for the Item type
package graph
import (
“fmt”
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Item the type of the binary search tree
type Item generic.Type
// Node a single node that composes the tree
type Node struct {
value Item
}
func (n *Node) String() string {
return fmt.Sprintf("%v", n.value)
}
// ItemGraph the Items graph
type ItemGraph struct {
nodes []Node
edges map[Node][]Node
lock sync.RWMutex
}
// AddNode adds a node to the graph
func (g ItemGraph) AddNode(n Node) {
g.lock.Lock()
g.nodes = append(g.nodes, n)
g.lock.Unlock()
}
// AddEdge adds an edge to the graph
func (g ItemGraph) AddEdge(n1, n2 Node) {
g.lock.Lock()
if g.edges == nil {
g.edges = make(map[Node][]Node)
}
g.edges[n1] = append(g.edges[n1], n2)
g.edges[n2] = append(g.edges[*n2], n1)
g.lock.Unlock()
}
// AddEdge adds an edge to the graph
func (g ItemGraph) String() {
g.lock.RLock()
s := “”
for i := 0; i < len(g.nodes); i++ {
s += g.nodes[i].String() + " -> "
near := g.edges[g.nodes[i]]
for j := 0; j < len(near); j++ {
s += near[j].String() + " "
}
s += “\n”
}
fmt.Println(s)
g.lock.RUnlock()
}
very simple. This is a test, the graphics will be filled and printed when run
$ go test
A -> B C D
B -> A E
C -> A E
D -> A
E -> B C F
F -> E
PASS
package graph
import (
“fmt”
“testing”
)
var g ItemGraph
func fillGraph() {
nA := Node{“A”}
nB := Node{“B”}
nC := Node{“C”}
nD := Node{“D”}
nE := Node{“E”}
nF := Node{“F”}
g.AddNode(&nA)
g.AddNode(&nB)
g.AddNode(&nC)
g.AddNode(&nD)
g.AddNode(&nE)
g.AddNode(&nF)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nB</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nC</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nB</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nC</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nE</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nF</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&</span><span style="color:#a6e22e">nD</span>, <span style="color:#f92672">&</span><span style="color:#a6e22e">nA</span>)
}
func TestAdd(t *testing.T) {
fillGraph()
g.String()
}
Traverse the graph: BFS
BFS(Breadth first search) is one of the most widely known algorithms for traversing graphs. Starting from a node, it first traverses all directly linked nodes, then processes the nodes linked to those nodes, and so on.
It is implemented using a queue, the queue is from mineTo implement the queue data structureUse code generation for node types:
// This file was automatically generated by genny.
// Any changes will be lost if this file is regenerated.
// see https://github.com/cheekybits/genny
package graph
import “sync”
// NodeQueue the queue of Nodes
type NodeQueue struct {
items []Node
lock sync.RWMutex
}
// New creates a new NodeQueue
func (s NodeQueue) New() NodeQueue {
s.lock.Lock()
s.items = []Node{}
s.lock.Unlock()
return s
}
// Enqueue adds an Node to the end of the queue
func (s *NodeQueue) Enqueue(t Node) {
s.lock.Lock()
s.items = append(s.items, t)
s.lock.Unlock()
}
// Dequeue removes an Node from the start of the queue
func (s NodeQueue) Dequeue() Node {
s.lock.Lock()
item := s.items[0]
s.items = s.items[1:len(s.items)]
s.lock.Unlock()
return &item
}
// Front returns the item next in the queue, without removing it
func (s NodeQueue) Front() Node {
s.lock.RLock()
item := s.items[0]
s.lock.RUnlock()
return &item
}
// IsEmpty returns true if the queue is empty
func (s *NodeQueue) IsEmpty() bool {
s.lock.RLock()
defer s.lock.RUnlock()
return len(s.items) == 0
}
// Size returns the number of Nodes in the queue
func (s *NodeQueue) Size() int {
s.lock.RLock()
defer s.lock.RUnlock()
return len(s.items)
}
Wire method
This is the implementation of BFS:
// Traverse implements the BFS traversing algorithm
func (g *ItemGraph) Traverse(f func(*Node)) {
g.lock.RLock()
q := NodeQueue{}
q.New()
n := g.nodes[0]
q.Enqueue(*n)
visited := make(map[*Node]bool)
for {
if q.IsEmpty() {
break
}
node := q.Dequeue()
visited[node] = true
near := g.edges[*node]
<span style="color:#66d9ef">for</span> <span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#ae81ff">0</span>; <span style="color:#a6e22e">i</span> < len(<span style="color:#a6e22e">near</span>); <span style="color:#a6e22e">i</span><span style="color:#f92672">++</span> {
<span style="color:#a6e22e">j</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">near</span>[<span style="color:#a6e22e">i</span>]
<span style="color:#66d9ef">if</span> !<span style="color:#a6e22e">visited</span>[<span style="color:#a6e22e">j</span>] {
<span style="color:#a6e22e">q</span>.<span style="color:#a6e22e">Enqueue</span>(<span style="color:#f92672">*</span><span style="color:#a6e22e">j</span>)
<span style="color:#a6e22e">visited</span>[<span style="color:#a6e22e">j</span>] = <span style="color:#66d9ef">true</span>
}
}
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">f</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">nil</span> {
<span style="color:#a6e22e">f</span>(<span style="color:#a6e22e">node</span>)
}
}
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">lock</span>.<span style="color:#a6e22e">RUnlock</span>()
}
Can use
func TestTraverse(t *testing.T) {
g.Traverse(func(n *Node) {
fmt.Printf("%v\n", n)
})
}
After being added to our test, it will print the road taken to traverse all our nodes:
A
B
C
D
A
E
F
Create a specific graphical data structure
You can use the following general implementation to generate type-specific diagrams by:
//generate a `IntGraph` graph of `int` values
genny -in graph.go -out graph-int.go gen "Item=int"
//generate a </span>StringGraph<span style="color:#e6db74">
graph of </span>string<span style="color:#e6db74">
values
genny -in graph.go -out graph-string.go gen “Item=string”
More tutorials:
- Use NGINX reverse proxy service Go service
- Copy structure in Go
- Basics of Go web server
- Sorting map types in Go
- In a nutshell
- Go to label description
- Start date and time format
- Use Go for JSON processing
- Variadic function
- Cheat sheet
- Go to the empty interface description
- Use VS Code and Delve to debug Go
- Named Go return parameter
- Generate random numbers and strings in Go
- File system structure of Go project
- Binary search algorithm in Go
- Use command line flags in Go
- GOPATH explained
- Use Go to build a command line application: lolcat
- Use Go to build CLI commands: Cowsay
- Use shell and tube in Go
- Go CLI Tutorial: Fortune Clone
- Use Go to list files in a folder
- Use Go to get a list of repositories from GitHub
- Go, append a short string to the file
- Go, convert the string to byte slices
- Use Go to visualize your local Git contributions
- Getting started with Go CPU and memory analysis
- Solve the "Does not support index" error in the Go program
- Measuring the execution time in the Go program
- Use Go to build a web crawler to detect duplicate titles
- Best Practice: Pointer or Value Receiver?
- Best practice: Should you use methods or functions?
- Go data structure: set
- Go to the map cheat sheet
- Generating the implementation of generic types in Go
- Go data structure: dictionary
- Go data structure: hash table
- Implement event listeners in "through the channel"
- Go data structure: stack
- Go data structure: queue
- Go data structure: binary search tree
- Go data structure: graphics
- Go data structure: linked list
- A complete guide to Go data structures
- Compare Go value
- Is Go object-oriented?
- Use SQL database in Go
- Use environment variables in Go
- Last tutorial: REST API supported by PostgreSQL
- Enable CORS on the Go web server
- Deploy Go application in Docker container
- Why Go is a powerful language to learn as a PHP developer
- Go and delete the io.Reader.ReadString newline
- To start, how to watch the changes and rebuild the program
- To count the months since the date
- Access HTTP POST parameters in Go