chapter06

Documentation

Overview

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Package chapter06 contains implementations of the algorithms introduced in Chapter 6.

Index

• func BellmanFord(G *DiGraph, sourceVertex int) ([]int, []int)
• func Dijkstra(G *DiGraph, sourceVertex int) ([]int, []int)
• func FindNegativeWeightCycle(G *DiGraph, shortest []int, pred []int) *list.List
• func FloydWarshall(G *DiGraph) (map[int][][]int, map[int][][]int)
• func HeapSort(A []int, n int) []int
• func Relax(G *DiGraph, shortest []int, pred []int, u int, v int)
• type DiGraph
• type Element
• type PriorityQueue
  • func NewBinaryHeapPriorityQueue() PriorityQueue
  • func NewBinaryHeapPriorityQueueWithCustomComparator(comparator utils.Comparator) PriorityQueue

Functions

func BellmanFord

func BellmanFord(G *DiGraph, sourceVertex int) ([]int, []int)

BellmanFord is an implementation of the Bellman-Ford algorithm.

func Dijkstra

func Dijkstra(G *DiGraph, sourceVertex int) ([]int, []int)

Dijkstra is an implementation of Dijkstra's algorithm.

func FindNegativeWeightCycle

func FindNegativeWeightCycle(G *DiGraph, shortest []int, pred []int) *list.List

FindNegativeWeightCycle is an algorithm designed to detect negative weight cycles in any directed graphs.

func FloydWarshall

func FloydWarshall(G *DiGraph) (map[int][][]int, map[int][][]int)

FloydWarshall is an implementation of The Floyd-Warshall algorithm.

func HeapSort

func HeapSort(A []int, n int) []int

HeapSort is an implementation of heap sort algorithm. We sort elements in A by putting them all in an empty queue Q and extract them back into a new array B.

func Relax

func Relax(G *DiGraph, shortest []int, pred []int, u int, v int)

Relax is a procedure used to determine whether a node u, which would be a node previous to v in topological order, should be part of the shortest path to v. We determine whether the edge (u, v) should be the last edge of the shortest path to v.

Types

type DiGraph

type DiGraph struct {
	Length   int
	Vertices []*Element
	Edges    map[*Element][]*Element
	Weights  map[*Element]map[*Element]int
}

DiGraph defines a structure to store directed graphs.

type Element

type Element struct {
	Key   interface{}
	Value interface{}
	// Index tracks the position of the element inside the underlying array
	Index int
}

Element is a structure containing keys and data values inside each element of PriorityQueue and DiGraph.

type PriorityQueue

type PriorityQueue interface {
	// Insert one element to the queue, given element.Key
	Insert(element *Element)
	// Remove the first element off the queue, which would have the lowest element.Key value
	ExtractMin() *Element
	// Change the position (priority) in the queue if there's a change in
	// element.Key
	DecreaseKey(element *Element)
	// Get the current number of element remaining in the queue
	GetLength() int
}

PriorityQueue is a priority queue data implemented with a binary heap.

func NewBinaryHeapPriorityQueue

func NewBinaryHeapPriorityQueue() PriorityQueue

NewBinaryHeapPriorityQueue returns a new instance of PriorityQueue, which is actually an interface and implemented with binaryHeapPriorityQueue struct. The reason why we are not directly exporting binaryHeapPriorityQueue is because we want to enforce Length: 0 when creating an instance of PriorityQueue. Note that the resulting binaryHeapPriorityQueue will use utils.IntComparator for key comparison. This is primarily due to the fact that we only used integers as keys until KeyComparator was introduced.

func NewBinaryHeapPriorityQueueWithCustomComparator

func NewBinaryHeapPriorityQueueWithCustomComparator(comparator utils.Comparator) PriorityQueue

NewBinaryHeapPriorityQueueWithCustomComparator returns a new instance of PriorityQueue, just like NewBinaryHeapPriorityQueue, but with the additional parameter comparator. We can specify the comparator function to be used for comparing keys. We introduced KeyComparator so that we can have data types other than integers to be used as keys of binary heap.