# Go data structure: graphics

## 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 node
• `AddEdge()`Add an edge between two nodes

with`String()`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”}
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nB</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nA</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nC</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nB</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nC</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nE</span>, <span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nF</span>)
<span style="color:#a6e22e">g</span>.<span style="color:#a6e22e">AddEdge</span>(<span style="color:#f92672">&amp;</span><span style="color:#a6e22e">nD</span>, <span style="color:#f92672">&amp;</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> &lt; 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”``````