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”


More tutorials: