PDF Publication Title:
Text from PDF Page: 155
dmperm function solves a bipartite matching problem instead of a simple linear pass over the graph edges using a standard connected component algorithm. Nonetheless, the issue with these computations is the algorithm implemen- tation and not the data structure. Thus, much as others in the literature, we represent graphs as sparse matrices in Matlab. Let’s review the sparse matrix data structure in Matlab. 6.2.1 Sparse matrices in Matlab To store an m×n sparse matrix M, Matlab uses compressed column format [Gilbert et al., 1992]. Matlab never stores a 0 value in a sparse matrix. It always “re-compresses” the data structure in these cases. If M is the adjacency matrix of a graph, then storing the matrix by columns corresponds to storing the graph as an in-edge list. We briefly illustrate compressed row and column storage schemes in fig- ure 6.1. 16 110497 13 ⎡⎢0 16 13 0 20 4 00⎤⎥ 2 12 4 Compressed sparse row rp 135791111 ci 2334253646∅ ai 161310124149207 4 Compressed sparse column 1 1 3 6 8 9 11 Figure 6.1 – Compressed row and columnstorage. Atfarleft,wehave a weighted, directed graph. Its weighted adjacency matrix lies below. At right are the compressed row and compressed column arrays for this graph and matrix. For sparse matrices, compressed row and column storage make it easy to access entries in rows and columns, respectively. Consider the 3rd entry in rp. It says to look at the 5th element in ci to find all the columns in the 3rd row of the matrix. The 5th and 6th elements of ci and ai tell us that row 3 has non-zeros in columns 2 and 5, with values 4 and 14. When the sparse matrix corresponds to the adjacency matrix of a graph, this corresponds to efficient access to the out-edges and in-edges of a vertex. 5 See section 6.3.1 for a discussion about the requirements for various graph algorithms. 3 14 5 00⎥ cp ⎢⎥ ⎢0 0 10 12 ⎢0400140⎥ 6.2 ⋅ graphs in matlab 133 6 ⎢0 0 9 0 0 20⎥ ⎢0 0 0 7 0 4⎥ ri ⎢⎣000000⎥⎦ Most graph algorithms are designed to work with out-edge lists instead of in-edge lists.5 Before running an algorithm, MatlabBGL explicitly transposes the graph so that Matlab’s internal representation corresponds to storing out- edge lists. For algorithms on symmetric graphs, these transposes are not required. The mex commands mxGetPr, mxGetJc, and mxGetIr retrieve pointers to Matlab’s internal storage of the matrix without making a copy. These functions make it possible to access a sparse matrix efficiently without making a copy and are a requirement of our implementation. 1 3 1 2 4 2 5 3 4 5 ∅ ai 1641310912714204PDF Image | Instagram Cheat Sheet
PDF Search Title:
Instagram Cheat SheetOriginal File Name Searched:
pagerank-sensitivity-thesis-online.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)