Transcript Applets
Sparse Matrices How to Implement Copyright © 2014 Curt Hill Recall a Matrix Copyright © 2014 Curt Hill Types • Many different types of matrices have been identified that crop up in various problems • Today we wish to look at the sparse matrix – This has most entries to be zero • If the matrix is large then maybe we do not want to store it in traditional two dimensional array form Copyright © 2014 Curt Hill Storage • Consider a square matrix that has size 100 • It requires 100 100 = 10,000 units – Where the unit is whatever we store in each cell – For doubles this would be 80,000 bytes • Strangely, that is not impractical in most current computers • What happens if the 100 gets large? Copyright © 2014 Curt Hill Larger • VCSU MEP has about 20,000 objects numbered from zero – Only about 4000 rooms • The adjacency matrix would then be a square 20,000 on a side • 20,0002 = 40,0000,000 • This is not the largest matrix that could be considered • How do we store these things? Copyright © 2014 Curt Hill Data Structures • Lots of possibilites • Lists • Single • List of lists • Vectors • Trees • Combinations Copyright © 2014 Curt Hill Lists • One possibility is a single list • Each item on this list has: – Source number – Destination number – Any other information • The numbers would be the subscripts of the matrix • Usually the list is sorted by source number • Ask for a picture Copyright © 2014 Curt Hill List of Lists • Similar to the last except the entry identifies the row number • It then is the root of lists that all contain an item • Each list is one row (or column) • Again ask for a picture Copyright © 2014 Curt Hill Vectors • A vector of vectors probably is not the best solution – Most of the storage is unused • A similar trick to the list may be used • The entry in a vector identifies the real subscript or pair of subscripts Copyright © 2014 Curt Hill Trees • Similarly look up the first subscript in a tree • Each node then roots another tree which will produce the second subscript Copyright © 2014 Curt Hill Combinations • Clearly a number of combinations are possible • A vector containing lists or trees • A tree containing lists • Hash tables are not impossible either Copyright © 2014 Curt Hill Dimitri • Creates an adjacency matrix of MOO rooms • The overall structure is a STL List of things • Each thing should indicate the source room – It should also root a list of destination rooms Copyright © 2014 Curt Hill