mst

iscyclic.go

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
		if !visited[n[1].name] {
			visited[n[1].name] = true // set to visited
			// get edges
			edges := g.Edges[n[1].name]
			for _, edge := range edges {
				// if this is not the from node
				if edge.node.name != n[0].name {
					// if it's visited the graph is cyclical
					if visited[edge.node.name] {
						return true
					}
					stack.Push([2]*Node{n[1], edge.node})
				}
			}
		}
	}
	return
}