Topological sort in MIPS assembly language. Tested in SPIM simulator.

topologicalsort.mips.s

# Copyright 2002 Manu Datta 
# All rights reserved

.data
adjMatrix:	.space 450
.align 2
count:		.space 225
#msg1:		.asciiz "Error in toplogical sort:\n"
#msg2:		.asciiz  "graph contanis a cycle\n"
msg3:		.asciiz "Vertex : "
msg4:		.asciiz " Indegree : "
msg5:		.asciiz " Visit vertex "
nl:		.asciiz "\n"

	 
	
.text
.globl main
main:
	addi	$s2,$zero,4
	#input the number of vertices
	li	$v0,5
	syscall
	#save the number of vertices in $s0
	move	$s0,$v0
	# i=0
	move	$t0,$zero
	# index into array
	move	$t2,$zero
initAdjMatrix:	
	beq	$t0,$s0,initCount
	# j=0
	move	$t1,$zero
doOneRow:
	# if j = 5 start another row
	beq	$s0,$t1,rowEnd	
	# at a[i][j] store 0
	sw	$zero,adjMatrix+0($t2)
	add	$t2,$t2,$t2
	add	$t2,$t2,$t2
	addi	$t1,1
	j	doOneRow
rowEnd:
	# i=i+1
	addi	$t0,$t0,1
	j	initAdjMatrix

	move	$t0,$zero
	move	$t1,$zero
initCount:	
	# if i = size we are done
	beq	$s0,$t0,inReadEdges
	sw	$zero,count+0($t1)
	add	$t1,$t1,$t1
	add	$t1,$t1,$t1
	addi	$t1,1
	j	initCount
inReadEdges:
	li	$v0,5
	syscall
	#save the number of edges in s1
	move	$s1,$v0
	move	$t2,$zero
	# we store the edges read in $t0 and $t1
	# adjMatrix[4*($t0*$s0+$t1)] gives the position of cell
readEdges:
	beq	$s1,$t2,countIndegree
	li	$v0,5
	syscall
	move	$t1,$v0
	mul	$t1,$t1,$s0
	li	$v0,5
	syscall
	move	$t0,$v0
	add	$t0,$t1,$t0
	mul	$t0,$t0,$s2
	addi	$t1,$zero,1
	sw	$t1,adjMatrix+0($t0)
	addi	$t2,1
	j	readEdges
countIndegree:
	#src is $t0
	#dest is $t1
	#address is computed in $t2
	addi	$t3,$zero,1
	move	$t0,$zero
	#intially $t2 points to the first word at adjMatrix hence is zero
	move	$t2,$zero
rowDone:
	beq	$s0,$t0,printIndegree
	move	$t1,$zero
	addi	$t0,1
doRowIndegree:
	beq	$s0,$t1,rowDone
	lw	$t4,adjMatrix+0($t2)
	bne	$t3,$t4,noIncr
	#get the count at destination
	mul	$t5,$t1,$s2
	lw	$t4,count+0($t5)
	#increment it by one
	addi	$t4,1
	sw	$t4,count+0($t5)
noIncr:
	#compute the next address (add 4) 
	addi	$t2,4
	addi	$t1,1
	j	doRowIndegree
printIndegree:
	move	$t0,$zero
	move	$t1,$zero
printNext:
	beq	$s0,$t0,topSort
	addi	$v0,$zero,4
	la	$a0,msg3
	syscall
	move	$a0,$t0
	addi	$v0,$zero,1
	syscall
	addi	$v0,$zero,4
	la	$a0,msg4
	syscall
	lw	$a0,count+0($t1)
	addi	$v0,$zero,1
	syscall
	addi	$v0,$zero,4
	la	$a0,nl
	syscall
	addi	$t0,1
	addi	$t1,4
	j	printNext
	# vertex = $t4
	add	$t4,$zero,$zero
	
topSort:
	beq	$s0,$t4,finish
	mul	$t3,$t4,$s1
	lw	$t5,count+0($t3)
	beq	$t5,$zero,doNextTop
	j	incrAndGo
doNextTop:
	move	$a1,$t4
	jal	topPrint
incrAndGo:
	addi	$t4,$t4,1
	j	topSort

finish:
	li	$v0,10
	syscall
	
topPrint:
	#set up standard activation record
	#24 bytes allocated in frame
	subu	$sp,$sp,32
	sw	$ra,20($sp)
	sw	$fp,16($sp)
	addiu	$fp,$sp,28
	sw	$a1,0($fp)
	#the procedure topPrint starts here
	#t0 is dest
	#a1 contians the vertex
	#save a0 in t1 at entry
	#if the inner call found a cycle abort
	#li	$t0,1
	#beq	$a0,1,retNoCycle
	#print the vertex
	la	$a0,msg5
	addi	$v0,$zero,4
	syscall
	move	$a0,$a1
	addi	$v0,$zero,1
	syscall
	la	$a0,nl
	addi	$v0,$zero,4
	syscall
	li	$t0,-1
	mul	$t2,$a1,$s1
	sw	$t0,count+0($t2)
	li	$t0,0
nextVertex:
	beq	$s0,$t0,retNoCycle
	mul	$t2,$a1,$s0
	addu	$t2,$t0,$t2
	mul	$t2,$t2,$s2
	lw	$t1,adjMatrix+0($t2)
	#we need to save dest which is being passed in $a0
	# s0 has the size
	sw	$t0,4($fp)
	beq	$t1,$zero,doneNextVertex
	sw	$t1,8($fp)
	#decrement count[dest] by one
	move	$t2,$t0
	mul	$t2,$t2,$s2
	lw	$t1,count+0($t2)
	subu	$t1,$t1,1
	#store it back
	sw	$t1,count+0($t2)
	bne	$t1,$zero,doneNextVertex
	
	move	$a1,$t0
	jal	topPrint
	lw	$t0,4($fp)
	lw	$a1,0($fp)
	li	$t1,1
	beq	$a1,$t1,retNoCycle	
doneNextVertex:
	addi	$t0,$t0,1
	j	nextVertex
retNoCycle:
	#remove the activation record
	lw	$ra,20($sp)
	lw	$fp,16($sp)
	addiu	$sp,$sp,32
	jr	$ra