在 Go 中将 Gonum 用于图形算法

Question

我是一名新的 Go 程序员，几天前刚刚完成 "A tour of Go" 教程。我想创建一个 150 x 120 大小的图，然后获取每个节点的所有边缘节点并实现一些图搜索算法，例如 BFS 和 Dijkstra。我找到了一个名为 Gonum 的漂亮库，它的 graph package 看起来很有用。

我的问题是信息太多，我不知道从哪里开始。我希望有某种教程可以让我朝着正确的方向开始，但我没有找到一个。

我在 Python 中设置它的方式是制作一个零的 numpy 数组来表示图的大小，然后遍历它以获得每个节点的每条边，但我不确定这是思考如何在 Go 中设置图形的最佳方式。

Answer 1

如果您刚开始使用 Go，我建议您坚持使用标准库一段时间，不要在您的学习曲线上添加更多内容。尝试用一些基本算法实现一个简单的图数据结构——这很容易，而且会让你练习语言。稍后当您需要更多 performance/features 时，您可以四处寻找图书馆（gonum 或其他）。例如，一个简单的图形可以表示为：

// Node is a node in the graph; it has a (unique) ID and a sequence of
// edges to other nodes.
type Node struct {
    Id    int64
    Edges []int64
}

// Graph contains a set of Nodes, uniquely identified by numeric IDs.
type Graph struct {
    Nodes map[int64]Node
}

Answer 2

偶然发现了这个问题，也在寻找使用 gonum/graph 计算边数的提示。除了挖掘 API 文档之外，我没有找到大量资源。

我想我找到了计算单个节点边数的正确方法。也许吧！

for _, node := range graph.NodesOf(g.Nodes()) {
    toNodes := g.From(node.ID()) // returns graph.Nodes
    nodeArray := graph.NodesOf( toNodes ) // returns []graph.Node
    edgeCount := len(nodeArray)
    // - or -
    edgeCount := len(graph.NodesOf( g.From(node.ID()) ))
    // do work with edge count
}

给定一个已知节点和您可以从那里到达的所有节点，您可以计算（例如：len(graph.NodesOf(g.From(node.ID())))边的数量！

计算所有的边：

totalEdges := len(graph.EdgesOf(g.Edges()))

在 Go 中将 Gonum 用于图形算法

Using Gonum for graph algorithms in Go

search

graph

go

gonum