Структуры данных Go: график

Анализ и реализация структуры данных Graph в Go

Аграфикпредставляет собой сетевую структуру. Существует множество примеров графического реального мира, классическими из которых являются Интернет и социальный граф.

Это в основном наборузлысвязаныкрая.

Я пропущу математические концепции, так как вы можете найти их повсюду, и сразу перейду к реализации графа в Go.

Выполнение

Эти методы будут представлены в структуре данных графа:

  • AddNode()вставляет узел
  • AddEdge()добавляет ребро между двумя узлами

иString()для целей проверки.

График определяется как

type ItemGraph struct {
    nodes []*Node
    edges map[Node][]*Node
    lock  sync.RWMutex
}

с узлом

type Node struct {
    value Item
}

Я буду реализовывать неориентированный граф, что означает, что добавление ребра от A к B также добавляет ребро от B к A.

Выполнение

// 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()
}

Довольно просто. Вот тест, который при запуске заполнит график и распечатает

$ 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()
}

По графику: BFS

BFS(Поиск в ширину) - один из наиболее широко известных алгоритмов обхода графа. Начиная с узла, он сначала проходит все его напрямую связанные узлы, затем обрабатывает узлы, связанные с ними, и так далее.

Это реализовано с использованием очереди, которая генерируется из моихПерейти к реализации структуры данных очередис генерацией кода для типа узла:

// 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)
}

Метод траверса

Вот реализация 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>()

}

который можно протестировать с помощью

func TestTraverse(t *testing.T) {
    g.Traverse(func(n *Node) {
        fmt.Printf("%v\n", n)
    })
}

который после добавления в наши тесты напечатает путь, который потребовался, чтобы пройти все наши узлы:

A
B
C
D
A
E
F

Создание конкретной структуры данных графа

Вы можете использовать эту универсальную реализацию для создания графиков, зависящих от типа, используя

//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:


Tech Wiki Online!