Goデータ構造:グラフ

Goでのグラフデータ構造の分析と実装

Aグラフネットワーク構造の表現です。グラフの実世界の例はたくさんあり、インターネットとソーシャルグラフは古典的なものです。

それは基本的にのセットですノードによって接続されていますエッジ

数学の概念はどこにでもあるのでスキップし、グラフのGo実装に直接ジャンプします。

実装

グラフデータ構造は、これらのメソッドを公開します。

  • AddNode()ノードを挿入します
  • AddEdge()2つのノード間にエッジを追加します

そして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(幅優先探索)は、グラフを走査するための最も広く知られているアルゴリズムの1つです。ノードから開始して、最初に直接リンクされたすべてのノードをトラバースし、次にそれらにリンクされたノードを処理します。

それは私のから生成されたキューを使用して実装されていますキューデータ構造の実装に進むノードタイプのコード生成:

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


その他のチュートリアル: