PDF Publication Title:
Text from PDF Page: 140
120 6 ⋅ software 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. 2 12 4 Compressed sparse row rp 135791111 ci 2334253646∅ ai 161310124149207 4 Compressed sparse column cp ri ∅ 1312425345 ai 16 4 13 10 9 12 7 14 20 4 Figure 6.1 – Compressed row and column storage. Atfarleft,wehaveaweighted, directed graph. Its weighted adjacency matrix lies below. At right are the com- pressed 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. 16 1 10497 6 13 20 4 3 14 5 16 13 0 0 0⎤⎥ ⎡⎢0 ⎢0 0 10 12 0 0⎥ 1 1 3 6 8 9 11 ⎢0 4 0 0140⎥ ⎢0 0 9 ⎢ ⎥ ⎢0 0 0 ⎢⎣0 0 0 0 0 20⎥ 7 04⎥ 0 00⎥⎦ 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. Let us recap. Sparse matrices are the best way to store graphs in Matlab. They provide all the necessary pieces to integrate cleanly with “natural” Matlab syntax and allow us access to their internals to run algorithms efficiently. 6.2.2 Other packages There are other graph packages for Matlab too. One of the first was the meshpart toolkit [Gilbert and Teng, 2002], which focuses on partitioning meshes. A more recent example is Matgraph [Scheinerman, 2009], which con- tains a rich set of graph constructors to create adjacency matrices for standard graphs. It also provides an interface to support graph properties, such as la- bels and weights. Various authors released individual graph theory functions on the Mathworks File Exchange [Various, 2009a, search for dijkstra]. For example, the Exchange contains more than three separate implementations of Dijkstra’s shortest path algorithm.PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.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 | RSS | AMP |