Optimizing Loops

The original code that I wrote to extract loops from the circuit node mesh does not necessarily obtain the smallest loops known as Windows. It traverses the mesh according to which nodes were placed first. So it tends to get a big overall loop followed by inner loops.

But, for circuit analysis, we want to have a set of the smallest loops. This is more efficient, and the standard way to do it. It’s easy to see these loops but harder to extract them in code.

I couldn’t think of a way to modify my original code, so the idea is to take the loops that it extracted and then process these. So after much head scratching and doodling, I came up with an algorithm to extract independent mesh windows:

  • Compare 2 loops
  • Find a common sequence of 3 or more nodes (cs)
  • Designate the loops A and B where B is the shortest loop
  • Replace inner nodes of cs in A with reversed B nodes minus cs nodes

And here is the code for it:

func minimize_loops(loops_):
	var idxa = 0
	while idxa < loops_.size() - 1:
		var idxb = idxa + 1
		# Look for subsequence of B in A
		var a1 = -1
		var b1 = -1
		for bi in loops_[idxb].size():
			var i = loops_[idxa].find(loops_[idxb][bi])
			if i > -1:
				a1 = i
				b1 = bi
				break
		if b1 > -1:
			var ai = a1
			var bi = b1
			var a2
			var b2
			var run_length = 1
			# Scan in clockwise direction
			while true:
				ai += 1
				# Wrap ai
				if ai == loops_[idxa].size():
					ai = 0
				bi += 1
				# Wrap bi
				if bi == loops_[idxb].size():
					bi = 0
				if loops_[idxa][ai] != loops_[idxb][bi]:
					break
				a2 = ai
				b2 = bi
				run_length += 1
			if run_length > 2:
				# Got a subsequence
				if loops_[idxa].size() > loops_[idxb].size():
					var l = shrink_loop(idxa, idxb, a1, a2, b1, b2, loops_, true)
					loops_[idxa] = loops_[idxb]
					loops_[idxb] = l
				else:
					loops_[idxb] = shrink_loop(idxb, idxa, b1, b2, a1, a2, loops_, true)
			else:
				# Scan in anticlockwise direction
				ai = a1
				bi = b1
				run_length = 1
				while true:
					ai -= 1
					# Wrap ai
					if ai < 0:
						ai = loops_[idxa].size()
					bi += 1
					# Wrap bi
					if bi == loops_[idxb].size():
						bi = 0
					if loops_[idxa][ai] != loops_[idxb][bi]:
						break
					a2 = ai
					b2 = bi
					run_length += 1
				if run_length > 2:
					# Got a subsequence
					if loops_[idxa].size() > loops_[idxb].size():
						var l = shrink_loop(idxa, idxb, a1, a2, b1, b2, loops_, false)
						loops_[idxa] = loops_[idxb]
						loops_[idxb] = l
					else:
						loops_[idxb] = shrink_loop(idxb, idxa, b1, b2, a1, a2, loops_, false)
		idxa += 1


func shrink_loop(idxa, idxb, a1, a2, b1, b2, loops_, reverse):
	var b_nodes = []
	if b1 > 0:
		b_nodes.append_array(loops_[idxb].slice(0, b1 - 1))
	if b2 < loops_[idxb].size() - 1:
		b_nodes.append_array(loops_[idxb].slice(b2 + 1, -1))
	if reverse:
		b_nodes.invert()
	var loopa
	if a2 > a1:
		if a1 > 0:
			loopa = loops_[idxa].slice(0, a1 - 1)
		loopa.append_array(b_nodes)
		if a2 < loops_[idxa].size() - 1:
			loopa = loops_[idxa].slice(a2 + 1, -1)
	else:
		if a2 > 0:
			loopa = loops_[idxa].slice(0, a2 - 1)
		loopa.append_array(b_nodes)
		if a1 < loops_[idxa].size() - 1:
			loopa.append_array(loops_[idxa].slice(a1 + 1, -1))
	return loopa

In the above code, the array indices may loop around. Also, the smaller loop is put into the place of array A and the larger loop is put into the place of array B, so it is used as array A on the next iteration of testing for an inner loop.

This code in a scripting language may seem like it may be slow, but it only runs once to compile the data that we need for simulation of our circuit.

More Devlog entries

Most recent first