sausheong

type Stack struct {
	nodes [][2]*Node
}

func (s *Stack) Push(n [2]*Node) {
	s.nodes = append(s.nodes, n)
}

func (s *Stack) Pop() (n [2]*Node) {
	n = s.nodes[len(s.nodes)-1]

sausheong

func (g *Graph) isCyclic(name string) (yes bool) {
	stack := &Stack{}
	visited := make(map[string]bool)
	startNode := g.GetNode(name)
	// use a 2 node array with first node as the from node and the second as the to node
	stack.Push([2]*Node{startNode, startNode})

	for len(stack.nodes) > 0 {
		n := stack.Pop()
		// if it's not visited before

sausheong

func (g *Graph) RemoveEdge(n1, n2 string) {
	rmEdge(g, n1, n2)
	rmEdge(g, n2, n1)
}

func rmEdge(g *Graph, m, n string) {
	edges := g.Edges[m]
	r := -1
	for i, edge := range edges {
		if edge.node.name == n {

sausheong

func (g *Graph) HasEdge(name string, edge *Edge) bool {
	for _, e := range g.Edges[name] {
		if e.node.name == edge.node.name && e.weight == edge.weight {
			return true
		}
	}
	return false
}

sausheong

type Heap []NodePair

func (h Heap) Len() int           { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i].edge.weight < h[j].edge.weight }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x any)        { *h = append(*h, x.(NodePair)) }

func (h *Heap) Pop() any {
	old := *h
	n := len(old)

sausheong

// Kruskal's algorithm for Minimum Spanning Tree
func kruskal(graph *Graph) (mst *Graph) {
	mst = NewGraph()
	h := &Heap{}
	heap.Init(h)
	// get a sorted list of edges
	for nodeName, edges := range graph.Edges {
		node := graph.GetNode(nodeName)
		for _, edge := range edges {
			heap.Push(h, NodePair{node, edge})

sausheong

// check if a node is in a subgraph
func in(node *Node, subgraph *Subgraph) bool {
	for _, n := range subgraph.nodes {
		if n.name == node.name {
			return true
		}
	}
	return false
}

sausheong

// combine 2 different subgraphs by connecting 2 nodes
func combine(n1, n2 *Node, subgraphs []*Subgraph) []*Subgraph {
	var s1, s2 *Subgraph
	var i2 int
	for i, subgraph := range subgraphs {
		// find the 2 subgraphs which has the 2 nodes
		for _, node := range subgraph.nodes {
			if n1.name == node.name {
				s1 = subgraph
			}

sausheong

type NodePair struct {
	node *Node
	edge *Edge
}

sausheong

// Boruvka's algorithm for Minimum Spanning Tree
func boruvka(graph *Graph) (mst *Graph) {
	mst = NewGraph()
	// set up the MST
	for _, node := range graph.Nodes {
		mst.AddNode(node)
	}

	var subgraphs []*Subgraph
	// set up the subgraphs; intially each subgraph has only 1 node