graph.go

     1  // run
     2  
     3  // Copyright 2021 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package main
     8  
     9  import (
    10  	"errors"
    11  	"fmt"
    12  )
    13  
    14  // _SliceEqual 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 [10]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  //
   157  //go:noinline
   158  func (e mazeEdge) Nodes() (mazeRoom, mazeRoom) {
   159  	m1, ok := zork[e.from]
   160  	if !ok {
   161  		panic("bad edge")
   162  	}
   163  	m2, ok := zork[e.to]
   164  	if !ok {
   165  		panic("bad edge")
   166  	}
   167  	return m1, m2
   168  }
   169  
   170  // The first maze in Zork. Room indexes based on original Fortran data file.
   171  // You are in a maze of twisty little passages, all alike.
   172  var zork = map[int]mazeRoom{
   173  	11: {exits: [10]int{north: 11, south: 12, east: 14}}, // west to Troll Room
   174  	12: {exits: [10]int{south: 11, north: 14, east: 13}},
   175  	13: {exits: [10]int{west: 12, north: 14, up: 16}},
   176  	14: {exits: [10]int{west: 13, north: 11, east: 15}},
   177  	15: {exits: [10]int{south: 14}},                   // Dead End
   178  	16: {exits: [10]int{east: 17, north: 13, sw: 18}}, // skeleton, etc.
   179  	17: {exits: [10]int{west: 16}},                    // Dead End
   180  	18: {exits: [10]int{down: 16, east: 19, west: 18, up: 22}},
   181  	19: {exits: [10]int{up: 29, west: 18, ne: 15, east: 20, south: 30}},
   182  	20: {exits: [10]int{ne: 19, west: 20, se: 21}},
   183  	21: {exits: [10]int{north: 20}}, // Dead End
   184  	22: {exits: [10]int{north: 18, east: 24, down: 23, south: 28, west: 26, nw: 22}},
   185  	23: {exits: [10]int{east: 22, west: 28, up: 24}},
   186  	24: {exits: [10]int{ne: 25, down: 23, nw: 28, sw: 26}},
   187  	25: {exits: [10]int{sw: 24}}, // Grating room (up to Clearing)
   188  	26: {exits: [10]int{west: 16, sw: 24, east: 28, up: 22, north: 27}},
   189  	27: {exits: [10]int{south: 26}}, // Dead End
   190  	28: {exits: [10]int{east: 22, down: 26, south: 23, west: 24}},
   191  	29: {exits: [10]int{west: 30, nw: 29, ne: 19, south: 19}},
   192  	30: {exits: [10]int{west: 29, south: 19}}, // ne to Cyclops Room
   193  }
   194  
   195  func TestShortestPath() {
   196  	// The Zork maze is not a proper undirected simple graph,
   197  	// as there are some one way paths (e.g., 19 -> 15),
   198  	// but for this test that doesn't matter.
   199  
   200  	// Set the index field in the map. Simpler than doing it in the
   201  	// composite literal.
   202  	for k := range zork {
   203  		r := zork[k]
   204  		r.index = k
   205  		zork[k] = r
   206  	}
   207  
   208  	var nodes []mazeRoom
   209  	for idx, room := range zork {
   210  		mridx := room
   211  		mridx.index = idx
   212  		nodes = append(nodes, mridx)
   213  	}
   214  	g := _New[mazeRoom, mazeEdge](nodes)
   215  	path, err := g.ShortestPath(zork[11], zork[30])
   216  	if err != nil {
   217  		panic(fmt.Sprintf("%v", err))
   218  	}
   219  	var steps []direction
   220  	for _, edge := range path {
   221  		steps = append(steps, edge.dir)
   222  	}
   223  	want := []direction{east, west, up, sw, east, south}
   224  	if !_SliceEqual(steps, want) {
   225  		panic(fmt.Sprintf("ShortestPath returned %v, want %v", steps, want))
   226  	}
   227  }
   228  
   229  func main() {
   230  	TestShortestPath()
   231  }
   232
View as plain text