paths

Documentation

Overview

Package paths has algorithms that compute certain paths of a graph.

Index

• func AStarU[W constraints.Ordered](g groph.RUndirected[W], from, to groph.VIdx, h func(u, v groph.VIdx) W) (p []groph.VIdx, l W)
• func DijkstraD[W constraints.Ordered, G groph.RDirected[W]](g G, v groph.VIdx) *graphs.InForest[W]
• func DijkstraU[W constraints.Ordered, G groph.RUndirected[W]](g G, v groph.VIdx) *graphs.InForest[W]
• func FloydWarshallD[W constraints.Ordered, G groph.WDirected[W]](g G)
• func FloydWarshallU[W constraints.Ordered, G groph.WUndirected[W]](g G)
• func GreedyTSP[W constraints.Ordered](g groph.RGraph[W]) (path []groph.VIdx, plen W)
• func TwoOptTSP[W constraints.Float](g groph.RGraph[W]) (path []groph.VIdx, plen W)

Examples

• FloydWarshallD
• GreedyTSP

Functions

func AStarU

func AStarU[W constraints.Ordered](
	g groph.RUndirected[W],
	from, to groph.VIdx,
	h func(u, v groph.VIdx) W,
) (p []groph.VIdx, l W)

func DijkstraD

func DijkstraD[W constraints.Ordered, G groph.RDirected[W]](g G, v groph.VIdx) *graphs.InForest[W]

func DijkstraU

func DijkstraU[W constraints.Ordered, G groph.RUndirected[W]](g G, v groph.VIdx) *graphs.InForest[W]

func FloydWarshallD

func FloydWarshallD[W constraints.Ordered, G groph.WDirected[W]](g G)

Example

fwres, _ := adjmtx.AsDirected[int32](nil, 0,
	0, 8, 0, 1,
	0, 0, 1, 0,
	4, 0, 0, 0,
	0, 2, 9, 0,
)
FloydWarshallD[int32](fwres)
sz := fwres.Order()
for i := 0; i < sz; i++ {
	for j := 0; j < sz; j++ {
		e := fwres.Edge(i, j)
		if j == 0 {
			fmt.Printf("%d", e)
		} else {
			fmt.Printf(" %d", e)
		}
	}
	fmt.Println()
}

Output:

8 3 4 1
5 8 1 6
4 7 8 5
7 2 3 8

func FloydWarshallU

func FloydWarshallU[W constraints.Ordered, G groph.WUndirected[W]](g G)

func GreedyTSP

func GreedyTSP[W constraints.Ordered](g groph.RGraph[W]) (path []groph.VIdx, plen W)

Example

am := adjmtx.NewUndirected(tspExample1.Order(), tspExample1.NotEdge(), nil)
groph.Copy[float64](am, tspExample1)
testShowMatrix(am)
w, l := GreedyTSP[float64](am)
fmt.Printf("%v %.2f", w, l)

Output:

Matrix:
 0:  0.00, 14.14,  9.22,  6.40,  8.54
 1: 14.14,  0.00,  8.06,  7.81,  7.28
 2:  9.22,  8.06,  0.00,  4.47,  8.49
 3:  6.40,  7.81,  4.47,  0.00,  4.47
 4:  8.54,  7.28,  8.49,  4.47,  0.00
[0 3 2 1 4] 34.76

func TwoOptTSP

func TwoOptTSP[W constraints.Float](g groph.RGraph[W]) (path []groph.VIdx, plen W)