PDF Publication Title:
Text from PDF Page: 148
128 6 ⋅ software With the visitor set up, all that remains is to call the function: dijkstra_sp(A,1,struct(’visitor’, vis)); discover_vertex called on s examine_vertex called on s examine_edge called on (s,u) edge_relaxed called on (s,u) discover_vertex called on u ... stopping an algorithm early returns a zero value, the algorithm halts. This behavior may be desirable. Consider the following example with astar_search: load graphs/bgl_cities.mat goal = 11; % Binghamton start = 9; % Buffalo % Use the Euclidean distance to the goal as the heuristic h = @(u) norm(xy(u,:) - xy(goal,:)); % Setup a routine to stop when we find the goal ev = @(u) (u ≠ goal); [d pred f] = astar_search(A, start, h, ... struct(’visitor’, struct(’examine_vertex’, ev))); The examine_vertex function returns 0 when the vertex is a targeted vertex. In this example, we want to find the shortest path between Binghamton and Buffalo. Once we find a shortest path to Buffalo, we can halt the algorithm! 6.3.6 Handling zero edge weights Matlab sparse matrices only store non-zero values. Because the structure of the Matlab sparse matrix is used to infer the edges of an underlying graph, MatlabBGL cannot distinguish between a 0-weight edge and an absent edge. To fix this problem, codes that accept a weighted graph allow the user to specify a vector of edge weights in an optional parameter. The easiest way to use this optional parameter is using a helper function called edge_weight¬ _vector. Given a weighted matrix pair (A, S), this function provides the appropriate optional argument when the graph has zero edge weights. Internally, this function computes the index of all the non-zero elements of A when using all of the structural non-zeros of S. An example helps to clarify what happens. We wish to create an undirected cycle where the weight of every edge is 0, except for a single edge with weight 1. n=8; E = [1:n 2:n 1; 2:n 1 1:n]’; w = [1 zeros(1,n-1) 1 zeros(1,n-1)]’; A = sparse(E(:,1), E(:,2), w, n, n); As = sparse(E(:,1), E(:,2), true, n, n); % create a structural sparse matrix ws = edge_weight_vector(As,A)’ The output reveals the single non-zero edge: ws = Columns 1 through 11 10100000000 Columns 12 through 16 00000 Atanypoint,ifavisitorfunction % 8 vertices, % edge list for a cycle % weight of each edge % create a weighted sparse matrixPDF 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)