A graph is a representation of a network structure. There are tons of graph real world examples, the Internet and the social graph being the classic ones.
It’s basically a set of nodes connected by edges.
I’ll skip the mathematical concepts since you can find them everywhere and jump directly to a Go implementation of a graph.
Implementation
A graph data structure will expose those methods:
AddNode()
inserts a nodeAddEdge()
adds an edge between two nodes
and String()
for inspection purposes.
A Graph is defined as
type ItemGraph struct {
nodes []*Node
edges map[Node][]*Node
lock sync.RWMutex
}
with Node being
type Node struct {
value Item
}
I’ll implement an undirected graph, which means that adding an edge from A to B also adds an edge from B to A.
Implementation
// Package graph creates a ItemGraph data structure for the Item type
package graph
import (
"fmt"
"sync"
"github.com/cheekybits/genny/generic"
)
// 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()
}
Quite straightforward. Here’s a test that when run, will populate the graph and print
$ 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)
g.AddEdge(&nA, &nB)
g.AddEdge(&nA, &nC)
g.AddEdge(&nB, &nE)
g.AddEdge(&nC, &nE)
g.AddEdge(&nE, &nF)
g.AddEdge(&nD, &nA)
}
func TestAdd(t *testing.T) {
fillGraph()
g.String()
}
Traversing the graph: BFS
BFS (Breadth-First Search) is one of the most widely known algorithm to traverse a graph. Starting from a node, it first traverses all its directly linked nodes, then processes the nodes linked to those, and so on.
It’s implemented using a queue, which is generated from my Go implementation of a queue data structure with code generation for the node type:
// 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)
}
Traverse method
Here’s the BFS implementation:
// 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]
for i := 0; i < len(near); i++ {
j := near[i]
if !visited[j] {
q.Enqueue(*j)
visited[j] = true
}
}
if f != nil {
f(node)
}
}
g.lock.RUnlock()
}
which can be tested with
func TestTraverse(t *testing.T) {
g.Traverse(func(n *Node) {
fmt.Printf("%v\n", n)
})
}
which after being added to our tests, will print the road it took to traverse all our nodes:
A
B
C
D
A
E
F
Creating a concrete graph data structure
You can use this generic implemenation to generate type-specific graphs, using
//generate a `IntGraph` graph of `int` values
genny -in graph.go -out graph-int.go gen "Item=int"
//generate a `StringGraph` graph of `string` values
genny -in graph.go -out graph-string.go gen "Item=string"
More go tutorials:
- Using NGINX Reverse Proxy to serve Go services
- Making a copy of a struct in Go
- The basics of a Go Web Server
- Sorting a map type in Go
- Go pointers in a nutshell
- Go Tags explained
- Go Date and Time Formatting
- JSON processing with Go
- Go Variadic Functions
- Go Strings Cheat Sheet
- The Go Empty Interface Explained
- Debugging Go with VS Code and Delve
- Named Go returns parameters
- Generating random numbers and strings in Go
- Filesystem Structure of a Go project
- Binary Search Algorithm Implemented in Go
- Using Command Line Flags in Go
- GOPATH Explained
- Build a Command Line app with Go: lolcat
- Building a CLI command with Go: cowsay
- Using Shell Pipes with Go
- Go CLI tutorial: fortune clone
- List the files in a folder with Go
- Use Go to get a list of repositories from GitHub
- Go, append a slice of strings to a file
- Go, convert a string to a bytes slice
- Visualize your local Git contributions with Go
- Getting started with Go CPU and memory profiling
- Solving the "does not support indexing" error in a Go program
- Measuring execution time in a Go program
- Building a Web Crawler with Go to detect duplicate titles
- Go Best Practices: Pointer or value receivers?
- Go Best Practices: Should you use a method or a function?
- Go Data Structures: Set
- Go Maps Cheat Sheet
- Generate implementations for generic types in Go
- Go Data Structures: Dictionary
- Go Data Structures: Hash Table
- Implement Events Listeners in Go through Channels
- Go Data Structures: Stack
- Go Data Structures: Queue
- Go Data Structures: Binary Search Tree
- Go Data Structures: Graph
- Go Data Structures: Linked List
- The complete guide to Go Data Structures
- Comparing Go Values
- Is Go object oriented?
- Working with a SQL Database in Go
- Using environment variables in Go
- Go tutorial: REST API backed by PostgreSQL
- Enabling CORS on a Go Web Server
- Deploying a Go Application in a Docker Container
- Why Go is a powerful language to learn as a PHP developer
- Go, remove the io.Reader.ReadString newline char
- Go, how to watch changes and rebuild your program
- Go, count the months since a date
- Accessing HTTP POST parameters in Go