go graph 源码

golang graph 代码

文件路径：/test/typeparam/graph.go

// run

// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package main

import (
	"errors"
	"fmt"
)

// _Equal reports whether two slices are equal: the same length and all
// elements equal. All floating point NaNs are considered equal.
func _SliceEqual[Elem comparable](s1, s2 []Elem) bool {
	if len(s1) != len(s2) {
		return false
	}
	for i, v1 := range s1 {
		v2 := s2[i]
		if v1 != v2 {
			isNaN := func(f Elem) bool { return f != f }
			if !isNaN(v1) || !isNaN(v2) {
				return false
			}
		}
	}
	return true
}

// A Graph is a collection of nodes. A node may have an arbitrary number
// of edges. An edge connects two nodes. Both nodes and edges must be
// comparable. This is an undirected simple graph.
type _Graph[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {
	nodes []_Node
}

// _NodeC is the contraints on a node in a graph, given the _Edge type.
type _NodeC[_Edge any] interface {
	comparable
	Edges() []_Edge
}

// Edgec is the constraints on an edge in a graph, given the _Node type.
type _EdgeC[_Node any] interface {
	comparable
	Nodes() (a, b _Node)
}

// _New creates a new _Graph from a collection of Nodes.
func _New[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]](nodes []_Node) *_Graph[_Node, _Edge] {
	return &_Graph[_Node, _Edge]{nodes: nodes}
}

// nodePath holds the path to a node during ShortestPath.
// This should ideally be a type defined inside ShortestPath,
// but the translator tool doesn't support that.
type nodePath[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {
	node _Node
	path []_Edge
}

// ShortestPath returns the shortest path between two nodes,
// as an ordered list of edges. If there are multiple shortest paths,
// which one is returned is unpredictable.
func (g *_Graph[_Node, _Edge]) ShortestPath(from, to _Node) ([]_Edge, error) {
	visited := make(map[_Node]bool)
	visited[from] = true
	workqueue := []nodePath[_Node, _Edge]{nodePath[_Node, _Edge]{from, nil}}
	for len(workqueue) > 0 {
		current := workqueue
		workqueue = nil
		for _, np := range current {
			edges := np.node.Edges()
			for _, edge := range edges {
				a, b := edge.Nodes()
				if a == np.node {
					a = b
				}
				if !visited[a] {
					ve := append([]_Edge(nil), np.path...)
					ve = append(ve, edge)
					if a == to {
						return ve, nil
					}
					workqueue = append(workqueue, nodePath[_Node, _Edge]{a, ve})
					visited[a] = true
				}
			}
		}
	}
	return nil, errors.New("no path")
}

type direction int

const (
	north direction = iota
	ne
	east
	se
	south
	sw
	west
	nw
	up
	down
)

func (dir direction) String() string {
	strs := map[direction]string{
		north: "north",
		ne:    "ne",
		east:  "east",
		se:    "se",
		south: "south",
		sw:    "sw",
		west:  "west",
		nw:    "nw",
		up:    "up",
		down:  "down",
	}
	if str, ok := strs[dir]; ok {
		return str
	}
	return fmt.Sprintf("direction %d", dir)
}

type mazeRoom struct {
	index int
	exits [10]int
}

type mazeEdge struct {
	from, to int
	dir      direction
}

// Edges returns the exits from the room.
func (m mazeRoom) Edges() []mazeEdge {
	var r []mazeEdge
	for i, exit := range m.exits {
		if exit != 0 {
			r = append(r, mazeEdge{
				from: m.index,
				to:   exit,
				dir:  direction(i),
			})
		}
	}
	return r
}

// Nodes returns the rooms connected by an edge.
//go:noinline
func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) {
	m1, ok := zork[e.from]
	if !ok {
		panic("bad edge")
	}
	m2, ok := zork[e.to]
	if !ok {
		panic("bad edge")
	}
	return m1, m2
}

// The first maze in Zork. Room indexes based on original Fortran data file.
// You are in a maze of twisty little passages, all alike.
var zork = map[int]mazeRoom{
	11: {exits: [10]int{north: 11, south: 12, east: 14}}, // west to Troll Room
	12: {exits: [10]int{south: 11, north: 14, east: 13}},
	13: {exits: [10]int{west: 12, north: 14, up: 16}},
	14: {exits: [10]int{west: 13, north: 11, east: 15}},
	15: {exits: [10]int{south: 14}},                   // Dead End
	16: {exits: [10]int{east: 17, north: 13, sw: 18}}, // skeleton, etc.
	17: {exits: [10]int{west: 16}},                    // Dead End
	18: {exits: [10]int{down: 16, east: 19, west: 18, up: 22}},
	19: {exits: [10]int{up: 29, west: 18, ne: 15, east: 20, south: 30}},
	20: {exits: [10]int{ne: 19, west: 20, se: 21}},
	21: {exits: [10]int{north: 20}}, // Dead End
	22: {exits: [10]int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}},
	23: {exits: [10]int{east: 22, west: 28, up: 24}},
	24: {exits: [10]int{ne: 25, down: 23, nw: 28, sw: 26}},
	25: {exits: [10]int{sw: 24}}, // Grating room (up to Clearing)
	26: {exits: [10]int{west: 16, sw: 24, east: 28, up: 22, north: 27}},
	27: {exits: [10]int{south: 26}}, // Dead End
	28: {exits: [10]int{east: 22, down: 26, south: 23, west: 24}},
	29: {exits: [10]int{west: 30, nw: 29, ne: 19, south: 19}},
	30: {exits: [10]int{west: 29, south: 19}}, // ne to Cyclops Room
}

func TestShortestPath() {
	// The Zork maze is not a proper undirected simple graph,
	// as there are some one way paths (e.g., 19 -> 15),
	// but for this test that doesn't matter.

	// Set the index field in the map. Simpler than doing it in the
	// composite literal.
	for k := range zork {
		r := zork[k]
		r.index = k
		zork[k] = r
	}

	var nodes []mazeRoom
	for idx, room := range zork {
		mridx := room
		mridx.index = idx
		nodes = append(nodes, mridx)
	}
	g := _New[mazeRoom, mazeEdge](nodes)
	path, err := g.ShortestPath(zork[11], zork[30])
	if err != nil {
		panic(fmt.Sprintf("%v", err))
	}
	var steps []direction
	for _, edge := range path {
		steps = append(steps, edge.dir)
	}
	want := []direction{east, west, up, sw, east, south}
	if !_SliceEqual(steps, want) {
		panic(fmt.Sprintf("ShortestPath returned %v, want %v", steps, want))
	}
}

func main() {
	TestShortestPath()
}

相关信息

go 源码目录

相关文章

go absdiff 源码

go absdiff2 源码

go absdiff3 源码

go absdiffimp 源码

go absdiffimp2 源码

go adder 源码

go aliasimp 源码

go append 源码

go boundmethod 源码

go builtins 源码