1

So I am working on doing a depth-first search on a graph of an unknown length. The graph itself will be coded as a "2D" array adjacency table.

Ex:

 Graph: .word 0, 1, 1, 1, 0
        .word 1, 0, 1, 1, 1
        .word 1, 1, 0, 1, 1
        .word 1, 1, 1, 0, 1
        .word 1, 1, 0, 0, 0

But, this graph can be any size, when it gets graded the TAs can put a graph of any size in my code to test. So I do not know the size of the graph.

This becomes a problem when I want to check the adjacency table. How do I know when I have reached the end of a row? How do I advance to a particular row? I know how to advance by word, but I do not know how I could advance to the next row without knowing how many elements (and therefore bytes) I need to advance through.

Alex Shesterov
  • 26,085
  • 12
  • 82
  • 103
Doronz
  • 704
  • 8
  • 21
  • 1
    Hint: the adjacency matrix has to be a square. – Carl Norum Mar 15 '13 at 02:49
  • Yeah, I realize that. But the problem is, there's no way for me to know the end of the array. So even knowing that it has to be a square, I have no way of knowing how many elements it has since there's no \0 or otherwise indicator of the end of the array. I'm interested if this is possible to find out, but I ended up just asking the user to enter the graph size. This still allows me to follow the spec, and does not require that I develop an algorithm to figure out the length. – Doronz Mar 15 '13 at 03:20
  • There must be some symbol after the adjacency matrix, right? – Carl Norum Mar 15 '13 at 03:21
  • Not necessarily. But I was considering adding one in manually myself. – Doronz Mar 15 '13 at 04:40
  • Add a label Size after Graph, with `Size: .word Size - Graph` (in gnu syntax) http://stackoverflow.com/questions/8987767/current-address-symbol-in-gnu-assembly – Aki Suihkonen Mar 15 '13 at 05:09

1 Answers1

1

If you want to compute the row size without user intervention, you need a marker after the graph definition (in my example, I used EndGraph label as a marker). Knowing the address of the first element of the matrix and where the matrix ends allows you to compute the row size, you just have to compute the squared root of the total number of elements of the matrix:

.data
 Graph: .word 0, 1, 1, 1, 0
        .word 1, 0, 1, 1, 1
        .word 1, 1, 0, 1, 1
        .word 1, 1, 1, 0, 1
        .word 1, 1, 0, 0, 0
EndGraph:
.text        
  la $t1, Graph
  la $t2, EndGraph
  sub $t2, $t2, $t1  # Get size of matrix
  srl $t2, $t2, 2    # Get the total number of items of the matrix
  move $t3, $zero
computeRowSize:
  mult $t3, $t3
  mflo $t4
  beq $t2, $t4, done
  addiu $t3, $t3, 1
  j computeRowSize
done:  
  sll $t3, $t3, 2    # compute the size of each row (number of row elements * size(element)
  # Here you have the RowSize in $t3
gusbro
  • 22,357
  • 35
  • 46