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

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">&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”

Go data structure: graphics

Analysis and Implementation of Graph Data Structure in Go

carried out

carried out

Traverse the graph: BFS

Wire method

Create a specific graphical data structure

More tutorials: