# Source file test/typeparam/graph.go

```     1  // run
2
4  // Use of this source code is governed by a BSD-style
6
7  package main
8
9  import (
10  	"errors"
11  	"fmt"
12  )
13
14  // _Equal reports whether two slices are equal: the same length and all
15  // elements equal. All floating point NaNs are considered equal.
16  func _SliceEqual[Elem comparable](s1, s2 []Elem) bool {
17  	if len(s1) != len(s2) {
18  		return false
19  	}
20  	for i, v1 := range s1 {
21  		v2 := s2[i]
22  		if v1 != v2 {
23  			isNaN := func(f Elem) bool { return f != f }
24  			if !isNaN(v1) || !isNaN(v2) {
25  				return false
26  			}
27  		}
28  	}
29  	return true
30  }
31
32  // A Graph is a collection of nodes. A node may have an arbitrary number
33  // of edges. An edge connects two nodes. Both nodes and edges must be
34  // comparable. This is an undirected simple graph.
35  type _Graph[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {
36  	nodes []_Node
37  }
38
39  // _NodeC is the constraints on a node in a graph, given the _Edge type.
40  type _NodeC[_Edge any] interface {
41  	comparable
42  	Edges() []_Edge
43  }
44
45  // Edgec is the constraints on an edge in a graph, given the _Node type.
46  type _EdgeC[_Node any] interface {
47  	comparable
48  	Nodes() (a, b _Node)
49  }
50
51  // _New creates a new _Graph from a collection of Nodes.
52  func _New[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]](nodes []_Node) *_Graph[_Node, _Edge] {
53  	return &_Graph[_Node, _Edge]{nodes: nodes}
54  }
55
56  // nodePath holds the path to a node during ShortestPath.
57  // This should ideally be a type defined inside ShortestPath,
58  // but the translator tool doesn't support that.
59  type nodePath[_Node _NodeC[_Edge], _Edge _EdgeC[_Node]] struct {
60  	node _Node
61  	path []_Edge
62  }
63
64  // ShortestPath returns the shortest path between two nodes,
65  // as an ordered list of edges. If there are multiple shortest paths,
66  // which one is returned is unpredictable.
67  func (g *_Graph[_Node, _Edge]) ShortestPath(from, to _Node) ([]_Edge, error) {
68  	visited := make(map[_Node]bool)
69  	visited[from] = true
70  	workqueue := []nodePath[_Node, _Edge]{nodePath[_Node, _Edge]{from, nil}}
71  	for len(workqueue) > 0 {
72  		current := workqueue
73  		workqueue = nil
74  		for _, np := range current {
75  			edges := np.node.Edges()
76  			for _, edge := range edges {
77  				a, b := edge.Nodes()
78  				if a == np.node {
79  					a = b
80  				}
81  				if !visited[a] {
82  					ve := append([]_Edge(nil), np.path...)
83  					ve = append(ve, edge)
84  					if a == to {
85  						return ve, nil
86  					}
87  					workqueue = append(workqueue, nodePath[_Node, _Edge]{a, ve})
88  					visited[a] = true
89  				}
90  			}
91  		}
92  	}
93  	return nil, errors.New("no path")
94  }
95
96  type direction int
97
98  const (
99  	north direction = iota
100  	ne
101  	east
102  	se
103  	south
104  	sw
105  	west
106  	nw
107  	up
108  	down
109  )
110
111  func (dir direction) String() string {
112  	strs := map[direction]string{
113  		north: "north",
114  		ne:    "ne",
115  		east:  "east",
116  		se:    "se",
117  		south: "south",
118  		sw:    "sw",
119  		west:  "west",
120  		nw:    "nw",
121  		up:    "up",
122  		down:  "down",
123  	}
124  	if str, ok := strs[dir]; ok {
125  		return str
126  	}
127  	return fmt.Sprintf("direction %d", dir)
128  }
129
130  type mazeRoom struct {
131  	index int
132  	exits int
133  }
134
135  type mazeEdge struct {
136  	from, to int
137  	dir      direction
138  }
139
140  // Edges returns the exits from the room.
141  func (m mazeRoom) Edges() []mazeEdge {
142  	var r []mazeEdge
143  	for i, exit := range m.exits {
144  		if exit != 0 {
145  			r = append(r, mazeEdge{
146  				from: m.index,
147  				to:   exit,
148  				dir:  direction(i),
149  			})
150  		}
151  	}
152  	return r
153  }
154
155  // Nodes returns the rooms connected by an edge.
156  //go:noinline
157  func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) {
158  	m1, ok := zork[e.from]
159  	if !ok {
161  	}
162  	m2, ok := zork[e.to]
163  	if !ok {
165  	}
166  	return m1, m2
167  }
168
169  // The first maze in Zork. Room indexes based on original Fortran data file.
170  // You are in a maze of twisty little passages, all alike.
171  var zork = map[int]mazeRoom{
172  	11: {exits: int{north: 11, south: 12, east: 14}}, // west to Troll Room
173  	12: {exits: int{south: 11, north: 14, east: 13}},
174  	13: {exits: int{west: 12, north: 14, up: 16}},
175  	14: {exits: int{west: 13, north: 11, east: 15}},
176  	15: {exits: int{south: 14}},                   // Dead End
177  	16: {exits: int{east: 17, north: 13, sw: 18}}, // skeleton, etc.
178  	17: {exits: int{west: 16}},                    // Dead End
179  	18: {exits: int{down: 16, east: 19, west: 18, up: 22}},
180  	19: {exits: int{up: 29, west: 18, ne: 15, east: 20, south: 30}},
181  	20: {exits: int{ne: 19, west: 20, se: 21}},
182  	21: {exits: int{north: 20}}, // Dead End
183  	22: {exits: int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}},
184  	23: {exits: int{east: 22, west: 28, up: 24}},
185  	24: {exits: int{ne: 25, down: 23, nw: 28, sw: 26}},
186  	25: {exits: int{sw: 24}}, // Grating room (up to Clearing)
187  	26: {exits: int{west: 16, sw: 24, east: 28, up: 22, north: 27}},
188  	27: {exits: int{south: 26}}, // Dead End
189  	28: {exits: int{east: 22, down: 26, south: 23, west: 24}},
190  	29: {exits: int{west: 30, nw: 29, ne: 19, south: 19}},
191  	30: {exits: int{west: 29, south: 19}}, // ne to Cyclops Room
192  }
193
194  func TestShortestPath() {
195  	// The Zork maze is not a proper undirected simple graph,
196  	// as there are some one way paths (e.g., 19 -> 15),
197  	// but for this test that doesn't matter.
198
199  	// Set the index field in the map. Simpler than doing it in the
200  	// composite literal.
201  	for k := range zork {
202  		r := zork[k]
203  		r.index = k
204  		zork[k] = r
205  	}
206
207  	var nodes []mazeRoom
208  	for idx, room := range zork {
209  		mridx := room
210  		mridx.index = idx
211  		nodes = append(nodes, mridx)
212  	}
213  	g := _New[mazeRoom, mazeEdge](nodes)
214  	path, err := g.ShortestPath(zork, zork)
215  	if err != nil {
216  		panic(fmt.Sprintf("%v", err))
217  	}
218  	var steps []direction
219  	for _, edge := range path {
220  		steps = append(steps, edge.dir)
221  	}
222  	want := []direction{east, west, up, sw, east, south}
223  	if !_SliceEqual(steps, want) {
224  		panic(fmt.Sprintf("ShortestPath returned %v, want %v", steps, want))
225  	}
226  }
227
228  func main() {
229  	TestShortestPath()
230  }
231
```

View as plain text