PDF Publication Title:
Text from PDF Page: 150
130 6 ⋅ software 6.4 gaimc The gaimc library implements a similar set of graph algorithms. It is written entirely in Matlab and the project is maintained at GitHub, http: //github.com/dgleich/gaimc. It follows the motivation of MatlabBGL closely and also uses the Matlab sparse matrix as its graph type. In the following example, we generate a random weighted graph and compute a minimum spanning tree: randn(’state’,0); rand(’state’,0); A=abs(sprandsym(10,0.2)); % symmetric random graph T = mst_prim(A); sum(sum(T))/2 % output the MST weight If we run this code with gaimc, it produces the output: ans = 3.9531 In comparison with MatlabBGL, the gaimc library is simple. Each algo- rithm is a single Matlab m-file that contains a single function. This conveys some advantages. MatlabBGL, while portable to 32-bit and 64-bit Matlab on Windows, Mac OSX, and Linux, is difficult to compile and maintain on all platforms. The gaimc library is trivial to port between all of these platforms. However, folklore about Matlab performance claims that “loops” are slow. After The Mathworks introduced the just-in-time compiler in Matlab 7 (R14), loops are no longer slow—although our experience is that extracting good performance can be difficult for complicated functions. In gaimc, we did our best to extract performance for each graph algorithm enumerated in table 6.1. Each algorithm is serial and operates on a set of compressed sparse row arrays. Using this approach, we obtained performance that is 2-4 times slower than MatlabBGL (see section 6.4.3).13 Table 6.1 – Algorithms in gaimc. For each function in gaimc, we list the common algorithm name and the source for the implementation. 13 In Matlab R2008b, it seems that the just-in-time compiler yields worse performance than in Matlab R2007b. Instead of a slowdown of 2-4 times, we found a slowdown of 3-8 times with respect to MatlabBGL! Function bipartite_matching.m clustercoeffs.m corenums.m dijkstra.m dirclustercoeffs.m floydwarshall.m mst_prim.m scomponents.m Algorithm max-weight bipartite matching clustering coefficients core numbers Dijkstra’s single source shortest path directed clustering coefficients Floyd-Warshall’s all-pairs shortest paths Prim’s minimum spanning tree Strongly-connected components Source Papadimitriou and Steiglitz [1998] Watts and Strogatz [1998] Batagelj and Zaversnik [2003] Cormen et al. [2001] Fagiolo [2007] Cormen et al. [2001] Cormen et al. [2001] Tarjan [1972] Let us begin describing the library by analyzing a necessary tool for many graph algorithms: a heap.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 (Standard Web Page)